Apple Interview Question Software Engineer / Developers
In fact you can traverse in O(√n) by preprocessing the list and doing O(√n) extra work during insert (indeed an intelligent work upon which the search will be O(√n)) . The answer is "Skip List". Even it is possible to do in O(lgn) by selecting a proper number of levels . Just search in google.
The most interesting thing is that it is possible to find an element in unsorted list with O( sqrt(n) ) complexity :) a quiz for cs theory
We can use parallel processing to solve this problem. Create sqrt(n) threads and use each thread to traverse sqrt(n) numbers simultaneously!
In fact you can traverse in O(√n) by preprocessing the list and doing O(√n) extra work during insert (indeed an intelligent work upon which the search will be O(√n)) . The answer is "Skip List". Even it is possible to do in O(lgn) by selecting a proper number of levels . Just search in google
The question incomplete. If we need to traverse all the n elements of the linked list then it can't be done < O(n).
If what they look for is O(n^0.5) then what needs to be traversed is a subset. Typically when given a linked list you don't know the total number of elements, so unless we know n or go thru the LL once to calculate it we wouldn't be able to skip around either.
I think this is a bogus question. But I did get the job :)
@samliPirate: I think apple likes idiots. btw, did you get any gold today? or did you walk the plank :D
I might be misleading due to me partial understanding of what a traversal could mean.
If n here could be considered as the number of iterations in the loop(for here we might have a loop something like while(node->next){...}) then I believe the following could be a solution.
//have two pointers for the linked list
//one to jump odd numbered nodes and other to jump in the even numbered nodes
traverse(node *n){
node *n_odd = n;
node *n_even = n->next;
while((n_odd) && (n_even))
printf("\n%d\n%d",n_odd->data, n_even->data);
if(!n_odd){
if(!(n_even))
printf("\n%d",n_even->data);
}
else
printf("\n%d",n_odd->data);
}
What I intended o do was to have two pointers jump alternate nodes and hence traversal would typically be n/2 which is n^0.5
This seems to be very simple question which by itself makes me worried if I have got something wrong.
Well if you are allowed to design your own linked list then search/insert/delete operations can be done in O(log n).
I think that Merge sort's algorithm of dividing the problem statement into half could be used .... and there is no such thing mentioned in the question about space.... so recursion is most likely the answer.
void traverse(mynode *head, mynode *tail) {
if(head->next == NULL){
//print the value stored in current head
}
mynode *temp1 = tail;
tail = get_mid(head, tail);
mynode *temp2 = tail->next;
tail->next = NULL;
traverse(head, tail);
traverse(temp2, temp1);
}
The answer is that it is POSSIBLE to traverse a list faster than O(N), at least theoretically, using a quantum computer.
Check out the Wikipedia article for Grover's algorithm here : en.wikipedia.org/wiki/Grover%27s_algorithm
They state an amortized running time of O(n^0.5), and space of O(log n). It also should be noted that it is not deterministic. That means that there is high probability that the algorithm will return the correct result, but it is not guaranteed.
Peace's Algorithm is a landmark in the history of Computer engineering. I wonder though that why restrict ourselves to jumping two nodes ? jump four nodes at a time and you get 0.25n , 8 nodes 0.125n , 16 nodes 0.0625 and so on. jump n nodes and you have got a O(1) and constant time traversal. No linear, logarithmic time no more.This moment will go down in history.
- Anonymous May 11, 2010