Google Interview Question
Developer Program EngineersCountry: United States
Interview Type: Phone Interview
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)
@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.
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
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()
{
{
LinkedList<int> input;
LinkedList<int> result;
input.PushBack(1);
MergeXwaySortedLL(input, 1, result);
LinkedListElement<int> *head = *(result.Release());
LinkedListElement<int> *tail = *(result.ReleaseTail());
assert(head->data == 1);
assert(tail->data == 1);
}
{
LinkedList<int> input;
LinkedList<int> result;
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);
LinkedListElement<int> *curNode = *(result.Release());
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}));
}
}
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
To sort it way you have to build a heap and maintain its size to be always = x
- Anonymous March 31, 20161- 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