## Problem statement

The algorithm is similar to Leetcode 18 4Sum, the algorithm is to find one unique quadruplets compared to Leetcode 18 finding all unique quadruplets.

Given an array S of n integers, are there elements a, b, c and d in S such that a + b + c + d = target? Find one unique quadruplets in the array which givens the sum of target.

## My mock interview practice

I practiced this algorithm more than four times, but every time I practiced the algorithm, I had different challenges from the peer. First time I was told that I should write the optimized algorithm, the optimized time should be less than O(n^{3}) and it can be implemented using hashmap to store all possible two sums first. The third time I could not complete the algorithm in 30 minutes using the idea to preprocess all possible two sum first, and the peer gave the review “**The code didn’t run through, so maybe you should work on a working solution first**” . So after the third mock interview, I decided only to find one of those four quadruplets with strictly ascending order.

## Highlights of 4th mock practice

I did manage to write the algorithm and used whiteboard testing to go over a simple test case, and passed all test cases in 30 minutes. To structure the interview, I start to practice whiteboard testing right away after I finish the writing, what I do is to put numbers associated with the simplest test case next to almost each line of code. Can we accept the code with whiteboard testing comment next to each line to expedite the writing and reduce the bugs in the code?

## Whiteboard testing is savior

It is the important skill for me to learn how to do whiteboard testing. It helps me to shorten the time to fix all bugs in my first writing. One time I forget to do whiteboard testing during the mock interview, and then I waste over one hour to using Visual Studio and find one simple mistake to mix two variable names, which can be quickly found by going over whiteboard testing in less than five minutes.

I chose the simple test case [3, 2, 1, 4, 5] and the given 4 sum is 12 = 1 + 2 + 4 + 5. Compared to the test case given in the problem statement, this one is easy to follow.

Through whiteboard testing, I found a bug in my design. The array may have duplicate numbers, and then I spent extra 5 minutes to change the design, two extra elements in the array are added to save index number of the array. For illustration, here is the statement in the code: newList.Add(new int[]{no1, no2, i, j}).

In order to avoid complicate logic checking, I enforced the extra rule for the quadruplets, four variables are named for easy to write, called no1, no2, no3, no4. Those variables are the values of the indexes of four elements in a sorted ascending array, assuming that no1 <= no2 <= no3 <= no4.

The following is my C# practice code, please help me review my code.

`using System; using System.Collections.Generic; class Solution { public static int[] FindArrayQuadruplet(int[] arr, int s) // [3, 2, 1, 4, 5] -> given sum: 12 = 1 + 2 + 4 + 5 { if (arr == null || arr.Length < 4) // false { return new int[0]; } Array.Sort(arr); // [1, 2,3, 4, 5] var dictionary = saveTwoSumToDictionary(arr); // int length = arr.Length; for (int first = 0; first < length - 3; first++) // 0, 1 { for (int second = first + 1; second < length - 2; second++) // 1 { var firstTwoSum = arr[first] + arr[second]; // 1 + 2 = 3 var no1 = arr[first]; // 1 var no2 = arr[second]; // 2 var search = s - firstTwoSum; // 12 - 3 = 9 // search the dictionary if (!dictionary.ContainsKey(search)) { continue; } // go over the list to find one var options = dictionary[search]; foreach (int[] pair in options) { // check very simple logic: var no3 = pair[0]; var no4 = pair[1]; var index3 = pair[2]; var unique = no2 <= no3 && second < index3; // same value but index is different, include duplicate number case if (unique) { return new int[] { no1, no2, no3, no4 }; // no1 < no2 < no3 < no4 , duplicate number -> index are different } } } } return new int[0]; } private static IDictionary<int, IList<int[]>> saveTwoSumToDictionary(int[] arr) // [1,2, 3, 4, 5] { var twoSum = new Dictionary<int, IList<int[]>>(); // int length = arr.Length; // 5 for (int i = 0; i < length - 1; i++) // 0 - 3 , 1, 2, 3, 4 { for (int j = i + 1; j < length; j++) // 1, 2, { var no1 = arr[i]; var no2 = arr[j]; var sum = no1 + no2; // 3 if (twoSum.ContainsKey(sum)) // 5 , [1,4], [2, 3] { twoSum[sum].Add(new int[] { no1, no2, i, j }); } else { var newList = new List<int[]>(); newList.Add(new int[] { no1, no2, i, j }); twoSum.Add(sum, newList); } } } return twoSum; } } `