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.