Amazon Wipro Technologies Interview Question for Software Engineer / Developers






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

I think most people forget to think about the Hardware aspect of things, remember that Arrays give much better locality as in caching is so much better when data is in consecutive blocks with the prefetch stuff in processors etc... im sure an ECE guy would be able to better ellaborate on that point ( sorry im CS :) )

- Muhariz Jabeer April 14, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

O(1) time to add an element to a linked list...also, linked list doesn't have a fixed size, so there will be no need to copy elements (like when you run out of space in a fixed-sized array), which is a very costly operation.

- Anonymous September 20, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Also linked lists don't have to be allocated contiguous memory like arrays, so the heap manager can allocate the memory where ever available

- Anonymous September 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

save memory

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

So if that's the only reason to use an array over a linked list, why would you always use it?

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

With linked lists, you need to do a linear search to find an element of the list with a specific index. With an array, you can just lookup the element in O(1) time.

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

I think saying arrays should be used always would be wrong. One should make a choice depending on the requirements:

Both arrays and linked lists are for storing objects of the same type.

Arrays:
- you know the number of elements before hand. If size is dynamic choice, arrays are a wrong (or costly) choice.
- element access time is importanta. It is O(1) for arrays and O(n) for linked lists

linked lists:
- when number of elements is unknown or dynamic
- suitable for representing trees and so on

Use arrayList in .net and have best of both. (Ok keeping in mind that capacity is well planned).

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

I really can't agree with you that an arraylist is the best of both worlds. Sure, an arraylist beats an array (one that's dynamic anyway), but it doesn't necessarily beat a linked list. A crucial difference is that element can be inserted in sorted order into a linked list quickly and efficiently.

It's also somewhat misleading to say that linked lists are suitable for representing trees. Although the data structures have some things in common, they are different data structures. A linked list cannot represent a tree.

- Gayle L McDowell July 28, 2005 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Agreed. linked list is not suitable for a tree (an adjacency list is more approp)...I was thinking in terms of a binary tree where each node maintains a list of parent/ child etc...same with inserting into an ArrayList. Usually I have a wrapper around arrayList which provides me sorted insert and so on. Thanks for your comments.

- Seshagiri July 28, 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 ]



Array Linked list

Indexing O(1) O(n)
Inserting O(n) O(1)
Deleting O(n) O(1)

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

Apart from the above differences, one important use of linked lists is to store persistent data (be able to access old data after new data is added) easily. If there is an array, and some changes are made to this array but you still want to be able to see the old array, the only way you can do this is by copying the entire array into a new array and making changes to the copy.
In a linked list, lets say you just want to change the front portion of a linked list, then you create a new front portion and at the end of this front portion, point to the old back portion (In effect, this lets you share the back portion).
If the change is random, you can come up with operations, which will point to appropriate old portions.

- PR March 31, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Arrays: Use them when most of the data will be static i.e. they won't change once they are inserted - and where there will be intensive search operations

Linked list: use them whenever the data is dynamic - lots of insertions and deletions - not too much of search intensive operations

- Kar June 05, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hi Gayle,

Inserting elements in sorted order will take O(n) in both arrays and linked-list. This is so because in arrays you have to move O(N) elements elements while in linked-list you have travel through O(N) nodes.

In fact, moving elements can be faster because of locality-of-reference of arrays.

Please correct me where I a wrong.

- creator June 09, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hi all..
answers i found here are good. i wanna give my answer here itself
in my view:
Mainly there are 4 importent factors which are responsible to use any array.
1.accessing time. If your application needs faster speed, then elements insertion(if array is empty and if no need to insert in the middle of an array) or extraction data. This gives advantage over linked-list.
2.if there are fixed number of elements you want to enter.
3. if ur program is for small applications and needs some what acceptible memory.(as for larger application there may not be that much of memory available serially)
4. Dealing with arrays are much easier logically than Liked-List.
so if my application needs
faster execution,
limitted and known number of elements
for easy logic,
i prefer to use Array than linked list..

- vishnu November 01, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

When the size of the data is not known in advance, linked list is the choice.

- funhere November 08, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Deleting/inserting a node in an array is not O(1) if the node is targeted at the front or in the middle. Deletion: the array contents would have to be shifted and the last node deallocated. Insertion: allocate a node and shift contents.
This is for a vector. For a deque, insertion/deletion in the middle is not O(1), but O(1) at front/back.

A linked list has O(1) deletion/insertion anywhere.

- Jack November 10, 2006 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In case of link list while allocating nodes worst case possible scenario may be that memory gets allocated in various pages , which may result in significant page faults , degarding the performance . Whereas it may not be the same case with Array as is it a contigous allocation , provided array data elements are not of page size .

- Anand Rai September 10, 2007 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

it depends on the situation. you can't say one is better than the other one in all cases !

- Anonymous September 28, 2009 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

You can build Windows Vista with linked lists to accommodate Blue screens

- GodKillsKittens September 21, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Awesome ...and really hillarious

- Anonymous September 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hilarious? No. Sophomoric, stupid, boring, unoriginal and cliched? Yes.

- Anonymous September 21, 2011 | Flag
Comment hidden because of low score. Click to expand.
0
of 2 vote

This question makes me want to go to other sites for better questions :)

- Anonymous September 22, 2011 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Answer no any people used

- aditipatel301@gmail.com August 10, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Arrays :
Random Access.
Excess of data are allocated even when they are not required.
Contigious memory allocation hence fast access to memory(very helpful in cache memory).
Linked List:
Sequential order.
Run time memory creation.
Random location creation of memory .

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

Arrays :
Random Access.
Excess of data are allocated even when they are not required.
Contigious memory allocation hence fast access to memory(very helpful in cache memory).
Linked List:
Sequential order.
Run time memory creation.
Random location creation of memory .

- sanjithkanagavel July 19, 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