Return to Revisions

I came cross the better idea to solve the algorithm array quadruplet through April 28 10:00 PM mock interview. I like to share better idea to write the algorithm with more elegant code and also address the issues in the above implementation.

I continued to learn the algorithm array quardruplet through mock interview practice. I had practiced over 10 rounds of mock interview last 12 months, and every round I had to work on the algorithm at least two times.

I have worked on the algorithm over 20 times, but I could not come out better idea for my own question here last 5 months. But on April 28, 2018 I had five mock interviews a day. At 12:00 AM, I had chance to interview a peer using array quadruplet again. I found out that the peer had hard time to write a brute force solution. Later in the day my fifth interview, starting from 10:00 PM, the peer finished his algorithm in less than 9 minutes, I finished my algorithm in less than 20 minutes. So I asked the peer a few questions to test his strength on algorithm. The peer has ICPC contest experience with medals in high school, a senior in the university, and then I asked his solution of array quadruplet. He wrote the pseudo code first, and I did not understand his code. So I asked him to explain the algorithm with the example. He gave me some explanation with an example.

Here is the peer'a analysis using C++:

unordered_max ‹ int, pair ‹ int, int› › allSums;

i:
allSums will contain arr[j] + arr[k] for all (j < i && j < k < i )

HashMap.count(x) -> 0 if x is absent
        non-zero otherwise
        
for (int thirdId = 0; thirdId < n; thirdId++) {
  for (int fourthId = thirdId + 1; fourthId < n; fourthId++) {
    int currSum = arr[thirdId] + arr[fouthId];
    if (allSums.count(sum - currSum)) {
      vector <int> ansIds(4);
      ansIds[0] = allSums[sum - currSum].first;  // ? key value - related to index third 
      ansIds[1] = allSums[sum - currSum].second;
      ansIds[2] = thirdId;
      ansIds[3] = fourthId;
      return ansIds;
    }
  }

  for (int firstId = 0; firstId < thirdId; firstId++) {
    allSums[firstId + thirdId] = make_pair(firstId, thirdId);
  }
}            

I asked the peer how allSums is defined, why it is defined that way? Here is his analysis:

thirdId = 0
allSums is empty
thirdId = 1
allSums is empty
thirdId = 2
allSums contain sum arr[0] + arr[1]
thirdId = 3
allSums contain arr[0] + arr[1], arr[0] + arr[2], arr[1] + arr[2]
thirdId = 4

I asked if the peer came cross this problem before. He said that he did.

I think that it is common pattern to build a hashmap based on visited elements in the array when iterating the array. The way to process all elements in the array to two sum hashmap is not smart, causing extra work to check duplicate etc. To reduce time complexity, for each sum only one pair of indexes need to be saved. In other words, there is no need to save all pairs with the same two sum value.

Here is my C# code I wrote based on the discussion in the mock interview.

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

class Solution
{
    public static void Main(string[] args)
    {
        var arrayQuadruplet = FindArrayQuadruplet(new int[] { 3, 2, 1, 4, 6 }, 12);
        Debug.Assert(arrayQuadruplet.Sum() == 12 ); 
    }

    public static int[] FindArrayQuadruplet(int[] numbers, int givenTarget)
    {
        if (numbers == null || numbers.Length < 4)
        {
            return new int[0];
        }

        Array.Sort(numbers);

        var firstTwoNumbersSums = new Dictionary<int, int[]>();

        int length = numbers.Length;

        for (int third = 0; third < length - 1; third++)
        {
            var thirdNumber = numbers[third];

            for (int fourth = third + 1; fourth < length; fourth++)
            {                                
                var fourthNumber = numbers[fourth];
                var lastTwoSum   = thirdNumber + fourthNumber;

                var search = givenTarget - lastTwoSum;

                if (!firstTwoNumbersSums.ContainsKey(search))
                {
                    continue;
                }

                var firstTwo = firstTwoNumbersSums[search];
                return new int[] { numbers[firstTwo[0]], numbers[firstTwo[1]], thirdNumber, fourthNumber };
            }

            // It is time to add visited element into two sum dictionary.
            // Argue that no need to add any two indexes smaller than third, why?            
            for (int firstId = 0; firstId < third; firstId++)
            {
                var firstNumber = numbers[firstId];
                var firstTwoSum = firstNumber + thirdNumber;
                if (!firstTwoNumbersSums.ContainsKey(firstTwoSum))
                {
                    firstTwoNumbersSums.Add(firstTwoSum, new int[]{firstId, third}); 
                }
            }
        }

        return new int[0];
    }    
}