Before the Shadow Play

Given a linked list, find the middle node. For an odd number of nodes, we want node [n/2]+1; for an even number, we want node [n/2].

The brute force method would run the length of the list, count up the number of nodes, and then start over from the beginning, counting off the appropriate number.

However, if we think about what the pointers do (one moves all the way, one moves halfway), we can do both at the same time, and use the “I ran off the end” condition to know when to check the pointer trying to get to halfway.

To do this, we run a fast pointer and a slow one, just like the loop detector tortoise and hare (and I’m patting myself on the back for having that insight), but in this case we use the fact that the lagging pointer moves exactly half as fast to ensure that it’s only gone halfway when the fast pointer runs off the end.

I had a little trouble getting the conditions right, but the final version that hits the right spots is this one:

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func middleNode(head *ListNode) *ListNode {
    // tortoise and hare solution
    if head == nil {
        return nil
    }

    p := head
    q := head
    // we're not at the end, and there's at least one node past
    // this one, so q.Next.Next to jump forward 2 is valid.
    for q != nil && q.Next != nil {
        q = q.Next.Next
        // p moves forward one so that it will have moved half
        // as far. When q runs off the end, p will be at the halfway
        // point.
        p = p.Next
    }
    return p
}

This is clever in that it comes up with a nice way to combine the two actions, but not “clever” in the sense of “how does this even work”. This feels like a good strong choice rather than a “look how clever I am with character values” fragile one.

Given an array of integers, is there at least one duplicate in it?

Again we’re counting things, but since we’re really caring about existence, the condition can be wrapped into the count loop:

func containsDuplicate(nums []int) bool {
    counts := map[int]int{}
    for i:=0; i < len(nums); i++ {
        if _, ok := counts[nums[i]]; ok {
            return true
        }
        counts[nums[i]]++
    }
    return false
}

We look to see if we’ve counted this at least once, and if we have, there’s no more work to do. If we never count something twice, then the answer is false, and we’ve only done one pass at the most over the array.

Speed 65%, memory 5%.

func containsDuplicate(nums []int) bool {
    counts := make(map[int]struct{})
    for _,i := range(nums) {
        if _, ok := counts[i]; ok {
            return true
        }
        counts[i] = struct{}{}
    }
    return false
}

Better on memory because it uses an empty struct as the sentinel value instead of an int, and much faster: 94% CPU, 37% memory. Definitely going to put this in my bag of tricks.

After other problems related to heights, this is an easy one. Find the maximum distance from the root to a leaf in a binary tree.

My first cut had an extra check for the null-left, null-right node, but I realized that the extra call with a nil pointer was faster than an extra conditional in the main path.

**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }
    return 1 + max(maxDepth(root.Left), maxDepth(root.Right))
}

func max(a, b int) int {
    if a >= b {
        return a
    }
    return b
}

100% on speed, 26% on memory. Finished about as fast as I could type it.

You are given two strings, possibly of different lengths, and you are to add them as if they were binary numbers, returning the result as a string.

My first cut was to use an iterator function to scan over the strings, delivering the digits in the order I want them, then summing them via a switch statement. Getting the carry right was the only real issue.

func addBinary(a string, b string) string {
    if a == "0" {
        return b
    } else if b == "0" {
        return a
    } else {
        iterA := nextDigit(a)
        iterB := nextDigit(b)
        max := len(b)
        if len(a) > max {
            max = len(a)
        }
        carry := 0
        sum := ""
        for i:=0; i < max; i ++ {
            x := iterA()
            y := iterB()
            switch x+y+carry {
                case 0:
                sum = "0" + sum
                case 1:
                sum = "1" + sum
                carry = 0
                case 2:
                sum = "0" + sum
                carry = 1
                case 3:
                sum = "1" + sum
                carry = 1
            }
        }
        if carry != 0 {
            sum = "1" + sum
        }
        return sum
    }
}

func nextDigit(s string) func() int {
    digits := []byte(s)
    i := len(digits)-1
    var one byte = '1'
    return func() int {
        if i >= 0 {
            j := digits[i]
            fmt.Println(j)
            i--
            if j == one {
                return 1
            } else {
                return 0
            }
        } else {
            return 0
        }
    }
}

This is quite slow: 5th percentile in speed, 19th percentile in memory. Let’s look at speed hacks. The call to the closure for every digit is probably hurting both of those, so let’s inline the logic and Cheaty McCheatface the values so we’re working with ints as much as possible:

unc addBinary(a string, b string) string {
    if a == "0" {
        return b
    } else if b == "0" {
        return a
    } else {
        ascan := len(a) - 1
        bscan := len(b) - 1
        carry := 0
        sum := ""
        for ascan >= 0  || bscan >=  0 {
            var aVal, bVal int
            if ascan < 0 {
                aVal = 48
            } else {
                aVal = int(a[ascan])
                ascan--
            }
            if bscan < 0 {
                bVal = 48
            } else {
                bVal = int(b[bscan])
                bscan--
            }
            switch aVal+bVal+carry {
                case 48+48+0:
                sum = "0" + sum
                case 48+49+0:
               sum = "1" + sum
                carry = 0
                case 49+49+0:
                sum = "0" + sum
                carry = 1
                case 49+49+1:
                sum = "1" + sum
                carry = 1
            }
        }
        if carry != 0 {
            sum = "1" + sum
        }
        return sum
    }
}

func nextDigit(s string) func() int {
    digits := []byte(s)
    i := len(digits)-1
    var one byte = '1'
    return func() int {
        if i >= 0 {
            j := digits[i]
            fmt.Println(j)
            i--
            if j == one {
                return 1
            } else {
                return 0
            }
        } else {
            return 0
        }
    }
}

Better. 100% on speed, but 18% on memory, no doubt all those string allocations. Let’s append and then reverse the output instead.

func addBinary(a string, b string) string {
    if a == "0" {
        return b
    } else if b == "0" {
        return a
    } else {
        ascan := len(a) - 1
        bscan := len(b) - 1
        max := ascan
        if bscan > ascan {
            max = bscan
        }
        // ensure we only allocate once
        byteString := make([]byte, max+2)
        optr := max+1
        carry := 0

        for ascan >= 0  || bscan >=  0 {
            var aVal, bVal int
            if ascan < 0 {
                aVal = 48
            } else {
                aVal = int(a[ascan])
                ascan--
            }
            if bscan < 0 {
                bVal = 48
            } else {
                bVal = int(b[bscan])
                bscan--
            }
            switch aVal+bVal+carry {
                case 48+48+0:
                //sum = "0" + sum
                byteString[optr] = 48
                optr--
                case 48+49+0:
                //sum = "1" + sum
                byteString[optr] = 49
                optr--
                carry = 0
                case 49+49+0:
                //sum = "0" + sum
                byteString[optr] = 48
                optr--
                carry = 1
                case 49+49+1:
                //sum = "1" + sum
                byteString[optr] = 49
                optr--
                carry = 1
            }
        }
        if carry != 0 {
            byteString[optr] = 49
        } else {
            optr++
        }

        sum := string(byteString[optr:])
        return sum
    }
}

Significantly harder to get right (remembering to fix all of the magic numbers is a particular pain) but now memory usage is at the 78th percentile, which is a huge boost. I’d call that a winner, modulo the dependencies we’ve added to make the memory usage smaller.

Given an array of n integers, find the majority element (the element whose count is >= [ n / 2]).

Count means map.

func majorityElement(nums []int) int {
    // Count means map.
    counts := map[int]int{}
    for _,v := range(nums) {
        counts[v]++
    }
    targetCount := len(nums) / 2
    currentMaxCount := 0
    target := -9999999999
    for k,v := range(counts) {
        if v > targetCount && v > currentMaxCount {
            currentMaxCount = v
            target = k
        }
    }
    return target
}

Scored top 90% on time, top 40% on memory. But if you know the trick (Moore’s candidate algorithm)…

func majorityElement(nums []int) int {
    // "If you know the trick"...Moore's voting algorithm
    count := 0
    var target int
    for i := 0; i < len(nums); i++ {
        if count == 0 {
            target = nums[i]
            count++
        } else if nums[i] == target {
            count++
        } else {
            count--
        }
    }
    return target
}

Gets us to 94% time, 71% memory. Using range() causes Go to use more memory (drops to 19%!).

The “best” algorithm is not that much better, so I’ll call my solution good.

Singly-linked list, reverse it.

This is the cycle() function from “two queues as a stack”, but I somehow had some problems getting it right out of the gate.

It’s the same basic thing: if the list is empty, you’re already done. Else, pop a node off the old list, push it onto the new one, return the pointer to the new list.

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    var newhead *ListNode
    var p *ListNode
    for {
        if head == nil {
            break
        }
        p = head        // point to head of current list
        head = head.Next // drop head node from list
        p.Next = newhead // append new list to p
        newhead = p      // save new list
    }
    return newhead
}

Interesting scoring – top 77% CPU, top 66% memory.

Good enough, I think.

Given a set of upper and lowercase letters, what is the longest possible palindrome for this set of letters?

I chose to do this with a pair of hashes to count the letters overall; the even counts can just be added. For the odd counts, add the largest count, then for the remaining counts, reduce them by one (since there has to be an even number of them to preserve symmetry), and add those to the total.

func longestPalindrome(s string) int {
    // More breaking down into runes
    letters := []rune(s)
    letterMap := map[rune]int{}
    for _,c :=range(letters) {
        letterMap[c]++
    }
    // any letter with an even count can be included
    // any letter with an odd number of occurrences
    // can be included if:
    // - it's even (so it's always symmetric)
    // - it's the letter with the largest odd count (also symmetric)
    // - it's a letter with at least a 3 count (once the largest odd
    //   count is removed, reduce odd counts by 1 and they're
    //   also symmetric)
    // Walk through the map and record
    // - the even counts
    // - the largest odd count
    // - the smaller odd counts, reduced by one
    palindromeLength := 0
    largestOddCount := 0
    var largestOddKey rune
    oddKeys := map[rune] int{}
    for k, v :=range(letterMap) {
        if v % 2 == 0 {
            palindromeLength += v
        } else {
            // odd. is this the largest odd count yet?
            if v > largestOddCount {
                largestOddKey = k
                largestOddCount = v
            }
            // Store the letter with it's count reduced by 1
            // so it can be added symmetrically.
            oddKeys[k] = v-1
        }
    }
    if largestOddCount != 0 {
        // there's at least one odd count.
        // delete the key of the max odd count, and add the count
        // to the palindrome length.
        palindromeLength += largestOddCount
        delete(oddKeys, largestOddKey)
        // the rest of the odd count letters can now be added.
        // the one-occurence letters/odd-occurrence letters
        // have been reduced by one, so either a) the count is
        // now zero, because there was only one occurrence of 
        // the letter, or it's an even numer now (it would not 
        // have been added if it was odd, and we reduced it by 1,
        // so it HAS to be even now -- whether zero or another even
        // number).
        for _, v :=range(oddKeys) {
            palindromeLength += v
        }
    } else {
        // there was no odd-numbered count, and we've already
        // added the even count. Nothing else to do.
    }
    return palindromeLength
}

Scorewise, it’s not that great – top 67% in time, bottom 10% in memory, but it was done fairly fast, so I’m grading it acceptable. I think you could do better with arrays and converting the rune values to indexes, but this falls into the “yes, I could optimize it that way, but this will always work” category.

You have an N step staircase that you can climb either 1 or 2 steps at a time. How many ways are there to climb it?

It was clear that this was a recurrence relation, and my instinct was to cache the computed values. This would be a better attack for a more complex problem; this is just a Fibonacci sequence!

I did do the cached one first, and I am very proud of myself for properly passing the cache through:

func climbStairs(n int) int {
    // this smells of caching...and a Fibonacci recurrence.
    // we know that if we're at N, it takes 0 steps to finish.
    // if we're at n - 1, there is one option: take 1 step.
    // if we're at n - 2, there are two options, 2 1 step, or 1 2 step.
    cache := map[int]int{
        0: 0,
        1: 1,
        2: 2,
    }
    return assist(n, &cache)
}

func assist(n int, cache *map[int]int) int {
    if steps, ok := (*cache)[n]; ok {
        return steps
    }
    (*cache)[n] = assist(n-1, cache) + assist(n-2, cache)
    return (*cache)[n]
}

A huge winner on runtime: 100%! But poor on memory: bottom 9%. An iterative Fibonacci calculation’s probably going to win on this one…Interestingly, it doesn’t! Runtime 82%, memory 33%.

func climbStairs(n int) int {
    // this smells of caching...and a Fibonacci recurrence.
    backTwo := 1
    backOne := 2
    sum := 0
    if n == 1 {
        return 1
    }
    if n == 2 { 
        return 2
    }
    for current := n; current > 2; current-- {
        sum = backOne + backTwo
        backTwo = backOne
        backOne = sum
    }
    return sum
}

Off to the solutions to see what’s there.. the most compact iterative solution still isn’t any better on memory, but is the same speed as the cached one I wrote:

func climbStairs(n int) int {
    next, secondNext := 0, 1
    for ; n > 0; n-- {
        next, secondNext = secondNext, next + secondNext
    }
    return secondNext
}

I’ll call this a win, and ++ for dynamic programming.

Given a magazine string, check to see if a ransomNote string can be composed by extracting characters from magazine. The count of ‘a’, ‘b’, ‘c’, etc. in magazine must be >= the count needed to compose ransomNote.

In another language, I might sort the strings and then compare them, but Go has no built-in string sorting, so putting the “I need to get this done” hat on, I chose building a map of characters in magazine and then progressively checking the letters in ransomNote to see if we either can’t find a needed letter, or run out.

I needed to go look up the syntax to convert a string to a rune array (it’s []rune(string), which is a weird-ass syntax), but otherwise it was pretty easy.

Not the most efficient possible: top 72% in speed, bottom 11% in memory, but I’d choose it if I was actually doing it in code I needed to get done. Also extremely straightforward.

Faster solutions take advantage of the characters a) being ASCII and b) being all lower-case; I’d argue against them in a real-world situation because any bad data would cause them to fall over with an array bounds issue. My solution could parse text in Nazca and still work.

func canConstruct(ransomNote string, magazine string) bool {
   // Add the magazine chars to a map of map[rune]int, incrementing
   // for each rune found.
   // walk through the note, decrementing the char counts as we go.
   // if we ever hit a rune that is not in the map, or whose count is 0,
   // then return false. Else return true.
   magazineMap := make(map[rune]int)
   for _, c := range([]rune(magazine)) {
       magazineMap[c]++
   }
   for _, c := range([]rune(ransomNote)) {
       if _, ok := magazineMap[c]; ok {
           if magazineMap[c] < 1 {
               return false
           } else {
               magazineMap[c]--
           }
       } else {
           // char not found
           return false
       }
   }
   return true
}

Given a function isBadVersion and a range of versions from 1 to N, find the lowest-numbered version that is “bad” as efficiently as possible.

This is another binary search, and I had a little less trouble with it. A few more and I’ll be able to knock one out right the first time. Since there weren’t any pointers or indexes or arrays to manage, this was easier. Still got tripped up on the order of testing, but when I sat down and delineated the terminal cases by hand I was able to easily code it.

Performance was excellent: 100% on CPU time, 95% on memory. Would be a win in an interview.

/** 
 * Forward declaration of isBadVersion API.
 * @param   version   your guess about first bad version
 * @return true if current version is bad 
 *	   false if current version is good
 * func isBadVersion(version int) bool;
 */

func firstBadVersion(n int) int {
    // Binary search it.
    // n is candidate.
    lowBound := 1
    highBound := n

    if isBadVersion(lowBound) {
        // short-circuit: if lowest possible version is bad,
        // no search is needed.
        return lowBound
    }

    // Now search between the bounds for the switchover point. Low is good,
    // high is bad.
    for {
        fmt.Println("Bad version between", lowBound, highBound)
        midpoint := (highBound+lowBound) / 2
        isBad := isBadVersion(midpoint)
        if isBad {
            highBound = midpoint
            if midpoint == lowBound+1 {
                 // midpoint is 1st bad above lowbound (known good)
                return midpoint
            }
        } else {
            lowBound = midpoint
            if highBound == midpoint+1 {
                // midpoint is good, 1 above is bad, so that's it
                return highBound
            }
        }
    }
}

Weirdly, removing the debug made it slower. 81st percentile CPU.

Which pretty much goes to show that trying to rate efficiency of code via leetcode is probably a bad idea.