Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

public static int [] findTempArray(int temp[]){		
		int out[] = new int[temp.length];
		Stack<Integer> stack = new Stack<>();		
		stack.push(0);
		for(int i =1 ; i < out.length ; i++){
			while(!stack.isEmpty()  && temp[i] > temp[stack.peek()]){
				int top = stack.pop();
				out[top] = i-top;
			}			
			stack.push(i);
		}		
		while(!stack.isEmpty()){
			int top = stack.pop();
			out[top] = -1; //nothing
		}
		return out;

}

- anurag.iitp November 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
1
of 1 vote

public static int [] findTempArray(int temp[]){		
		int out[] = new int[temp.length];
		Stack<Integer> stack = new Stack<>();		
		stack.push(0);
		for(int i =1 ; i < out.length ; i++){
			while(!stack.isEmpty()  && temp[i] > temp[stack.peek()]){
				int top = stack.pop();
				out[top] = i-top;
			}			
			stack.push(i);
		}		
		while(!stack.isEmpty()){
			int top = stack.pop();
			out[top] = -1; //nothing
		}
		return out;

}

- Anurag Kumar November 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

The algorithm in Python:

import random

temperatures = random.sample(range(50,100), 10)
#temperatures = [73, 74, 75, 71, 69, 72, 70, 74, 76, 72]
tempCount = len(temperatures)
warmerDelay = [0] * tempCount

tempStack = [temperatures[0]]
idxStack = [0]
for i in range(1, tempCount, 1):
    topVal = tempStack.pop()
    topIdx = idxStack.pop()
    nextVal = temperatures[i]
    while nextVal > topVal:
        warmerDelay[topIdx] = i - topIdx
        stackLen = len(tempStack)
        if stackLen == 0:
            break
        topVal = tempStack.pop()
        topIdx = idxStack.pop()
    if nextVal < topVal:
        tempStack.append(topVal)
        idxStack.append(topIdx)
    tempStack.append(nextVal)
    idxStack.append(i)

print temperatures
print warmerDelay

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

Following is an O(nlogn) solution-

int binSearch(vector<pair<int,int> > bst,int low,int high,int target)
{
        if((high-low)<2)
        {
                for(int i=low;i<=high;i++)
                {
                        if(bst[i].first<target)
                                return i;
                }
                return high+1;
        }
        int mid = low+(high-low)/2;
        if(bst[mid].first>target)
        {
                return binSearch(bst,mid+1,high,target);
        }
        else
        {
                return binSearch(bst,low,mid,target);
        }
}
vector<int> findWarmerDays(vector<int> v)
{
        vector<int> output(v.size(),-1);
        vector<pair<int,int> > bst;
        int j;
        bst.push_back(make_pair(v[0],0));
        for(int i=1;i<v.size();i++)
        {
                j = binSearch(bst,0,bst.size()-1,v[i]);
                pair<int,int> p;
                int count = 0;
                for(int k=bst.size()-1;k>=j;k--)
                {
                        p = bst[k];
                        output[p.second] = (i-p.second);
                        bst.pop_back();
                }
                bst.push_back(make_pair(v[i],i));
        }
        return output;
}

- md.lisul.islam November 24, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

int [] output = new int[n];

for int i = 0 to i-1:
	output[i] = 0;

// 0 is nothing 
int localMax = input[0]
int localMaxIndex = 0;
for i = 1 to n-1:
	if input[i] > localMax:
		for j = localMaxIndex to i -1
			output[j] = i - j
		localMax = input[i]
		localMaxIndex = i

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

int [] output = new int[n];

for int i = 0 to n-1
	output[i] = 0; // 0 is nothing

int localMax = input[0]
int localMaxIndex = 0;
for i = 1 to n-1:
	if input[i] > localMax:
		for j = localMaxIndex to i -1
			output[j] = i - j
		localMax = input[i]
		localMaxIndex = i

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

public static void main(String[] args) {
		int[] arr = { 73, 74, 75, 71, 70, 76, 72 };
		calcFreq(arr);
	}

	public static void calcFreq(int[] arr) {

		int n = arr.length;
		int[][][] maxind = new int[100][2][2];
		for (int i = 0; i < 100; i++){
			Arrays.fill(maxind[i][0], 1000);
			Arrays.fill(maxind[i][1], 1000);
		}
			
		for (int i = n - 1; i >= 0; i--) {
			for (int k = 100; k >= 0; k--) {
				if(k == arr[i])
					maxind[k][0][1] = i;
				if (arr[i] - k > 0 && (i > maxind[k][0][1] || maxind[k][0][1] == 1000)) {
					maxind[k][0][0] = arr[i] - k;
					maxind[k][1][0] = i;
				}
			}
		}

		for (int i = 0; i < n; i++) {
			int index = maxind[arr[i]][1][0];
			System.out.print((index == 1000 ? "Nothing" : (index-i)) + " ");
		}
	}

- sudip.innovates November 25, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Idea is to Keep a stack and push every element to stack but before that pop out all elements that are smaller and update its daysToWarm. Notice we push indices on stack. By virtue of this algo notice Stack always contains elements in increasing order from top i.e. top one smallest. Since each element gets pushed and popped from stack atmost once time complexity is O(n). Here is a c++ version.

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

void
daysToBeWarm(vector<int> &dailyTemp, vector<int> &daysToWarm)
{
    stack<int>  S;
    for(int i=0; i<dailyTemp.size(); i++)
    {
        while(!S.empty() && dailyTemp[i]>dailyTemp[S.top()])
        {
            daysToWarm[S.top()] = i-S.top();
            S.pop();
        }
        S.push(i);
    }
}

int
main(int argc, char *argv[])
{
    vector<int> dailyTemp;
    int i;
    while(1)
    {
        cin>>i;
        if(i!=-1)
            dailyTemp.push_back(i);
        else
            break;
    }
    vector<int> daysToWarm(dailyTemp.size(),0);
    daysToBeWarm(dailyTemp,daysToWarm);
    for(int i=0;i<daysToWarm.size();i++)
        cout<<daysToWarm[i]<<" ";
}

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

O(N)
keep record of every descending line,
and when meeting an ascending line, compare with every descending line.
merge them if possible.

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

I don't think you need to use Stack:

private int[] howManyMoreDays2(int[] array) {
        // last element is always 'nothing'
        int[] res = new int[array.length];
        res[array.length - 1] = -1;
        int start = 0;
        int i;

        while (start < array.length) {
            for (i = start + 1; i < array.length - 1; i++) {
                if (array[start] < array[i]) {
                    res[start] = i - start;
                    break;
                }
            }
            if (i == array.length - 1) {
                res[start] = -1;
            }
            start++;
        }

        return res;
    }

- Hugh May 28, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NextGreaterElement {

public static void main(String[] args) {
// TODO Auto-generated method stub

int[] ht = {73, 74, 75, 71, 69, 72, 76, 73};
Stack<Integer> st = new Stack<>();

int[] nge = new int[ht.length];
st.push(0);

for(int curr = 1; curr < ht.length; curr++) {

while(!st.isEmpty() && ht[st.peek()] < ht[curr]) {
int val=curr-st.peek();
nge[st.pop()] = val;

}
st.push(curr);
}

while(!st.isEmpty()) {
nge[st.pop()] = 0;
}

for(int i = 0; i < ht.length; i++) {
System.out.print(nge[i]+" ");
}
}

}

- Anonymous October 26, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

public class NextGreaterElement {

public static void main(String[] args) {
// TODO Auto-generated method stub

int[] ht = {73, 74, 75, 71, 69, 72, 76, 73};
Stack<Integer> st = new Stack<>();

int[] nge = new int[ht.length];
st.push(0);

for(int curr = 1; curr < ht.length; curr++) {

while(!st.isEmpty() && ht[st.peek()] < ht[curr]) {
int val=curr-st.peek();
nge[st.pop()] = val;

}
st.push(curr);
}

while(!st.isEmpty()) {
nge[st.pop()] = 0;
}

for(int i = 0; i < ht.length; i++) {
System.out.print(nge[i]+" ");
}
}

}

- Kamran Shakil October 26, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 3 vote

This problem can be solved in O(n) runtime. We need to do the calculation backward.

vector<int> T={73, 73, 75, 71, 70, 76, 72};
    	vector<int> wait_time(T.size());

    	wait_time[wait_time.size()-1]=NULL;
    	for(int i=wait_time.size()-2; i>=0; i--){
        	if(T[i]<T[i+1]){
            		wait_time[i]=1;
        	}else{
            		if(wait_time[i+1]==NULL){
                		wait_time[i]=NULL;
            		}else{
                		wait_time[i]=wait_time[i+1]+1;
            		}
        	}
    	}

- Anonymous November 23, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Hello, but this code is wrong. Since, it generates wrong output when compiled, but when performed manually it is perfect and goes good. Please check it once again.

- Mohit Patel March 07, 2019 | Flag
Comment hidden because of low score. Click to expand.
-1
of 1 vote

/*
Given a list of daily temperatures, produce a list that, for each day in the input, tells you how many days you would have to wait until a warmer temperature.
[73, 74, 75, 71, 70, 76, 72] -> [1, 1, 3, 2, 1, nothing, nothing]
November 22, 2017  
*/
Solution ::
#include <bits/stdc++.h>
using namespace std;

int main(){
    vector<int> T={73, 74, 75, 71, 70, 76, 72};
    	vector<int> wait_time(T.size());

    	wait_time[wait_time.size()-1]=0;
    	for(int i=wait_time.size()-2; i>=0; i--){
        	if(T[i]<T[i+1]){
            		wait_time[i]=1;
        	}else{
            		if(wait_time[i+1]==0){
                		wait_time[i]=0;
            		}else{
                		wait_time[i]=wait_time[i+1]+1;
            		}
        	}
    	}
    	for(auto it=wait_time.begin();it!=wait_time.end();it++){
    	    cout<<*it<<" ";
    	}
    return 0;
}

- harrypotter0 November 24, 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