## Google Interview Question for Software Engineers

• 2

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]

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]``````

Comment hidden because of low score. Click to expand.
2

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;``

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]``````

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))

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.

Comment hidden because of low score. Click to expand.
0

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];
}

}``````

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
}``````

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

Comment hidden because of low score. Click to expand.
0

Exactly !!

Comment hidden because of low score. Click to expand.
0

N must be unknown or this is trivial.

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--;
}
}``````

Comment hidden because of low score. Click to expand.
0

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

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;

}``````

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.......

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);
}
};``````

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);
}
};``````

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--;
}
}``````

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``````

Comment hidden because of low score. Click to expand.
0

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

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;
}``````

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.

### 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.