leetcode month, day 1: Twosum and Add Two Numbers

Well, these were fun, and definitely showed me I’m not ready to walk into an interview at the moment!

Twosum

Twosum is an easy challenge: you are given an array of numbers and a target value; your job is to find the only two numbers at different indexes in the array that sum to the target value and return those two indexes.

The brute-force strategy just repeatedly walks through the array, trying to find the right pair of numbers. This ends up being O(n^2) because we essentially run over the upper triangle of a square of the elements of the array> If in the example below were looking for numbers that sum to 9, we’d run over the numbers four times finally finding it on the fourth pass, and doing 4+3+2+1 = 10 checks. (We can save operations by precomputing the second term in the sum: subtract the first search value from the target sum, and just compare that against the value in the array at that index instead of summing the two.)

>1  2  3  4  5
 1 >2  3  4  5
 1  2 >3  4  5
 1  2  3 >4  5

But the old Perl adage “when someone says search, consider a hash” comes in handy here. We can precompute exactly the number we want, so if we can make the values the keys of a hash (and we can, as we know that there is only one pair that sums to the target value), then we can make the indexes the values.

We walk through the array twice:

• The first iteration builds the hash by taking each value and inserting it as the key with the index as its value. And since we’re doing one iteration over the whole array anyway at this point, we can check each item as we insert it to see if it hits the target with the first item!
• If we don’t luck out during the insert, then we iterate over items 2 to N, calculating the value we’d need to hit the target, and then doing a hash lookup to see if it’s there The hash lookup is O(1), and the pass over the array (including the load) is also O(1), so we’ve made a pretty good reduction in overall runtime.

Things I’d forgotten in the last year of pretty much nothing but Scala:

• The only loop structure in Go is the for loop.
• var, not val. val is Scala, and as one tries for as much immutable data as possible in Scala, my fingers are trained to type val at every turn.
• Go array initializer syntax. Square brackets, then the type, then the values in curly braces.
• I remembered I needed to make() a map, but used Scala syntax instead of Go syntax trying to specify the types.
• Go does not consider [2]int to be the same as []int. Fair.
• Gotta have the parens for every function. Perl and Scala made me sloppy about that.

Things discovered:

• Adding the “try to catch it in the load pass” made a significant speed difference when the first term was at index 0.
• Putting the first index in the array initializer for the result array instead of assigning it vastly increased the speed of the search loop — I went from the top 75% to the top 95% with that one change.
• The hash solution uses more memory; I was at the 15th percentile on memory, but I’ll definitely take being faster than 95% of the other solutions as better.
• I missed the “must be different indexes” restriction on my first pass; fortunately the second test case was for 6 with [3, 4, 2], and I got a test fail for [0,0].

Here’s the final version. I do comment even when writing these because I can line out the code with comments and put the actual code itself in later. Writing down the assumptions helps clarify them as well (thanks loads, ADHD).

func twoSum(nums []int, target int) []int {
    // Given that
    // - there is only one solution, then all entries must be unique
    // - therefore they can be used as keys to a hash
    // - this means we can iterate O(1) over the array for term 1
    //   and lookup term 2 in the hash, getting its index. No need
    //   for a linear search for it.

    // Fill the hash...and see if we can catch the solution
    // during this pass, since we have to do it anyway.
    locations := make(map[int]int)
    prematch := target - nums[0]
    for i := 0; i < len(nums); i++ {
        if i > 0 && nums[i] == prematch {
            return []int{0, i}
        }
        locations[nums[i]] = i
    }

    // scan the nums, looking for a match.
    // first match wins.
    for i := 0; i < len(nums); i++ {
        result := []int{i, -1}
        term2 := target - nums[i]
        j, ok := locations[term2]
        if ok {
            // Disqualify same-entry match. Missed this first time,
            // thank you test cases.
            if i == j {
                continue
            }
            // Found
            result[1] = j
            return result
        }
    }
    // This is a "should not get here"; meant to show me if I've totally
    // blown the loop.
    panic("did not find a solution")
}

Add two numbers

This one was recommended by leetcode as a “hot” problem, and it looked like fun, so I did it. It’s not in the Grind 75 list, but it’s a nice pointer manipulation problem, and I was a bit stale on pointers.

The function is passed two linked lists; each list has an integer from 0-9 and a pointer to the next digit. The digits are presented in right-to-left order. The function is to take these two lists, and return a new list that represents the sum of the two numbers. Of course, the lists can be different lengths; if they are, then the list that runs out first is treated as if it were returning zeroes for the purposes of the sum.

It was instantly clear that the challenge here would be maintaining the scan pointers for the two numbers and the result, and that trying to do bookkeeping for all of it in the loop would suck. So my approach was to construct a function to return a closure that would follow the rules for reading the numbers off the list:

• If the scan pointer is null, return 0 and false
• If the scan pointer is not null, return the node’s value and true, advancing the pointer to the next node.

This meant that the list management was dead simple:

first  := iterator(L1)
second := iterator(L2)

fVal, fState := first()
sVal, sState := second()

Each call to the first and second closures returns the next value to use in the sum; when both are false, the sum is complete.

So all I had to manage in the loop was the scan pointer for the sum, and the carry from the addition operation: adding it in, clearing it, and recalculating it after the current operation.

Things learned/relearned:

• Had to remember when I needed * and when I didn’t for variable types.
• The first run segfaulted. I realized that I’d mismanaged the scan pointer; I needed to save the root node, and then scan forward while doing the operations.
• Once I fixed that, I found out I wasn’t clearing the carry. Whoops. Easy to fix.
• The closures worked perfectly.
• The “end the loop” and “restart the loop” keywords are break and continue. Trivial, but I had to go look it up.

I did make one major mistake: I missed that the output was supposed to be another list, and started calculating the sum as an integer. This wasn’t too terribly off from the desired solution; I had figured out that I’d need the carry tracking, and I had a power variable that I was multiplying by 10 to switch columns in the output variable, but that probably wasted 5 or 10 minutes and might have made the difference between a pass and a fail in an interview.

It was pretty easy to switch to the list building, but lesson hammered home again: be sure you read the problem statement correctly and know what the output is. Confirming with the interviewer that I got the details right is probably a good idea in a timed problem.

**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
    // The tricky bit with this one is going to be watching out
    // for the end of the list.

    // the dumbest and easiest way is to have a bool for each
    // list; when one list has no more entries, we set its bool
    // to false and return a zero value for it.

    // when both lists return a false value, we're done.
    first := iterator(l1)
    second := iterator(l2)
    var currentDigit *ListNode
		var root *ListNode
		carry := 0

    for {
        fVal, fState := first()
        sVal, sState := second()

        if (!fState && !sState) {
            // run off the end of both. Stop loop, finalize sum.
						fmt.Println("Done")
            break
        }
        // At least one still returning a value. (The other returns 0
        // if there's no value.)
        // Sum the digits and the curent carry; if > 9,
        // take mod 10 and set the carry to 1. (no two
        // digits can sum to > 18).
        digitSum := fVal + sVal + carry
        carry = 0
        if digitSum > 9 {
            carry = 1
            digitSum = digitSum - 10
        }
        // Add space for a new digit, append it, continue.
        if currentDigit != nil {
            currentDigit.Next = &ListNode{digitSum, nil}
		    currentDigit = currentDigit.Next
        } else {
		    // Create and save root digit
            currentDigit = &ListNode{digitSum, nil}
			root = currentDigit
        }
    }
    if (carry != 0) {
        // last addition had a carry we need to keep
        currentDigit.Next = &ListNode{carry, nil}
    }
    return root
}

func iterator(l *ListNode) func()(int, bool) {
    // Close over the pointer.
    p := l
    return func()(int, bool) {
        if p == nil {
            // Reached end. Keep returning 0 and false.
            return 0, false
        } else {
            // Capture next digit, advance pointer,
            // return next digit and true. If new pointer
            // is nil, we'll just return 0 and end-of-list signal
            // forever.
            v := p.Val
            p = p.Next 
            return v, true
        }
    }
} 

So how’d I do overall in comparison? Pretty fuckin’ good. I was in the top 95% on speed, and the top 91% in memory use. I suspect that managing all the bookkeeping in the loop might make it a tad faster (no call overhead for the closures), but at the cost of significantly more complexity. This solution is fast and small, and I’ll take it.

Conclusions

• My Go is pretty good. I didn’t spend a huge amount of time chasing bugs, and had it in a couple tries. I have a good grasp of the concepts and know mostly how to do things.
• My Go is fairly stale. I don’t remember how to say things!
• I had to look up a lot of things that I should have just remembered, like len() for array length (not .len, that’s Scala!). I need this practice!

Tomorrow I’ll start off with Valid Parentheses.