Friday, May 1, 2020

toy interiew problems in rust

2019 was my "Year of Rust".  I'd hoped to blog about that, yet here we are. :)
 Recently I've been doing random problems at random "coding-interview" sites.  This is a bit like working musical scales. Practice in flexing the low level muscle memory to allow it to fade into the background and allow thinking at a higher level.

  I mostly do them in python to work out the kinks in my algorithm (seriously, they are all about fixating on annoying edge cases.)  And then a few I work out in rust.


Today's challenge: Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree on

Check If a String Is a Valid Sequence from Root to Leaves Path in a Binary Tree

Given a binary tree where each path going from the root to any leaf form a valid sequence, check if a given string is a valid sequence in such binary tree.
We get the given string from the concatenation of an array of integers arr and the concatenation of all values of the nodes along a path results in a sequence in the given binary tree.


A few things to note about my solution:
  • The recursion is pretty simple and makes lovely use of the match syntax
  • rust match syntax doesn't allow matching a slice into (head, tail) as one might be used to in other pattern match languages or a lisp where all arrays are built up from recursively defined two element lists, e.g. (a, (b, (c, (d, nil))))
  • During development, I worked out all the edge case logic with the recursive calls commented out and short circuited. After getting that all working, I dug into the type issues with my intial naive attempt at executing the recursion.
  • extracting a value from a Option<RC<RefCell<T>>> requires jumping through a couple of hoops.
  • My internal recursive function has a slightly different signature than the public function. In my python solution, I was able to use the primary interface in my recursion code. Passing literal vecs as borrowed from the RefCell was just never going to work.


Now let's add some tests!
The leetcode interface handles converting tests from a text form, populating the tree and then running the algorithm. Details of their population routine are not available. Adding tests manually is ... annoying. Which makes it a good practice exercise for building RC

Rust Playpen

Full code available to edit and play with on the rust playpen

No comments: