Leave a comment

Nov 18, 2011 | Rio does Interview Algorithms: Episode 1

In order to keep myself accountable for the next 10 days or so I have to brush up on my algorithms (in anticipation of interviews), I’ve decided to log a few of the algorithms I come across while on my hunt for interesting questions that I may be asked, specifically to prevent myself from getting stage-fright whenever someone asks me to write up a piece of code on a blank whiteboard. So without further ado, here goes. Each question will have an accompanying Python code.

I’d much rather be ideating on a whiteboard

Let’s start simple.

Given a set of numbers, give me the oral description/equivalent of it. For example:

“11” should return “There is one 1”
“21” should return “There is two 1s”
“1122” should return “There is one 1 and 2 twos”

Here’s one that I recently learned that’s really nice- a good portion is courtesy of Barry Carroll. We can build upon this in the next example.

Give me all the unique permutations of a string

Though it’s a nice implementation, we can actually come up with one that maintains lexicographic order, which is useful. The following actually harnesses the power of generators in Python, which help in memory allocation by only producing results as needed.

It turns out finding the next lexicographic item isn’t so easy, however. If we’re asked: Given the string “abcde”, give me the one that appears next in lexicographic order, that is, “abced”, there’s a neat approach we can take that’s highlighted in Wikipedia.

The algorithm is coded below:

Now there are obviously a lot of alternatives to each of these pieces of code, but I’ve written and selected ones that seem relatively easy to write on a whiteboard.

This entry was posted on Friday, November 18th, 2011 at 12:15 pm, EST under the category of Coding. You can leave a response, or trackback from your own site.