I took up Russell’s generous offer to provide me with a mock interview for this leetcode problem. Because Russ had instructed me to just find a problem I hadn’t done before and to not look at it, I didn’t realize that this problem worked with linked lists. I had read about linked lists, but never used one, so I ended up having to figure that out during the interview.
This was what the failing code looked like at that point:
var mergeTwoLists = function(list1, list2) {
if (list1 === null) return list2
if (list2 === null) return list1
let head
let current
function iterateNodes(list1Pointer, list2Pointer){
if (list1Pointer === null){
return list2
}
if (list2Pointer === null){
return list1
}
let current
if (list1Pointer.val >= list2Pointer.val){
current = list2Pointer
list2Pointer = list2Pointer.next
} else if (list1Pointer.val < list2Pointer.val){
current = list1Pointer
list1Pointer = list1Pointer.next
} else {
console.log("unexpected case")
}
console.log(current.val)
current.next = iterateNodes(list1Pointer, list2Pointer)
return current
}
return iterateNodes(list1, list2)
};^ This was after 45 minutes, the allotted time for the interview. Russ invited me to keep going and see this process to it’s end.
Russ was the one to realize my mistake. If you look, you can see that in the base cases* (a term I learned today) of the iterateNodes function, I am accidentally returning list1 and list2, not list1Pointer and list2Pointer.
I could have avoided this mistake by declaring my recursive function outside of the main function, or even by simply doing everything in one function. I do stand by my call of writing a second function however, as it was easier for me to reason about recursion that way.
Aside
In 7) Depth First Search, Benjamin Arnev extolls additional virtues of defining a second function inside of your first in the first. In this article, however, it’s definitely the villain.
After I fixed this mistake, this is what I ended up with:
// Requirements and constraints
// must remain sorted
// if both lists are empty, return []
// if one list is empty and the other has an element in it, return a list with element 0
// all values comparable, values are unbounded
// lengths of lists: fit in memory
// I will be given the heads of each list - the first nodes of each list
// may be given an empty list
// To do
// how to test for an empty list
// ListNode
// Each node has a val field -> integer
// They are comparable, val field can have less than greater than
// Example data
// example1:
// list1[1, 2, 4]
// list2[1, 3, 4]
// output: [1, 1, 2, 3, 4, 4]
// Doesn't matter if two nodes have the same value - they are interchangeable in sorting
// If the value is lower than the other, I have to pick it first
// Notes
// Probably don't use a map to index the values - they may not be ints
/**
* Definition for singly-linked list.
* function ListNode(val, next) {
* this.val = (val===undefined ? 0 : val)
* this.next = (next===undefined ? null : next)
* }
*/
/**
* @param {ListNode} list1
* @param {ListNode} list2
* @return {ListNode}
*/
/* (list1 head)
node.val = 1
node.next = {node.val === 2}
/*
/* (list2 head)
node.val = 1
node.next = {node.val == 3}
*/
function iterateNodes(list1Pointer, list2Pointer){
if (list1Pointer === null){
return list2Pointer
}
if (list2Pointer === null){
return list1Pointer
}
let current
if (list1Pointer.val >= list2Pointer.val){
current = list2Pointer
list2Pointer = list2Pointer.next
} else if (list1Pointer.val < list2Pointer.val){
current = list1Pointer
list1Pointer = list1Pointer.next
} else {
console.log("unexpected case")
}
console.log(current.val)
current.next = iterateNodes(list1Pointer, list2Pointer)
return current
}
var mergeTwoLists = function(list1, list2) {
if (list1 === null) return list2
if (list2 === null) return list1
let head
let current
return iterateNodes(list1, list2)
};It took us another 10 minutes to take this function to fruition. Afterwards, I went back over it and cleaned it up to demonstrate to myself that a second function wasn’t necessary:
function mergeTwoLists(list1, list2){
if (list1 === null) return list2
if (list2 === null) return list1
let current
if (list1.val >= list2.val){
current = list2 // we set current to the head of list2
list2 = list2.next
// now that current is set, we can safely change the list2 head to NEXT node in list2, keeping things moving
} else if (list1.val < list2.val){
current = list1
list1 = list1.next
} else {
console.log("unexpected case")
}
current.next = mergeTwoLists(list1, list2)
return current
}Positives
- I am proud of how well I was able to figure out how to use linked lists under pressure
- I am satisfied with my process of levelly walking back through my code with actual values when I did run into a bug
Programming Takeaways
- Don’t declare functions inside other functions. Not only does it allow for variable collisions like the one above - it’s also less performant
and readable- Alternate take in 7) Depth First Search
- In JavaScript especially, scan for variable name conflicts as a first step when addressing bugs
- Avoid the blanket anxiety that there is something fundamentally wrong with an implementation - even if there is, there is a specific bug that causes it. Look for those, and permit those bugs to be trivial
Lived
The last point continues to track! I just had an interview with Figma and although my general implementation was spot on, there was a single detail in my way from solving my interview problem. As my hail mary in the last three minutes, I decided to modify my implementation, further showing that under pressure I tend to doubt, myself. But once again - the implementation was generally good. I could have benefited more from calmly reviewing my code than by supposing a major anti-pattern.
Code Interview Takeaways
- If an interview is asking questions during the whiteboard or implementation phase, they are probably trying to tell you something
- Ask for examples to run in your code - they may tell you something about the cases you need to worry about most
- Listen carefully to the interviewer - it is psychologically difficult not to help people when you know the answer, and they may slip up and give you major hints. At the very least, it is easy to slip into a more collaborative mode, and you can certainly use a collaborator
- Don’t panic
- Do ask very basic questions about the problem
- Talk through your process, and if you get lost, start from first principles, not some grand idea of what you “should” do
- Write Psuedocode - it can be turned into real code
- Write real code whenever possible, and if you aren’t sure it’s ready, just comment it - this will save time later
Lived
On the the subject of listener carefully to an interviewer, I had the advantage here of being in the same room as them. However, online, using a multiscreen setup, you may be looking at another screen much of the time instead of the interview. At this time, I believe this is a mistake - there is a lot of information conveyed by their faces, gestures, and mannerisms. I believe that keeing a videocall window next to the IDE as much as possible is valuable.
*Base Case the part of a recursive function that is not recursive. In this example, conditionals that set out “current” linked list
Things to think about in the future
- handles, symlinks, references, pointers - how are these things different? Relevant to the way
javascriptworks here in lines5and6of the function we defined. We set current tolist2, and then we change list 2. I had a nightmare moment where I though, wait we’re changing whatlist2means andcurrentreferenceslist2, aren’t we also changing current?? But no, in javascript, settingcurrenttolist2doesn’t pointcurrentto the referencelist2itself, but the base object thatlist2refers to in memory, so we’re safe.
However, I’d still like to understand this better. Are there situations in javascript where we are chaining our references, and if the address one reference points to changes, then the ones downstream do too?
Review of Value Reference Behavior in Javascript
Okay I’ve gotten around to refreshing how values are referenced in JS, depending on variable type!
In JavaScript, simple values like strings and numbers aren’t references. That is to say, if var1 and var2 are both strings and var2 is set to the value of var1, you can do whatever you want to var1 and var2 will stay the same.
But other data structures in JavaScript, like arrays and Lists, are references rather than the value of those references themselves. So if var2 is set to the value of var1 and these things are arrays or objects, a change to var1 will affect what var2 evaluates to.
Here’s that behavior in simple variables:
But when we are working with arrays and objects, that behavior is different.
If we don’t want this behavior, we can use the spread operator:
If I understand this correct, what we are doing here is getting the value of zuko at that time, similar to what we did with the string and number data types, and we are creating a whole new array or object with the value we receive. Our data structure is still a reference to a value that can change, but it’s now a new data structure with no relation to the original.
Like prince Zuko himself, you have to understand how you are referencing memory (addresses) of the past in order to evaluate the present.
