Microsoft Interview Question
0of 0 votessort a linked list in O(n)....
I can think of one solution.
1. Run through the list and find the MAX. TC = O(n).
2. Create a vector with size MAX and initialize to 0 or something else. SC = O(MAX)
3. run through the original array and using value of each element in the array as the index for your vector , set the vectors value to 1. TC = O(n)
4.Now run through the Vector and store the elements back in the array who's values are set to 1. TC= O(MAX)
So total Time complexity is = 2O(n) + O(MAX) ~= O(n)
So total Space complexity is = O(MAX)
Create a bigger array with 2 * Abs(MAX) elements and consider the minimum on index 0.
The problem is when the array is bigger than the memory.
Complexity is defined on the size of the input and not on the input value, so for the above sol, the complexity denoted as 2O(n)+O(MAX) is actually 2*O(n)+O(2^(log MAX))
(as a number n is represented by log n bits).
Now if the second term dominates, then the algo turns out to be exponential, not O(n).
// k = maximum value of any element of the given array -> O (n)
for i ← 1 to k do // -> O (k)
c[i] ← 0
for j ← 1 to n do // -> O (n)
c[A[j]] ← c[A[j]] + 1
//c[i] now contains the number of elements equal to i
for i ← 2 to k do // -> O (k)
c[i] ← c[i] + c[i-1]
// c[i] now contains the number of elements ≤ i
x = 0
for j ← 1 to n do
if (x<j)
{ while (x!=j)
{ c[A[j]] ← c[A[j]] - 1
b[A[j]] <- A[j]
x ++
}
}
// solution is the b[j] array
yes we can implement it in O(n)
1.find max element in linked list- O(n)
2.create an array of size max
3.traverse linked list and put element of liked list in to correspinding index in array suppose read element of linked list is 5 then it has to inserted at arr[5]
4.finally array is sorted and we can copy array element back to linked list
time complexity-O(n)
space complexity-O(n)
think before u write dude..
1. how will u take care of the duplicates
2. suppose there is no element called 5 ?
3. n how is it O(n) ?
4. so max element is 30 and there is no number from 1-20 ?
..what will do u of the 20 elements in the array created..
not discouraging u but think before u write :)
U r direction is good, do not consider people discouraging you...you can do better...Thank of using HashTable,,or something like TreeMap in Java...You can achieve in O(N), i am sure, you just need to think little harder. Good luck !!
@Rest: if you have balls, give the answer, or else get the fuck out of here, u morons !! \m/
copy the linked list to an array..sort the array in O(n)..copy it back to the linked list..whats wrong with this one?
Yes, We can do it as we don't have to worry about the space complexity. We remove the head of the linked-list and insert this node into a Min-Heap. After inserting all the elements of linked-list into priority -queue we repetitively remove the head of the Min-Heap and insert back into linked -list.
If somebody comes up with the answer he can patent it....
- DashDash August 18, 2010