## Google Interview Question

Software Developers**Country:**United States

**Interview Type:**In-Person

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)

```
"""
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]))
```

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

```
public class FarthestSeatOnBench {
private static class Seat {
int leftEdge, rightEdge;
Seat(int leftEdge, int rightEdge) {
this.leftEdge = leftEdge;
this.rightEdge = rightEdge;
}
public String toString() {
return "["+leftEdge +" " + rightEdge+"]";
}
}
public static void main(String[] args) {
int[] a = {0,0,0,0,0,0,0,0,0,0};
PriorityQueue<Seat> seatingSpace = new PriorityQueue<>(new SeatComparator());
for(int i = 0; i < 10; i ++) {
System.out.println("Next Seat Option: " + getSeat(a, seatingSpace));
}
}
private static int getSeat(int[] input, PriorityQueue<Seat> seatingSpace) {
if(input[0] == 0) {input[0] = 1; return 0;}
if(input[input.length-1] == 0) {
seatingSpace.add(new Seat(0, input.length -1));
input[input.length-1] = 1;
return input.length - 1;
}
//get the max Seat
Seat currentSeat = seatingSpace.poll();
seatingSpace.add(new Seat(currentSeat.leftEdge, (currentSeat.leftEdge + currentSeat.rightEdge) / 2));
seatingSpace.add(new Seat((currentSeat.leftEdge + currentSeat.rightEdge) / 2, currentSeat.rightEdge));
return (currentSeat.leftEdge + currentSeat.rightEdge) / 2;
}
static class SeatComparator implements Comparator<Seat> {
public int compare(Seat one, Seat two) {
return Integer.compare(two.rightEdge - two.leftEdge, one.rightEdge - one.leftEdge);
}
}
}
Output:
========
Next Seat Option: 0
Next Seat Option: 9
Next Seat Option: 4
Next Seat Option: 6
Next Seat Option: 2
Next Seat Option: 7
Next Seat Option: 3
Next Seat Option: 8
Next Seat Option: 5
Next Seat Option: 1
```

time Complexity:

1. Build Heap: O(N)

2. Return next seat: O(1) --> getMax operation

3. Add entries to heap: 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.

- AK October 07, 2018Assuming the bench is linear.

Is this algorithm, sounding correct?