Google Interview Question
Applications DevelopersCountry: United States
Interview Type: In-Person
Using Binary search code (as the input is sorted).
Note the input is a rotated array ...
private static int getPeak(int[] input) {
/**
* TODO Handle null/empty checks
*/
int low = 0;
int high = input.length - 1;
int mid = 0;
while (low <= high) {
mid = low + (high - low) / 2;
if (input[mid] < input[high]) {
if (input[mid] >= input[low]) {
low = mid + 1;
} else {
high = mid - 1;
}
} else {
if (input[mid] == input[high]) {
return input[mid];
}
int rightIndex = mid + 1; // Check the right neighbour
if (rightIndex < input.length) {
if (input[mid] < input[rightIndex]) {
low = mid + 1;
} else {
return input[mid];
}
}
}
}
return -1;
}
JavaScript easy to understand binary search O(log N).
I'm assuming that
1. The input is not empty.
2. There are only integer numbers with no duplicates.
3. Increasing/decreasing input is valid and last/first element is the solution.
function findPeak(nums){
const N = nums.length;
let lo = 0;
let hi = N - 1;
while(lo <= hi){
const mid = Math.floor((lo + hi) / 2);
if (mid === N - 1){
// it's the last element so must be the peak
return nums[mid];
}
else if (nums[mid] < nums[mid + 1]){
// we are on the left part of the hill
lo = mid + 1;
}
else if (mid === 0){
// it's the first element so must be the peak
return nums[mid];
}
else if (nums[mid - 1] < nums[mid]){
// it's the peak!
return nums[mid];
}
else {
// we are on the right part of the hill
hi = mid - 1;
}
}
}
console.log(findPeak([3])); // 3
console.log(findPeak([5, 2, 1])); // 5
console.log(findPeak([7, 9])); // 9
console.log(findPeak([3, 5, 8, 4, 2])); // 8
int peak_value(vector<int>a, int start, int end){
if (start==end) return a[start];
if(start>end) return 0;
int mid=(start+end)/2;
if(a[mid]<a[mid+1]){
return peak_value(a,mid+1, end);
}else if(a[mid]>a[mid+1]){
if((mid-1)>=0){
if(a[mid-1]>a[mid]){
return peak_value(a, start, mid-1);
}else{
return a[mid];
}
}else{
return a[mid];
}
}
}
int find_the_peak_value(vector<int> a){
if(a.size()==0){
return 0;
}else{
cout<<"calling first peak_value function"<<endl;
return (peak_value(a, 0, a.size()-1) );
}
}
If the input doesn't contain duplicates, O(log n) time, O(1) space.
If the input contains a lot of duplicates, O(n) time, O(log n) space.
#include <iostream>
#include <vector>
using namespace std;
int Peak(vector<int> const &a, int start, int end)
{
int l = start + 1;
int r = end - 1;
while (l <= end &&
l - 1 >= start &&
r >= start &&
r + 1 <= end &&
l <= r)
{
int i = (l + r) / 2;
if (a[i - 1] < a[i] &&
a[i + 1] < a[i])
{
return i;
} else if ((a[i - 1] <= a[i] && a[i + 1] > a[i]) ||
(a[i - 1] < a[i] && a[i + 1] >= a[i]))
{
l = i + 1;
} else if ((a[i - 1] >= a[i] && a[i + 1] < a[i]) ||
(a[i - 1] > a[i] && a[i + 1] <= a[i]))
{
r = i - 1;
} else {
int left = Peak(a, l, i - 1);
if (left != -1) {
return left;
}
return Peak(a, i + 1, r);
}
}
return -1;
}
int main() {
vector<int> in = {1, 2, 2, 2, 3, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1};
cout << Peak(in, 0, in.size() - 1) << "\n";
}
#include <bits/stdc++.h>
using namespace std;
/*
Given an array which is in ascending order till some point and then descending order till end. find peak element
*/
int peak_value(vector<int>a, int start, int end){
if (start==end) return a[start];
if(start>end) return 0;
int mid=(start+end)/2;
if(a[mid]<a[mid+1]){
return peak_value(a,mid+1, end);
}else if(a[mid]>a[mid+1]){
if((mid-1)>=0){
if(a[mid-1]>a[mid]){
return peak_value(a, start, mid-1);
}else{
return a[mid];
}
}else{
return a[mid];
}
}
}
int find_the_peak_value(vector<int> a){
if(a.size()==0){
return 0;
}else{
cout<<"calling first peak_value function"<<endl;
return (peak_value(a, 0, a.size()-1) );
}
}
int main(){
static const int arr[] = {1,2,3,4,5,3,1};
vector<int> vec (arr, arr + sizeof(arr) / sizeof(arr[0]) );
cout<<find_the_peak_value(vec);
return 0;
}
#include <bits/stdc++.h>
using namespace std;
/*
Given an array which is in ascending order till some point and then descending order till end. find peak element
*/
int peak_value(vector<int>a, int start, int end){
if (start==end) return a[start];
if(start>end) return 0;
int mid=(start+end)/2;
if(a[mid]<a[mid+1]){
return peak_value(a,mid+1, end);
}else if(a[mid]>a[mid+1]){
if((mid-1)>=0){
if(a[mid-1]>a[mid]){
return peak_value(a, start, mid-1);
}else{
return a[mid];
}
}else{
return a[mid];
}
}
}
int find_the_peak_value(vector<int> a){
if(a.size()==0){
return 0;
}else{
cout<<"calling first peak_value function"<<endl;
return (peak_value(a, 0, a.size()-1) );
}
}
int main(){
static const int arr[] = {1,2,3,4,5,3,1};
vector<int> vec (arr, arr + sizeof(arr) / sizeof(arr[0]) );
cout<<find_the_peak_value(vec);
return 0;
}
O(logn) soln. -
public static void main(String[] args){
int[] arr = {10, 12, 14, 15, 10, 7, 2, 1, 0};
int n = find(arr);
System.out.println(n);
}
public static int find(int[] arr){
int n = arr.length;
int l = 0;
int h = n-1;
while(l <= h){
int mid = (h-l)/2 +l;
if(mid-1 >= 0 && mid+1 < n && arr[mid-1] < arr[mid] && arr[mid] > arr[mid+1])
return arr[mid];
else if(mid-1 >= 0 && mid+1 < n && arr[mid-1] < arr[mid] && arr[mid] < arr[mid+1])
l = mid+1;
else
h = mid-1;
}
return -1;
}
static void Main(String[] args)
{
var A = new int[] { 0, 3, 5, 10, 8, 4, 2 };
Console.WriteLine(Peak(A) + " is the peak number");
Console.ReadLine();
}
static int Peak(int[] array)
{
int p = -1;
int c = 0;
bool found = false;
while (!found && c < array.Length)
{
if (array[c + 1] < array[c])
{
p = array[c];
found = true;
}
c++;
}
return p;
}
As far as I understand it can be solved this way:
def get_peak(array_list):
previous = None
for i, element in enumerate(array_list):
if previous and element < previous:
return max(previous, element)
previous = element
if __name__ == '__main__':
array_list = [1, 2, 3, 4, 5, 100, 3, 2, 1]
print(get_peak(array_list))
class Peak {
public static void main(String[] args) {
Peak peakElement = new Peak();
int[] arr = { 10, 20, 30, 40, 50, 35, 25, 15, 1 };
peakElement.findHighesInArray(arr);
}
public void findHighesInArray(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int j = i - 1;
if (arr[i] < arr[j]) {
System.out.println(arr[j]);
break;
}
}
}
}
it can be solved in O(n) as pointed out by @dubai_data_science but there is as well a O(lg(n)) solution involving binary search:
- Chris November 22, 2017- you go into the middle and check the element in the middle and it's preceeding. If you find a rising value, you know left of you is increasing, so you element in in the range [middle..end]. So, you repeat that step on this range until you're on the peak ;-)