Amazon Interview Question
Software Engineer / Developersfor searching both take linear time..
for sorting array seems faster but with skip list (complex implementation compared to array) can reach very near to array's sort.
for sorting both are equivallent i think because in both cases we can do o(nlgn)
optimal solution one exception is that we can apply the counting sort in arrys in O(n) time if the ranges of numbers are given but not in linked list
as far as searching is concerned i think array is much better ecause many times we have a sorted raay and to serach that by binary search we can do the binary serach in o(lg n) time but this will not going to be possible in the case of the linked lists.
Both have their limitations but being said the elements are arranged either in array or in linked list, the answer should be array. Because it has index associated with each element and also swapping is easy.
- Anonymous June 11, 2011