## Google Interview Question for Software Engineers

• 3

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

}

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

}

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

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

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

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

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

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

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.

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

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

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

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.

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

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.