Recently failed my Google tech screen (L5). It was just a single DS and Algs question. What would you rate this question? (Couldn’t find it on LC). At the time I struggled to reason if my naive solution was even correct. My interviewer gave no cues or hints, so I was afraid I was completely off. In the end I was able to come up with a solution that was near optimal. After the interview I figured it out after another hour thinking on it. In hindsight, the solution is pretty straightforward. But in a 30 min interview I couldn’t come up with it - let alone with well structured code. The question: “”” You are given an array of time slot requests for meetings. Return a map of meeting room to time slots which uses the least amount of rooms. “”” Example: Input : [ (r1, 8am, 9am), (r2, 9am, 12pm), (r3, 8:30am, 10am) ] Output: { room1: [r1, r2], room2: [r3] } ** Edit: Everyone seems confident, but no right answers so far. #engineering #software #swe
Yeah, this question would be a dream.
Variation of merging overlapping intervals
Wouldnt it work like this? Make a new array with [start, end, request id], sort all of them based on start id , if start same, sort on end times, now go through each one, and see if the current request start time is smaller than prev end time, assign to new Room, else just append to existinf room. This looks similar to merge interval question and a bit of Meeting Rooms II . Will this work?
Sort of, but not quite. I think you're on the right track, but it depends on how you implement the check & "just append to existing room". Assuming you mean just keep track of the 'currentInterval', and if theres no overlap, then assign it to the 'currentRoomSet', else start a new 'currenetRoomSet'. That wouldn't give us a correct solution. For example: the input was in a different order: [ (r1, 8am, 9am), (r3, 8:30am, 10am) , (r2, 9am, 12pm)] If I'm following your approach, then we would get: { room1: [r1], room2: [r3], room3: [r2] }
I see my approach wont work, thinking of Single Threaded Cpu question, let me dream about thisproblem :)
tech screen is before onsite right? funny they usually skip that for me go straight to onsite
I think you need a deque and a pq here
Why is r1 and r2 together. R1 ends at 9am r2 starts at 9am technically that isn’t a meeting conflict.
There's no conflict which is why they can be in the same room
I realized that after I submitted.. durr. Makes sense
1. Sort meetings input by start time 2. Create a min-heap where a node is a tuple (end_time, room_id), so the top of the heap will always have the earliest meeting end time. 3. Iterate thru the sorted meetings: 3.a. If a meeting can fit in the meeting room at top of the heap, pop from heap and add it back with updated end time 3.b. Else, create a new meeting room and push onto the heap def Solution(meetings): meetings.sort(key=lambda x:x[1]) res = defaultdict(list) rooms = [] room_id = 0 for i, start, end in meetings: if rooms and rooms[0][0] <= start: room_end, existing_room_id = heapq.heappop(rooms) res[existing_room_id].append(i) heapq.heappush(rooms, (end, existing_room_id)) else: room_id += 1 res[room_id].append(i) heapq.heappush(rooms, (end, room_id)) return res
Looks almost identical to what I came up with. Even down to the variable names. Wild
Got this for one of my amazon on-site questions. Sort by start time + use min heap
This is interval scheduling. I got asked the same thing when I got hired at L3. I believe there's a greedy solution. You learn it in college. Then you forget all about greedy algorithms cause you never use them xD. I'm pretty sure I can't solve it now unless I studied again.
Greedy problems are intuitive but very hard to prove i guess
? This is like easy question
? Solution?
Without thinking about it my guess is greedy alg