## Google Interview Question

Interns**Country:**United States

Comment hidden because of low score. Click to expand.

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

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.

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.

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.

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:

removeStudent:

- studentsIdx_ is the hashtable

the full code (C++ 11)

- ChrisK August 12, 2017