Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

1) I see lots of correct solutions for the binary search algorithm so I won't elaborate further.

2) The most effective solution here is not to rotate M times, each of those rotations is O(M), so your worst case complexity is O(N^2) (as M can approach N/2 if you pick the shorter direction to rotate in).

Reversing an array in place can be done in O(N). A better solution is to reverse the half of the string before and after the pivot. and then reverse the entire string. O(N)!

Example: [ 4 7 9 9 12 1 2] -> [ 12 9 9 7 4 2 1 ] -> [1 2 4 7 9 9 12]

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

def bsr(a, left=None, right=None):
    if left == None:
        left = 0
    if right == None:
        right = len(a)-1
    if len(a) == 0:
        return -1
    mid = (left + right) //2
    if a[mid] >= a[mid+1]:
        return mid
    if a[left] > a[mid]:
        return bsr(a, left, mid)
    elif a[mid] > a[right]:
        return bsr(a, mid, right)
    else: #left <= mid <= right
        return right

a = [3, 4, 5, 6, 7, 1]
print bsr(a)

new = a*2
print new[bsr(a)+1:len(a)+bsr(a)+1]

- aaa June 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
2
of 2 votes

Just a small suggestion that when you do this

mid = (left + right) //2

, then it might throw an overflow exception. the correct way is to

mid = left  + (right - left)/2;

- madhur.eng June 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

def bsr(a, left=None, right=None):
    if left == None:
        left = 0
    if right == None:
        right = len(a)-1
    if len(a) == 0:
        return -1
    mid = (left + right) //2
    if a[mid] >= a[mid+1]:
        return mid
    if a[left] > a[mid]:
        return bsr(a, left, mid)
    elif a[mid] > a[right]:
        return bsr(a, mid, right)
    else: #left <= mid <= right
        return right

a = [3, 4, 5, 6, 7, 1]
print bsr(a)

new = a*2
print new[bsr(a)+1:len(a)+bsr(a)+1]

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

Use binary search.
Divide the array into 2 halves. Check the leftmost and rightmost item in both halves.
If left > right, then the peak is in that half. Then take it and do the same recursively.
Binary search is O(log(n))

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

1.
If peak means highest element than we can find it with the help of smallest element. Just find out index of smallest element - say it is i, if i is greater than 0, than i-1, will be the largest element otherwise last element from the array will be largest element. Here is code for that:

public static int search(int A[]) {
		int N = A.length;
		int L = 0;
		int R = N - 1;
		while (A[L] > A[R]) {
			int M = L + (R - L) / 2;
			if (A[M] > A[R])
				L = M + 1;
			else
				R = M;
		}
		if(L == 0){
			return N-1;
		}else{
			return L-1;
		}

	}

2. To rearrange the array in to original shape we will use following property of rotation :
After X rotation array[i] will move to array[(i + X) % arrayLength]

So if we rotate an array of size N, by N times (or say X==N), than array did not change, or it will remain in sorted order.

So just rotate it by (N-X) time to get original array.

- Ajeet June 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Your answer to 2 is O(n^2). There is an O(n) solution.

- yaronbic October 05, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

public static int findPeek(int[] arr) {

		if (arr[0] < arr[arr.length - 1])
			return -1;

		int lo = 0;
		int hi = arr.length - 1;

		return findPeek(arr, lo, hi);
	}

	private static int findPeek(int[] arr, int lo, int hi) {

		if (lo > hi)
			return -1;

		int mid = (lo + hi) / 2;

		if (mid != hi && arr[mid] > arr[mid + 1])
			return mid + 1;

		if (arr[lo] > arr[mid]) {
			return findPeek(arr, lo, mid);
		} else {
			return findPeek(arr, mid + 1, hi);
		}

	}

	public static void rearrange(int[] arr) {
		int peek = findPeek(arr);
		if (peek == -1) {
			return;
		}

		int[] aux = new int[arr.length];
		for (int i = 0; i < aux.length; i++) {
			aux[i] = arr[i];
		}

		int pos = 0;
		for (int i = peek; i < aux.length; i++) {
			arr[pos++] = aux[i];
		}
		for (int i = 0; i < peek; i++) {
			arr[pos++] = aux[i];
		}

	}

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

//write  a program to find the index of peak value in an rotated sorted array 
public static void main( String args[]){
  //consider an int array sorted ascending 
  //and rotated n times 
  // so there are total n elements out of order 
  // look for them 
  
  for(int i = 0 ; i < inputarray.Length ; i++) {
   if inputarray[i] > inputarray[i+1] {
       Count++; // this is count index that keeps the track of no of 
                       // rotations if not given, this must be a peak too
       }
       }
      //print peak 
       System.Console.Writeln("index of peak is {0} and peak value is {1}",Count,inputarray[Count]);
       
  
  //problem 2: sort them back
  //to start we need not move the values etc., we can just shift the positions
  
  int endPosition = Count; 
  int startPosition  =  ++Count;
  // now if you still want to shift them from index 0 to  Length -1 , 
 // then the most efficient way processing time is to shift each elements from i to i-n and   //keep count2 = n-1 until the count2 == 0 
}

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

Is this a trick question? If N is given (number of time rotation done to sorted array), why can't i just access the element at a[Length-1 - (n % length)] assuming it was left rotation
or a[(Length-1 + (n % length)) % length] if it was right rotation

Other answers apply if n is unknown.
Start from mid of the array.
Check both sides of array
if both array first element <= last element, this is the answer
otherwise move towards the array where first element > last element

- pc June 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Exactly !!

- Anonymous June 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

N must be unknown or this is trivial.

- Dave June 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

1.) I suppose we could reuse the n that's given to find the peak
right rotation: peak = n - 1;
left rotation: peak = len - n - 1;

2.) To rearrange the numbers we have to rotate len - n times. Here is the code done using the 3 times reversearr method.

It seems to be working fine, let me know if there are any issues.

static int findPeak(int[] arr, int rotated) {
		int len = arr.length;
		
		if(len < 1) {
			return -1;
		}
		
		if(rotated == 0)
			return arr[len-1];
		else 
			return arr[rotated - 1]; //for left rotation its len - rotated - 1
			
	}
	
	
	static void rearrangeArr(int[] arr, int rotated) {
		int len = arr.length;
		int originalArr = len - rotated;
		
		reverseArr(arr, 0, len - 1);
		reverseArr(arr, 0, originalArr - 1);
		reverseArr(arr, originalArr, len - 1);
		
		
		for(int i=0; i < len; i++) {
			System.out.println(arr[i]);
		}
	}
	
	static void reverseArr(int[] arr, int i, int j) {
		while(i<j) {
			arr[i] ^= arr[j];
			arr[j] ^= arr[i];
			arr[i] ^= arr[j];	
			i++;
			j--;
		}
	}

- Killbill June 03, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

The complexity to rotate the array is O(2N) which is O(N) in the above method

- Killbill June 03, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

a. To find the peak element index:
The largest element in an array is always a peak. Thus the last element of a sorted array is a peak and remains a peak after any number of rotations.
After n rotations in an array of length L, an element at position i goes to (i - n%L) th position. Here i = L. Ans: i-n%i given n.

public int find_peak(int A[], int n){
        //A is a sorted array which had n rotations after that
        //return an index of a peak element in this rotated array
        //O(1)
        int len = A.length;
        return len - (n%len);
    }

b. To get the sorted array back/removing the rotation
Solution 1: Rotate in the opposite direction n number of times
Solution 2: find the offset where the rotation has taken the first element of original array.
Copy from the offset to end and then from the start to offset - 1 into a new array.

public int[] unrotate(int A[], int n){
        //retrieve the original array from the input of array after n rotations
        //O(n)
        int offset;
        offset = A.length - n;
        
        int[] result = new int[A.length];
        int index = 0;
        
        for(int i = offset; i<A.length; i++){
            result[index++] = A[i];
        }
        for(int i=0; i<offset; i++){
            result[index++] = A[i];
        }
       return result; 
        
    }

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

if the array was in increasing order and is rotated N times,then would n't the last(largest element) will be always the peak so the last element will be (a[size-1+N]%size) after N rotations.What's the need of binary search here????????

it will be very nice if anyone could explain.......

- keshav farmaha June 04, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*Question : Given an array and is rotated n number of times find the number where the peak happens. 
*The array is sorted in increasing order. 
*Follow up question: How will you rearrange them in normal sorted order.
*/

var array = [3, 4, 5, 6, 1, 2];

/*find the peak when given an sorted array and number of rotations
 *@param a Array
 *@param n integer
 */
var findPeak = function (a, n) {
    //    debugger;
    if (a.length === 1 || (a.length !== 0 || n == 0) {
        return a[a.length - 1];
    } else if (a.length > 1) {
        var peakLocLeftShift = a[a.length - ((n % a.length) + 1)];
        var index = (n % a.length) - 1;
        if (index === undefined || index < 0) index = 0;
        var peakLocRightShift = a[index];
        if (peakLocLeftShift > peakLocRightShift) {
            return peakLocLeftShift;
        } else {
            return peakLocRightShift;
        }
    } else {
        throw "Array is empty";
    }
};

//rearranges the array
var rearrangeArray = function (a, n) {
    try {
        if (a.length < 2) {
            return a;
        }
        debugger;
        var highest = findPeak(a, n);
        var oIndex = a.indexOf(highest);
        var part1 = a.slice(oIndex + 1, a.length);
        var part2 = a.slice(0, oIndex + 1);
        var result = part1;
        for (var i = 0; i < part2.length; i++) {
            result.push(part2[i]);
        }
        return result;
    } catch (e) {
        console.log(e.message);
    }
};

- undefined June 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/*Question : Given an array and is rotated n number of times find the number where the peak happens. 
*The array is sorted in increasing order. 
*Follow up question: How will you rearrange them in normal sorted order.
*/

var array = [3, 4, 5, 6, 1, 2];

/*find the peak when given an sorted array and number of rotations
 *@param a Array
 *@param n integer
 */
var findPeak = function (a, n) {
    //    debugger;
    if (a.length === 1 || (a.length !== 0 || n == 0) {
        return a[a.length - 1];
    } else if (a.length > 1) {
        var peakLocLeftShift = a[a.length - ((n % a.length) + 1)];
        var index = (n % a.length) - 1;
        if (index === undefined || index < 0) index = 0;
        var peakLocRightShift = a[index];
        if (peakLocLeftShift > peakLocRightShift) {
            return peakLocLeftShift;
        } else {
            return peakLocRightShift;
        }
    } else {
        throw "Array is empty";
    }
};

//rearranges the array
var rearrangeArray = function (a, n) {
    try {
        if (a.length < 2) {
            return a;
        }
        debugger;
        var highest = findPeak(a, n);
        var oIndex = a.indexOf(highest);
        var part1 = a.slice(oIndex + 1, a.length);
        var part2 = a.slice(0, oIndex + 1);
        var result = part1;
        for (var i = 0; i < part2.length; i++) {
            result.push(part2[i]);
        }
        return result;
    } catch (e) {
        console.log(e.message);
    }
};

- Sunil B N June 07, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

This is my implementation in C#, similar to other already post. To find the peak the problem don't specify the rotation orientation (left or right) so we need to handle that case. The re-arrange is in place and has a O(N)

// Returns the index of the peak
public int FindPeak(int[] a, int n)
{
	n = n % a.Length;
	if (n == 0)
		return a.Length - 1;

	int length = a.Length;
	return (a[n - 1] > a[n]) ? n - 1 : length - n - 1;
}

public void Rearrange(int[] a, int n)
{
	int peakIndex = FindPeak(a, n);
	if (peakIndex == a.Length - 1)
		return;

	SwapValues(a, 0, peakIndex);
	SwapValues(a, peakIndex + 1, a.Length - 1);
	SwapValues(a, 0, a.Length - 1);
}

private void SwapValues(int[] a, int start, int end)
{
	while (start < end)
	{
		int tmp = a[start];
		a[start] = a[end];
		a[end] = tmp;

		start++;
		end--;
	}
}

- hnatsu June 09, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Do the normal BS, but to decide in which partition one should go, use the A[i] and A[j] value and campare it with A[q], 
if A[q] > A[i] then go to g<=>j 
else if a[q] < a[i] and a[q] < a[j] then go to i<=>q
else return q only

- sonesh June 15, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

BTW once you have found 1, all you have to do is to reverse the array 3 times,
First reverse 1 to q array, then reverse q+1 to n array, then reverse 1 to n array.

complexity is O(N) only

- sonesh June 15, 2015 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

Similar to binary search but had to change the return condition and when setting high and low, they're set to mid rather than mid-1/mid+1.

int binarySearchForPivot(vector<int> &data) {
  size_t low = 0;
  size_t high = data.size()-1;
  size_t mid;

  while (low<=high) {
    mid = low + (high-low)/2;
    if (data[mid]>data[mid+1]){
      return mid;
    }
    if (data[low]>data[mid])
      high = mid;
    else if (data[mid]>data[high])
      low = mid;
    else
      return -1;
  }
  return mid;
}

- thewhatwhat July 06, 2015 | 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