Coding Interview | Stack Questions

Interview Rating:

Do you want to advance this person to the next round (e.g. onsite)?
Yes

Technical Skills: 4/4
Problem Solving Ability: 4/4
Communication: 4/4

Self Review:
How well do you think you did?
3/4

[li-kaiwu]

I love the interviewer. So considerate and fun to work with.

[bijujjacob]

Was curious as to why you cannot do this when iterating from the back of the array. Just figured that you actually can -
The solution remains pretty much the same, i.e. you keep pushing elements and their positions into the stack, but if the element to be pushed is larger than the head of the stack, pop until that condition is false. And before pushing the element into the stack, you can peek on the head to get the position of the next highest element!

[ravi]

just watching these videos makes me nervous. not sure what happens in my actual interview.

[avinashmehtadelhi]

there is a for and a while loop, is the runtime not O(n2)?

[shitalsavekar]

I don't know much about stacks -- Here is something I tried using linked lists -

#include<stdio.h>
#include<stdlib.h>

struct Node {
int temp;
struct Node *tomorrow;
};

void GetForCast(struct Node **);
struct Node * CreateDay(int);
int main()
{
struct Node *Day;
Day = CreateDay(70);
Day->tomorrow = CreateDay(60);
Day->tomorrow->tomorrow = CreateDay(100);
= CreateDay(80);
= CreateDay(50);

GetForCast(&Day);
}
void GetForCast (struct Node **firstDay)
{
struct Node *today = (*firstDay);
struct Node *Backup;
Backup = today;
int wait = 1;
while (today != NULL) {

if (today->tomorrow == NULL )
{
printf("%d ", 0);
today = today->tomorrow;
} else
{
if (today->tomorrow->temp > today->temp) {
printf("%d ", wait);
wait = 1;
today = Backup->tomorrow;
Backup = today;
} else {
wait ++;
today = today->tomorrow;
if (today->tomorrow == NULL) {
printf("%d ", 0);
today = Backup->tomorrow;
Backup = today;
}
}
}
}
}

struct Node * CreateDay(int temp) {
struct Node *a;
a = (struct Node *) malloc (sizeof (struct Node));
a->temp = temp;
a->tomorrow = NULL;
return a;
}


Output : 2 1 0 0 0

[SeemZify]

Oh, this beautiful "gotcha" moment. As soon as I hear about using a stack - oof!
Anyway there are 2 layers in this problem: 1 - find and understand the solution and 2 - Actually write it right
Love your vids

[danielk]

Could you(anyone) please explain when do you pop a value from the stack? And how does that value get added to the result array?

[ialpha]

Since, interviewing.io is having a waitlist :( :(, I am using your videos to simulate the situation. Thanks a lot ! Here is my solution (accepted on Leetcode)
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
if not T:
return []
res = [0 for _ in range(len(T))]
stack = []
for i, t in enumerate(T):
while stack and T[stack[-1]] < t:
idx = stack.pop()
res[idx] = i - idx
stack.append(i)
return res