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

- Anonymous March 31, 2016 | Flag Reply
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.

- smallchallenges March 31, 2016 | Flag Reply
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.

- Naz20 March 31, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Merge K sort. Use heap.

- Anonymous March 31, 2016 | Flag Reply
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

- EPavlova April 01, 2016 | Flag Reply
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)

- Mustafa April 01, 2016 | Flag Reply
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.

- nghi1129 April 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

hi

- Anonymous April 01, 2016 | Flag Reply
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

- Anonymous April 01, 2016 | Flag Reply
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.

- Anonymous April 08, 2016 | Flag Reply
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)

- Shakti Papdeja April 15, 2016 | Flag Reply
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()
{
    {
        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}));
    }
}

- peter tang April 28, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Insertion sort gives O(nk) running time.

- Anonymous July 20, 2016 | Flag Reply
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

- Anonymous April 01, 2016 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More