# F-1 B.S. Job Hunting Diary #01

I am an international student in the U.S. about to graduate from university and get my B.S. in Electrical Engineering and Computer Engineering. I decided to try to find a job instead of going to graduate school. Although I do plan on getting a Ph.D., I thought working for a bit and honing my practical skills would be a good idea. It turned out to be a mistake given the much more xenophobic political climate these days. Regardless, I decided to make the most of the time. I have learned a lot from the grueling search for my first engineering job, and I find myself compelled to share my experience in the form of diaries, especially with students on F-1 visas.

Although I have been to a few technical interviews, I recently had my first coding interview with a startup. The technical part of the interview lasted for a little over 40 minutes and consisted of one problem broken down into three parts. For this first post, I will focus on the coding problem and my thought process of solving it, and thus I won’t get into political discussion or advice for F-1 students.

The interview setting was a typical one-on-one pen-and-paper coding interview. I will present the problem and solution in a conversation style more or less true to what was said. The code presented here is different from what I wrote because I don’t remember exactly what I wrote.

INTERVIEWER: For the first part of the problem, give me an implementation of a FILO stack with push and pop methods. Pushing and popping should be constant time.

ME: OK. My first thought was a linked list where I maintain a tail pointer. For now I will use a doubly linked list for simplicity. What kind of data are we storing?

INTERVIEWER: You can assume we are storing integer.

ME: (Started to write down code while explaining to the interviewer my thought process) For a doubly linked list, I need a struct for the nodes with two pointers and a data variable. I’ll also define a data type for stack, which has only the pointer to the tail for now.

```typedef struct node_t {
int data;
struct node_t *next;
struct node_t *prev;
} node_t;

typedef struct stack_t {
node_t *tail;
} stack_t;
```

ME: I’ll also define a initialization function that returns a pointer to a new stack. The tail of a new empty stack should be set to `NULL`.

```stack_t *stack_create(void)
{
stack_t *new = malloc(sizeof(stack_t));
new->tail = NULL;
return new;
}
```

ME: For push and pop operations, I need to check if the stack is empty first. For `pop`, I also need to check the validity of the previous node before adjusting its next pointer.

```void stack_push(stack_t *stack, int data)
{
node_t *new = malloc(sizeof(node_t));
new->data = data;
new->next = NULL;
new->prev = NULL;

if (!stack->tail) {
stack->tail = new;
return;
}

stack->tail->next = new;
new->prev = stack->tail;
stack->tail = new;
}

void stack_pop(stack_t *stack, int *data)
{
if (!stack->tail) {
data = NULL;
return;
}

*data = stack->tail->data;

if (stack->tail->prev)
stack->tail->prev->next = NULL;

node_t *temp = stack->tail;
stack->tail = stack->tail->prev;
free(temp);
}
```

INTERVIEWER: That looks good. Now for the second part, I want you to implement a method that returns the minimum element in the stack.

ME: OK. Is there a time complexity requirement?

INTERVIEWER: Don’t worry about time complexity for this part.

ME: In that case I’ll just do a linear search through the stack. I don’t need to modify the existing structs and methods. I will iterate through the linked list and look for the minimum value.

```int stack_min(stack_t *stack, int *min)
{
if (!stack->tail)
return -1;

node_t *current = stack->tail;
*min = tail->data;

while (current) {
if (current->data < *min)
*min = current->data

current = current->next;
}

return 0;
}
```

INTERVIEWER: Good. Now for the last part, implement `stack_min` in constant time while keeping push and pop in constant time.

ME: (Thinking while telling the interviewer my thought process.) If memory is not an issue, I could maybe keep a sorted array of every element in the stack. This way I can just access the first element for the min.

INTERVIEWER: Think about the cost of sorting.

ME: Right! That would prevent pushing or popping from being O(1). I can maintain a pointer in the stack that points to the minimum element in the stack. When I push, I just check if the new element is smaller than the current min.

INTERVIEWER: (Thinking) Hmm. But what about when you pop?

ME: Oh! Popping the current min will cause the stack to lose track of the min. What if in each node I also maintain an extra pointer that points to the previous min? This way, when popping off a min, I can update the stack’s min to be the previous min. There would effectively be a chain of mins.

INTERVIEWER: Sounds like it will work.

ME: I will need to change a few things in the existing code.

```typedef struct node_t {
int data;
struct node_t *next;
struct node_t *prev;
struct node_t *prev_min;
} node_t;

typedef struct stack_t {
node_t *tail;
node_t *min;
} stack_t;

stack_t *stack_create(void)
{
stack_t *new = malloc(sizeof(stack_t));
new->tail = NULL;
new->min = NULL;
return new;
}

void stack_push(stack_t *stack, int data)
{
node_t *new = malloc(sizeof(node_t));
new->data = data;
new->next = NULL;
new->prev = NULL;
new->prev_min = NULL;

if (!stack->tail) {
stack->tail = new;
stack->min = stack->tail;
return;
}

stack->tail->next = new;
new->prev = stack->tail;
stack->tail = new;

if (data < stack->min->data) {
stack->tail->prev_min = stack->min;
stack->min = stack->tail;
}

void stack_pop(stack_t *stack, int *data)
{
if (!stack->tail) {
data = NULL;
return;
}

*data = stack->tail->data;

if (stack->tail == stack->min)
stack->min = stack->min->prev_min;

if (stack->tail->prev)
stack->tail->prev->next = NULL;

node_t *temp = stack->tail;
stack->tail = stack->tail->prev;
free(temp);
}
```

INTERVIEWER: Congratulations! You solved it.

What I improved a lot in this interview from previous ones was my communication with the interviewer. I did not silently write code. Instead, I tried to justify everything I wrote to the interviewer. This way I not only got constant feedback, but also showed the interviewer my thought process. This should be applied to other types of interviews as well. Failing to solve a 3-stage BJT amplifier circuit is not a big deal as long as you can show the interviewer your logic and knowledge by verbalizing your thoughts.