Google Interview Question
Software DevelopersCountry: United States
Interview Type: In-Person
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.
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;
}
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;
}
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));
}
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));
}
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));
}
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));
}
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));
}
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));
}
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));
}
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));
}
)))
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;
}
}
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
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
- 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)
- 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)
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
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;
}
}
}
}
}
* 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;
}
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.
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.
O(n*log(k)) time.
- emb June 01, 2016