Technical Interview - Find Pairs in Array

Here are my notes on a recent Frontend Dev - ReactJS job. There are a lot of lessons learned.

Before the Interview

I was asked that I prepare my editor of choice before the interview. The interview duration would be set to 45min.

I was going to use VSCode and prepared a create-react-app default app.

The Technical Problem

Given an array of numbers arr, find the pairs that add up to the given number k

Clarifying Questions

I only asked a single clarifying question: Is an optimized solution or just a solution that works? Answer: “Haha, well a solution that works is totally fine”

Later this would turn out to be one of my biggest mistakes. I should have asked a lot more questions before I got started.

Implementing the Solution

Instead of using my prepared react project, I choose to use one of my existing code-training projects with a basic Typescript + Jest setup.

Writing Tests

Since the problem is so simple - I decided it would be better do demonstrate my skills and discipline and write tests first.

I choose to write three scenarios: One positive result, no result, and more than one pair found.

This impressed the interviewer. Additionally, the rest of the development gets a lot easier. Your only focus is now that the test suite does not fail.

import { findPairs } from './addArray'

it('finds positive pairs', () => {
	const input = [1, 2, 3, 4, 5, 6, 7, 8, 9]
	const value = 3
	const output = [[1, 2]]
	expect(findPairs(value, input)).toEqual(output)
})

it('finds no pairs', () => {
	const input = [1, 2, 3]
	const value = 80
	const output: number[][] = []
	expect(findPairs(value, input)).toEqual(output)
})

it('finds positive pairs 2', () => {
	const input = [-1, 1, 2, 3, 4, 5, 6, 7, 8, 9]
	const value = 3
	const output = [
		[-1, 4],
		[1, 2]
	]
	expect(findPairs(value, input)).toEqual(output)
})

Solving the problem

My first working solution was a very solution:

1. iterate over the array
2. Subtract the wanted value from the current value
3. If the array includes the value, add it to the output array

export const findPairs = (k: number, arr: number[]): number[][] => {
	let output: number[][] = []
	arr.forEach((firstParam) => {
		const searchValue = k - firstParam
		if (arr.includes(searchValue)) {
			output.push([firstParam, searchValue])
		}
	})

	return output
}

This solution solves the problem and is short and simple to read.

Feedback to the solution

The interviewer was not happy. The complexity of the solution is O(n^2). While it did find the correct pairs it found two distinct pairs. For the first test case: [[1,2], [2,1]] Additionally, the interviewer did not like that I used Array.forEach(). I was asked to refactor the code to use the more efficient for-loop and If I could change the code so I only get one pair.

Second Implementation

As requested I swapped the forEach() to for loops. Instead of using Array.includes() - I also am using a for-loop and only am iterating over the remaining items.

The implementation is now at O(n*log(n))

export const findPairs2 = (k: number, arr: number[]): number[][] => {
	let output: number[][] = []
	for (let i = 0; i < arr.length; i++) {
		const current = arr[i]
		const searchValue = k - current
		for (let j = i; j < arr.length; j++) {
			const secondParameter = arr[j]
			if (secondParameter === searchValue) {
				output.push([current, searchValue])
			}
		}
	}

	return output
}

Feedback to the solution

Well its fine - did not really improve the optimization - we still have 15min time. There is a solution that is O(n) and uses a single while loop. For this you can assume that the array is sorted.

Third implementation

I needed 20min to find the solution. Mostly because the loop did not end correctly. The solution uses two indexes for the array. It then compares the first and last item of the array. If it matches the sum, it gets added to the output array. If not the indexes are adjusted.

export const findPairs3 = (k: number, arr: number[]): number[][] => {
	let firstIndex = 0
	let lastIndex = arr.length - 1
	const output: number[][] = []

	while (firstIndex < lastIndex) {
		const firstValue = arr[firstIndex]
		const secondValue = arr[lastIndex]
		const sum = firstValue + secondValue

		if (sum > k) {
			lastIndex -= 1
		}
		if (sum < k) {
			firstIndex += 1
		}
		if (sum === k) {
			output.push([firstValue, secondValue])
			firstIndex += 1
			lastIndex -= 1
		}
	}
	return output
}

Summary

What did go right?

• Found multiple solutions
• Used Test Driven Development
• Had knowledge of the O-notation
• Had a backup project available for the interview

What went wrong?

• I should have noticed earlier that the output could have multiple pairs
• Not asking if the array is sorted
• Not asking if the array has unique items
• Assuming that a ‘working solution’ is good enough
• Stumbling during the implementation to correctly end the while loop

Interview Red flags

• A pure algorithms-technical question. No demonstration of ReactJS skills
• No feedback from the interviewer that in my test cases the return pairs are incomplete
• Interviewer disappointed I did not consider millions of items in my first solution.

End of the Interview

The end of the interview was nice. He pointed out where all I had flaws in the solution. The interviewer was impressed that I could produce 3 solutions in such a short time frame.

He was however very disappointed that I did not consider millions of items in my original solution.

I blew it with my response: “In a ReactJS app usually you do not deal with a million item array, you would send only a subset of the data to the client. Do you have to deal with million item arrays in your application?”

The interviewer was rather embarrassed and said something along the lines of “core algorithm skills” are needed. He admitted in a practical application, with small arrays, the performance increase would be probably unnoticeable.

Needless to say - I never heard back from the company.