leetcode day 16: evaluation

So let’s take a breath; we’re just past the midpoint, and I don’t think I’ll finish the whole set of exercises this month, even though I’ve ripped through 11 today.

I do feel like I’m learning things; some of them are generally useful, and others are “okay, you could do that if you really had to squeeze every microsecond out”.

• The old Perl rule of thumb “if someone’s asking you to count things, start with a hash” has generally paid off well. There are a lot of tricky choices in this, but the following rules of thumb seem to be true:
  • If you are coding a for loop, putting the condition in the for seems to run fastest. It’s definitely preferable to a bare for{... with a conditional break inside.
  • Using range will often give you better CPU time at the expense of more memory.
  • Making two extra function calls on the nil subtrees of a leaf to a function that immediately drops out on the null case is better than having a leaf case inline.
• I need to brush up on my tree-crawling algorithms. I know them well enough to code them and not break things, but the upcoming “diameter of a binary tree” problem is going to be one I have trouble with, similar to the trouble I had with lowest common ancestor and balanced tree: I simply am not comfortable enough thinking about trees to see the solutions easily; sometimes I’ve having trouble getting the problem statement clear enough to solve the problem.
• Also need more practice with binary searches. I struggled a lot with the first binary search, but did a lot better with the second one in minimum bad version.
• I have learned some interesting new things:
  • The Euler tour for transforming the lowest common ancestor problem into a maximum-in-range problem.
  • The tortoise-and-hare-pointer algorithm for detecting loops in a list turned out to be applicable to finding the middle of a linear list.
  • If a Go problem is mostly linear searching and adding and removing stuff from the front of a list, using a real linked list will often be significantly faster, though more memory-intensive.
  • Dipping a toe into dynamic programming. I definitely need to spend more time with this, as I definitely got a 2-D dynamic programming question at Bloomberg and wasn’t able to solve it, even in Perl.
  • Moore’s candidate algorithm for the majority element. Ridiculously simple…once you’ve seen it.
  • If you just need a thing to indicate that something is there in a map, a map[type]struct{} is much, much faster than any other type.
  • If your problem space is small enough, using an array instead of a hash will get you big speedups and save a ton of memory while still letting you count things by a key; it’s just that the key is now an integer (e.g., anagrams, if the letters are guaranteed to only be ASCII a-z).
  • Converting a byte array to a string is way faster than progressively building up a string by concatenation. If you can precalculate your maximum space requirement for the byte array, you can make it even faster by preallocating with make(), which lets you dynamically choose the initial size for the array.
  • string() on a slice is just as fast as string() on a full array.
  • It’s actually pretty easy to work with byte arrays, and they let you nicely mix numeric and character values for characters. (Though you should limit this to ASCII.)
• Things I’m pleased about
  • I had less trouble than I expected with 2D arrays (flood fill). Getting the basic stuff right was the hard part, and after that it was straightforward.
  • I’ve gotten the hang (mostly) of passing pointers into Go functions, allowing me to do things like build persistent caches recursively.
  • I had my very own insight on the middle-of-a-linked-list problem that solved it with a fast and slow pointer.
  • I’ve used closures as iterators twice, and both times they significantly simplified the code.
  • I’m feeling better and better about my skill with Go. I’m definitely a very solid intermediate programmer, and I think I will be able to say I’m an advanced one after getting through all these problems. I’m much more comfortable with pointers in Go that I was when I started. The syntax is still a little gnarly.

I have more stuff to do for Shymala’s art business tomorrow, but I hope to get back to things in a few days. I’ve finished week one and most of week two; I’m two exercise short and two days behind, but there were two weeks of pretty much continuous work on the business in there, so maybe I will finish it off this month. We’ll see.

At any rate, I think I’ll feel a lot less anxious doing coding interviews once I’ve gone through this, and that was the point of this project.