Home »
Interview coding problems/challenges
Bike Tour Google Kick Start Round B Problem 1 Solution
Bike Tour Google Kick Start Round B Problem 1 Solution: This problem has been featured in Google Kick Start 2020 Round B.
Submitted by Radib Kar, on August 14, 2020
Problem statement:
Li has planned a bike tour through the mountains of Switzerland. His tour consists of N checkpoints, numbered from 1 to N in the order he will visit them. The ith checkpoint has a height of Hi.
A checkpoint is a peak if:
It is not the 1st checkpoint or the Nth checkpoint, and
The height of the checkpoint is strictly greater than the checkpoint immediately before it and the checkpoint immediately after it.
Please help Li find out the number of peaks.
Input:
The first line of the input gives the number of test cases, T. T test cases follow. Each test case begins with a line containing the integer N. The second line contains N integers. The ith integer is Hi.
Output:
For each test case, output one line containing Case #x: y, where x is the test case number (starting from 1) and y is the number of peaks in Li's bike tour.
Constraints:
1 ≤ T ≤ 100.
1 ≤ Hi ≤ 100.
3 ≤ N ≤ 100.
Example:
Input:
4
3
10 20 14
4
7 7 7 7
5
10 90 20 90 10
3
10 3 10
Output:
Case #1: 1
Case #2: 0
Case #3: 2
Case #4: 0
Solution:
This is a trivial problem where we need to check each element as per its constraints. So an element is peak if it's not the corner element and it's strictly greater than its neighbours. So the algorithm would be
Let n=number of elements and peak be number of peaks
 Peak =0 initially

for i 0 to n1
if(i==0 or i==n1)
Skip this as it's corner elements and can't be peak
Else if(arr[i]>arr[i1] and arr[i]>arr[i+1])
Increment peak
End if
End for
 Peak is the final result
What can be done as part of optimizing further?
One think we can do is instead of checking each and every element to be a peak, we can skip few elements. If an element(arr[i]) is peak then we can skip the immediate right neighbour(arr[i+1]) as that can’t be peak as per constraints. This can be done in terms of optimization, but still will lead to O(n) complexity.
Since the algo is pretty intuitive and selfexplanatory I am not going for dry run. However you can do a dry run for better understanding.
C++ Implementation:
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
int arr[100];
int main()
{
int test_case;
cin >> test_case;
for (int tc = 1; tc <= test_case; tc++) {
int n;
cin >> n;
int count = 0;
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
for (int i = 0; i < n; i++) {
if (i != 0 && i != n  1 && arr[i] > arr[i  1] && arr[i] > arr[i + 1])
count++;
}
cout << "Case #" << tc << ": " << count << endl;
}
return 0;
}
Output:
4
3
10 20 14
Case #1: 1
4
7 7 7 7
Case #2: 0
3
10 3 10
Case #3: 0
5
10 90 20 90 10
Case #4: 2
Also tagged in: Google Interview Questions
TOP Interview Coding Problems/Challenges
ADVERTISEMENT
ADVERTISEMENT