Blog

  • leetcode day 16: max depth of binary tree

    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.

  • leetcode day 16: add two binary strings

    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.

  • leetcode day 16: majority element

    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.

  • leetcode day 16: reverse a list

    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.

  • leetcode day 16: longest palindrome

    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.

  • leetcode day 16: climbing steps

    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.

  • leetcode day 16: ransom note

    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
    }
  • leetcode day 16: lowest bad version

    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.

  • Leetcode day 15: a queue from two stacks

    An old favorite, which I got at a Google interview. Not understanding the Google mindset at the time (2007 or so), I had my engineer hat on first, and pointed out that if you’re going to build a data structure, build the damn data structure. It’s ludicrous to build two stacks when you could build one queue in approximately the same amount of time.

    However, the real purpose was “do you understand that pushing onto one stack and then popping items off onto the other reverses their order?”. Sure. OK. Fine. You could ask me “what would happen if…”, but no, it needs to be a no-one-with-any-brains-would-ever-do-this programming problem. (Again, this is a “let’s talk about your algorithm choices in our next 1-1” problem.)

    Anyway, yeah. So I tried with arrays again to start and it was a huge PITA. I tried that for about ten minutes and said, forget this, I’m building it with linked lists.

    So we have a Node that is added at the head to push, and delinked to its tail to pop. Easy-peasy.

    The push operation just adds to the incoming stack, and doesn’t do anything else until we have our first pop, and which point we call the core routine here, Cycle. Cycle pops items one at a time off the in stack and pushes them to the out stack. Now a pop pulls the first item that was pushed, as required, since we’ve just reversed the in stack. I did have one error, caught in the submit, in that you don’t just check for the in stack being empty, but you also need to check for the out stack not being empty. If you don’t, you end up queueing an item out of order. Always wait for the output to be empty before actually cycling.

    I did have to refresh my memory on adding a method to a struct – it’s func (this *Node) Cycle – but otherwise this was almost as much a breeze as the tree inversion.

    I do need to do some exercises on managing arrays better, though — you can’t always use a linked list, especially if you need actual indexing.

    Overall, pleased with the solution: 82nd percentile runtime, but 18th percentile memory. Might be better if I kept the popped nodes on a free list.

    type Node struct {
        Val int
        Next *Node
    }
    
    type MyQueue struct {
        In *Node
        Out *Node
        free *Node
    }
    
    func Constructor() MyQueue {
        return MyQueue{
            In: nil,
            Out: nil,
        }
    }
    
    func(this *MyQueue) Cycle() {
        fmt.Println(">>>cycling in to out")
        if this.In == nil {
            // Nothing to cycle
            fmt.Println(">>cycle empty in")
            return
        }
        if this.Out != nil {
            // Don't cycle yet
            return
        }
        // Pop items off the in stack, push on the out stack
        for {
            current := this.In
            this.In = this.In.Next // Pop In
            fmt.Println("cycle>> pop in", current.Val)
            
            current.Next = this.Out // Push Out
            this.Out = current
    
            current = this.In
            if current == nil {
                break
            }
        }
        // Clear in stack
        fmt.Println("cycle>> clear in")
        this.In = nil
    }
    
    func (this *MyQueue) Push(x int)  {
        // Append to in stack. Leave there until we cycle.
        n := &Node{
            Val: x,
            Next: this.In,
        }
        this.In = n
        fmt.Println(">>push on in", x)
    }
    
    
    func (this *MyQueue) Pop() int {
        if this.Empty() {
            panic("popped empty stack")
        }
        if this.Out == nil {
            this.Cycle()
        }
        value := this.Peek()
        fmt.Println(">>pop Out")
        this.Out = this.Out.Next
        return value
    }
    
    
    func (this *MyQueue) Peek() int {
        if this.Empty() {
            panic("peek on empty stack")
        }
        this.Cycle()
        fmt.Println("peek>>")
        return this.Out.Val
    }
    
    
    func (this *MyQueue) Empty() bool {
        fmt.Println("check for empty")
        return this.In == nil && this.Out == nil    
    }
    
    
    /**
     * Your MyQueue object will be instantiated and called as such:
     * obj := Constructor();
     * obj.Push(x);
     * param_2 := obj.Pop();
     * param_3 := obj.Peek();
     * param_4 := obj.Empty();
     */

    Editorial note: other solutions submitted really stretch the definition of stack – a lot of them do do appends and slices, but of a single array, which is kind of not implementing two stacks at all.

    Note 2: adding a free queue of nodes improves memory usage by 1%. Not worth it.

  • leetcode day 13: linked list loop

    Given a linked list, determine if it has a loop.

    I started out with the simplest possible thing that could work: when looking to see if you have more than N of a thing, use a map.

    **
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    func hasCycle(head *ListNode) bool {
        seen := make(map[*ListNode]bool)
        for scan := head; scan != nil; scan = scan.Next{
             _, ok := seen[scan] 
             if ok {
                return true
            }
            seen[scan] = true
        }
        return false
    }

    Small, simple, but not very fast. 14th percentile in speed, 8th percentile in memory.

    I vaguely remembered that there was a pointer-chasing way to do this, and that’s the fast and small way. (This falls into the “do you know the trick” category, which I kinda hate.)

    func hasCycle(head *ListNode) bool {
        slow := head
        fast := slow
        
        if head == nil {
            return false
        }
        
        for {
            // if we'd run off the end, stop.
            if slow.Next == nil || fast.Next == nil || fast.Next.Next == nil {
                return false
            }
    
            slow = slow.Next
            fast = fast.Next.Next
    
            if fast == slow {
                return true
            }
        }
        return false
    }
    

    Considerably faster: 95th percentile in speed, 45th in memory, which is interesting.

    Now we start getting into “I would fire you if you did this” solutions.

    How about if we just overwrite the value with an impossible one, and if we see the impossible value, return true (because it couldn’t be there unless we put it there)? It’s slower, which is to be expected, since we’re modifying the nodes and looking at them, not just looking at pointers. But surprisingly, the memory usage is still around 43%. And the list contents are trashed.

    /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    const invalidValue = 99999999
    
    func hasCycle(head *ListNode) bool {
        // Destructive version.
        scan := head
        
        if head == nil {
            return false
        }
        
        for {
            // if we'd run off the end, stop.
            if scan.Next == nil {
                return false
            }
            if scan.Val == invalidValue {
                return true
            }
            scan.Val = invalidValue
    
            scan = scan.Next
        }
        return false
    }

    So what gets us better memory usage? How about breaking the links, and pointing them to na-na land, and stopping if we get a pointer to na-na land?

    /**
     * Definition for singly-linked list.
     * type ListNode struct {
     *     Val int
     *     Next *ListNode
     * }
     */
    
    func hasCycle(head *ListNode) bool {
        // Another destructive version.
        scan := head
        
        // Create an off-in-nowhere node.
        tumbolia := &ListNode{9999999, nil}
        
        if head == nil {
            return false
        }
        
        for {
            if scan == tumbolia {
                // we're in na-na land
                return true
            }
    
            // if we'd run off the end, stop.
            if scan.Next == nil {
                return false
            }
    
            // point the next of this node to na-na land.
            here := scan
            scan = scan.Next
            here.Next = tumbolia
        }
        return false
    }

    No major improvement. 90th percentile in speed, 43rd percentile in memory. List structure is trashed.

    So overall, the Floyd two-pointer is the winner; would love to see something that uses less memory, but haven’t found anything yet.