Qualcomm Interview Question


Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
11
of 13 vote

Array Elements are stored in contiguous memory locations. Hence they will be faster to retrieve.

- devenster March 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

This translates to better cache behavior...that's why arrays (IN THIS CASE) are faster.

- omouri March 25, 2013 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

What do you mean by contiguous memory locations? Physical or Virtual ?
AFAIK, it might as well be virtual.

So I am not able to justify why they should be faster. One index of the array could be in one page and the other in another page mbs away. So why would that make it any faster or result in better cache behavior?

- Bibhu Mohaptra May 06, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 3 votes

its physical not virtual, thatswhy it is faster

- vinit May 19, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

First, there is no requirement for random access, only iterate one by one.
In this case, continuous memory does not matter so much.

It really depends on the Link List implementation and the size.
If it is a normal size data, array will be a little faster.
But if it is a really big size, link list may be faster because it does not need allocate the big continuous memory block for data loading.

- Jie July 22, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Locality of reference plays here if you take cache into account.

- viki July 28, 2013 | Flag
Comment hidden because of low score. Click to expand.
5
of 5 vote

Arrays are continous memory blocks hence indexing and searching is faster than linked list
linked lists are nodes pointing to other nodes so to find the 200th node in a linked list of 10,000 nodes you would have to traverse 200 nodes

it is easier to faster to add a node anywhere in the linked list and push the right half of the nodes by 1 place since it involves just changing the prev nodes pointer and pointing the new node to next node hence it is of constant time O(1)

same goes for deleting

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

Though the question suggests that we just need to iterate in a for loop and print it, saying that it would almost be the same in either case and that the difference would be at the assembly level like prem has suggested would probably be correct. But pointing out that if we are allowed only a Singly Linked list and we are to iterate from the last element to the first then Array would be faster, would fetch additional points from the interviewer I suppose.

- teli.vaibhav March 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

even if we print linked list in reverse order still o(n)

- Bahar P March 24, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

to do it in o(n) you'd do an in order traversal and use a stack to reverse the order before printing.
otherwise you'd need o(n^2)

- Houston Hoffman July 01, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

Arrays are faster than linked list. To access any element in array it takes O(1) ,but in linked list to access nth element it takes O(n)

- bobbyblue24 June 13, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 2 vote

Well we all know that Array Access is faster of course .. The main reason is as follows

As it is just to iterate the loop , many may get confused as we need loop in both case but the main question here is..

Struct Node *ptr=node -> next;
and
array[counter+1].

Now if you beak this into assembly language, it is sure that array would hv lesser Instruction to execute than LL (people may try writing the assembly to verify).

Now as we knw the each instruction may take 1 / 2 / 3 CPU cycles to execute .. then you can verify why Array access always results faster than LL

- hprem991 March 15, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Plz correct me if i am wrong.
in array, it is done by Increamenting the pointer by a fixed known amount.
whereas in case of ll first it will have to access the amount to be increased by accessing the
->next value.

so, in case of array accessing time is saved. So it would be faster.

- LAP March 18, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

in an array since u know the index in the continuous memory block, u can directly access the element in O(1)

- Sandy March 21, 2013 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

O(1) is for accessing single element, but here we have to iterate, so it is O(n)

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

I wonder not to see a basic difference discussed...

array is on stack & Link list is on heap. Access to stack memory is predictable and faster... while with link list it is not...

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

array can be also in heap, if we allocated memory by malloc.

- Sandeep July 10, 2014 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

It depends on the location of the data in the memory,If the data is side by side like data in the array,then linked list will be the faster ones.

- Sumanth Vakacharla November 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

array is faster than the linklist because in array we have direct address of the node while in link list we have to traverse in *next direction to find an eliment.....

- kamlesh khatvani December 09, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I think to iterate over all elements in array it is of O(n) where n is the number of elements in array.
Also,it is O(n) in linked list.
But I think array is faster due to contiguous memory allocation and also due to less memory access as you dont need to access next pointer.

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

In Array, index i have to 1. incremented 2. resigned which involves two operations to point next value.
In Linked list, just assigning the next location, so only one operation.

So linked list is faster.

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

For you scenario Linked List is faster, because in case of List, I have a memory in hand, so i can directly print (ptr->data), where as with array i have to do addition then get the right index and print (array[1]) --> arr+1.)

- sivanraj November 27, 2014 | Flag Reply
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 votes

I hold reservation about the answer. Value of an array can be accessed by offset, too. See the discussion here. h-t-t-p://stackoverflow.com/questions/5445131/why-are-linked-lists-faster-than-arrays

- walnutown March 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
2
of 2 votes

In an array, the values are stored contiguously, and therefore there should be fewer memory ops and fewer cache misses as well. Generally this is likely to trump the cost of a pointer addition. Besides, in the linked list, even things like list = list->next can involve an arithmetic calculation for the address (internally it becomes something like list = contents of memory ( list + offset of field named "next").

- eugene.yarovoi March 15, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

I didn't thought of cache misses. That looks like more prominent reason for arrays to be faster.

- Cerberuz March 16, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

Yes. Also consider that an array has (almost) nothing but data, whereas the linked list has data and next pointers. There's just more memory locations that need to be examined to complete a traversal of a linked list.

- eugene.yarovoi March 17, 2013 | Flag


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