Google Interview Question
SDE1sCountry: United States
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;
}
}
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[0] - 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";
}
@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) :)
@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.
#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[8]={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;
}
#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[8]={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;
}
- Scavi January 01, 2018