## Microsoft Interview Question

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

If somebody comes up with the answer he can patent it....

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

patent psycho patent psycho :P :P

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

patent psycho patent psycho :P :P

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

Not possible

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

does the value of each items has a scope?
then we can use counting sort.
otherwise,i have no idea

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

I can think of nlogn as many of you would. Traverse through the list and create a btree But cannot think of O(n) to apply in linked list

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

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)

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

Worst case memory hog but Works!

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

@CodeBoyS what if the input is something like ->
-10000000 10000000 ........

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

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.

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

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

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

@Triton: you are right... but if you tell the interviewer that you are going to use 4GB of memory (which is O(1) - constant), I think s/he will be very unhappy with the answer... :)

The solution with the array is O(n) when Abs(a[i]) = O(n).

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

Sort in O(n)? Give me a break.

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

le le bhai break..chai pani pi ke aana :P :P

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

bhai bahut break ho gaya wapas aa jaa ab

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

Kit kat break to banta hai.

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

aja mahi aja maho...aa soniye
kaha gayab ho gya??

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

// 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

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

linked list don't have random access iterator. so you can't do CS on linked list. can possible when you copy linked list element to array A and then again copy B to linked list

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

sayak we are taling about linked lsit sorting and then its the count sort which requires a lot of memory and that too you can use when you know the range of numbers only...if A[j]=10000 what will be your B array's size ?? did you know what is the maximum element in the array ??

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

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)

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

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 :)

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

@ramu: think it twice before posting!!

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

ramu is a comedian? :p

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

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/

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

We can use radix sort which will sort the list with O(kn) time and O(kn) space where k is the number of digits (or chars) in the longest key.

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

why not we use counting sort instead to sort the array which is o(n)?

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

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?

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

Great..but how do you sort an array in O(n)?! :P

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

why not create a entirely new linkedlist. fetch an element from the current list and parse the new list to find the position of this pointer. simultaneously free the node which has been arranged in the new linked list.

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

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.

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

Are you kidding?! :)
Well, we can do it if quantum computing comes practical!!

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.