Making Change: Interviewing with CSS

11.30.2014

"Please code this in a language of your choice." CSS is a language. It runs in O(awesome time).

This entry is pure fantasy—bored corporate fanfic. Someday, I hope something like this happens. If you pull it off—you legend you*mdash;let me know.

Overview of a Technical Interview

The technical interview is a cornerstone of life for professional software engineers. They are our entry point to the field and something we participate in throughout our career, sitting on both sides of the table.

From the outside, the technical interview is straightforward. Forty-five minutes elapse. The first few are genial chatter. The last few are genial chatter. In between, there are one or two technical questions. At many companies, the interviewer will ask the candidate to solve the problems in a language of their choice.

A language of their choice.

JavaScript, being the language of the web, is a perfect language to answer questions in. Particularly if you're interviewing for a front end role. It's a language we're expected to know. But let's say we don't want to be practical. Not today.

We don't want to answer the question in JavaScript.

The Question: Make Change

We're in a room with an interviewer. She settles into her chair and outlines a problem. In a nutshell, she wants us to write a program that takes an amount of money in cents as an input and outputs the coins necessary to make change for the amount. As part of the question, she notes that the coin system should be arbitrary. To start with, we can assume pennies, nickels, dimes, and quarters.

"Please answer the question in the language of your choice," the interviewer says.

We stand by the whiteboard, choosing our favorite color of dry erase marker. Purple and blue should work nicely.

"Let's solve the problem in CSS and HTML," we say.

"And JavaScript?" The interviewer prompts.

"Just HTML and CSS," we politely respond.

Getting to the Solution

The first thing to do is define our inputs and outputs. How will our program take in the input, and how will it output the result? Our environment for the solution is HTML, CSS, and the browser. The HTML file will be the input, and we assume that it will link in our CSS, which the browser will use to process the HTML. The result will be displayed in the browser window. Since we're building a website, we can actually display pictures of the coins themselves on the website.

We need a way to capture the notion of an amount of money. We'll assume that the money is an integer, representing cents. In particular, we'll use an unordered list with one list item per cent.

<ul>
  <li>cent</li>
  <li>cent</li>
  <li>cent</li>
  ...
</ul>

To start with, we'll render each of these as a penny.

The CSS for this is straightforward. We style each item with a width and height, and give it a penny as a background.

.change.pennies li {
  display: inline-block;
  width: 100px;
  height: 100px;
  background: #a00;
}

Now, we need to figure out how many of these should be turned into dimes and how many into nickels.

Let's start with nickels. We need to group the pennies in sets of five. So, counting from the end of the list, we'll draw a blue box around each penny that needs to be a nickel.

This is done by using the :nth-last-of-type pseudo selector.

.change li:nth-last-of-type(5n) {
  border: 4px solid #009;
}

What do we do with the four pennies after the blue one? How do we select those? Also, why are we using the :nth-last-of-type pseudo selector? The answer to both is the same: we need to use the younger sibling selector '~'. The tilde selector selects younger siblings (elements that are siblings but come after the element). The reason we go from the end is so that we can always know that we are selecting the correct number of cents to collapse into a coin.

So, let's write a selector to draw a green border around the inner coins.

This involves figuring out which siblings come after the nickel but are also not nickels. In order to find these, we can find all younger siblings that are not fifth-from-last elements. We can use the :not pseudo-selector to do this.

li:nth-last-of-type(5n) ~ li:not(:nth-last-of-type(5n)) {
  border: 4px solid #090;
}

The next step is to hide these coins and turn the fifth-from-last elements into nickels.

The following CSS accomplishes this, changing the background image and displaying 'none' to hide some elements.

li:nth-last-of-type(5n) {
  background-image: url(http://upload.wikimedia.org/wikipedia/commons/7/72/Jefferson-Nickel-Unc-Obv.jpg);
}

li:nth-last-of-type(5n) ~ li:not(:nth-last-of-type(5n)) {
  display: none;
}

The same thing can be done with dimes. Since CSS cascades and our dime rules will have the same specificity as our nickel rules, the dime CSS should come later.

We've done it! We've unlocked the key to basic calculation and change-making using raw HTML and CSS. We can now optimally split any amount of cents into pennies, nickels, and dimes. What's more, we can display a human-readable version of our result in the browser window.

Our CSS now looks something like this:

/* Pennies */
li {
  display: inline-block;
  width: 100px;
  height: 100px;
  background: url(http://upload.wikimedia.org/wikipedia/commons/2/2e/US_One_Cent_Obv.png);
  background-size: 100%;
}

/* Nickels */
li:nth-last-of-type(5n) {
  background-image: url(http://upload.wikimedia.org/wikipedia/commons/7/72/Jefferson-Nickel-Unc-Obv.jpg);
}

li:nth-last-of-type(5n) ~ li:not(:nth-last-of-type(5n)) {
  display: none;
}

/* Dimes */
li:nth-last-of-type(10n) {
  background-image: url(http://upload.wikimedia.org/wikipedia/commons/3/3c/Dime_Obverse_13.png);
}

li:nth-last-of-type(10n) ~ li:not(:nth-last-of-type(10n)) {
  display: none;
}

Discovering Limitations

Going to quarters breaks some things. 50 cents should be split into two quarters. Only one displays.

The problem is that while dimes always fall on nickel spaces, since 10 divides by 2 without a remainder, dimes do not evenly divide quarters. So the dime is hiding every other quarter. To fix this, we could add a display of inline-block to each coin when it is displayed.

However, in this case, since the quarter doesn't fall on a dime, it divides a dime. This means that the dime would only take up 5 coins. We've found a limit in our solution. Each coin in the system must evenly divide the next largest coin. We can handle pennies, nickels, dimes, fifty-cent pieces, and dollars. We can handle pennies, nickels, quarters, fifty-cent pieces, and dollars. However, we can't handle quarters and dimes at the same time. As an exercise to the reader: there is a way to use lowest common denominators to solve for dimes and quarters.

Wrapping Things Up

We proudly stand back and admire our work. We've taken an HTML file with a list as an input, used CSS to process it, and visually displayed the result using a browser. Pretty impressive for two languages that are often not considered real languages.

The interviwer leans back in her chair. At least I'm not bored, she thinks to herself. "What are the limitations of this solution?"

We think for a moment before iterating them:

The interviewer smiles. "One last question."

"Yes?"

"What's the running-time of this solution?"

We pause to think about the ramifications of the browser parsing the HTML and hashing the list items. We consider that WebKit is working on implementing a JIT compiler for its CSS. We wonder how to even quantify big-O running time for CSS calculations.

"It runs in O(awesome time)."

Read More
CSS
Corporate Fanfic