Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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;
}
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
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;
}
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)) + " ");
}
}
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]<<" ";
}
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;
}
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]+" ");
}
}
}
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]+" ");
}
}
}
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;
}
}
}
/*
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;
}
}
- anurag.iitp November 23, 2017