← Adobe Interview InsightsSoftware Engineer

Adobe·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

Adobe SWE interview with a classic array intersection problem. The question had a few layers to it and the follow-up caught me a bit flat-footed.

Questions Asked (2)

Q1

Given two sorted integer arrays, find their intersection. Walk through a two-pointer approach, explain how you'd handle duplicates (set vs multiset semantics), and compare it to a hash-set solution in terms of complexity.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

I jumped straight to two pointers which felt right, and the linear time part clicked pretty naturally.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Start by clarifying the problem: confirm sorted order, whether arrays can contain duplicates, and whether the output should have unique elements (set) or preserve multiplicity (multiset). Then walk through the two-pointer technique step-by-step, explaining how to handle duplicates for both semantics. Finally, compare with a hash-set approach, analyzing time and space complexity and discussing trade-offs.

Pro tip: Mention that the two-pointer approach is optimal for sorted arrays because it uses O(1) extra space and can be easily adapted for set or multiset semantics, while the hash-set approach uses O(n) space but works for unsorted arrays. Also, note that if the arrays are very different in size, binary search on the smaller array might be more efficient.

1. Clarify requirements

Ask whether the arrays are sorted, if duplicates are allowed, and whether the intersection should have unique elements (set) or include duplicates (multiset). Confirm the expected output format.

2. Explain two-pointer approach

Initialize pointers i and j at the start of each array. While both pointers are in bounds, compare elements: if equal, add to result and advance both; if one is smaller, advance that pointer. This works because arrays are sorted.

3. Handle duplicates

For set semantics, after adding an element, skip all consecutive duplicates in both arrays. For multiset semantics, add the element and advance both pointers by one, but if duplicates exist, continue comparing and adding as long as elements are equal.

4. Compare with hash-set solution

Describe the hash-set approach: insert all elements of one array into a set, then iterate the other array and check for membership. Discuss time complexity O(m+n) and space O(m) or O(n), and contrast with two-pointer's O(m+n) time and O(1) extra space (excluding output).

5. Summarize trade-offs

Conclude that two-pointer is better for sorted arrays due to lower space, while hash-set is more general (works for unsorted) but uses extra space. Mention that for set semantics, a hash-set can also deduplicate automatically.

Key Points to Mention

  • Two-pointer technique leverages sorted order to achieve O(m+n) time and O(1) extra space.
  • Duplicate handling: set semantics require skipping duplicates; multiset semantics require counting occurrences.
  • Hash-set approach: O(m+n) time but O(min(m,n)) space if using the smaller array for the set.
  • Edge cases: empty arrays, no intersection, all elements intersecting, one array much larger than the other.
  • Complexity analysis: two-pointer is optimal for sorted arrays; hash-set is preferable for unsorted or when space is not a concern.
  • Possible optimization: if one array is much smaller, binary search each element in the larger array for O(n log m) time.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.

Q2

Follow-up: if one array is much smaller than the other, how would you change your approach? Think about binary search.

Algorithms & Data StructuresTechnical Trade-offs
Author's notes

Did not see this coming.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Acknowledge that the optimal approach depends on the relative sizes of the arrays. If one array is much smaller, iterate over the smaller array and for each element, use binary search on the larger sorted array to find a match or intersection. This reduces time complexity from O(m+n) to O(m log n) where m << n.

Pro tip: Mention that if the smaller array is also sorted, you can use a two-pointer approach, but binary search is better when the larger array is sorted and the smaller is not, or when m is significantly smaller than n. Also, consider the cost of sorting if arrays are unsorted.

1. Identify the problem context

Clarify the original problem (e.g., intersection, common elements, or search) and the sizes of the arrays. Confirm that one array is much smaller than the other.

2. Choose the right algorithm

If the larger array is sorted, iterate over the smaller array and binary search each element in the larger array. If the larger array is not sorted, consider sorting it first if the number of queries justifies the O(n log n) preprocessing.

3. Analyze time and space complexity

Compare the binary search approach (O(m log n)) with the two-pointer approach (O(m + n)) and explain why binary search is better when m << n. Discuss space complexity, typically O(1) extra space if output not counted.

4. Handle edge cases and duplicates

Discuss how to handle duplicates (e.g., using binary search to find first and last occurrence) and edge cases like empty arrays or no common elements.

5. Summarize and justify

Conclude that the binary search approach is optimal for skewed sizes, and mention any trade-offs such as the need for sorted input or the overhead of sorting if not already sorted.

Key Points to Mention

  • Time complexity: O(m log n) vs O(m + n), where m is the size of the smaller array and n is the size of the larger array.
  • Binary search requires the larger array to be sorted; if not, sorting it first adds O(n log n) time.
  • Two-pointer approach is better when both arrays are sorted and sizes are comparable, but binary search wins when one array is much smaller.
  • Use binary search to find elements, and if duplicates matter, find the range of occurrences.
  • Space complexity remains O(1) extra space (excluding output) for binary search, while two-pointer also uses O(1).
  • Consider using a hash set for O(m + n) time but O(m) space; binary search is more space-efficient.

AI-generated suggestions, not part of the candidate's original notes. May be inaccurate — verify before relying on them.