IBM Interview Question Tech Leads
Country: India
Interview Type: Phone Interview
Comment hidden because of low score. Click to expand.
0
of 0 vote
I'm not sure if that is possible in O(n) time. I would suggest the following algorithm:
Loop through the linked list:
Add to min or max binary heap
While the heap is not empty:
Pop off the heap and print
The complexity is O(n log(n)) on average it would be O(n) time since inserting on a heap approximates constant time (according to wikipedia article on it).
Comment hidden because of low score. Click to expand.
0
of 0 vote
If a node of linked list contain only positive integers, then you can sort it in O(n), using Counting sort. And then print it in Ascending and Descending order. Solution complexity is O(n).
Comment hidden because of low score. Click to expand.
Comment hidden because of low score. Click to expand.
0
of 0 vote
My guess is that the full original question was one of the following:
1. As previously mentioned here, relatively low integers (radix/counting sort to the rescue). By adding O(N) memory, you can sort it in O(N) runtime and then iterate on it easily on either direction.
2. Another option, is that the request was to just print the linked list start-to-end and also end-to-start.
In that case, a recursion method can be used for the backwards printing.
{{{void print_backwards(Node *n) {
if (!n) return;
if (n->next) print_backwards(n->next);
printf("%d, ",n->val);
}
3. You can't use extra memory, but you're allowed to change the linked list (as long as you return it to original state)
first pass:
print forward, while reversing the order of the list.
if it was [1] -> [2] -> [3]
on first step turn it into [2]->[1]->[3] , and then [3]->[2]->[1]
doing exactly the same again will both restore the order of the linked list, and also print it backwards :)
In summary - we don't have enough context for the original question to know for sure.
of course, this will take the same space and time complexity as above.
Is the question about printing an unsorted list in sorted order (ascending and descending), or is it about printing a list left-to-right and right-to-left?
- 010010.bin June 09, 2015If it's the former, it's pretty much impossible unless you are given some specific information about the data that the list holds, since sorting in general is not achievable in O(n).