Toy Problems, Real Interviews

We are now going to start a repository for the ages. It’s called toy-problems. Go create that repository on your GitHub page right now, then come back here.

…

Great. Toy problems are exactly what they sound like: Problems that are meant to be treated as toys.

Toy problems are not real problems. They are basically mind-teasers for programming nerds. Sometimes they are trivia. Often they are puzzles. My personal favorites are about systems design.

Toy problems are very popular in programming interviews. Since programming computers to do things is an endless series of problem-solving, interviewers want to see a demonstration! Sometimes (often), they don’t expect you to fully solve the problem during the interview. They just want to see how you can think.

Whether toy problems are efficient demonstrations whether you can program is a debatable subject. But their presence in interviews cannot be denied.

Some of the most common forms of toy problems are sorting algorithms and data structures. In this chapter, we will create an algorithm that sorts numbers from lowest to highest.

But first, you have an interview.

Interview

You are interviewing at CityBucket, a startup whose business is “data storage and data science for municipalities around the country.”

Your interviewer is a back-end engineer.

Interviewer: Hello, welcome to CityBucket! We are excited to be interviewing you. I mentioned your name to some of the people at the Python meetup I attended last week, and they said they had met you at the local front-end meetup!

You: Great to meet you, Interviewer! Yes, I’ve been going to their monthly meetups for a few months now.

Interviewer: Let me tell you about this position. We are primarily looking for a front-end engineer. We are going to set up a front-end as a separate application. Does this make sense to you?

You: Yes. You are saying that the front-end code will be a separate codebase from the back-end codebase. The codebases will probably live on different servers and communicate through HTTP.

Interviewer: Exactly.

Interviewer: Let me tell you about CityBucket.

Interviewer: Cities all over the country have data. Tons of data. Data is so hot right now. They have data on water sources - rainfalls, river flows. They have water usage datas for all the houses and all the neighborhoods. They have data on traffic - which roads and times of the day are most popular.

You: Electricity usage. Natural gas usage. Hotel occupancy rates. Big data!

Interviewer: That’s right. And they don’t know what to do with all this big data. They don’t know how to store the terabytes they are generating. And these municipalities don’t want to (and literally can’t) pay to hire their own data management team.

Interviewer: AND THAT’S WHERE CITYBUCKET SWOOPS IN. For $1,000 to $50,000 a month, we provide data storage and data statistics to municipalities all over the country. We provide curated data sets to those who have their own in-house statisticians. Those in-house statisticians are mostly just using Excel.

Anyways, all of this storage and statistics calculations happens on the backend. We are running a PostgreSQL database and a Python Django API server. The API sends the front-end application data. It’s pretty much always in JavaScript Object Notation format. Here’s an example or the sort of data you would expect to get on the front-end:

water_categories_data = [
  {
    "title": "river",
    "order": 3,
    "id": "yqM3w",
  },
  {
    "title": "ocean",
    "order": 1,
    "id": "b1en2n",
  },
  {
    "title": "ocean",
    "order": 2,
    "id": "b1en2n",
  }
]

You: I’m familiar with JSON. This is an array containing three objects. All three objects have the same 3 fields (keys): title, order, and id.

Interviewer: That’s correct. And you’ll notice that the objects are out of order in the array.

Interviewer: I now want you to solve a problem for me.

Write a function that takes an array of numbers as input. It should output an array of those same numbers sorted from lowest to highest.

You: So you want a function that takes an array like [5, 3, 1, 2, 4] and returns [1, 2, 3, 4, 5]?

Interviewer: Yes.

You: Do we care about complexity or how long it takes to run?

Interviewer: No.

You: Cool. Can I use the whiteboard?

You: I am going to solve this using a simple bubble sort algorithm.

You: This is how it works. Whatever the array’s length (i.e. its number of members) is - you loop over the entire array that same number of times. During each loop, you pass over every position of the array.

As you pass through each position, you compare the number at that position with the number in front of it. If the currently positioned number is greater than that number in the position in front of it, make them swap positions. So on that first pass, you’re at least going to get the biggest number in the whole array in the last position… it “bubbles” to the top.

Before I write the code, let me give a quick demo with the unsorted array, [3, 4, 1, 2]. On the first pass, the 4 bubbles to the top and you have [3, 1, 2, 4]. On the second pass, the 3 bubbles to its spot, and you have [1, 2, 3, 4]. It would look something like this.

Interviewer: You have two needless loops at the end there.

You: Well, the third loop is necessary - until it stops making swaps, the function does not yet know. So we would at least need to go through the third loop and know that we didn’t have to swap a single thing. That’s how the algorithm could make sure.

Interviewer: This is why this solution has N-squared complexity…

You: Yes, that is right. The computational complexity of an algorithm can be measured as the number of instructions the computer will have to execute when given an input of a certain size.

To take our example above a little further, we explain: The array is four members long, so the algorithm loops over it four times. During each of those four loops, it performs the comparison action four times. So four loops, and four instructions per loop. That’s 16 instructions. 4^2 = 16. We can generalize this calculation to an input of any size and just say “For an input of size N, our algorithm will perform N^2 computations.”

Interviewer: Yes. In Big O notation, we would describe this as O(n^2).

You: Yes.

Interviewer: That concludes today’s interview. Please code your solution in a JavaScript file named bubbleSort.js and email it to me. We will be in touch after that.

Code The Solution

We’ll take a step back from the Interviewing scenario now. Clone your toy-problems repo to your local machine:

git clone https://github.com/<YOUR-USERNAME>/toy-Problems

Make a file

cd toy-problems
touch bubbleSort.js

Now use the JavaScript console, and try to write your own sorting function. Here’s mine:

// The algorthm

const bubbleSort = function(numbers) {
    const length = numbers.length;

    for (let loop = 0; loop < length; loop++) {
        for (let position = 0; position < length; position++) {
            if (numbers[position] < numbers[position + 1]) {
              // swap
              const smallerNumber = numbers[position + 1];
              numbers[position + 1] = numbers[position];
              numbers[position] = smallerNumber;
            }
        }
    }

return numbers;
}


// Testing

let testArray = [ 420, 4, 69, 11, 62];

console.log("Sorted? ", bubbleSort(testArray));

Take all of your code and save it to bubbleSort.js file. Commit and push.

git add bubbleSort.js
git commit -m "Simplest bubble sort function in JavaScript."
git push origin master

You’re Hired!

Your interviewer called you back, and… congratulations! You’re now been hired at CityBucket!

Recap

Good work finishing your first toy problem. Toy problems are great confidence builders and will prepare you for interviews. You can find lots of examples of them on the web.

Exercises

  1. Do the exercises at the end of Eloquent JavaScript’s chapter 2.

Store your work as .js files in your toy-problems repo, and push them to GitHub. You may want to reference these in the future… and you may as well keep building your public coding resume with what you’re working on! You never know who may want to talk about it at the next meetup! This is a good way to engage mentors.

  1. Watch a few YouTube videos on sorting algorithms. There are TONS of great ones out there. One really fabulous video out th ere is called “15 Sorting Algorithms in 6 Minutes”.

  2. Read Eloquent JavaScript Chapter 3.

  3. What is an algorithm?

  4. What is computation complexity?