Blog

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.