How do you solve the Two Sum problem and array deduplication in linear time (O(n)) during an SDET technical assessment, and which test cases should you write for them?
Asked by The SDET Playbook
Asked Sep 28, 2026Viewed 0 times
How do you solve the Two Sum problem and array deduplication in linear time (O(n)) during an SDET technical assessment, and which test cases should you write for them?
Asked by The SDET Playbook
Sign in to answer and to vote.
For Two Sum, walk the array once and remember each value's index in a Map. For each number, check whether its complement has already been seen:
/** Returns the indexes of two different elements that add up to target, or null. */
export function twoSum(nums: readonly number[], target: number): [number, number] | null {
const seen = new Map<number, number>();
for (let i = 0; i < nums.length; i++) {
const partner = seen.get(target - nums[i]);
if (partner !== undefined) return [partner, i];
seen.set(nums[i], i);
}
return null;
}
/** Removes duplicates, keeping the first occurrence of each value in order. */
export const dedupe = <T>(items: readonly T[]): T[] => [...new Set(items)];
Both are O(n) in time and space. Set keeps insertion order, so dedupe preserves the original order. It compares values with SameValueZero: NaN counts as equal to itself, but two different objects with the same content don't, which is worth saying before you're asked.
The tests are where you show testing judgment:
import { describe, expect, it } from 'vitest';
import { dedupe, twoSum } from './arrays';
describe('twoSum', () => {
it('finds a pair', () => expect(twoSum([2, 7, 11, 15], 9)).toEqual([0, 1]));
it('does not use the same element twice', () => expect(twoSum([3, 5], 6)).toBeNull());
it('uses two equal values at different indexes', () => expect(twoSum([3, 3], 6)).toEqual([0, 1]));
it('handles negatives and zero', () => expect(twoSum([-4, 0, 4], 0)).toEqual([0, 2]));
it('returns null when there is no pair or no input', () => {
expect(twoSum([1, 2, 3], 100)).toBeNull();
expect(twoSum([], 0)).toBeNull();
});
});
describe('dedupe', () => {
it('keeps the first occurrence, in order', () => expect(dedupe([3, 1, 3, 2, 1])).toEqual([3, 1, 2]));
it('treats NaN as one value', () => expect(dedupe([NaN, NaN])).toEqual([NaN]));
it('keeps objects that are equal in content but not identical', () => expect(dedupe([{ a: 1 }, { a: 1 }])).toHaveLength(2));
});
Before coding, ask what the function should return when there is no pair, or when several pairs qualify. Clarifying the contract is part of what the interviewer is assessing.