Google Interview Question for Software Developers


Country: United States
Interview Type: In-Person




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

Alright, here goes my stream of consciousness - that's how I solved this problem, full thought process.

So say, we have a permutation of length N. We know that permutation of length N can be represented by storing a number for each position "count of numbers bigger than current on the left of it" - for example
3 2 1
For 3 this number will be 0
For 2 this number will be 1 (becaue 3 is on the left of it)
For 1 this number will be 2 (because 3 and 2 are on its left).
It can be proven that (0, 1, 2) uniquely represents a permutation (3 2 1).
It's also easy to see that sum of (0, 1, 2) will give us a number of inversions.

Alright, suppose for some element i, the count of elements greater than it on the left is a. We can see that we can only decrease a by k - by moving elements larger than i from the left to the right of it (each time element i will move one position left).
Also consider this: for largest element this value will be 0, so we can't decrease it, for second largest - either 0 or 1, for third largest - either 0 or 1 or 2.
So we could decrease the inversions count by this number: (n - 1) + (n - 2) + ... + (n - k). Suppose k = n - 1, then this number will be 1 + ... + (n - 1) = n*(n-1)/2 which is maximum number of inversions in array (this means, if k = n - 1, we can sort it).

So how could we sort the array now? Simply take a permutation, rewrite it in the "count of bigger elements on the left" form, then subtract (n-1)+(n-2)+...+(n - k) from values (if you stop earlier, don't worry you've just sorted whole array) and then restore the permutation.

Let's take an insertion sort that moves values only by k to the left. Let's prove that it's correct.

def limited_insertion_sort(arr, k):
    arr = list(arr)
    for last_sorted in xrange(1, len(arr)):
        new_elem = arr[last_sorted]
        insertion_point = last_sorted
        while insertion_point > max(0, last_sorted - k) and arr[insertion_point - 1] > new_elem:
            arr[insertion_point] = arr[insertion_point - 1]
            insertion_point -= 1
        arr[insertion_point] = new_elem
    return arr

arr = [4,3,2,1]
assert limited_insertion_sort(arr, 2) == [2, 1, 3, 4]
assert limited_insertion_sort(arr, 1) == [3, 2, 1, 4]

Time O(n*k)
After first k steps first k+1 elements will be sorted. Let's call this "top". At each moment
this "top" will contain top k elements.
Clearly: suppose the next element is bigger than everything in the "top". Then it will just
land at the head of the "top".
Suppose it's smaller than "top"-s k elements. Then it will land at the tail of the top (because element can move k positions left).
Otherwise, the element will land somewhere in the middle of the top and the smallest element will get evicted.
This means that every element will be able to decrease its inversion count by k (of course, after taking into consideration it's limit on maximum inversions), so insertion sort is the same as the permutation converting algorithm in the beginning.

However, we can do better - there is a data structure suitable for keeping top k elements and evicting smallest, named heap.

def limited_top_keeper_sort(arr, k):
    # python doesn't allow us to heapify subarray
    # but in c++ this is possible, so I'll use a separate
    # array for simplicity.
    result = []
    topk = []
    for i in xrange(min(len(arr), k)):
        topk.append(arr[i])

    if len(arr) > k:
        heapq.heapify(topk)
        for i in xrange(min(len(arr), k), len(arr)):
            result.append(heapq.heappushpop(topk, arr[i]))

    result.extend(sorted(topk))

    return result

assert limited_top_keeper_sort(arr, 2) == [2, 1, 3, 4]
assert limited_top_keeper_sort(arr, 1) == [3, 2, 1, 4]

O(n*log(k)) time.

- emb June 01, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

That's a good approach. I'm only not sure about max heap structure.
As far as I understand, it's not a regular max heap, but some special heap. It supports HeapPushPop operation, meaning that when we push a new element to the heap, it automatically pops min element. I'm not sure it's still logK complexity for such operation for a regular max heap.
However, we can use balanced binary search tree of size K, for instance:
- find min - O(LogK) (worst), O(1) (average, with min tracking)
- remove element - O(LogK)
- insert element - O(LogK)
So, the same O(LogK) complexity for required operations and O(N*LogK) overall complexity.

- Alex M. April 26, 2017 | Flag
Comment hidden because of low score. Click to expand.
1
of 1 vote

assumtion #1: "sortedness" is kind of vague. i'm going to define it as the number of disordered pairs, ie:
sortedness(1,2,3) = 0
sortedness(3,1,2) = 1

assumption #2: can each element move left k times (and if so, is it the index location that can be moved k times, or the value contained there?), or can all elements combined move left k times? I assumed the latter. If its the former, instead of passing around a single int k parameter, we would pass around a hashmap<integer, integer> that we initialize for every element with value k, and decrease as we move that element. This would not make much sense for an array that contains duplicate values

My approach goes through each element and attempts to swap left from 1..k times. Each new ordering needs an o(n) check for sortedness, so this will run in o(k*n^2) if we cache values.

I used a global variable for the result, which isn't great style. Better solution would be to write a wrapper class to return, or pass as recursive method parameters (a little more icky).

int bestSortValue = Integer.MAX_VALUE;
    int[] bestSortedArray = null;
    
    public int[] kSort(int[] input, int k){
    	if(input.length==0 || input.length==1) return input;
    	kSortH(input, k);
	return bestSortedArray;
    }
    
    //recursive helper
    private void kSortH(int[] input, int k){
    	//base case 1 - we've already found the best sort
    	if(bestSortValue==0) return;	
    
    	int curSortVal = checkSortDistance(input);
    	//base case 2, current array is sorted
    	if (curSortVal==0){
    		bestSortValue = 0;
    		bestSortedArray = input.clone();
    		return;
    	} 
    
    	//check if current distance is best distance
    	if(curSortVal < bestSortValue){
    		bestSortValue = curSortVal;
    		bestSortedArray = input.clone();
    	}
    	
    	//insert cache value here (key is [input,k])
    
    	for(int i=1; i< input.length; i++){
    		for(int j=1; (i-j)>=0 && j<=k; j++){
    		    //Insert cache check here
                input = swapArr(input, i, j);
    			kSortH(input, k-j);
    		}
    	}
    }
    
    //swap index x and y values
    private int[] swapArr(int[] input, int i, int j){
    	int temp = input[j];
	    input[j] = input[i];
	    input[i] = temp;
	    return input;
    }
    
    
    //a 0 sort distance means the array is sorted properly
    private int checkSortDistance(int[] input){
    	if(input.length==1) return 0;
    	int count = 0;
    	for(int i=0; i<input.length-1; i++){
    		if(input[i] > input[i+1]) count++;
    	}
    	return count;
    }

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

This question is pretty vague - what does more or less sorted mean?

I'm going to quantify "sorted-ness" by the number of unordered pairs. ie:
sortedness(1,2,3)=0
sortedness(3,1,2)=1
sortedness(1,3,2)=1

My strategy is to iterate through the array, and for each index, attempt to swap the value left from 1...k times, to generate a new ordering. For each new order we create, we call "checkSortDistance()" which returns a count for each element that is out of order in o(n).
We can use recursion, and cache our results to prevent repetitive calculations. I believe this approach will run in o(k*n^2)

int bestSortValue = Integer.MAX_VALUE;
    int[] bestSortedArray = null;

    public int[] kSort(int[] input, int k){
	//base case: already sorted
    	if(input.length==0 || input.length==1) return input;
    	kSortH(input, k);
	return bestSortedArray;
    }
    
    //recursive helper
    private void kSortH(int[] input, int k){
    	//base case 1 - we've already found the best sort
    	if(bestSortValue==0) return;	
    
    	int curSortVal = checkSortDistance(input);
    	//base case 2, current array is sorted
    	if (curSortVal==0){
    		bestSortValue = 0;
    		bestSortedArray = input.clone();
    		return;
    	} 
    
    	//check if current distance is best distance
    	if(curSortVal < bestSortValue){
    		bestSortValue = curSortVal;
    		bestSortedArray = input.clone();
    	}
    	
    	//insert cache value here (key is [input,k])
    
    	for(int i=1; i< input.length; i++){
    		for(int j=1; (i-j)>=0 && j<=k; j++){
    		    //Insert cache check here
                input = swapArr(input, i, j);
    			kSortH(input, k-j);
    		}
    	}
    }
    
    //swap index x and y values
    private int[] swapArr(int[] input, int i, int j){
    	int temp = input[j];
	    input[j] = input[i];
	    input[i] = temp;
	    return input;
    }
    
    
    //a 0 sort distance means the array is sorted properly
    private int checkSortDistance(int[] input){
    	if(input.length==1) return 0;
    	int count = 0;
    	for(int i=0; i<input.length-1; i++){
    		if(input[i] > input[i+1]) count++;
    	}
    	return count;
    }

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

I think we can do this with bubblesort with O(nk):
The outer loop will run for K times. So only the smallest integer would be shifted a maximum of k times to the left.
int temp;
for(int i=0; i < k; i++){

for(int j=1; j < arr.length-i; j++){
if(arr[j-1] > arr[j]){
temp=arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
System.out.println((i+1)+"th iteration result: "+Arrays.toString(arr));
}

- subzero740 June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

We can do this with a bubble sort. The outer loop will run for k times with O(nk). The smallest integer would be shifted k times to the left.

int temp;
for(int i=0; i < k; i++){

for(int j=1; j < arr.length-i; j++){
if(arr[j-1] > arr[j]){
temp=arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
System.out.println((i+1)+"th iteration result: "+Arrays.toString(arr));
}

- subzero740 June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A bubble sort can be used here. The outer loop will run for K times with O(nk). The smallest integer is the only which would get shifted to left for K times. other integers would be shifted to left for less then K times.

int temp;
        for(int i=0; i <k; i++){
 
            for(int j=1; j < arr.length-i; j++){
                if(arr[j-1] > arr[j]){
                    temp=arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println((i+1)+"th iteration result: "+Arrays.toString(arr));
        }

- subzero740 June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A bubble sort can be used here. The outer loop will run for K times with O(nk). The smallest integer is the only which would get shifted to left for K times. other integers would be shifted to left for less then K times.

int temp;
        for(int i=0; i <k; i++){
 
            for(int j=1; j < arr.length-i; j++){
                if(arr[j-1] > arr[j]){
                    temp=arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println((i+1)+"th iteration result: "+Arrays.toString(arr));
        }

- subzero740 June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A bubble sort can be used here. The outer loop will run for K times with O(nk). The smallest integer is the only which would get shifted to left for K times. other integers would be shifted to left for less then K times.

	int temp;
        for(int i=0; i <k; i++){
 
            for(int j=1; j < arr.length-i; j++){
                if(arr[j-1] > arr[j]){
                    temp=arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println((i+1)+"th iteration result: "+Arrays.toString(arr));
        }

- subzero740 June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A bubble sort can be used here. The outer loop will run for K times with O(nk). The smallest integer is the only which would get shifted to left for K times. other integers would be shifted to left for less then K times.

int temp;
        for(int i=0; i < arr.length-1; i++){
 
            for(int j=1; j < arr.length-i; j++){
                if(arr[j-1] > arr[j]){
                    temp=arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println((i+1)+"th iteration result: "+Arrays.toString(arr));

}

- subzero740 June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A bubble sort can be used here. The outer loop will run for K times with O(nk). The smallest integer is the only which would get shifted to left for K times. other integers would be shifted to left for less then K times.

int temp;
        for(int i=0; i < k; i++){
 
            for(int j=1; j < arr.length-i; j++){
                if(arr[j-1] > arr[j]){
                    temp=arr[j-1];
                    arr[j-1] = arr[j];
                    arr[j] = temp;
                }
            }
            System.out.println((i+1)+"th iteration result: "+Arrays.toString(arr));
        }

- subzero740 June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int temp

- Anonymous June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A bubble sort can be used here. The outer loop will run for K times with O(nk). The smallest integer is the only which would get shifted to left for K times. other integers would be shifted to left for less then K times.

(((

int temp;
for(int i=0; i < k; i++){

for(int j=1; j < arr.length-i; j++){
if(arr[j-1] > arr[j]){
temp=arr[j-1];
arr[j-1] = arr[j];
arr[j] = temp;
}
}
System.out.println((i+1)+"th iteration result: "+Arrays.toString(arr));
}
)))

- subzero740 June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

I'll be really happy to hear any comments on this. I'm using merge sort. The only exception is that when merging I make sure not to move an element from the right to the left by more than k.

struct Node
{
	int idx;
	int val;

	Node(int i, int v) :idx(i), val(v){}

	friend bool operator<=(Node &N1, Node &N2){ return N1.val < N2.val || N1.val == N2.val; }
};


void Merge(vector<Node> &ToSort, int s1, int e1, int s2, int e2, int k)
{
	int start1 = s1;
	int end1 = e1;
	int start2 = s2;
	int end2 = e2;

	vector<Node> Res;

	while (start1 < end1 && start2 < end2)
	{
		if (ToSort[start1] <= ToSort[start2])
		{
			Res.push_back(ToSort[start1]);
			start1++;
		}
		else
		{
			if (ToSort[start2].idx - start1 <= k)
			{
				Res.push_back(ToSort[start2]);
				start2++;
			}
			else
			{
				Res.push_back(ToSort[start1]);
				start1++;
			}
		}
	}

	while (start1 < end1)
	{
		Res.push_back(ToSort[start1]);
		start1++;
	}

	while (start2 < end2)
	{
		Res.push_back(ToSort[start2]);
		start2++;
	}

	for (int i = s1; i < e2; ++i)
	{
		ToSort[i] = Res[i - s1];
	}
}


void MSort(vector<Node> &ToSort, int s, int e, int k)
{
	if (s == e || s == e - 1)
	{
		return;
	}

	int Med = s + (e - s) / 2;
	MSort(ToSort, s, Med, k);
	MSort(ToSort, Med, e, k);
	Merge(ToSort, s, Med, Med, e, k);
}


void SpecialSort(vector<int> & Arr, int k)
{
	vector<Node> ToSort;

	for (int i = 0; i < Arr.size(); ++i)
	{
		ToSort.push_back(Node(i, Arr[i]));
	}

	MSort(ToSort, 0, ToSort.size(),k);

	for (int i = 0; i < ToSort.size(); ++i)
	{
		Arr[i] = ToSort[i].val;
	}
}

- Guy June 02, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

How is this question different then traditional insertion sort ?? In my opinion, it is a straight advanced usage of insertion sort. Here is my also.

1> For each K elements, use counter counting the number of occurrences of each one of em among N elements. So, its like 1 occurred 20 times, 5 occurred 3 time and so on.

2> Now, apply insertion sort, for each element, you pick, and insert in sorted array, insert whole list of occurrences in it. Example, if we encounter 1, we insert 20 ones. in the sorted array.

3> For rearrangement, as you can any number of right hand space, we dont need to bother and for left hand movement , it never goes above k number of swaps. Infact, we can even optimise to lower value.

Time Complexity :- O(n) + Insertion Sort Time
Space :- K number of each element counter

- hprem991 June 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Start with k leftmost elements of the array as they cannot be move beyond k steps to the left & full fill the requirement of the question. Sort the k elements. Now move to the right one element at a time. If the current element is less than the current minimum in the k window make the current element the current minimum & keep the k-window sorted. Time Complexity should be (n-k)*k+klogk

- Anonymous June 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- insertion/bubble sort short should be used, as there algorithms are not optimized when N is a very high number.

solution
- use quick sort

- startIndex = 0, endIndex = k-1
- A -> store how many position moved left or right for a given number. Initially it will store "0" for all number. +x value for a given number means that number moved left by x, -y means number moved right by y

1. sort from startIndex to endIndex using quick sort

2. In Array A - if number move by x in left store x for that number & if number move y towards right then store -y (-ve y) for that number , always make sure x <= k
this array will be utilized to maintain rule "no element travels more than k positions to its left an element however can travel as much as it likes to its right."

3. startIndex = startIndex+1, endIndex = endIndex+1

repeat step-1, 2 & 3 until endIndex < (size of the input array)

- Anonymous June 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

- insertion/bubble sort short should be used, as there algorithms are not optimized when N is a very high number.

solution
- use quick sort

- startIndex = 0, endIndex = k-1
- A -> store how many position moved left or right for a given number. Initially it will store "0" for all number. +x value for a given number means that number moved left by x, -y means number moved right by y

1. sort from startIndex to endIndex using quick sort

2. In Array A - if number move by x in left store x for that number & if number move y towards right then store -y (-ve y) for that number , always make sure x <= k
this array will be utilized to maintain rule "no element travels more than k positions to its left an element however can travel as much as it likes to its right."

3. startIndex = startIndex+1, endIndex = endIndex+1

repeat step-1, 2 & 3 until endIndex < (size of the input array)

- Anonymous June 03, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

@Mukesh How do you gurantee that no element will not move more then k times to left.

- eshan740 June 13, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class EnumKBitSet {
	char[] ch=null;
	public void enumKBitSet(int K)
	{
		ch = new char[K];
		for (int i=0; i < ch.length; i++) ch[i]='0';
		for (int k =0; k <= ch.length ; k++)
			enumKBit(k, ch, ch.length);
	}
	private void enumKBit(int k, char[] ch, int pos)
	{
		int n = ch.length-1;
		if (k==0) 
		{
			System.out.print(new String(ch)+" ");
			return;
		} // n = 2, k = 1, pos=2, 
		for (int p=n-(k-1); p > n-pos; p--)
		{
			ch[p]='1';
			enumKBit(k-1, ch, n-p);
			ch[p]='0';
		}
	}
	public static void main(String argv[])
	{
		EnumKBitSet ekbs = new EnumKBitSet();
		ekbs.enumKBitSet(4);
	}
}
// k = 3
// 000, 001, 010, 100, 011, 101, 110, 
// k = 4
// 0000 0001 0010 0100 1000 0011 0101 0110 1001 1010 1100 0111 1011 1101 1110 1111

- Robert June 21, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class Solution {

    public static void main(String [] args) {

        int [] array = {20,4,3,2,1,7,8,0};

        System.out.println(Arrays.toString(array));

        sort(array, 2);

        System.out.println(Arrays.toString(array));


        int [] array1 = {5,40,20,4,3,2,1,7,8,0};

        System.out.println(Arrays.toString(array1));

        sortOptimized(array1, 3);

        System.out.println(Arrays.toString(array1));

    }

    public static void sortOptimized(int [] array, int k) {

        PriorityQueue<Integer> priorityQueue = new PriorityQueue<>(k+1);

        for (int i = 0; i <= k; i++) {
            priorityQueue.add(array[i]);
        }

        int index = 0;
        for (int i = k+1; i < array.length; i++) {
            array[index++] = priorityQueue.poll();
            priorityQueue.add(array[i]);
        }

        while (!priorityQueue.isEmpty()) {
            array[index++] = priorityQueue.poll();
        }

    }

    public static void sort(int [] array, int k) {

        for (int i = 0; i < k; i++) {
            for (int j = 0; j < array.length - i - 1; j++) {
                if (array[j+1] < array[j]) {
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }

}

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

def special_insertion_sort(arr, k):
    for i in xrange(1, len(arr)):
        cur = arr[i]
        j = i - 1
        while j >= max(0, i - k) and cur < arr[j]:
            arr[j+1] = arr[j]
            j -= 1
        arr[j+1] = cur

arr = [4,3,2,1]
special_insertion_sort(arr, 2)

- Nitish Garg January 15, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

* Create a min-heap, also storing original location of each element. Min-heap is a data structure, which stores minimum element at top, insertion/removal complexity is log(n).
* Pop elements one by one, if their new index differs more than k from original, push them to end, otherwise push them in sorted array.
* Time complexity: O(n * log(n)), Space: O(n)

tuple t;
for (i = 0; i < n; i++) {
	t.n = a[i];
	t.pos = i;
	min-heap.insert(t);
}

start = 0, end = n - 1;
for (i = 0; i < n; i++) {
	t = min-heap.pop();
	if (start + k > t.pos)
		a[start++] = t.n;
	else
		a[end--] = t.n;	
}

- Mukesh June 05, 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