CategoryAlgorithms

Calendar Conflicts Coding Interview Question

Here’s the video and code for the Calendar Conflicts video which walks through a linear complexity solution to a common coding interview problem. The idea is that you’re given a list of calendar events and you must find any events in the calendar which conflict.

There is an easy brute force solution to this problem, but the optimal solution is linear. The code here is written in vanilla PHP. If you’re interviewing at a company like Google, Facebook, Apple, etc., this is exactly the kind of coding interview question you might have to face.

Dinner Party Coding Interview Problem

You’ll find the text-form code from the second episode here. Following some very good critical feedback I got from friends and viewers, this episode is much, much shorter and focuses entirely on a coding challenge. The full video is here:

With this coding problem, you’re main challenge is generating combinations. There are some really fancy ways to achieve this. My favourite approach involves using bitmasks and Hamming Weights. Such an approach would just count up from 0 to 2^n looking for any number with a Hamming Weight of table_size. While that’s super snazzy, it’s also not super representative of what a person not familiar with these types of problems might come up with, so I didn’t take that approach for this video.

Instead, this video focuses on recursion. Reasoning about recursion can be a real challenge for our poor human brains. To ease this, in the video I draw the recursion chart shown here:

A diagram of a 4 choose 3 combination result created via a recursive function call.

A diagram of a 4 choose 3 combination result created via a recursive function call.

From this, you can get a basic idea of how a recursive approach to this problem might be solved. The really tricky thing for someone tackling such a problem for the first time is that you have to recurse twice in every function execution. Many people think of recursion as an approach where the function calls itself. The exciting thing about this algorithm is that the function calls itself not once, but twice!

One flaw with this code I noticed only after finishing the video and uploading it is that my groups argument is actually a bug. Because the default arguments are static across all calls to a function, this list will continue to grow and grow every time the find_dinner_parties function is invoked. It’s an easy thing to fix, but I ran out of whiteboard anyway. For those playing along at home, please add a list for groups in the call to combine_friends inside find_dinner_parties.

Least Disruptive Subrange Coding Interview Problem

Here’s the code from the first episode. This is a basic coding interview question that you might be asked in an interview at a tech company. You can see the video associated with this code here:

The problem here can be stated pretty simply. Imagine that you need a function that can take two inputs: 1) a list of integers and 2) another list of integers. The first list could be thousands of integers long. It can contain positive and negative numbers. It’s not sorted in any way. Any integer could be at any position. The second list is similar except that it’s equal in length to the first list or shorter.

What we want to do with these lists is find where in the first list we could substitute the second list, integer for integer, that would create the least amount of change in each integer from the original list. For this problem, we consider change to be measured in number line distance (i.e. absolute value). So, you can’t use some negative distance to offset some positive distance. If you substitute -2 for 2, that’s a change of 4.

An example would be something like this:

original =    [1, 2, 3, 4, 5]
replacement = [3, 5, 3] 

In this example, the “disruption” created by each possible substitution looks like this:

0th position swapping
 0  1  2  3  4
---------------
[1, 2, 3, 4, 5]
[3, 5, 3] 
 2, 3, 0 -- total disruption of 5

1st position swapping
 0  1  2  3  4
---------------
[1, 2, 3, 4, 5]
   [3, 5, 3] 
    1, 2, 1 -- total disruption of 4

2nd position swapping
 0  1  2  3  4
---------------
[1, 2, 3, 4, 5]
      [3, 5, 3] 
       0, 1, 2 -- total disruption of 3

You can see from this, that the best replacement choice here would be the 2nd index, which would create a subrange disruption of just 3, compared to all the other options.

So how might you solve this? Well, here’s a bit of JavaScript that aims to tackle the problem. This algorithm runs in O(n*m) time, where n refers to the length of the first input and m is the length of the second input. Interestingly, the longer the second input is, the shorter the run of the algorithm will be. So, the worst case is something like the length of replacement being half the length of original. In that case, the algorithm will do something along the lines of m*m work. It’s a constant memory problem in that it uses no additional arrays or objects to store state. I guess you could achieve this with a hash table if you just felt like wasting RAM. 😀

While this algorithm (as far as I know) is correct, it does leave many details unserved. For instance, I don’t address the potential to integer underflow by subtracting from the minimum integer value in JavaScript. Likewise, I could integer overflow by adding to distance until it bubbles over the maximum integer value in JavaScript. My test cases are also fairly limited and don’t test for cases like empty list inputs. Also, because JavaScript, I should be checking for null inputs and handling that case reasonably. I’m also not checking for the case where replacement could be longer than original. I’m sure there are like a dozen other defects here.

The point is not to create a bullet-proof library function. Rather, I was aiming to simulate a real coding interview focusing on what you’d have time to accomplish. Let me know what you think. Especially let me know if I got it all wrong!

Generating a Color Picker Style Color Wheel in Python

color gamut generated from Python

This color wheel was generated with Python. Check out the code on GitHub.

For the record, I am very bad at Python. Yet, it has become more and more my go-to language for doing little things that aren’t web. For instance, I recently undertook to create a color picker/color wheel in Python.

For the uninitiated, a color wheel or color spectrum is a series of hues that run from red to indigo (roughly purple to our eyes). It’s the rainbow. The color wheel is this same thing but wrapped around in a way that shows all the hues the human eye can see. In reality, indigo doesn’t converge on red as you go up in light frequency, but the hues that you would see if it did are colors we know well — magenta/pink.

So, generating a color wheel is an interesting challenge. The primary colors can be created from the hex colors 0xff0000 (red), 0x00ff00 (green), and 0x0000ff (blue). You probably see the pattern easily. A color breaks down into three channels, each of which has up to 0xff or 256 values from 0, completely absent, to 0xff, completely displayed. Blending from blue to green implies moving from 0x00ff00 to 0x0000ff by decrementing the green channel monotonically as you monotonically increment the blue channel. So, you can probably start to see how the logic for generating the color spectrum graphic will have to work. Of course I’m ignoring a few colors that are important. Red, green, and blue are only half the colors that are necessary for the color wheel to look complete. The others are 0x00ffff (cyan), magenta (0xff00ff), and yellow (0xffff00). These colors appear in color spectrum interwoven between the primary colors. If you’re wondering why red and green make yellow, you’ll probably want to read about Color by Addition. Though, from a numbers perspective it’s easy to see a relationship between 0xff0000 -> 0xffff00 -> 0x00ff00.

Creating the gamut requires calculating how much of each color to use in the blending. One important aspect of a color wheel is that any color you can select is a blend of at most two colors. So, one way to generate a color wheel is to go pixel-by-pixel through the image you want to create figuring out what sextant you’re in, deciding which color you’re closest to, then figuring out how much of the other color to blend into it. That’s the approach I took. It’s true that you can do this other ways. In fact, I’m pretty sure there is a slick algorithm for this that I didn’t realize. I was on a plane when I wrote this and consider it more about learning Python than about making the most compact implementation of color spectrum generation.

Anyway, here’s the code (using the Python Image Library) on GitHub.