## IBM Interview Question for Tech Leads

Country: India
Interview Type: Phone Interview

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

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?

If 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).

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:

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.
0

That's also assuming that the integers are small relative to the size of the list so the k in the O(n+k) doesn't overpower the n.

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.

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.

### 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.

### 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.

### 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.