Coding Interview Question – Optimizing toy purchases

Problem

My son gets a weekly allowance of $15. He takes that money every Friday and goes to Toys’R’Us to find two toys he can buy for $15. He wants to use all his money and does not want any changes left over. Also he wants to buy exactly two toys. Can you write a program to figure out if there is a set of toys that he can buy this week given the stated constraints ?

In case you haven’t figured it out, this is the classic Two Sum problem. Stated simply:

“Given an array of integers and a target value, check if any two numbers in the array sum up to the given target value.”

Example

Array = [ 2,7, 11, 15] , target value = 9

Clarifying Questions to Ask Interviewer

1. What should the function return ? 
   • It can return either a bool indicating if there are two numbers that add up to the given target.
   • Or, it can return the indices of numbers which add up to the given target. The indices could be returned in an array. If the array is empty, then there are no numbers that add up to the given target.
   • we’ll choose to return a boolean value.
2. Is the input array sorted ?
   • This is a pivotal question – because that’ll tell you what type of algorithm you can use.
   • If the interviewer says, it’s not sorted, go to question # 3 below.
   • If the interviewer says it’s sorted, definitely use solution # 2 except the sorting part.
3. Should we optimize for Space or Run-time ?
   • The interviewer might choose either.
   • Solution # 1 optimizes runtime while Solution # 2 optimizes for space
4. What should we do if the input array is empty or has one value ? That is, what behavior does the calling code expect ?
   • Should we return false or throw an exception ?
   • For .Net or java, throwing a descriptive exception is mostly preferable
5. Could there be future needs to do the same calculations on other data types like doubles or floats ?
   • The problem statement already states that you’re given an integer. However, asking this question shows that you’re not only thinking about the problem at hand, but also future extensibility !
   • If the interviewer desires, you can use Generics in C# or Templates in C++ to make this code work for any numeric data types !
6.  Do we care if the original input array is preserved ?
   • If you need to keep the input array unchanged, then in most cases, you’ll need to use an additional data structure to operate on. In this case, solution # 1 becomes attractive.
   • If the input does not need to be preserved, it opens us the possibility of using solution # 2.

Solution # 1 – Optimize for run time

HINT : Use a HashTable

Algorithm:

1. Loop through the array once and put each entry in a hashtable
2.  Loop through the array a second time and for each value in the array:
   • Calculate the difference of the current array value from the target value; we’ll call this “hashTableValueRequired“
   • Check if the difference is in the hash table or not.
   • If yes, return true
3. If you’ve finished looping through the array without finding the hashTableValueRequired , we return false.

public static bool TwoSum(int[] inputArr, int targetVal)
{
    if(inputArr.Length < 2)
    {
        throw new ArgumentException("Input array needs to have at least two elements!");
    }

    Hashtable myHashTable = new Hashtable();

    // Insert the values in the input array in the hashtable
    for (int i = 0; i < inputArr.Length; i++)
    {
        if (!myHashTable.ContainsValue(inputArr[i]))
        {
            myHashTable.Add(i, inputArr[i]);
        }
    }

    //For each array value, check if the difference between the target value
    // and the array value exists in the hashtable
    for(int i=0; i < inputArr.Length; i++)
    {
        int hashTableValRequired = targetVal - inputArr[i];
        if(myHashTable.ContainsValue(hashTableValRequired))
        {
            // Found a value, which when added to the current array value , add up to the target value
            return true;
        }
    }
    //We finished checking all the values in the array, no luck !
    return false;
}

Time Complexity: O(n) — we loop twice -> n + n = O(n)

Memory Complexity: O(n) — the hash table needs to store n elements

This is all great – but is two scans really necessary ? It turns out no – we can solve this in one scan ! Here’s how :

Algorithm:

1. Loop through the array and for each element in the array:
   • Calculate the difference of the current array value from the target value; we’ll call this “hashTableValueRequired“
   • Check if the difference is in the hash table or not.
   • If yes, return true
   • otherwise, add the array element to the hash table
2. If we’ve looped through the entire array without returning true, it means that there are no two numbers that sum up to the given target.

public static bool TwoSumOneScan(int[] inputArr, int targetVal)
{
    if (inputArr.Length < 2)
    {
        throw new ArgumentException("Input array needs to have at least two elements!");
    }

    Hashtable myHashTable = new Hashtable();

    for (int i = 0; i < inputArr.Length; i++)
    {
        int hashTableValRequired = targetVal - inputArr[i];

        if (myHashTable.ContainsValue(hashTableValRequired))
        {
            // Found a value, which when added to the current array value , add up to the target value
            return true;
        }

        myHashTable.Add(i, inputArr[i]);

    }

    return false;

}

Time Complexity : O(n) — Note that even though the theoretical complexity did not change, we’ll actually save time practically because we’ve eliminated one scan !

Memory Complexity : O(n) — the hash table needs to store n elements

Solution # 2 – Optimize for space

The basic idea here is to solve the problem without the use of an auxiliary data structure like a hash table.

Hint : Sort the array if it’s not already sorted

Algorithm:

1. Sort the given array – this is an O(nlg(n)) operation
2. Get a pointer to the first element of the array, call this leftIndex. Also, get a pointer to the last element of the array, call this rightIndex.
3. Extract the first and last element of the array and store their sum in a temporary variable, called “sum“
4. Loop through the array. On each iteration, check:
   • If targetValue is equal to sum, you’ve established that there are two elements in the array which add up to the given sum. Return true from the function.
   • If sum is less than targetValue, we need to pick a bigger number to add – which must exists to the right of the first value because the array is sorted. So increment leftIndex.
   • If sum is greater than targetValue, we need to pick a smaller number to add – which must exist to the left of the last value. So decrement rightIndex.
5. If you’ve reached the end of the loop and did not return true, such a value must not exist. Return false.

public static bool TwoSumInPlace(int[] inputArr, int targetVal)
{
    if (inputArr.Length < 2)
    {
        throw new ArgumentException("Input array needs to have at least two elements!");
    }

    //Sort the input array
    // This is O(nlg(n)) operation
    Array.Sort(inputArr);

    //get a pointer to the first and last element of the array
    int leftIndex = 0;
    int rightIndex = inputArr.Length - 1;

    while(leftIndex < rightIndex)
    {
        int sum = inputArr[leftIndex] + inputArr[rightIndex];

        // If the element at leftIndex and rightIndex sums to target value, we return true
        if(sum == targetVal)
        {
            return true;
        }

        //if the sum is less than target value, the first element must be to the right of the element at current left index.
        // Why ? Because the array is sorted and the value must be bigger than the value at left index
        // So we increment the left index to the next element in sorted array and check again
        if(sum < targetVal)
        {
            leftIndex = leftIndex + 1;
        }

        // similarly, if the sum is greater than the target value, we need to add two smaller numbers.
        // the way to achieve this is by picking a smaller value for the second number. Since the array is sorted,
        // the smaller value must be to the left of the current rightIndex. So decrement the right index and check again
        if(sum > targetVal)
        {
            rightIndex = rightIndex - 1;
        }
    }

    //we're done looping through the array without having found two such numbers - so Two Sum does not exist
    return false;
}

Time Complexity: There’s two parts:

• Sorting the array – this is O(nlg(n)) operation
• Processing each element of the array – this is O(n) operation
• The two are not nested , hence they just add up : n + nlg(n) = O( nlg(n))

Memory Complexity: O(1) because we’re not using any auxiliary data structure.

Key Lessons to Remember for Coding Interviews

1. Don’t forget to ask clarifying questions to the interviewers – if you don’t, some interviewers might not give you a “hire” rating even if you solve the problem ! For entry level candidates and interns, this is not a big deal, but for experienced level candidates , asking questions and discussing the trade-offs matter a lot !

2. Every solution you choose has a trade-off – most commonly the trade-off the interviewer wants to discuss is between run-time vs memory.  However, instead of asking a canned question like “Should I optimize for space or runtime?” – you can ask a contextual question – for example, where do you expect this code to run ? If it’s in a cache server which is serving queries, speed is more important than memory and you might opt for the hash table solution. Whereas if this is some job that runs in your data layer asynchronously and processes millions of records, duplicating those records in memory might be a no-go and you’ll probably want to run it using the sorting technique.

3. Don’t forget to agree on the algorithm with the interviewer before you start coding ! And yes..ask for help if needed, you might be pleasantly surprised 🙂

If you liked this article, please share it with your friends.