## Google Interview Question for Applications Developers

Country: United States
Interview Type: In-Person

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

``````static void Main(String[] args)
{
var A = new int[] { 0, 3, 5, 10, 8, 4, 2 };

Console.WriteLine(Peak(A) + " is the peak number");
}

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

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

#include<stdio.h>
#include<conio.h>
main()
{
int a[10]={1,2,3,4,5,4,3,2,1};
large=a[0];
for(i=0;i<10;i++)
{
if(large>a[i])
large=a[i];
}
printf("%d",large);
getch();
return 0;
}

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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

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.