Amazon Interview Question Software Engineer Interns
Country: United States
Interview Type: Phone Interview
HashMap : Insert - O(1), search (by key) O(1)
Array : Insert - O(1), search O(n)
Linked List : Insert - O(n), search O(n)
Queue : Insert (by front pointer) - O(1), search O(n)
Search by index in Array? That would make it a hashMap (with possibility the trivial hash h(i) = i).
^ yeah, the actual insertion procedure if O(1) (just reroute some pointers).
However, if you want to insert a node into the middle of a linked list, you really got to start from the beginning traverse to the position where you want to insert the node and then do the actual insertion procedure. The traversing would then take O(n).
Insertion at the beginning is O(1) (no traversing necessary).
And, inserting at the end could take O(1) if you kept a reference to the tail of the list.
------------------ |Insert* | Search
-------------------|-----------------------------------------------------------
HashMap | O(1) | O(1)
--------------------------------------------------------------------------------
Array | O(1) | O(n)
--------------------------------------------------------------------------------
LinkedList | O(1) | O(n)
--------------------------------------------------------------------------------
Queue | O(1) | O(n)
--------------------------------------------------------------------------------
*Assuming insertion at the end
- Le Snob. March 17, 2014[ Avg / Worst Case ] Insert Search HMap 1/n 1/n UnorderedArray 1/1 n/n UnordLinkedList 1/1 n/n Queue <Queue does not denote a DS implementation, it is an ADT. Refer to possible implementation types, like two items listed above>