## Google Interview Question for SDE1s

Country: United States

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

``````public int findPlace(@Nonnull final boolean[] input) {
int pos = 0;
int maxDistance = 0;
int left = 0;
int right = 0;

for (int i = 0; i < input.length; ++i) {
if (input[i]) {
if (left == 0 && !input) {
pos = 0;
} else {
pos = right - left > maxDistance ? left + ((right - left) / 2) : pos;
}
left = right;
} else if (i == input.length - 1) {
pos = right - left > maxDistance ? i : pos;
} else {
maxDistance = Math.max(maxDistance, right - left);
}
right++;
}
return pos;
}``````

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

Questions:
- is the input given as a flag array or array with taken seat positions, is it sorted?
- has the bench a start and an end or is it a circular bench around a circular table?
- Should it be optimzed to seat a single person or multiple people?

Assumption/Definition:
- start with an array of sorted, occupied seats, assume the array is sorted
- to avoid edge cases, assume it's a circular bench around a round table
- n: number of seats

Solution:
- create a binary heap that contains the min distance from a seating between two
taken seats
- when querying for a seat, use that heaps top element, remove it, create two new \
once (left and right) and re-insert it
- O(n) space, O(lg(n)) time per query, O(m*lg(m)) to prepare, assuming, m seats are
taken initially.

Additionals:
what if seats can get unoccupied again once they were occupied?
- in this case, it's better to use a tree instead of a heap, becaue the tree has an
order and it's easy to have a vector with tree-items so, I can access either
using the seat index to merge empty spaces if a person leaves.
- Besides this, it stais the same problem.

``````#include <vector>
#include <queue>
#include <iostream>

using namespace std;

class SeatFinder
{
struct QComp {
bool operator () (const pair<int, int>& a, const pair<int, int>& b) {
return a.second < b.second;
}
};
size_t n_;
priority_queue<pair<int, int>, vector<pair<int, int>>, QComp> heap_; // start, length

public:
SeatFinder(int seatCount, const vector<int>& takenSeats) : n_(seatCount) {
size_t m = takenSeats.size();
for (size_t i = 1; i <= takenSeats.size(); ++i) {
int start = takenSeats[i - 1];
int end = takenSeats[i % m];
putSlot(start, end);
}
}

// returns next empty slot with highest distance to left and right
int getNextEmptySlot() {
if (heap_.empty()) {
putSlot(0, 0);
return 0;
}
if (heap_.top().second < 1) return -1; // returns -1, because there is no space left.
auto slot = heap_.top(); // start, length --> start + length is the next taken seat, start is the previous taken seat, length must be >= 2
heap_.pop();
int seatIdx = (slot.first + 1 + slot.second / 2) % n_; // start + floor(length / 2) takes it to the middle
putSlot(slot.first, seatIdx);
putSlot(seatIdx, (slot.first + slot.second + 1) % n_);
return seatIdx;
}

private:
// closed interval [start, end] where start is the previous taken seat and end is the next taken seat
void putSlot(int start, int end) {
int length = (n_ + (end - 1) - start) % n_;
heap_.push({ start, length });
}
};

int main()
{
SeatFinder sf(16, {1, 2, 3, 9});
for (int i = 0; i < 16; i++) {
cout << sf.getNextEmptySlot() << endl;
}
}``````

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

I assume the taken place numbers are sorted.

``````#include <iostream>
#include <vector>

using namespace std;

int Place(vector<int> const &a, int bench_start, int bench_end)
{
int place = -1;
if (a.empty()) {
place = bench_start;
} else {
int max_free_space = -1;
for (int i = 0; i + 1 < a.size(); ++i) {
int free_space = a[i + 1] - a[i] - 2;
if (free_space > max_free_space) {
max_free_space = free_space;
place = a[i] + 1 + free_space / 2;
}
}
int free_space = a - bench_start - 1;
if (free_space >= max_free_space / 2) {
max_free_space = free_space * 2;
place = bench_start;
}
free_space = bench_end - a[a.size() - 1] - 1;
if (free_space >= max_free_space / 2) {
place = bench_end;
}
}
return place;
}

int main()
{
cout << Place({1, 3, 4, 5, 9}, 1, 10) << "\n";
}``````

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

@ChrisK. There is a nuance, which makes the problem a bit more complicated. E.g. the following situation:
0 1 2 3 4 5 6
2 and 6 are occupied.
It would be correct to occupy 4, but most people would probably prefer take 0, because this way we only disturb 1 person (at 2), not two persons (at 2 and 6) :)

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

@Alex, two things:
1) I I defined it a round table, because I didn't like the special cases on the left and right end. so, 0 would be next to 6. First thing was a straight bench, came to mz mind, but a round one is more convenient with less corner cases and since that wasn't specified.
2) Any chance to PM? Maybe follow my profile link, if your interested.

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

@ChrisK.
1. Sorry, I have to read assumptions.
2. Sure. Thank you!

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

#include <iostream>
using namespace std;
int min(int a,int b)
{
return a<b?a:b;
}
void show(int a[])
{
cout<<endl;
for(int i=0;i<8;i++)
{
cout<<a[i]<<" ";
}
}

int min(int b[],int i,int j,int size)
{
if(i<0 && j>=size)
return 0;
if(i<0)
return b[j];
if(j>=size)
return b[i];
return min(b[i],b[j]);

}
int maxloc(int a[],int size)
{
int m = -1;
int loc = 0;
for(int i=0;i<size;i++)
{
if(a[i]>m)
{
m= a[i];
loc = i;
}
}
return loc;
}
int findpos(int a[])
{
int b={0};
for(int j=0;j<8;j++)
{
show(b);
for(int i=0;i<8;i++)
if(a[i]==0)
{
b[i]= min(b,i-1,i+1,8)+1;
}
}
return maxloc(b,8);

}
int main()
{
int a[]= {0,1,0,1,0,1,0,0};
int pos = findpos(a);
cout<<pos;
return 0;
}

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

``````#include <iostream>
using namespace std;
int min(int a,int b)
{
return a<b?a:b;
}
void show(int a[])
{
cout<<endl;
for(int i=0;i<8;i++)
{
cout<<a[i]<<" ";
}
}

int min(int b[],int i,int j,int size)
{
if(i<0 && j>=size)
return 0;
if(i<0)
return b[j];
if(j>=size)
return b[i];
return min(b[i],b[j]);

}
int maxloc(int a[],int size)
{
int m = -1;
int loc = 0;
for(int i=0;i<size;i++)
{
if(a[i]>m)
{
m= a[i];
loc = i;
}
}
return loc;
}
int findpos(int a[])
{
int b={0};
for(int j=0;j<8;j++)
{
show(b);
for(int i=0;i<8;i++)
if(a[i]==0)
{
b[i]= min(b,i-1,i+1,8)+1;
}
}
return maxloc(b,8);

}
int main()
{
int a[]= {0,1,0,1,0,1,0,0};
int pos = findpos(a);
cout<<pos;
return 0;
}``````

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