Amazon Interview Question






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

please give me the answer

- aditya June 30, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

7. Traverses the current node before traversing the children.

8. Each node is linked to one other via a pointer. Advantages: fast insertion and deletion. Disadvantages: slow searching, even when sorted.

- Ben Kazez July 05, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

7. google for depth-first tree

8. I think that using up more memory is one of the disadvantage too. For searching, I think that array and linked list are about the same. Of course, linked list needs to access the node member to get the value, which uses up extra time. But it won't be too much difference I assume.

- someone July 26, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

oops, I mean depth-first search

- someone July 26, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Another disadvantage for linked list is that accessing the i-th node is not O(1) .

- someone July 26, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Linked List:
? They allow a new element to be inserted or deleted at any position in a constant number of operations (changing some references) O(1).
? Easy to delete a node (as it only has to rearrange the links to the different nodes).
? To find the nth node, will need to recurse through the list till it finds [linked lists allow only sequential access to elements. ]

Array
? Insertion or deletion of element at any position require a linear (O(n)) number of operations.
? Poor at deleting nodes (or elements) as it cannot remove one node without individually shifting all the elements up the list by one.
? Poor at inserting as an array will eventually either fill up or need to be resized, an expensive operation that may not even be possible if memory is fragmented. Similarly, an array from which many elements are removed may become wastefully empty or need to be made smaller

? easy to find the nth element in the array by directly referencing them by their position in the array.[ arrays allow random access ]

- Suji September 29, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

7.
//data-leftchild-rightchild order
struct binarytreenode
{
struct binarytreenode *lchild;
int data;
struct binarytreenode *rchild;
}

preorder (binarytreenode *node)
{
printf("%d",node->data);
preorder(node->lchild);
preorder(node->rchild);
}

8. In addition to above advantages of linked list, one more advantage I can think of is that linked lists dont have to be stored in contigous memory location whereas arrays require it. If an array contains a large number of elements, that becomes a definite disadvantage in instances where storage is limited. Linked lists take up whatever memory area is available in such cases, hence they are more effecient in certain cases.

- DesiNole August 27, 2006 | 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