Google Interview Question Software Engineers
Country: United States
Interview Type: Phone Interview
Finding the peak/bottom will take O(log N) for binary search.
if array is [2 3 4 5 6 7 10 9 8 7] => array looks like /\
So peak = a[6], that gives two sub arrays as a[0 - 5] and a[6 - 9]
smallest = min (a[0], a[9]) => 2
largest = max(a[5], a[6]) = 10
if array is [7 6 5 4 3 2 7 8 9 10] => array looks like \/
bottom = a[5], that gives two sub arrays as a[0 - 4] and a[5 - 9]
smallest = min (a[4], a[5]) = 2
largest = max (a[0], a[9]) = 10
Run time is O(log N) for binary search
1. Find pivot element (index where sequence changes from ascending to descending) using modified binary search - O (Log n)
2. max element will be either pivot-1 or 0. Min element will always be a corner element, either a[0] or a[a.length-1]. Check for these.
Total time: O(log N)
public class FindMinMax {
public static void main(String[] args) {
int[] a = {2,3,4,5,6,7,10,9,8,7};
int[] a2 = {10,9,8,7,6,5,4,3,2};
int[] a3 = {1,2,3,4,5,6,7,8};
int[] a4 = {6,7,8,10,11,12,13,14,15,16,9,8,7,6};
printMinMax(a);
printMinMax(a2);
printMinMax(a3);
printMinMax(a4);
}
private static void printMinMax(int[] a) {
int pivot = a.length == 1 || a[0] > a[1] ? 0 : findPivot(a, 0, a.length-1);
int max = pivot > 0 ? a[pivot-1] : a[0];
int min = Math.min(a[0], a[a.length-1]);
System.out.println("max = " + max + ", min = " + min);
}
private static int findPivot(int arr[], int low, int high) {
if (high < low)
return -1;
if (high == low)
return low;
int mid = (low + high) / 2;
if (mid < high && arr[mid] > arr[mid + 1])
return mid;
if (mid > low && arr[mid] < arr[mid - 1])
return (mid - 1);
if (arr[low] >= arr[mid])
return findPivot(arr, low, mid - 1);
return findPivot(arr, mid + 1, high);
}
}
#include <iostream>
#include <climits>
using namespace std;
void minmax(int a[], int n)
{
int min = INT_MAX, max = INT_MIN;
min = a[0]>a[n-1] ? a[n-1] : a[0];
cout<<"\nmin value is: "<<min;
int l=0,r=n-1;
int mid = INT_MAX;
while(l<r)
{
mid = l + (r-l)/2;
if(a[mid]>a[mid-1])
{
l = mid;
}
if(a[mid]>a[mid+1])
{
r = mid;
}
}
cout<<"\nmax value is: "<<a[mid];
}
int main() {
int a[] = {1,2,3,4,5,6,7,8,7,4};
int n = sizeof(a)/sizeof(a[0]);
minmax(a,n);
return 0;
}
#include <iostream>
#include <climits>
using namespace std;
void minmax(int a[], int n)
{
int min = INT_MAX, max = INT_MIN;
min = a[0]>a[n-1] ? a[n-1] : a[0];
cout<<"\nmin value is: "<<min;
int l=0,r=n-1;
int mid = INT_MAX;
while(l<r)
{
mid = l + (r-l)/2;
if(a[mid]>a[mid-1])
{
l = mid;
}
if(a[mid]>a[mid+1])
{
r = mid;
}
}
cout<<"\nmax value is: "<<a[mid];
}
int main() {
int a[] = {1,2,3,4,5,6,7,8,7,4};
int n = sizeof(a)/sizeof(a[0]);
minmax(a,n);
return 0;
}
#include <iostream>
#include <climits>
using namespace std;
void minmax(int a[], int n)
{
int min = INT_MAX, max = INT_MIN;
min = a[0]>a[n-1] ? a[n-1] : a[0];
cout<<"\nmin value is: "<<min;
int l=0,r=n-1;
int mid = INT_MAX;
while(l<r)
{
mid = l + (r-l)/2;
if(a[mid]>a[mid-1])
{
l = mid;
}
if(a[mid]>a[mid+1])
{
r = mid;
}
}
cout<<"\nmax value is: "<<a[mid];
}
int main() {
int a[] = {1,2,3,4,5,6,7,8,7,4};
int n = sizeof(a)/sizeof(a[0]);
minmax(a,n);
return 0;
}
#include <iostream>
#include <climits>
using namespace std;
void minmax(int a[], int n)
{
int min = INT_MAX, max = INT_MIN;
min = a[0]>a[n-1] ? a[n-1] : a[0];
cout<<"\nmin value is: "<<min;
int l=0,r=n-1;
int mid = INT_MAX;
while(l<r)
{
mid = l + (r-l)/2;
if(a[mid]>a[mid-1])
{
l = mid;
}
if(a[mid]>a[mid+1])
{
r = mid;
}
}
cout<<"\nmax value is: "<<a[mid];
}
int main() {
int a[] = {1,2,3,4,5,6,7,8,7,4};
int n = sizeof(a)/sizeof(a[0]);
minmax(a,n);
return 0;
}
/*
#include <iostream>
#include <climits>
using namespace std;
void minmax(int a[], int n)
{
int min = INT_MAX, max = INT_MIN;
min = a[0]>a[n-1] ? a[n-1] : a[0];
cout<<"\nmin value is: "<<min;
int l=0,r=n-1;
int mid = INT_MAX;
while(l<r)
{
mid = l + (r-l)/2;
if(a[mid]>a[mid-1])
{
l = mid;
}
if(a[mid]>a[mid+1])
{
r = mid;
}
}
cout<<"\nmax value is: "<<a[mid];
}
int main() {
int a[] = {1,2,3,4,5,6,7,8,7,4};
int n = sizeof(a)/sizeof(a[0]);
minmax(a,n);
return 0;
}
*/
Binary search for Max value:
#include <iostream>
#include <climits>
using namespace std;
void minmax(int a[], int n)
{
int min = INT_MAX, max = INT_MIN;
min = a[0]>a[n-1] ? a[n-1] : a[0];
cout<<"\nmin value is: "<<min;
int l=0,r=n-1;
int mid = INT_MAX;
while(l<r)
{
mid = l + (r-l)/2;
if(a[mid]>a[mid-1])
{
l = mid;
}
if(a[mid]>a[mid+1])
{
r = mid;
}
}
cout<<"\nmax value is: "<<a[mid];
}
int main() {
int a[] = {1,2,3,4,5,6,7,8,7,4};
int n = sizeof(a)/sizeof(a[0]);
minmax(a,n);
return 0;
}
#include <iostream>
#include <climits>
using namespace std;
void minmax(int a[], int n)
{
int min = INT_MAX, max = INT_MIN;
min = a[0]>a[n-1] ? a[n-1] : a[0];
cout<<"\nmin value is: "<<min;
int l=0,r=n-1;
int mid = INT_MAX;
while(l<r)
{
mid = l + (r-l)/2;
if(a[mid]>a[mid-1])
{
l = mid;
}
if(a[mid]>a[mid+1])
{
r = mid;
}
}
cout<<"\nmax value is: "<<a[mid];
}
int main() {
int a[] = {1,2,3,4,5,6,7,8,7,4};
int n = sizeof(a)/sizeof(a[0]);
minmax(a,n);
return 0;
}
O(nlogn) using recursion. based off 1st answer.
int getLargest(int[] arr) {
if(arr.length == 1) {
return arr[0];
}
if (arr.length == 2) {
return arr[0] > arr[1]? arr[0]:arr[1];
}
// largest will be at the turn
return findTurn(arr, arr.length/2, arr.length);
}
// binary search for turning point
int findTurn(int[] arr, int middle, int end) {
if (arr[middle-1] < arr[middle] && arr[middle] > arr[middle+1]) {
return arr[middle]; // return the turning point
} else if (arr[middle] < arr[middle+1]) {
// rising half
return findTurn(arr, (middle+end)/2, end);
} else {
// descending half
return findTurn(arr, middle/2, middle);
}
}
Similar to previous posts, the minimum value is getting from the first and last elements; To find the highest value we use a modification of binary search; We continue advancing/ spliting in the direction where the highst value is.
public static Tuple<int,int> FindMaxMin(int[] a)
{
int min = Math.Min(a[0], a[a.Length-1]);
int low = 0;
int high = a.Length - 1;
int max = int.MinValue;
while (low < high)
{
int midle = (low + high) / 2;
//Console.WriteLine("L = " + low + ", H = " + high + ", M = " +midle);
if (midle > 0 && a[midle] > a[midle - 1] && midle < a.Length -1 && a[midle] > a[midle + 1])
{
max = a[midle];
break;
}
if (midle < a.Length -1 && a[midle + 1] > a[midle])
low = midle + 1;
else
high = midle - 1;
}
if (low == high && max == int.MinValue)
max = a[low];
return Tuple.Create(min, max);
}
I don't understand what will happen if there are two or more number that are equal. Will the binary search method still work or is there a way to make it work?
for example: [2,3,4,5,6,6,6,7,10,9,8,7]
Should we be handling this spl case such that mid keeps decreasing until if finds a different number on the left or a different number on the right?
The other solution would be to remove the duplicates from the array before processing.
What about the condition when descending part comes first in the array. For example [10,9,8,7,2,4,5,6,7]
In this case the smallest number is never at the first or last place, it will be the Largest number which will be arr[0] or arr[n-1].
And search will be for the smallest number in that case.
Using greedy algorithm to solve in O(n) time,
When the array is ascending then descending,
Max will be the one after which the array starts descending
Min will be minimum of first and last values
When the array is descending then ascending,
Min will be the one after which the array starts ascending
Max will be the maximum of first and last values
Please correct me if I am wrong
Following is the code:
public static void main(String[] args)
{
int[] arr = new int[] {2,3,4,5,6,7,10,9,8,7};
findMinMax(arr);
int[] arr2 = new int[] {7,6,5,4,3,2,7,8,9,10};
findMinMax(arr2);
}
public static void findMinMax(int[] arr)
{
int len = arr.length;
int min = 0;
int max = 0;
boolean asc = true;
if (len == 1)
{
min = arr[0];
max = arr[0];
}
else if (len == 2)
{
if (arr[0] > arr[1])
{
min = arr[1];
max = arr[0];
}
else
{
min = arr[0];
max = arr[1];
}
}
//len > 2
else
{
if (arr[0] > arr[1])
asc = false;
if (asc)
{
min = ( arr[0] < arr[arr.length -1] ) ? arr[0] : arr[arr.length -1];
for (int i=1; i< arr.length; i++)
if (arr[i-1] > arr[i])
{
max = arr[i-1];
break;
}
}
else
{
max = ( arr[0] > arr[arr.length -1] ) ? arr[0] : arr[arr.length -1];
for (int i=1; i< arr.length; i++)
if (arr[i-1] < arr[i])
{
min = arr[i-1];
break;
}
}
}
System.out.println("Min: " + min);
System.out.println("Max: " + max);
}
Find the index at which the array is split using the recursive function (modified binary search). Once we find this index we can then determine the min and max between the start, end and the split index in constant time. The recursive algo to find the min and max is O(log n)
public class Problem1 {
private int splitInd(int[] n , int s , int e)
{
assert s <= e;
if( e - s <= 1)
return s;
int m = (s+e)/2;
if( (n[m-1] < n[m] && n[m] > n[m+1]) || (n[m-1] > n[m] && n[m] < n[m+1]))
{
System.out.println("split Index " + m);
return m;
}
if( (n[s] <= n[m-1] && n[m-1] <= n[m]) || n[s] >= n[m-1] && n[m-1] >= n[m])
return splitInd(n , m, e);
else
return splitInd(n,s,m);
}
@Test
public void solution() {
// int[] n = {};
int[] n = { 6,4,3,2,8,9,10,11,12};
// int[] n = {1};
// int[] n = {2,2,2,2};
// int[] n = {1,2,3,5,5,6,4,2,0};
// int[] n = {10,9,8,7,6,5,2,0};
if(n == null || n.length == 0)
{
System.out.println("Emtpy or null input array");
return ;
}
int splitInd = splitInd(n, 0, n.length-1);
int min = n[0], max= n[0];
if(min > n[splitInd])
min = n[splitInd];
if(max < n[splitInd])
max = n[splitInd];
int l = n.length-1;
if(min > n[l])
min = n[l];
if(max < n[l])
max = n[l];
System.out.println("Max: " + max + " Min : " + min );
}
}
var arr0 = [10,9,8,7,2,3,4,5,6,7];
var arr1 = [1,3,4,5,6,12,9,8,7,5];
var minMax = [];
var findMinMax = function(arr){
let b = true;
let c = true;
minMax=[];
for(let i=0; i<arr.length; i++){
if(arr[i]<arr[i+1]){
if(b){
minMax.push(arr[i]);
b=false;
}
}
else{
if(c){
minMax.push(arr[i]);
c = false;
}
}
if(minMax.length==2)break;
}
}
findMinMax(arr0);
console.log(minMax);
findMinMax(arr1);
console.log(minMax);
var arr0 = [10,9,8,7,2,3,4,5,6,7];
var arr1 = [1,3,4,5,6,12,9,8,7,5];
var minMax = [];
var findMinMax = function(arr){
let b = true;
let c = true;
minMax=[];
for(let i=0; i<arr.length; i++){
if(arr[i]<arr[i+1]){
if(b){
minMax.push(arr[i]);
b=false;
}
}
else{
if(c){
minMax.push(arr[i]);
c = false;
}
}
if(minMax.length==2)break;
}
}
findMinMax(arr0);
console.log(minMax);
findMinMax(arr1);
console.log(minMax);
//Written in Javascript
var arr0 = [10,9,8,7,2,3,4,5,6,18]; // 2, 18
var arr1 = [2,3,4,5,6,12,9,8,7,1]; // 1, 12
var arr2 = [2,3,4,5,6,7,10,9,8,7]; // 2, 10
var minMax = [];
var findMinMax = function(arr){
let b = true;
let c = true;
minMax=[];
for(let i=0; i<arr.length; i++){
if(arr[i]<arr[i+1]){
if(b){
let x=(arr[i]<arr[arr.length-1]?arr[i]:arr[arr.length-1]);
minMax.push(x);
b=false;
}
}
else{
if(c){
let y=(arr[i]>arr[arr.length-1]?arr[i]:arr[arr.length-1]);
minMax.push(y);
c = false;
}
}
if(minMax.length==2)break;
}
}
findMinMax(arr0);
console.log(minMax);
findMinMax(arr1);
console.log(minMax);
findMinMax(arr2);
console.log(minMax);
The binary search won't work for the following use case {1000,90,80,70,60,-200,3,4,5,100000000} as we would go towards the opposite end for getting the max value and also the min value is in middle.
Here's the code that deals with such usecase. The complexity is O(n).
int[] a= {1000,90,80,70,60,-200,3,4,5,100000000};
if (a.length < 2) {
throw new IllegalArgumentException("Getting a profit requires at least 2 prices");
}
int min = a[0];
int max = a[1];
for (int i = 1; i < a.length; i++) {
int current = a[i];
min = Math.min(min, current);
max = Math.max(max, current);
}
System.out.println("Min is :"+min);
System.out.println("Max is :"+max);
public static int[] findLargestAndSmallest(int[] array){
int[] res = new int[2];
res[0] = Math.min(Math.min(array[0],array[array.length-1]),findSmallest(array,0,array.length-1));
res[1] = Math.max(Math.max(array[0],array[array.length-1]),findLargest(array,0,array.length-1));
return res;
}
//assume ascending then descending
//O(logn)
public static int findLargest(int[] array, int left, int right){
if(left == right) return array[left];
if(right - left == 1) return Math.max(array[left],array[right]);
int mid = left + (right - left)/2;
if(array[mid] > array[mid-1] && array[mid] > array[mid+1]){
return array[mid];
}
if(array[mid] < array[mid+1]){
return findLargest(array,mid+1,right);
}else {
return findLargest(array,left,mid-1);
}
}
//assume descending then ascending
//O(logn)
public static int findSmallest(int[] array, int left, int right){
if(left == right) return array[0];
if(right - left == 1) return Math.min(array[left],array[right]);
int mid = left + (right - left)/2;
if(array[mid] < array[mid-1] && array[mid] < array[mid+1]){
return array[mid];
}
if(array[mid] < array[mid+1]){
return findLargest(array,left,mid-1);
}else {
return findLargest(array,mid+1,right);
}
}
public int[] findMinMax(int[] nums){
int[] result = new int[2];
int mid = (nums.length/2) - 1;
if(nums[0] > nums[mid]){
result[1] = nums[0];
result[0] = findMin(nums, 0, nums.length - 1);
}else{
result[0] = nums[0];
result[1] = findMax(nums, 0, nums.length - 1);
}
return result;
}
public int findMax(int[] nums, int start, int end){
int mid = start + (end-start)/2;
int pivot = nums[mid];
if(pivot < nums[end]){
return findMax(nums, mid+1, end);
}
if(pivot > nums[end]){
return findMax(nums, start, end-1);
}
return pivot;
}
public int findMin(int[] nums, int start, int end){
int mid = start + (end-start)/2;
int pivot = nums[mid];
if(pivot < nums[end]){
return findMin(nums, start, mid);
}
if(pivot > nums[end]){
return findMin(nums, start+1, end);
}
return pivot;
def find_min_max(arr):
if not arr: return None, None
if len(arr) == 1: return arr[0], arr[0]
sort_start = None
sort_end = None
rsort_start = None
rsort_end = None
for i in xrange(1, len(arr)):
if i == 1:
if arr[1] >= arr[0]:
sort_start = 0
else:
rsort_start = 0
else:
if sort_start is not None and a[i] < a[i - 1]:
sort_end = i-2
rsort_start = i -1
rsort_end = len(arr) - 1
break
if rsort_start is not None and a[i] > a[i - 1]:
rsort_end = i-2
sort_start = i -1
sort_end = len(arr) - 1
break
if sort_start is not None and sort_end is None:
return arr[sort_start], arr[-1]
if rsort_start is not None and rsort_end is None:
return arr[-1], arr[rsort_start]
return min(arr[sort_start], arr[rsort_end]), max(arr[rsort_start], arr[sort_end])
a = [5,4,-1, -10, 1,2,3,4,5,6]
print find_min_max(a)
Smallest is obvious, it's Math.Min(input[0], input[input.Length-1])
I'm surprised that they even asked that.
For finding the max, we would use binary search so that it finishes in O(logn) time.
This would be a modified binary search, instead of looking for a value, we're looking for a condition. The condition is that the number should be greater than both it's left & right neighbor. If it's less than it's right neighbor, we search the right half, if it's less than it's left neighbor, we search the left half.
The minimum is always at either A[0] or A[n - 1]. logn solution to search for the maximum.
The idea is to compare A[i] with A[i+1]. if A[i + 1] > A[i], we are in the rising half of the array. If A[i + 1] < A[i], then we are in the falling half. With this knowledge, we can recurse on a subproblem half the size, with an O(1) check at each recursion. O(logn); code below
- Anonymous September 29, 2016public static int getMax(int[] a){ //assumes a is sorted in ascending then decreasing order. if(a.Length == 1){ return a[0]; } if(a.Length == 2){ return a[0] > a[1] ? a[0] : a[1]; } int start = 0; int end = a.Length - 1; int middle = (start + end) / 2; while( !(a[middle] > a[middle - 1] && a[middle] >a[middle + 1]) ){ if(a[middle + 1] > a[middle]){ //we're in the rising sequence. middle = (middle + end) / 2; }else{ middle = (start + middle) / 2; } } return a[middle]; }