Amazon Interview Question for SDETs


Country: United States
Interview Type: Phone Interview




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

Use a binary min heap. Insertion is O(logN) and get_min will be O(1).

- dev June 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

C++, implementation

class AddAndGetMin {
private:
    multiset<int> data;
public:
    void add(int n) { data.insert(n); }
    int getMin() {
        multiset<int>::iterator it = data.begin();
        int n = 0;
        
        if (it != data.end()) {
            n = *it;
            data.erase(it);
        }
        
        return n;
    }
};

- kyduke June 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Every time you Add you update a minimum value, so the GetMin method will be O(1) time.

- hnatsu June 08, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think they wanted the whole array in a sorted order. Not just the minimum number.

- thewhatwhat June 11, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use stack

- vejon June 20, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

use a PriorityQueue with greater predicate, here is the example in C++

class AddGetDS{
    
private:
    priority_queue<int,vector<int>,greater<int>> myQueue;
    
public:
    void add(int x){myQueue.push(x);}
    int getmin(){return myQueue.top();}
    
};

- AndroidFan August 12, 2016 | 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