Tag: leetcode month

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.

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.

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.

I had a really hard time getting my head around this problem, which contributed to major flailing on my part trying to get it sorted. I had several almost-right solutions, but I kept not getting the recursion right. I eventually sorted it out to “I need to check the subtree heights” as the right attack, but didn’t finally sort it until the 10th try or so.

This wold absolutely have been a fail in an interview. I’m getting much better with pointers – I had no trouble getting the recursions to work, and never had a nil pointer problem – but I just could not get the concept clear enough in my head, and that lead to my just not getting it right in the code.

After a lot of flailing I finally came up with a height-checking algorithm that was the best shot at it I could do, but I had to finally check with the solutions to spot my error, which was treating the left and right subtrees separately when they needed to be unified.

Final version after the fix did okay in the rankings: top 84% in speed and top 81% in memory, but the path to getting it was really bad. I need to spend a lot more time on tree-crawling.

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    if root == nil || (root.Left == nil && root.Right == nil) {
        return true
    }
    _, which := heightCheck(root)
    return which
}

func heightCheck(root *TreeNode) (int, bool) {
    if root == nil {
        return 0, true
    }
 
    lH, lB := heightCheck(root.Left)
    rH, rB := heightCheck(root.Right)

    // I was way overcomplicatng this, tracking the
    // branches separately and not sending along a
    // give-up flag. Doing that helped a lot.
    if !lB || !rB  || abs(lH - rH) > 1 {
        return -1, false
    }

    return max(lH, rH) + 1, true
}

func abs(a int) int {
    if a > 0 {
        return a
    }
    return -a
}

func maxDepth(root *TreeNode) int {
    if root == nil {
        return 0
    }

    left := maxDepth(root.Left)
    right := maxDepth(root.Right)

    return max(left, right)+1
}


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

Interestingly, if one adds a second recursion shortcut check for leaves, the memory usage gets much better: 99th percentile, but the execution time gets much worse: 54th percentile.

A bit of a break working on a friend’s art business launch; still working on that, but made some time to come back to leetcode month today.

Today’s problem is flood fill; another easy-rated one. This is again a recursion problem, and the tricky bit is as usual preventing extra recursion that doesn’t need to happen.

Doing this one is made a lot easier by unifying the calling sequence with a helper function that adds an

Go-specific issues for me were properly extracting the dimensions of a two-D array and having to do that with a pointer. Since we want to alter the array we’re flood filling, we need to pass a pointer to it so that we can actually modify the source array.

I got tripped up by the termination condition. In addition to “are we outside the bounds of the array”, we also need to check if this cell needs filling at all (is it the fill color already? Is it the color we want to fill?).

I did need a couple runs with debug prints in to spot where my recursion was going wrong; the first cut didn’t have the “is this already the right color” test, and I was able to catch that one with the supplied test cases. It. failed on the submit because I wasn’t checking for “is the fill already done” case.

How did I do relative to other cases? Pretty good! Runtime in the top 92%, memory usage a quarter of a percent short of the 100th percentile. Should be a pass in an interview. (I did get this one at Thumbtack, and came out with a solution similar to this one, except I used an 8-cell neighborhood when a 4-cell will work. Too many Game-of-Life programs.)

func floodFill(image [][]int, sr int, sc int, color int) [][]int {
    eligibleColor := image[sr][sc]
    return *floodFillHelper(&image, sr, sc, color, eligibleColor)
}

func floodFillHelper(image *[][]int, 
                     sr int, sc int, 
                     fillColor int, 
                     eligibleForFill int) *[][] int {
    if sr < 0 || 
       sc < 0 || 
       sr > len(*image) - 1 || 
       sc > len((*image)[0]) - 1 ||
       (*image)[sr][sc] != eligibleForFill ||
       (*image)[sr][sc] == fillColor {
       return image
    }
    
    (*image)[sr][sc] = fillColor
    
    floodFillHelper(image, sr-1, sc, fillColor, eligibleForFill)
    floodFillHelper(image, sr+1, sc, fillColor, eligibleForFill)
    floodFillHelper(image, sr, sc-1, fillColor, eligibleForFill)
    floodFillHelper(image, sr, sc+1, fillColor, eligibleForFill)
    
    return image
}

Should have been an easy one, but I haven’t written one by hand in years. Ended up Googling.

Some interesting notes on the code:

• for with a conditional break inside is considerably slower than for condition.
• The version of this that I learned back when used a step division, and that actually is much harder to get right. The upper/lower/mid version is much easier to get right.
• I decided to not do a recursive solution this time on purpose. The expressivity that recursion gives you is not to be denied.

Final version scored well: 90% on speed, 97% on memory. Acceptable, but the amount of dicking around was not. Note: study up more of these common but not commonly coded algorithms.

func search(nums []int, target int) int {
    // Find midpoint, check element; equal, less, or greater.
    // if the step size goes to 0 we did not find.
    low := 0
    high := len(nums) -1

    for low <= high {
        mid := (high + low )/ 2
        if nums[mid] < target {
            low = mid + 1
        } else if nums[mid] > target {
            high = mid -1
        } else {
            return mid
        }
    }
    return -1
}

Problem: two strings. Are they anagrams of each other?

Software engineer hat again: if these are arbitrary Unicode strings, then the right solution is count the characters in the first string, binning the counts by character, and then subtract the counts of the characters in the second string. If the characters are ASCII, then you can be clever and use the character value as an index into an array and do the same add/subtract algorithm…but someone will use a non-ASCII character, sooner or later. And the failure mode of clever is…well.

Score: bottom 15% in time and space, but I’ll take that for the vastly reduced need to worry about weird input. If we remove the conversion to string and use bytes, then it improves to 30%. The real win doesn’t happen until the conversion to arrays. I initially had a delete to remove counts that went to 0 and a check for counts that went negative (chars in t not in s) but there wasn’t a significant speedup.

func isAnagram(s string, t string) bool {
    // easiest way is to map the character counts into a hash.
    // if the two strings match, there should be no odd counts.
    if len(s) != len(t) {
        return false
    }

    charCounts := make(map[byte]int)
    for i := range(s) {
        charCounts[s[i]]++
    }
    for i := range(t) {
        x := string(t[i])
        charCounts[x]--
    }
    for _, count := range(charCounts) {
        if count != 0 {
            return false
        }
    }
    return true
}

Giving up and using an array of 256 ints, indexed by the int value of the bytes, it’s much faster: 93% on time, 98% on space. Good enough. I suppose you could use this on Unicode input, since it’s just looking at raw bytes. Depends on whether you have a character that can be represented in more than one way in Unicode.

The syntax for creating arrays continues to be a problem. I’m going to standardize on assigning the type followed by {} to the variable.

func isAnagram(s string, t string) bool {    if len(s) != len(t) {        return false    }    charCounts := [256]int{}    for i := range(s) {        charCounts[int(s[i])]++    }    for i := range(t) {        x := int(t[i])        charCounts[x]--    }    for _, count := range(charCounts) {        if count != 0 {            return false        }    }    return true}

The classic whiteboard problem.

I chose the “busy software engineer” approach: I know an algorithm that will work and is trivial to implement. Implement that.

To remind everyone what inverting a tree is: if criterion for insertion is left branch < right, then then output tree should have left branch > right. The dead simple algorithm is top-down: save the left, assign the right to the left, assign the saved to the right, recurse.

It’s clear, it’s simple, and fast to code. I literally had a working solution in 2 runs (forgot the null root case on the first run).

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func invertTree(root *TreeNode) *TreeNode {
    if root == nil {
        return nil
    }
    
    invertTree(root.Left)
    invertTree(root.Right)

    t := root.Left
    root.Left = root.Right
    root.Right = t
    
    return root
}

About as simple as you can possibly get. Scorewise, it’s fast: top 77%. Memorywise, it’s pretty poor: bottom 8%.

I’m betting a pointer crawl would use less memory but wouldn’t necessarily be that much faster. Let’s see.

First note, still writing append as if this were Scala. Sigh.

This try ends up in an infinite loop; I’m mismanaging the stack somehow. (See why letting Go do it is better?) I’m declaring this good enough and moving on. I expect I could write a version where I manage the stack myself, but this is why we invented higher-level languages.

Unless our trees are always incredibly deep, this is the right way to do this. Even skipping the recursion for nil subtrees doesn’t really make it faster.

On the other hand, I solved the initial recursive version in about 5 minutes, so I’m getting my feet back under me.

I’m perceiving a pattern in my failures here and it is 100% “did you absolutely understand the requirements”.

Detecting a palindromic string was the easy part: just put an index at the end and the beginning, and march them toward the middle. If they meet or pass each other, then we succeeded. If at any point the characters at the indexes don’t match, we fail.

The problematic part was the cleanup of the initial string. Lowercasing wasn’t bad, though I had to look up where the function lived (it’s strings.ToLower()). Filtering the input was harder. I had to go check Stack Overflow and found this code, which is very nice and will go in my personal toolbox:

func cleanup(str string) string {
    return strings.Map(func(r rune) rune {
        if !unicode.IsDigit(r) && !unicode.IsLetter(r) {
            return -1
        }
        return r
    }, str)
}

The strings.Map function is really nice for “do something for every rune in a string”, especially since the special -1 return value says “drop this character”. Can do just about any transliteration you want with that! The unicode.IsDigit function highlights my “you did not read the instructions” error: I assumed that it would be alpha only, and that was incorrect; it was alphanumeric input.

I did spot a useful optimization: if the string is less than two characters long, by definition it’s a palindrome, so we can skip scanning it altogether.

Otherwise the algorithm I coded to scan was right the first time.

How’d I do comparatively? Meh. Runtime in the bottom 50%, memory in the top 60%. I think the lowercase followed by the cleanup is the culprit, and doing it all in one loop would be faster. I don’t think it’s as clear.

I tried a couple variations, and all of them are worse:

• Reverse the string and compare it to itself
• Inline the cleanup

This just may be something that Go kind of sucks at doing.

func isPalindrome(s string) bool {
    // lowercase, skim out all non-alpha characters
    s = strings.ToLower(s)
    s = spaceMap(s)

    if len(s) < 2 {
        return true
    }
    begin := 0
    end := len(s) - 1

    for {
        if begin > end {
            return true
        }
        if begin == end {
            return true
        }
        if s[begin] != s[end] {
            return false
        }
        begin++
        end--
    }
}

func spaceMap(str string) string {
    return strings.Map(func(r rune) rune {
        if !unicode.IsDigit(r) && !unicode.IsLetter(r) {
            return -1
        }
        return r
    }, str)
}

Didn’t do so well on this one on the first pass.

You’re given an ordered array of prices, and are asked to find the maximum inter-day profit. Constraints: the buy must be before the sell (first price array index < second price array index), and profit is 0 if there is no positive delta.

I originally did a brute force solution that essentially came down to a double loop. Worked fine for small examples, but failed on time for long ones.

So I went and took a shower, and got half of it: if I find the minimum value, then no price after that can possibly have a bigger delta. However, it’s possible that there was a bigger delta preceding that, and I got stuck there for a while, wondering about iterating backward, but couldn’t see a definite siimple algorithm.

I got a hint that I could use a sliding window, and that gave me the right solution.

Start at index 0 as the tentative minimum.
Walk a second index forward.
If the walking index finds a new minimum, move the minimum pointer.
Otherwise, calculate the delta between the current minimum and the walking index price.
If the delta is > the old max delta, save it.

My original insight would eliminate whatever part of the array that followed the global minimum, but would have missed possible local maximum deltas (e.g., [10, 100, 1, 5] would have a true max delta of 90; scanning only after the global minimum would only have found a delta of 4). The sliding window finds that first delta of 90, and then keeps it, even though we find a new minimum at 1.

func maxProfit(prices []int) int {
    // iterate over the array from the start.
    // take the current item as the start price.
    // find the max price after this one that leads to a profit, or 0.
    // repeat for each day up to the last-1.
    // if the profit for a given iteration is > the current, save it instead.
    maxProfit := 0
    tentativeMinIndex := 0

    for i := tentativeMinIndex; i < len(prices); i++ {
        if prices[i] < prices[tentativeMinIndex] {
            tentativeMinIndex = i
            continue
        }
        // haven't moved minimum, calc profit
        thisProfit := prices[i] - prices[tentativeMinIndex]
        if thisProfit > maxProfit {
            maxProfit = thisProfit
        }
    }
    return maxProfit
}

How’d I do? Bad on the initial O(N^2) iteration, but fab on the sliding window version: top 99% in speed, top 93% in memory.

Taking a shower helped, but I won’t be able to do that in an interview, alas. (Another good argument for working at home.)

Next is palindromes, and we’ll be back to fun with Go strings again.