Approaching Interview Questions: Finding Winning Sets In A Collection Of Lottery Numbers

I got this question from an interview I participated in recently. I went in and read the problem description, and remembered it was similar to something I saw previously. However, I was at a large impasse since the question asked for multiple sets and it threw me for a loop. Worst part was that I was on the right track in the first place.

The Problem

An individual’s lottery numbers are contained within an array. In order to win the lottery, there must be some combination of three numbers that total up to a specific whole number. Given an array of lottery numbers, find all the possible three-way combinations (without duplicate combos) in the array that could win. If there are no combos that could win, simply return nothing (an empty array, an empty string).

The Solution

I’m not going to give this one a tl;dr section since a reasonable solution is actually pretty easy, but a complete one needs more information. I’m going to talk about the issue I had when reading and processing this question instead.

The question asks for every possible combination, barring duplicate sequences. My problem was “what if there were two sequences that just had a slight difference?”

This is a great application for a Set; in fact, it’ll leverage the way a Set was used to solve the movie lengths problem. It’ll look pretty similar, too. For this post I’m going to try to write out more pseudocode before regular code.

First, we need to iterate over the whole array, right? Simple enough, start with a good ol’ for loop:

for (int i = 0; i < lotteryNumbers.Length; i++)
{
    // to be implemented
}

Now what? Our goal is to look for combinations of three numbers that add up to our sum. We want to ensure that we won’t run into any duplicate combinations.

If you’re really stuck

If you’re in a jam and you’re trying to remember what the fast approach is, start out by doing something kludgy. Loop through the whole deal with three nested loops! Easy to think of, but the most important part is to remember the constraints for the loops themselves.

for (int i = 0; i < lotteryNumbers.Length - 2; i++)
{
    for (int j = i + 1; j < lotteryNumbers.Length - 1; j++)
    {
        for (int k = j + 1; k < lotteryNumbers.Length; k++)
        {
            if (lotteryNumbers[i] + lotteryNumbers[j] + lotteryNumbers[k] == winningNumber)
            {
                Console.WriteLine($"Triplet is {lotteryNumbers[i]}, {lotteryNumbers[j]}, {lotteryNumbers[k]}");
            }
        }
    }
}

First index starts at i = 0, runs until the length of the array minus 2. Second index starts at j = i + 1, runs until the length of the array minus 1. Third index starts at k = j + 1, runs until the length of the array.

This is good in a pinch but relies on remembering constraints, it’s kinda hard to read, and it’s slow in regards to Big O performance (n^3).

Using our secret weapon

So we’ve got our initial loop to move through our lottery numbers. What now? Since we need to find unique sequences, my first thought was that we’d definitely be using a Set, but where I struggled was how I was going to use it to prevent duplicate sequences.

However, I think interview questions are an area where we want to cross that bridge when we get to it; it’s best to have code on the screen/whiteboard and I was reminded recently that I had forgotten to vocalize my thoughts during interviews, since most of my code sessions had been on automated systems.

Getting back to code, let’s take a step back and think about what we need to do with each number in the array of lottery numbers. For each lottery number in the array, we need to find two other numbers in the array such that all three total up to the provided winning value.

Remember that in the easy-to-think-of approach, we had three loops. Is there a way we can get rid of at least one of those loops? Absolutely. If we implement the second loop, we’ll be able to look at two numbers, one for each index. If we subtract both of those numbers from the sum, we’ll get the number we’re looking for!

for each number in the array
    for each subsequent number in the array
        calculate the difference between both numbers and the winning sum

It’s a start, but what do we do with this? It doesn’t solve the problem itself at all. If we leave it as is and simply log the result, we might get third numbers that don’t exist in the sequence. Is there anything we can use as a filter? Yes! The Set!

So, we want to use this set to store numbers and then verify that they’re in the set, but how will this work? This is different from the previous Movie Lengths problem that leveraged a Set in this manner, as now we’re being selective about what’s going to go into the Set rather than adding every difference we calculate to it.

Our condition will work in the following manner: if the difference we previously calculated is in the set, we’ll log the triple (or add it to some kind of collection). If it isn’t, we’ll add the current subsequent number (the one being tracked by the nested loop) to the Set.

Why only add the number from the nested loop? Remember that the parent loop is going to be checking each number in the array of lottery numbers for two other numbers that might form a winning trio, so our logic here should always consider the number being looked at in the parent group as always being part of the triple.

Now our pseudocode looks way more complete!

for each number in the array
    create a set for filtering
        for each subsequent number after the parent loop's current number
            calculate the difference between both numbers and the winning sum
            if our set contains the difference
                print the current numbers for parent loop and child loop
                remove the difference from the set
            if it doesn't
                add the child loop's current number to the set

From this point, it’s pretty straightforward to convert this into code.

void Lottery(int[] lotteryNumbers, int sum)
{
    for (int i = 0; i < lotteryNumbers.Length; i++)
    {
        HashSet<int> set = new HashSet<int>();
        for (int j = i + 1; j < lotteryNumbers.Length; j++)
        {
            int diff = sum - (lotteryNumbers[i] + lotteryNumbers[j]);
            if (set.Contains(diff))
            {
                Console.WriteLine($"Winning Lottery Triple: {lotteryNumbers[i]}, {lotteryNumbers[j]}, {diff}");
                set.Remove(diff);
            }
            else
            {
                set.Add(lotteryNumbers[j]);
            }
        }
    }
}

At this point, now that we’ve got our pseudocode and translated it into code, it’s sufficient for the interview question and ready for analysis by the interviewer. If there’s sufficient time left, you might want to think about how you might break the logic shown here as you’ll have to demonstrate resilience (belief that the code is correct) and flexibility (acknowledging the interviewer finding flaws) under scrutiny. One word of warning: using a Set is only one way we can approach this problem more efficiently. There’s another way to do this that involves what’s called the “two pointer” technique, which relies on… you guessed it, two pointers.

I wouldn’t call any of these questions fun, especially since a new position was on the line for me, but it was interesting to think about this question and understand why its solutions work.