Google Interview Question
Software DevelopersCountry: United States
Interview Type: In-Person
ii need a python code for this. unable to understand stmt "populate the max heap based on distance between two occupied seats. For each node in heap have distance, start seat no and end seat no."
For max heap, in this example, first seat that will be allocated to the first person entered, would be 7 or 8 for an array of 15 elements for seat umbers. lets assume 8. what value the max heap root node have?
if it is 8, then its not the max number in terms of sequence and seat value.
please help how do we assign start seat number, end seat number and distance between them as max heap node?
A few clarifying questions that i would ask:
1. What if the bench is emtpy. Can i return any seat number?
2. What if bench is full. Should i return -1.
3. How big can n be?
4. How many queries are we making?
Algo:
1. Traverse the bench once (saved as array or vector) and populate a max heap based on distance between two occupied seats. For each node in heap have distance, start seat no and end seat no.
2. When a query is made return the seat no as (end seat no - start seat no)/2 for the root node in heap.
3. Replace the root node with one node formed by (end seat no - start seat no)/2 and end seat no and call heapIfY() on heap.
4. insert the seconds node formed by start node no and (end seat no - start seat no)/2 in the heap.
Repeat process from 2 to 4 for each query.
Complexity:
Forming heap: O(n)
For each query: O(log(n))
Your logic looks correct.
The only change that is needed is the return seat numbers be calculated as either
1. (end_seat + start_seat) / 2 . or
2. start_seat + (end_seat - start_seat) / 2
your logic of (end_seat - start_seat) / 2 will lead to wrong seating index due to missing offset
Example: for finding a seat between 5 and 9 indexes should return 7 (5 + (9-5)/2 ). Your logic will return 2 instead (9-5)/2.
Also run time as per my understanding should be:
Forming heap: O(N)
Each Query (Get Max): O(1)
Insert: O(logN)
For the first two people, I want to make them sit on each end. Have Queue that tracks next possible spot where a person can sit. Initially, the queue will hold an arrangement start as 0 and end as n. When the third person comes we can ask to him to sit at the midpoint in Queues first entry and remove that entry from the Queue then enqueue two other possible next arrangements to the queue, so that place could be used in future. This process repeats.
Assuming the bench is linear.
Is this algorithm, sounding correct?
"""
a = [1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0]
empty seat = 0
taken seat = 1
find seat most far away from taken seat
"""
def longestdistance(arr):
max_cnt = float('-inf')
tmp = []
for i in range(len(arr)):
if arr[i] != 1:
left = i-1
right = i+1
current_cnt = 0
while left > 0 and right < len(arr) and arr[left] != 1 and arr[right] != 1:
left -= 1
right += 1
current_cnt += 1
if current_cnt > max_cnt:
max_cnt = current_cnt
tmp.append(i)
return tmp.pop() if tmp else False
print("position: ", longestdistance([1,0,0,0,1,0,0,0,0,1,0,0,0,0,0,0,0,1,0,0,0]))
print("position: ", longestdistance([1]))
print("position: ", longestdistance([0]))
This could be done by binary approach i guess.
The max distance btw 2 ppl possible is if one sits first & other at last i.e. 0 and n.
So if we have 'c' ppl.
We have a possibility of answer being from 0(all at the same seat) to n(one at start other at end).
low=0, high=n;
if(mid is possible)
then try possibilities > mid; //left=mid+1;
else
try possibilities <mid ; //right=mid-1;
'mid' is possible can be checked if we place c students at distances of mid from one another , such that total distance btw first and last does not exceed n.
Hope it makes sense :P .
Please let me know if doesnot pass for any case.
The logic is same as suggested by other answers.
Use Max priority Queue (implementation of Heap) to identify which seat is farthest from the occupied seats.
Logic: Every time a call to find the seat is made, it performs 2 operations
1. Get the Max element from the heap that represents the longest distance between the currently occupied seats. Return the middle seat for that longest distance.
2. Add 2 more entries in the heap that represent the seat just occupied by the caller.
Example:
If the occupied seats currently are 0 and 9.
Next call to findSeat which get [0,9] from the heap. Divide it in the middle and add 2 entries to the heap that presents [0,4][4,9].
Here is the code
time Complexity:
- Saurabh October 10, 20181. Build Heap: O(N)
2. Return next seat: O(1) --> getMax operation
3. Add entries to heap: O(logN)