Google Interview Question Interns
Country: United States
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
a) add:
- 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
addStundent looks like:
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
add(newStudent); // add new node to tree and index
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;
add(leftSentinel);
add(rightSentinel);
}
~ClassRoom()
{
for (Student* s : students_) delete s; // clean up
}
int addStudent(int studentId)
{
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
add(newStudent); // add new node to tree and index
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
void add(Student* student)
{
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
add(student); // add it again
}
};
int main()
{
ClassRoom r(10);
cout << "add(1): " << r.addStudent(1) << endl; // 0
cout << "add(2): " << r.addStudent(2) << endl; // 9
cout << "add(3): " << r.addStudent(3) << endl; // 4
cout << "add(4): " << r.addStudent(4) << endl; // 6
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(8): " << r.addStudent(8) << endl; // 7
cout << "add(9): " << r.addStudent(9) << endl; // 1 (first 1 space)
cout << "add(10): " << r.addStudent(10) << endl; // 3
cout << "add(11): " << r.addStudent(11) << endl; // 5
cout << "add(12): " << r.addStudent(12) << endl; // 8 (last empty space)
cout << "add(13): " << r.addStudent(13) << endl; // -1, full
cout << "remove(3)" << endl;
r.removeStudent(3);
cout << "add(14): " << r.addStudent(14) << endl; // 4 (only empty space)
}
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
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
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));
}
int AddStudent(int id)
{
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_;
};
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
- random August 20, 2017At 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