Episode 04 of the series is available now on my YouTube channel.
This problem revolves around generating permutations of a sequence incrementally. Rather than pouring out a huge vector of output, this problem asks for a generator that can output the next permutation of a vector with every iteration.
For this video, I code in C++ and uses a functor to create the generator.
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.
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.
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.