Interview Question for Software Engineer / Developers

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

Merge sort, because merge sort has worse case of O(nlogn) complexity (compring to O(n^2) for quick sort) and during the merge phase, you do not need to allocate extra memory like you have to for array.

Comment hidden because of low score. Click to expand.
0

You are not merging anything. So how will you use Merge sort?

Comment hidden because of low score. Click to expand.
0

I assume the question is for inplace sorting. because if extra memory is allowed then any efficient sort can be used.
Since we don't have direct indexing we cannot access an element directly and for merge sort we would require n additional pointers to each node (doesn't matter if it's by recursion). So we cannot use merge sort because it would require O(n) space. Maybe insertion sort is the best in for linked list, any suggestions?

Comment hidden because of low score. Click to expand.
0

For merge sort additional pointers are not required.

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

Sorry, i guess you meant by recursion (mergesort). But even that takes additional space if i am not wrong.

Comment hidden because of low score. Click to expand.
0

@Kishore
No, it takes O(1) space.
Because unlike sorting an array using merge sort, there is no need for an auxiliary array when you're merging two linked list.
When you merge, you can just modify the pointer(reference) of the last element in the sorted list to point to the next element. All you need is to keep track of the last element in the sorted list, and the pointers to the two candidates for next element to be added.

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

To sort a linked list merge sort is good in comparison to other sorts because
1.QuickSort: In linked list choosing a pivot is not O(1) also arranging the elements against pivot is O(n^2).
2. Similar comparison can be drawn for other sorts on the basis of accessing an element in Araay (O(1)) and Linked list (O(n)).

Here, merging is in place and of O(n) at each level of recursion.
Although choosing mid is again not of O(1) as compare to array. Even though the time complexity is O(nlogn).

Apart from that with the use of extra space we can use generic Qsort function to sort.
e.g.
We can create an array of pointer of the nodes and sort this array with a compare function like

``````int compare_func(const void* node1, const void* node2)
{
const node* keyNode1 = (node*)node1;
const node* keyNode2 = (node*)node2;
return (keyNode1->data - keyNode2->data)
}``````

After sorting finishes we can re-make the list using this array.

Comment hidden because of low score. Click to expand.
0

hmm.... an array of pointers. I believe that is still O(n) space. And if we have an array of pointers we can use any O(nlogn) sorting algo.

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

www(dot)chiark(dot)greenend(dot)org(dot)uk/~sgtatham/algorithms/listsort.html

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.