2024-06-02

🧠 Education

🧠🏰 What makes something memorable?
a-simple-way-to-learn-complex-skills

🏋️ Practice

Revisiting this problem from yesterday.

🎉 Yesterday, while I was happy to get the correct solution on the first try (minus a single “typo” that I found very quickly)
(which I can thank manual testing for… I found so many bugs in the initial implementation)
⌛ It took 60 minutes.
⚡ In an interview, I’ll need to complete a problem in something closer to 15 minutes.

So how can we improve?

Well, what took so long?
The problem is very fiddly.
There are null pointers to check and next pointers to rewire…
It takes a lot of focus and working memory to keep track of all of that state while coding up a solution AND while testing the solution.
So rather than doing everything in a single pass…

We can split the problem into simpler sub problems

In this case, we

1. collect the nodes of each list into its own array

This handles all of the next-pointer dereferencing (and associated null checks)
It’s also nicely extractable into its own helper.
We implement it in isolation, which is easier (and less error-prone) than implementing the whole problem
And we use it in 2 places in the larger problem.
Importantly, we also return a more well-typed object to work with.
An array of ListNodes, none of which are null.

2. merge-sort the arrays

This is the same basic logic that was at the core of yesterday’s solution.
But it’s easier because there aren’t any null checks to worry about.
(Although, checking for an empty array is similar.. but we still have fewer checks to worry about)

3. link the nodes in the merge-sorted array

Given an array of nodes, it’s very simple to link one to the next.

🥁 Results

🎉 16:29
Dramatically faster.
Initial implementation was faster (<7m).
Testing was much faster (<10m).
It’s amazing how much faster testing is when we don’t find any bugs…
Also, I didn’t test the helper functions.
Perhaps it’s valuable to do so (assuming we have the time) but a simpler implementation is easier to be confident in.

Takeaways

Consider alternative solutions
Aim to decompose problems into simpler, easier sub-problems.

Problem statement

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.

Solution

/**  
 * Definition for singly-linked list.  
 * class ListNode {  
 *     val: number  
 *     next: ListNode | null  
 *     constructor(val?: number, next?: ListNode | null) {  
 *         this.val = (val===undefined ? 0 : val)  
 *         this.next = (next===undefined ? null : next)  
 *     }  
 * }  
 */  
  
/* Plan  
1. collect the nodes of each linked list into an array  
2. merge the lists  
3. link the nodes  
4 return the head  
  
// initial implementation: <7m  
// finished 4 manual tests: <16m  
*/  
const collect = (l: ListNode | null): ListNode[] => {  
  const results = []  
  while (l) {  
    results.push(l)  
    l = l.next  
  }  
  return results  
}  
  
const link = (ls: ListNode[]): ListNode | null => {  
  if (!ls.length) {  
    return null  
  }  
  const result = ls.shift()  
  let cursor = result  
  while (ls.length) {  
    cursor.next = ls.shift()  
    cursor = cursor.next  
  }  
  cursor.next = null  
  return result  
}  
  
function mergeTwoLists(list1: ListNode | null, list2: ListNode | null): ListNode | null {  
  // 1. list1=[] list2=[]  
  // 2. list1=[1] list2=[]  
  // 3. list1=[] list2=[2]  
  // 4. list1=[3,5] list2=[4,6]  
  const l1 = collect(list1)  
  // 1. l1=[]  
  // 2. l1=[1]  
  // 3. l1=[]  
  // 4. l1=[3,5]  
  const l2 = collect(list2)  
  // 1. l2=[]  
  // 2. l2=[]  
  // 3. l2=[2]  
  // 4. l2=[4,6]  
  const merged = []  
  while (l1.length || l2.length) {  
    if (!l1.length) {  
      merged.push(l2.shift())  
      // 3. merged=[2] l2=[]  
      // 4.4 merged=[3,4,5,6] l2=[]  
    } else if (!l2.length) {  
      merged.push(l1.shift())  
      // 2. merged=[1] l1=[]  
    } else if (l1[0].val <= l2[0].val) {  
      merged.push(l1.shift())  
      // 4.1 merged=[3] l1=[5]  
      // 4.3 merged=[3,4,5] l1=[]  
    } else {  
      // 4.2 merged=[3,4] l2=[6]  
      merged.push(l2.shift())  
    }  
  }  
  return link(merged)  
  // 1. []  
  // 2. [1]  
  // 3. [2]  
  // 4. [3,4,5,6]  
};

🏋 More Practice

LeetCode 2486. Append Characters to String to Make Subsequence

Problem Statement

You are given two strings s and t consisting of only lowercase English letters.
Return the minimum number of characters that need to be appended to the end of s so that t becomes a subsequence of s.
A subsequence is a string that can be derived from another string by deleting some or no characters without changing the order of the remaining characters.

🪞 Reflections

I didn’t immediately understand the problem, but rather than dwell on the statement for too long, I moved to the examples to clarify my understanding
I attempted to guess the answers to the examples before looking at the provided answers
Solving the example problems in my head gave me some intuition for an algorithmic approach
I didn’t consider any alternative approaches.
Is this bad?
I’m not sure.
It seemed clear that this approach was optimal in terms of worst case algorithmic complexity (if reading the input is O(N), and you must read the whole input to solve the problem, you can’t do any better than O(N)).
The approach also seemed simple enough to implement.
Based on these factors, I decided that my time was probably best spent getting right into the implementation rather than trying to imagine alternative approaches.
It seemed to work out in this example, but maybe I just got lucky.
In general, it’s probably still worth attempting to consider alternative approaches, but I’m not really sure if it’s always worth the time in an interview context.
I’m finding this method of manual testing to be pretty effective:

Write out my manual tests as comments describing the state of key variables as I walk through the code
Write the state for changed variables under the line of code that changes them.
- I don’t know why, but it seems more intuitive for me for the comments to be under the line of code.
- When I started using this technique a few days ago, I tried writing the comment above the line of code responsible for the state change, but when referencing previously written lines of state, I found myself erroneously looking below the lines of code naturally, which is what prompted me to change.
Prefix the comment with the test case number
- When in a loop, append the loop number to the test number
write the name of the variable = state
- explicitly writing the name of the variable in the comment avoids later confusion
- and copy/paste doesn’t take much time (especially with vim keybindings: yyp to copy and paste, then edit as necessary)
for non-primitive objects, an intuitive short-hand seems to be a good enough representation
- e.g. [c,b,a] is a good enough representation of a stack containing 3 single-character strings
if a single line changes multiple variables, annotate the new state of both variables on the same line, separated by a space

Definitely test. Always test. Practicing the annotation technique makes it faster and I always find bugs, sometimes quite a few of them, and typically pretty quickly.
I’m not focused on it right now because I’ve already kinda sold myself on it, but the planning step is also incredibly valuable. Think about what to do before doing it. Writing it down clarifies thought and extends our memory.

My Solutions

/*  
minimum characters appended to s such that t is a subsequence of s  
  
Plan:  
First idea:  
1. find the largest prefix of t that is a subsequence of s  
2. the length of the remainder of t is the answer  
  
How?  
Find first occurrence of first character of t in s  
...moving cursor forward  
Find first occurrence of next character of t in s  
...repeat until we run out of t or s  
if we ran out of t, return 0  
if we ran out of s, return length of remainder of t  
  
1. Scan s left to right  
2. While scanning, drop characters from t as they are found  
3. if we run out of s, return length of t  
4. if we run out of t, return 0  
  
Run-time complexity: O(N) where N is the length of S  
  
implementation complete: 10:04  
fixed a couple of bugs during testing  
finished testing & submitted at 17:38  
perfect on first submission!  
*/  
function appendCharacters1(s: string, t: string): number {  
  // 1. s='' t=''  
  // 2. s='a' t=''  
  // 3. s='' t='a'  
  // 4. s='zaxcb' t='abc'  
  const stack = t.split('').reverse().filter(x => !!x)  
  // 1. stack=[]  
  // 2. stack=[]  
  // 3. stack=[a]  
  // 4. stack=[c,b,a]  
  for (let i = 0; i < s.length && stack.length; i++) {  
    // 4.1 s[0]=z  
    // 4.2 s[1]=a  
    // 4.3 s[2]=x  
    // 4.4 s[2]=c  
    // 4.5 s[2]=b  
    if (s[i] === stack[stack.length - 1]) stack.pop()  
    // 4.1 stack=[c,b,a]  
    // 4.2 stack=[c,b]  
    // 4.3 stack=[c,b]  
    // 4.4 stack=[c,b]  
    // 4.4 stack=[c]  
  }  
  return stack.length  
  // 1. 0  
  // 2. 0  
  // 3. 1  
  // 4. 1  
}  
  
  // slight optimization for fun: drop the stack (untimed)  
function appendCharacters(s: string, t: string): number {  
  // 1. s='' t=''  
  // 2. s='a' t=''  
  // 3. s='' t='b'  
  // 4. s='abc' t='cb'  
  // 5. s='abc' t='b'  
  let j = 0  
  for (let i = 0; i < s.length && j < t.length; i++) {  
    // 4.1 s[0]=a t[0]=c  
    // 4.2 s[1]=b t[0]=c  
    // 4.3 s[2]=c t[0]=c  
    // 5.1 s[0]=a t[0]=b  
    // 5.2 s[1]=b t[0]=b  
    if (s[i] === t[j]) j++  
    // 4.1 j=0  
    // 4.2 j=0  
    // 4.3 j=1  
    // 5.1 j=0  
    // 5.2 j=1  
  }  
  return t.length - j  
  // 1. 0 - 0 = 0  
  // 2. 0 - 0 = 0  
  // 3. 0 - 0 = 0  
  // 4. 2 - 1 = 1  
  // 5. 1 - 1 = 0  
}

bagrounds.org

Explorer