Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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]
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]
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.
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];
}
}
//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
}
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
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--;
}
}
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;
}
/*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);
}
};
/*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);
}
};
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--;
}
}
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
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;
}
1) I see lots of correct solutions for the binary search algorithm so I won't elaborate further.
- Dave June 03, 20152) 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]