Google Interview Question Software Engineers
Country: United States
Interview Type: In-Person
Here's my solution using stack
void order(int * num, int size){
int max = 0;
stack<int> s;
for(unsigned int i = 0; i < size; i++){
if(num[i] > max){
max = num[i];
s.push(max);
}
while(!s.empty() && num[i] < s.top()){
s.pop();
}
}
while(!s.empty()){
printf("%d ", s.top()) ;
s.pop();
}
printf("\n");
}
int main(){
int a[] = {6, 5, 4, 3, 9, 100, 87, 64, 34, 101};
int b[] = {3, 4, 7, 1, 8, 12};
order(a, 10) ;
order(b, 6) ;
return 0;
}
def greaterThanLeftLessThanRight(array):
if array is None:
raise TypeError('Array cannot be None')
if len(array) == 0:
return None
leftArray = [0 for _ in range(len(array))]
rightArray = [0 for _ in range(len(array))]
leftMax = array[0]
rightMin = array[-1]
# build array of greatest element seen so far at each index from the left
for i in range(1, len(array)):
leftArray[i] = leftMax
if array[i] > leftMax:
leftMax = array[i]
# build array of smallest element seen so far at each index from the right
for i in range(len(array) - 2, -1, -1):
rightArray[i] = rightMin
if array[i] < rightMin:
rightMin = array[i]
# iterate over array - checking conditions to print
for i in range(len(array)):
if i == 0:
if array[i] < rightArray[i]:
print array[i]
elif i == len(array) - 1:
if array[i] > leftArray[i]:
print array[i]
elif array[i] > leftArray[i] and array[i] < rightArray[i]:
print array[i]
public class Numbers {
public static void main(String[] args) {
int[] a = new int[] { 3, 4, 7, 1, 8, 12 };
printFitNumbers(a);
}
public static void printFitNumbers(int[] a) {
int count = 0;
for (int i = 0; i < a.length; i++) {
int k;
for (k = 0; k < i; k++)
if (a[k] >= a[i]) {
count++;
break;
}
if (count == 0 && (i + 1 < a.length)) {
for (int j = i + 1; j < a.length; j++)
if (a[i] >= a[j]) {
count++;
break;
}
}
if (count == 0)
System.out.print(a[i] + " ");
count = 0;
}
}
}
public int[] solution(int [] input){
int maxTillNow = Integer.MIN_VALUE;
int minAfterNow = Integer.MAX_VALUE;
int index = 0;
List<Integer> result = new ArrayList<Integer>();
for(int i = 0;i<input.length;i++){
if(i>=index){
minAfterNow = Integer.MAX_VALUE;
for(int j=i+1;j<input.length;j++){
if(input[j]<minAfterNow){
minAfterNow=input[j];
index=j;
}
}
}
if(input[i]>maxTillNow && input[i]<minAfterNow){
result.add(input[i]);
}
maxTillNow = Math.max(maxTillNow, input[i]);
}
int[] returnVal = new int[result.size()];
int idx = 0;
for(int r : result){
returnVal[idx]=r;
idx++;
}
return returnVal;
}
Simple Recursive solution is following
FindElement(int[] arr, int MaxTillNow, int currentIndex)
{
if(currentIndex == 0)
{
return FindElement(arr, arr[currentIndex], currentIndex + 1);
}
if(currentIndex == arr.Length-1)
{
return arr[currentIndex];
}
int minTillNow = FindElement(arr, Math.Max(MaxTillNow, arr[currentIndex]), currentIndex + 1)
if(arr[currentIndex] > MaxTillNow && arr[currentIndex] < minTillNow)
{
Console.WriteLine(arr[currentIndex]);
}
return Math.Min(minTillNow, arr[currentIndex]);
}
Complexity : O(N), we are only doing one pass to the array.
Space complexity is O(1).
The trick here is that there can only be one - a maximum
package com.prajnainc;
import java.util.HashSet;
import java.util.Set;
public class Peaks {
/* Second question Given an array of integers, print all the numbers that meet the following requirement - when the
* number is greater than every number on its left and smaller than every number on the right.
*/
/* There can only be one - so just find the maximum */
static int a[] = {1,3,-1,5,7,9,1,3};
public static void main(String args[]) {
int max_i = 0;
for(int i = 1; i<a.length; i++) {
if(a[i] > a[max_i]) {
max_i = i;
}
}
System.out.println("a["+max_i+"]="+a[max_i]);
}
}
The trick here is that there can only be one. so just find the maximum
package com.prajnainc;
import java.util.HashSet;
import java.util.Set;
public class Peaks {
/* Second question Given an array of integers, print all the numbers that meet the following requirement - when the
* number is greater than every number on its left and smaller than every number on the right.
*/
/* There can only be one - so just find the maximum */
static int a[] = {1,3,-1,5,7,9,1,3};
public static void main(String args[]) {
int max_i = 0;
for(int i = 1; i<a.length; i++) {
if(a[i] > a[max_i]) {
max_i = i;
}
}
System.out.println("a["+max_i+"]="+a[max_i]);
}
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greed and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions. Thanks for reading.
Interviewee's solution
- aonecoding April 13, 2017#include <iostream> #include <vector> using namespace std; void printLargerSmaller(const vector<int> &v) { int n = v.size(); vector<int>leftMax(n, INT_MIN); for(int i=1;i<n; ++i) leftMax = max(leftMax[i-1], v[i-1]); int rightMin =INT_MAX; for(int i=n-1;i>=0; i--) { if(i<n-1)rightMin = min(rightMin, v[i+1]); if(v >leftMax && v < rightMin) cout << v << " "; } } int main() { vector<int>v = {3,4,7,1,8,12}; printLargerSmaller(v); return 0; }