## Google Interview Question for Interns

Country: United States

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

This could be solved maintaining a max heap of lengths of segments of empty seats as keys, and the pairs of segment endpoint indexes as values

At any point in time, the following could represent the state of the row ,where x denotes an occupied seat , and a . represents an empty seat.
x .....x..x......x..x

On add_student, remove the max element S_max of the heap, and place the student in the middle of the segment S_max returned. This would split S_max into two parts, which would then be added to the heap.
Also maintain the student's location and neighbor (the immediate left and right array indexes that are occupied) info in a hashtable indexed on the student id.

On delete, just update the array, and add the new large segment ,so formed due to removal of the student, to the heap.Update the neighbor info of the neighbors of the student_id. The older segments with student's index as one of the endpoints could be left around. Finally remove the student_id from the hashtable

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

Solution:
1) Brute force approach:
- store all students positions and when adding one, choose the two
with the greatest distance among each other and place the new
student in the middle
- If students are kept in sorted order in array it's O(n) time
complexity
- accordingly removal has time complexity O(n)
- space complexity is O(n)
it will require special care for the first two, as seating the
first at postion 0 and second at position n-1

2) Tree as ordered set for distances:
- have a tree that orders the students according to the
free distance on their right (if equal, take position of student)
- have a hashtable that tranlates from student id to tree-node
- deal with special case if less than two students (see below)
- pick student with largest distance on its right and insert
the new student in between.
- update the nodes accordingly
- time complexity: O(lg(n))
b) remove:
- find the right node (O(1))
- patch nodes to the left and right
- update nodes (O(lg(n))
- total timecomplexity O(lg(n))

Since we are talking about a row of students, I assume 20 or 30
people is the upper bound for that row. In this case the O(lg(n))
solution is outprformed by the O(n) solution due to cache reasons
and because of lower consts.

Anyway the O(lg(n)) solution is more fun to code:
- to solve the issue with the empty row, I placed two sentinel
nodes at position -1 and n, the left's left links back to itself,
the right's right links back to itself
- I place a dist function (getDist), which will look like
right.pos - this.pos and due to the sentinels always work.
- I create a compare function that uses this dist function and
on equality prefers the lower position (as the problem stated)
- I have an add function which will add a tree node and an entry
to it in the idex (hashtable)
- I have a update function which reorders the tree when the nodes
key change (I remove and re-insert with STL)
- I have a Student structure which has pos_, left_, right_ and id_
attributes (id_ is informative)
- students_ is the ordered set, ordered according the description
above

``````int addStudent(int studentId)
{
Student* left = *students_.begin(); // the one with the largest space on the right
Student* right = left->right_;
if (right->pos_ - left->pos_ == 1) return -1; // no space
Student* newStudent = new Student(studentId, -1, left, right); // pos = -1
if (left->left_ == left) newStudent->pos_ = 0; // right of left sentinel
else if (right->right_ == right)  newStudent->pos_ = right->pos_ - 1; // left of right sentinel
else newStudent->pos_ = (right->pos_ + left->pos_) / 2; // between two students
left->right_ = newStudent;
right->left_ = newStudent;
update(left); // update left node in tree, right node's distance and pos didn't change
return newStudent->pos_;
}``````

removeStudent:
- studentsIdx_ is the hashtable

``````void removeStudent(int studentId)
{
auto itRemove = studentsIdx_.find(studentId);
Student* remove = *itRemove->second; // student to remove
Student* left = remove->left_; // left of student to remove
Student* right = remove->right_; // right of student to remove
left->right_ = right;
right->left_ = left;
update(left); // left's node distance changed, right nodes distance and pos didn't
students_.erase(remove); // remove pointer from set
studentsIdx_.erase(itRemove); // remove from hashtable
delete remove; // free memory
}``````

the full code (C++ 11)

``````#include <cassert>
#include <iostream>
#include <set>
#include <unordered_map>

using namespace std;

struct Student
{
int id_; // the id of the student
int pos_; // the position of the student
Student* left_; // student on the left
Student* right_; // student on the right
int getDist() const { return right_->pos_ - pos_; }
Student(int id, int pos, Student* left, Student* right)
: id_(id), pos_(pos), left_(left == nullptr ? this : left),
right_(right == nullptr ? this : right) {
}
};

struct StudentOrderComp
{
bool operator() (const Student* left, const Student* right) {
if (left->getDist() > right->getDist()) return true; // first the greater distances
if (left->getDist() < right->getDist()) return false;
return left->pos_ < right->pos_; // if equal distance, first lower positions
}
};

class ClassRoom
{
private:
int seatCount_;	// number of seats
set<Student*, StudentOrderComp> students_; // ordered set with students
unordered_map<int, decltype(students_)::const_iterator> studentsIdx_; // student id -> Student

public:
ClassRoom(int rowLength)
{
seatCount_ = rowLength;
Student *leftSentinel = new Student(-1, -1, nullptr, nullptr);
Student *rightSentinel = new Student(-2, seatCount_, leftSentinel, nullptr);
leftSentinel->right_ = rightSentinel;
}

~ClassRoom()
{
for (Student* s : students_) delete s; // clean up
}

{
assert(studentId >= 0); // id -1 and -2 is reserved for left and right sentinels
Student* left = *students_.begin(); // the one with the largest space on the right
Student* right = left->right_; // the student on the right of left
if (right->pos_ - left->pos_ == 1) return -1; // no space
Student* newStudent = new Student(studentId, -1, left, right);
if (left->left_ == left) newStudent->pos_ = 0; // left sentinel
else if (right->right_ == right)  newStudent->pos_ = right->pos_ - 1; // right sentinel
else newStudent->pos_ = (right->pos_ + left->pos_) / 2; // in between two students
left->right_ = newStudent; // patch existing left's right pointer
right->left_ = newStudent; // patch existings right's left pointer
update(left); // update left node in tree, right node's distance and pos didn't change
return newStudent->pos_;
}

void removeStudent(int studentId)
{
assert(studentId >= 0); // id -1 and -2 is reserved for left and right sentinels
auto itRemove = studentsIdx_.find(studentId);
assert(itRemove != studentsIdx_.end()); // must exist
Student* remove = *itRemove->second; // student to remove
Student* left = remove->left_; // left of student to remove
Student* right = remove->right_; // right of student to remove
left->right_ = right; // patch left's right
right->left_ = left; // patch right's left
update(left); // left's node distance changed, right nodes distance and pos didn't
students_.erase(remove); // remove pointer from set
studentsIdx_.erase(itRemove); // remove from index
delete remove; // free memory
}

private:
// insert into index and ordered set
{
studentsIdx_[student->id_] = students_.insert(student).first;
}

// used to update the tree node in the set (remove and re-insert)
void update(Student* student)
{
auto it = studentsIdx_.find(student->id_);
assert(it != studentsIdx_.end()); // must exist
students_.erase(it->second); // remove it
}
};

int main()
{
ClassRoom r(10);
cout << "remove(2)" << endl;
r.removeStudent(2);
cout << "add(5): " << r.addStudent(5) << endl; // 2 (it's first 3 space)
cout << "add(6): " << r.addStudent(6) << endl; // 9 (now only 3 space)
cout << "remove(1)" << endl; // creates a 2 space
r.removeStudent(1);
cout << "add(7): " << r.addStudent(7) << endl; // 0 (first 2 space)
cout << "add(9): " << r.addStudent(9) << endl; // 1 (first 1 space)
cout << "add(12): " << r.addStudent(12) << endl; // 8 (last empty space)
cout << "remove(3)" << endl;
r.removeStudent(3);
cout << "add(14): " << r.addStudent(14) << endl; // 4 (only empty space)
}``````

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

I think a “binary fill” approach would work here. Just an idea but we can seat the first student at row0 and second student rowN-1, then third student in middle and keep alternating seating for left and right half. What do you guys think?

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

Do we have to use hash table here?

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

This could be solved maintaining a max heap of lengths of segments of empty seats as keys, and the pairs of segment endpoint indexes as values

At any point in time, the following could represent the state of the row ,where x denotes an occupied seat , and a . represents an empty seat.
x .....x..x......x..x

On add_student, remove the max element S_max of the heap, and place the student in the middle of the segment S_max returned. This would split S_max into two parts, which would then be added to the heap.
Also maintain the student's location and neighbor (the immediate left and right array indexes that are occupied) info in a hashtable indexed on the student id.

On delete, just update the array, and add the new large segment ,so formed due to removal of the student, to the heap.Update the neighbor info of the neighbors of the student_id. The older segments with student's index as one of the endpoints could be left around. Finally remove the student_id from the hashtable

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

This could be solved maintaining a max heap of lengths of segments of empty seats as keys, and the pairs of segment endpoint indexes as values

At any point in time, the following could represent the state of the row ,where x denotes an occupied seat , and a . represents an empty seat.
x .....x..x......x..x

On add_student, remove the max element S_max of the heap, and place the student in the middle of the segment S_max returned. This would split S_max into two parts, which would then be added to the heap.
Also maintain the student's location and neighbor (the immediate left and right array indexes that are occupied) info in a hashtable indexed on the student id.

On delete, just update the array, and add the new large segment ,so formed due to removal of the student, to the heap.Update the neighbor info of the neighbors of the student_id. The older segments with student's index as one of the endpoints could be left around. Finally remove the student_id from the hashtable

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

``````class EmptyRange {
public:
EmptyRange(int from_idx, int to_idx) : from_idx_(from_idx), to_idx_(to_idx)
{
}
bool operator<(EmptyRange const &other) const
{
int len = to_idx_ - from_idx_;
int len_other = other.to_idx_ - other.from_idx_;
if (len == len_other) {
return from_idx_ > other.from_idx_;
}
return len < len_other;
}
int from_idx_, to_idx_;
};

class Row {
public:
Row(int size)
{
if (size < 2) {
cerr << "invalid size\n";
exit(-1);
}
seats_.resize(size, -1);
pq_.push(EmptyRange(0, seats_.size() - 1));
}
{
if (id < 0 ||
students_.size() >= seats_.size() ||
students_.find(id) != students_.end())
{
return -1;
}
EmptyRange r = pq_.top();
pq_.pop();

int idx = -1;
if (r.from_idx_ == 0) {
idx = 0;
pq_.push(EmptyRange(1, r.to_idx_));

} else if (r.to_idx_ == seats_.size() - 1) {
idx = seats_.size() - 1;
pq_.push(EmptyRange(r.from_idx_, seats_.size() - 2));
} else {
idx = r.from_idx_ + (r.to_idx_ - r.from_idx_) / 2;
if (idx > r.from_idx_) {
pq_.push(EmptyRange(r.from_idx_, idx - 1));
}
if (idx < r.to_idx_) {
pq_.push(EmptyRange(idx + 1, r.to_idx_));
}
}
seats_[idx] = id;
students_[id] = idx;
return idx;
}

void RemoveStudent(int id)
{
auto it = students_.find(id);
if (it != students_.end()) {
int idx = it->second;
seats_[idx] = -1;
students_.erase(id);
RebuildPQ();
}
}

private:
void RebuildPQ()
{
while (!pq_.empty()) {pq_.pop();} // should be pq_.clear();
int from_idx = -1;
int to_idx = -1;
for (int i = 0; i < seats_.size(); ++i) {
if (from_idx == -1) {
if (seats_[i] == -1) {
from_idx = i;
}
} else {
if (seats_[i] != -1 ||
i == seats_.size() - 1)
{
int to_idx = seats_[i] != -1 ? i - 1 : i;
pq_.push(EmptyRange(from_idx, to_idx));
from_idx = -1;
}
}
}
}

vector<int> seats_;
unordered_map<int, int> students_;
priority_queue<EmptyRange> pq_;
};``````

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.

### 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.