Katkat
Back

Solve meeting and tree problems

BloombergSoftware Engineer · Technical Screen
EasySoftware EngineerTechnical ScreenCoding & Algorithms

Last updated

This problem tests your ability to manipulate overlapping intervals and perform specific tree traversals to extract structural information.

Part 1: Meeting Scheduler

Given a list of meeting intervals intervals where each interval is [start, end], determine if a person can attend all meetings.

Example: Input: [[0, 30], [5, 10], [15, 20]] Output: false (5-10 and 15-20 overlap with 0-30)

def can_attend_meetings(intervals: list[list[int]]) -> bool:
    pass

Part 2: Tree Right View

Given the root of a binary tree, return the values of the nodes you can see when standing on the right side of the tree, ordered from top to bottom.

Example: Input: root = [1, 2, 3, null, 5, null, 4] Output: [1, 3, 4]

class TreeNode:
    def __init__(self, val=0, left=None, right=None):
        self.val = val
        self.left = left
        self.right = right

def right_side_view(root: TreeNode) -> list[int]:
    pass

Constraints:

  • For intervals: 0 <= intervals.length <= 10^4.
  • For trees: The number of nodes is in range [0, 100].

Hints

Hint 1

For the meeting intervals, sorting the meetings by start time allows you to check for overlaps by comparing the end of one meeting with the start of the next.

Hint 2

For the tree right view, performing a level-order traversal (BFS) allows you to easily capture the last node processed at each depth level.

Hint 3

Alternatively, a modified DFS (Root, Right, Left) can be used to track the depth of the tree, adding a node to the result list only if it is the first node visited at that specific depth.

Follow-up questions

  • How would you modify the meeting scheduler if you needed to return the minimum number of meeting rooms required?
  • What is the time and space complexity of your right-side view solution in terms of tree height and number of nodes?
  • How would you implement the tree traversal if you were asked for the 'left view' instead of the 'right view'?