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

- Chris November 22, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Hey! Was this your coding challenge or phone screen round?

- Cool November 22, 2017 | Flag Reply
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;
	}

- Anon November 23, 2017 | Flag Reply
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

- Anonymous November 23, 2017 | Flag Reply
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) );
    }
}

- Anonymous November 23, 2017 | Flag Reply
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";
}

- Alex November 23, 2017 | Flag Reply
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;
}

- harrypotter0 November 24, 2017 | Flag Reply
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;
}

- harrypotter0 November 24, 2017 | Flag Reply
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;
  }

- sudip.innovates November 25, 2017 | Flag Reply
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");
            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;
        }

- Peter_D November 26, 2017 | Flag Reply
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;
}

- nazeer December 02, 2017 | Flag Reply
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))

- dubai_data_science November 22, 2017 | Flag Reply
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;
			}
		}
	}
}

- nk08 November 23, 2017 | Flag Reply


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More