## Microsoft Interview Question for Senior Software Development Engineers

Country: India
Interview Type: Phone Interview

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

keep a heap. add elements to the heap until it reaches k elements. when this happens, keep adding elements, but for every element added, remove the min from the heap and output it. when there are no more elements, remove and output all the heap elements.

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

Use insertion sort. It will run in O(N x K). But since K is constant, it should run in O(N).

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

Heap gives answer in N*log(K) which is slightly better.

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

This is good answer but also requires extra space O(k).

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

Use insertion sort. It will run in O(N x K). But since K is constant, it should run in O(N).

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

Can you elaborate your algorithm, how will to modify the original Insertion sort to sort array in O(N x K) time?

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

With insertion sort, you're always finding the min element in a range, and putting it at the beginning. This is similar, but you know the min element is within a range of 2k positions from the current. However, if we have a sliding window of size k that moves left to right, we ever only need to look at k elements each time (since anything to the left will be implicitly sorted).

Iow, for each element, search up to k-1 elements to the right of it, find min, swap with current element. Keep going until you hit the 2nd to last element.

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

I had another algorithm with O(1) space and O(n * Log k) time complexity.

1. Start with a window of min(2k, items in array). Sort it.
2. First k elements are sorted
3. Move window min(k, items left in array) index ahead
4. Goto step1 till items remaining in the array

sorting 2k Elements O(2k log 2k), n/k times
O(2k * n/k log 2k) = O(2n * log 2k) = O(n log k)

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

``````public static void order(int a[], int k) {
for (int i = 1; i < a.length-1; i++) {
if (a[i] > a[i + 1]) {
swap(a, i, i+k);
} else if (a[i - 1] > a[i]) {
swap(a, i, i-k);
}
}
}

private static void swap(int a[], int i, int k) {
int tmp = a[i];
a[i] = a[k];
a[k] = tmp;``````

}

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

``````public static void order(int a[], int k) {
for (int i = 1; i < a.length-1; i++) {
if (a[i] > a[i + 1]) {
swap(a, i, i+k);
} else if (a[i - 1] > a[i]) {
swap(a, i, i-k);
}
}
}

private static void swap(int a[], int i, int k) {
int tmp = a[i];
a[i] = a[k];
a[k] = tmp;``````

}

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

The optimal single threaded solution can be described something like this
implement a routine, which given l element between i,i+l indexes of an array, sort this l size subarray using inplace l x log(l) time algorithm.(options are : heap sort, or quick sort with proper pivot).
Once we have this routine, we can call it n/k times to sort the whole array as explained by @pc.
I am presenting the multithreaded algorithm which can solve this problem in n/r x log(k) time with r as maximum threads systme can allocate to this program.

``````A <- input array, k is the condition as per this question
Step : 1
do Parallel for j = 0; j < n; j  = j + 3k
sort(A, j, j+3k-1)

Step  : 2
do parallel for j = 2; j < n; j = j + 3k;
sort (A, j, j + 2k -1)``````

I havn't considered the edge cases in both the steps for simplicity, and btw they can only add upto O(k x log(k)) more complexity to the total complaxity.
one can easily check that given r threads, both the steps will only take O(n/r x log(k)) time.

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

``````void sort(int A[], int n, int k)
{
assert(A != NULL && n > 0 && k > 0 && k <= n);

priority_queue<int> que;

for (int i = 0; i < k; ++i) que.push(A[i]);

for (int i = 0; i < n - k; ++i)
{
a[i] = que.top(); que.pop(); que.push(a[i + k]);
}

for (int i = n - k; i < n; ++i)
{
a[i] = que.top(); que.pop();
}
}``````

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

Why not bubble sort? Typically, bubble sort is n^2 because for each number, there may be up to n swaps needed. But in this case, for any number, there are at most k swaps needed, so the complexity for bubble sort in this case should be o(kn), or o(n), since k is constant.

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

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.