Amazon Interview Question for Software Engineer / Developers






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

- hashtable(an unsorted linked list is used for handling collision.
)
insert: O(1)
delete: O(n)
lookup: O(n)

- linked list
insert: O(n)
delete: O(n)
lookup: O(n)

- someone September 30, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Insertion/deletion in a linked list is O(1) and not O(n)

- Ran November 18, 2009 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

in case of hashtable solution, if we consider uniformly distributing hashing, then lookup time surely will come down to O(1)

- spiderman August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Ran is absolutely right about insertion in linked list, as insertion is done at the begining of linked list which just takes creation of new node and making it head of the linked list.

But, in case of deletion in linked list, lookup itself will take O(N) in the worst case, that is traversing time in linked list.

- spiderman August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

map restricts key-value mapping to 1:1 .. so u cant have duplicate keys.
u could use hashing .. all constant time operations and trees O(lg n) operations

- ashish November 13, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- Give two data structures you could use
1. HashMap using hash table (unsorted map)
2. TreeMap using Red-Black Tree (sorted map)
- What is average and worst case insert time, delete time, look up time
1. for HashMap: average O(1) worst O(N)
2. for TreeMap: average O(log N) worst (unbalanced) O(N)
- What are pros/cons of each
1. for HashMap: speed
2. for TreeMap: sorted

- Jason February 27, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The simplist one to use is an array.
lookup: O(1)
delete: O(n) due to shifting
insert: O(n) due to shifting
avg: O(n)

Cons:
Too many mem writes when shifting.

Pros:
Least mem overhead for lookup.

Hashmap and Treemap are good ones too.

- Jack February 27, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

In array, key lookup will take n-iteration in worst case, where n is the size of array

- spiderman August 20, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Jason, RB tree is balanced. so the wosrt case for insert, delete, and lookup time is O(log N)

- anony July 19, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

For linked list, why does deletion and insertion need O(n)? It should be
O(1). For example, When i do deletion on a given element, I can just copy the next node info to the memory of the delete element, and free the mem of the next node. It is O(1).

- tt September 09, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

only if you have a pointer to the node to be deleted

- chaos January 23, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

and the node can not be the last one

- chaos January 23, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use a red black tree

- Tarun February 05, 2008 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Could you give more details? Thanks!

- chaos January 26, 2010 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Wonder why no one thought of a struct of key val pair, arranged in a BST and one which has several linked lists ,each linked list having a hashed value it is connected to

- code756 March 21, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

For insertion or deletion in a linked list, we have to traverse through the list...so the complexity is O(n)

- Happy January 05, 2007 | 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