## Google Interview Question for Developer Program Engineers

Country: United States
Interview Type: Phone Interview

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

To sort it way you have to build a heap and maintain its size to be always = x
1- start by adding x elements to the queue
2- Each time you encounter a new element remove the head of the heap (Min element) and append it to the result(This element must be the smallest element in the stream)
3- Add the new element and continue

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

Assuming ascending sort criterion, how about we create a heap of x elements and insert the first x list elements. Since the list sorting is off by x elements, the smallest should be in the heap. Then keep adding one additional element to the heap and extract the next min element.

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

We can consider x sorted lists, and do a merge to combine these x lists to find the final sorted list L.

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

Merge K sort. Use heap.

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

First we add 2*x elements to priority queue and take first x elements - these are first x sorted elements. Then we add next block of x elements and do the same till the end of the list

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

1. Find the minimum element starting from 1 to x elements of list and swap it with first element of the list
2. Find the minimum element starting from 2 to x +1 and swap it with 2nd element of the list and continue the similar process until (n - step) times, where n is length of list.

``````def my_min_index(part_list):
min_index = 0
n = len(part_list)
i = 1
print(part_list, n)
while i < n:
if part_list[i] < part_list[min_index]:
min_index = i
i += 1
return min_index

def x_sorted(input_list, step):
print("Unsorted list : {0}".format(input_list))
i = 0
n = len(input_list)
while i <= ((n - step) + 1):
cur_min_index = i + my_min_index(input_list[i:i+step])
print(cur_min_index, input_list[cur_min_index])
input_list[i], input_list[cur_min_index] = input_list[cur_min_index], input_list[i]
i += 1
print(input_list)
print("Sorted list : {0}".format(input_list))
return input_list

x = [2,3,1,7,8,4,5,9,6]
x_sorted(x, 3)``````

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

@Naz20 - Yep, totally agreed. This is basically right in the middle of a merge-sort operation. At the base of the recursion of merge sorts, you have L.length lists of size 1, and as they merge, somewhere up the recursion tree you have x sorted lists of size L.length / x. When x == 1 (top of recursion tree), you have L fully sorted.

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

hi

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

Hello,
I appreciate ur solution but I think this wouldn't work, inf act it is not supporting the presorted condition in the problem. The input which you have taken is not presorted by x terms. See the below example Input..

Input List: 5 1 10 15 2 11 20...so on...and x=3
see the sorted sublists are: 5 15 20 and 1 2 and 10 11...

Thanks

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

Use a min-heap. add first x elements to the heap. then,

1. pick out smallest element, find it's index i by parsing elements in L from 0..x-1
2. if (i+x) < len(L) add L[i+x] to the min heap. go to step 1
3. else do nothing, go back to step 1.

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

Use min heap, with x+1 elements,
1. add x+1 elements into heap
2. remove element from heap, and add the next element from input array, if available
3. repeat the process of step 2 till heap has more elements.
4. Complexity is O(xlogx)

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

Two approaches are proposed. The basic idea is similar as merging sorted list. Here we have X sorted list.
Details: cpluspluslearning-petert.blogspot.co.uk/2016/04/merge-x-way-sorted-list.html
Test

``````void Test_LL()
{
{
input.PushBack(1);
MergeXwaySortedLL(input, 1, result);
assert(tail->data == 1);
}

{
const std::array<int, 16> data = { 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15 };
for (auto iter = data.begin(); iter != data.end(); ++iter) {
input.PushBack(*iter);
}

MergeXwaySortedLL(input, 4, result);
unsigned int count = 0;
while (curNode) {
assert(curNode->data == count);
curNode = curNode->next;
++count;
}

assert(count == 16);
}
}

void Test_Arr()
{
{
const std::vector<int> data = { 1, 3, 2, 4 };
std::vector<int> result = MergeXwaySortedArr(data, 5);
assert(result.empty() == true);
result = MergeXwaySortedArr(data, 2);
assert(result == std::vector<int>({ 1, 2, 3, 4 }));
}

{
const std::vector<int> data = { 0, 4, 8, 12, 1, 5, 9, 13, 2, 6, 10, 14, 3, 7, 11, 15 };
std::vector<int> result = MergeXwaySortedArr(data, 17);
assert(result.empty() == true);
result = MergeXwaySortedArr(data, 4);
assert(result == std::vector<int>({0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15}));
}
}``````

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

Insertion sort gives O(nk) running time.

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

Hello,
I appreciate ur solution but I think this wouldn't work, inf act it is not supporting the presorted condition in the problem. The input which you have taken is not presorted by x terms. See the below example Input..

Input List: 5 1 10 15 2 11 20...so on...and x=3
see the sorted sublists are: 5 15 20 and 1 2 and 10 11...

Thanks

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.