A few weeks ago, Ian Douglas asked me to help give mock technical interviews for Turing students. As someone coming out of a code school, tech interviews are the emotional equivalent of walking into Mordor. They're absolutely horrifying. (Full disclosure: I cry after every tech interview. And then drink heavily. I can't be the only one.)

I've been thinking a lot about the questions asked lately. And, unsurprisingly to you, O(n) and sorts come up frequently. I'm not going to go into too much detail about O(n) because, frankly, I don't feel qualified. Greek symbols in math scare me. They're like warning signs for the rest of us.

For developers, the purpose of these questions is to measure your understanding of time complexity — the length of time your algorithm (function, method, code) takes to process the result.

O(n) refers to linear time. The algorithm will take more time proportionate to the size of the input.

Sample Problem

Let's take an interview question like: Write a function that takes a list of integers and returns it from least to greatest in O(n) time. Godspeed if you have to do this on a whiteboard. Sending good thoughts your way.

Sorts have always fascinated me and I don't know much about them so it's a great opportunity to learn something new. (If you haven't seen the Hungarian folk dance of bubble sort, you're missing out.)

I'm the first to admit that computer science fundamentals are a growth area for me. I'm far from an expert in the area of well-known algorithms. A little googling and I found that the most reliably linear algorithm for sorting is quicksort. Awesome. (I should say here that algorithms are always evaluated on worst-case scenario. And in worst-case, quicksort is not O(n). That said, it's pretty darn good.)

A little more googling and it turns out quicksort should be called hardestsort. But I decided to give it a shot anyway.

An article on DevCamp gave me a start. But, Ruby's syntactic sugar was too much for me. I couldn't tell what was happening. This solution is beautiful, but I need to keep looking.

This StackOverflow post (note the verbose quicksort algorithm toward the bottom) led me to Khan Academy and helped me break down what exactly is happening.

Here's how quicksort works:

You have a list. Yay for arrays!
You choose a pivot point. This is an index in the list you'll use to split the array into three parts: the left array, the pivot and the right array. From my research, I've seen the pivot selected randomly, as well as first or last index being used. Let's talk about this using the first item in the array as the pivot.
Compare the pivot to the value to its right. If the pivot is smaller than its neighbor, leave it. If the pivot is larger than the value to the right, switch their positions.
Buckle up for recursion. Move the pivot and do the same thing.

Handcrafted Quicksort

Let's dive into some code.

If you're still confused about what's happening, let's look at the output. This is the list each time we call quicksort(). I added a bit of color whenever two values are swapped.

Pretty cool, huh?

Fancy Quicksort

OK, I feel like I have much more of a grasp of what's actually happening. I'd be lying if I said I could deliver an hour-long lecture about it, but I'm learning!

I wanted to revisit the "elegant" version I saw before. And found this lovely video.

To the code, Batman!

This implementation involves meta-programming (I'm a little nervous about this) and extending the Array class.

OMG is that so much better that the first go.

Remember how we pass the block in with the less than symbol? This sorts the numbers greatest to least. If you were to call partition(&pivot.method(:>)) instead, it would sort the values least to greatest.

For more reading on the partition method, check out the docs.

I sincerely hope this helps you on your next interview question on sorting. But like I said, if you're at the whiteboard, I'm sorry. Good luck!