Amazon Interview Question for SDE1s


Country: United States




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

We can use a maxheap. The root of the maxheap is the minimum number. When checkout, we get the root. When checkin, we insert the number. GetRoot and Insert both take O(logn).

MaxHeap heap( LONG_MAX );
long CheckOut( MaxHeap heap )  return heap.GetRoot();
void CheckIn( MaxHeap heap, long input )  heap.Insert( intput );

- cctsinghua May 05, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

one point on your implementation, the question says "checkout should return the minimum available LONG number" and in your implementation you are returning MAX number...

- ABC May 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Thanks, I thought it requires to return maximum. Use a max heap instead could return minimum.

- cctsinghua May 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Simple solution, use 2 TreeSets (sorted sets) one for the "checked out" elements and one for "checked back in" elements. Then:

- To insert: Check the max in "checked out" set and see if there if the min number in "checked back in set" < max , if yes return that. If not, just check in max+1.
This will be O(log(n)) in the worst case

- To checkin - Just insert the element in "checked back in" set.
This will also be O(log(n)) in the worst case.

- nixcoder May 04, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We could use heap for this, though I am concerned about the maximum size of heap in worst case. Here is some code (which assume a heap data structure exists). You can use priority queue in Java to implement this.

If we use checkin and checkout operations alternatively, then heap size will be zero. In worst case when we check out 1..N and then start checking in numbers < N then heap size can reach upto N-1

private long value = 1;
    private Heap h = new Heap();
    
    public long checkout() {
        // We want the next number in the sequence
        if(h.size() == 0) {
            this.value++;
            return value - 1;
        } else {
        // return the minimum value from heap
            return h.removeRoot();
        }
    }
    
    public void checkin(long val) {
        // Checkin the previous number that was checkedout
        if(val == this.value - 1) {
            this.value--;
        } else {
        // insert into heap as its not in the sequence
            h.add(val);
        }
    }

- CodeNameEagle May 09, 2013 | 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