Amazon Interview Question for SDE1s

Country: United States
Interview Type: In-Person

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

unordered_map is the new data structure added to C++ STL as part of C++11 version (in <unordered_map> library).

Here is the direct quote from

"Unordered map is an associative container that contains key-value pairs with unique keys. Search, insertion, and removal of elements have average constant-time complexity.

Internally, the elements are not sorted in any particular order, but organized into buckets. Which bucket an element is placed into depends entirely on the hash of its key. This allows fast access to individual elements, since once hash is computed, it refers to the exact bucket the element is placed into."

Original map (<map>) implementation was done using a balanced tree implementation and therefore having the O(log N) time complexity to get/put/delete elements. However, <ordered_map> library is implemented differently as described above and have _amortized_ O(1) time complexity for get/put/delete operations.

Note that, if you go to actual manual page at, you can see the time complexities for each operations and you will see that worst case analysis in certain cases may vary from O(1) to (N), but if I were the interviewer I'd be OK with O(1).

- oOZz November 14, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
of 1 vote

An unsorted Map is a tipicall implementation of a Hashtable or a HashMap, where the keys' hashcode (in Java at least) will make room to the value in a certain bucket in the table.
The difference between the Hashtable Vs HashMap is that the hashtable is thread safe and the HashMap is not.
both run operation in constant time.

the opposite of a unsorted Map would be a SortedMap which a tipical implementation whould be a TreeMap, which Operation such as containsKey(), get(), put() are done on O(log n)

- Axel November 15, 2013 | Flag Reply

Add a Comment

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.


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


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