Amazon Interview Question for Software Engineer in Tests


Country: United States
Interview Type: Phone Interview




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

I came across the following on stack Exchange, its about linked List vs Dynamic Arrays

In short:

The linked-list approach has worst-case O(1) guarantees on each operation; the dynamic array has amortized O(1) guarantees.
The locality of the linked list is not as good as the locality of the dynamic array.
The total overhead of the dynamic array is likely to be smaller than the total overhead of the linked list, assuming both store pointers to their elements.
The total overhead of the dynamic array is likely to be greater than that of the linked list if the elements are stored directly.
Neither of these structures is clearly "better" than the other. It really depends on your use case. The best way to figure out which is faster would be to time both and see which performs better.

Hope this helps!

- pulkit.mehra.001 December 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The best way to implement stack and queue is using linked list as it can grow dynamically. Also, since the operation are performed at the top of stack and Front and Rear of a Queue, they can be easily implemented in linked list using pointers to the head and tail.

Arrays are useful for quick random access. Since a stack or queue requires insertion/deletion operation at the extreme ends of list, linked list will give similar performance like arrays. Plus, it can grow dynamically as compared to Arrays.

- Coder December 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Arrays can also grow dynamically by use of malloc/calloc/realloc functions...just like linked list. SO i believe, this won't be an advantage of linked list over arraylist..

- Anonymous March 19, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Actually ArrayList based on arrays, so it is almost the same.
Pros of arrays - fast random access, because you dont need to iterate over links. But in stack/queue it is doesnt matter. Pros of this approach - your queue or stack can become quite big, so it can cause promotion failure in from young ot tenured. Also when your array will become fullilled youl'll have long operation of memory allocation and replacing your data. in case of big arrays - big risk of OutOfMemoryError.
LinkedList pros - very fast append both to head and tail, low risj of outof memory error and there is no need to allocate big amounts of memory. Pros memory defragmentation and long garbage collecting. GC have to raverse all references(there are a lot of them in list) to be sure that all nodes are reachable.

- glebstepanov1992 December 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

1. Simple array implementation - operations will be O(1), but maximum size of the stack must be defined in advance and can not be changed.
2. Dynamic array implementation - Here you increment the array size as you push the element to the stack. It is too expensive to implement. For an example to push second element, you create a new array of size 2, copy old element from old array (of size 1) to new array and at index 1 (n-1 in general) you add second element. Similarly for adding third element you create a new array of size 3, copy old elements from old array and at index 2 add new element. After n push the number of copy operations will be ~O(n squared). The complexity can be bettered by repeated doubling i.e. creating a new array of double the size instead of increasing the size by one.
3. Linked list implementation - This is the best approach as stack size here increases and decreases gracefully. Operations are O(1). Only that it uses extra spaces for references.

- Rakesh Roy December 27, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Stack (LIFO) - Dynamic array would be suffice. You add items to the end of the array and you pop them from the end of the array which results in O(1) for add and removal.

Queue (FIFO) - Linked List as the element at the front of the list can be easily be popped with O(1). Arrays on the other hand would require a reshuffle of the elements which is O(n) for the pop operation.

- Dru January 08, 2014 | 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