Google Interview Question for Software Developers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 3 vote

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)

- Saurabh October 10, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- Smita June 18, 2021 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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))

- Alok September 22, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- Saurabh October 10, 2018 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 vote

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?

- AK October 07, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

My clarifying questions:
1. Is bench straight or circular?

- chandresh October 02, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- lee19856 October 05, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- anshuk2305 February 06, 2019 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More