Google Interview Question for Interns


Country: United States




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

- ChrisK August 12, 2017 | Flag Reply
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?

- Itsme August 13, 2017 | 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