Uber Interview Question for Senior Software Development Engineers


Country: India
Interview Type: Phone Interview




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

Use BST to keep integers in sorted format.
And use a stack to keep min difference also a metadata regarding which nodes contribute to it.

When you add a node in BST.
Check, its in order successor and predecessor to compute min diffs and if it is less the current top of stack , update the stack.

When you delete a node in BST, delete it . And keep popping the stack until the top of stack does not utilize the said node (maximum two pops)

Complexity->
Add -> logN
Get Min - O(1)
Delete -> log N

- krbchd August 16, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

There are three primary methods

1) add
2) delete
3) peekMinDifference

I would first ask which operation would get called the most. That gives us an idea for what we should optimize for. For example if peek gets called rarely then we can simply make add and delete O(1) operation and make peek nlogn with simple sort and adjacent dif check.

Another option is to use min heap. That would make add/delete constant and peek logn operation but building that in interview might not be as easy as option A.

- Itsme August 17, 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