← Visa Interview Insights

Visa·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
Mar 2026

Summary

Visa SWE interview had at least one coding problem that looked straightforward until you actually had to nail the time complexity. The binary search angle wasn't obvious to me at first and I think it showed.

Questions Asked (1)

Q1

Given a sorted integer array, an integer k, and a target value x, return the k closest elements to x in the array, sorted in ascending order. For ties, prefer the smaller value.

Algorithms & Data Structures
Author's notes

My first instinct was to just binary search for x and then expand outward with two pointers, which works but I fumbled explaining the complexity.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use binary search to find the insertion point of x, then use two pointers to expand outward and select the k closest elements based on distance, breaking ties by preferring the smaller value. Finally, sort the selected elements in ascending order (or collect them in order if expanding correctly).

Pro tip: Clarify edge cases upfront, such as when k equals the array length or when x is outside the array bounds, and discuss how your approach handles them. Also, mention that the two-pointer expansion can be done in O(k) time after O(log n) binary search, giving O(log n + k) total time.

1. Understand the problem and edge cases

Restate the problem to ensure clarity: find k closest elements to x in a sorted array, with ties broken by smaller value. Discuss edge cases like k >= n, x smaller than all elements, or x larger than all elements.

2. Find the insertion point

Use binary search to find the index where x would be inserted to keep the array sorted. This gives the starting point for the two-pointer approach.

3. Use two pointers to select k closest

Initialize left pointer at insertion point - 1 and right pointer at insertion point. Compare distances of elements at left and right, and pick the closer one, moving the pointer accordingly. For ties, pick the left (smaller) element.

4. Collect and sort the result

Collect the selected elements. If you expand from the middle, you may need to reverse the order to get ascending sorted order. Alternatively, use a data structure to maintain order.

5. Analyze complexity and test

State time complexity: O(log n + k) if done optimally, or O(n) if using a simpler approach. Walk through a few test cases to verify correctness, including edge cases.

Key Points to Mention

  • Binary search to find the closest position efficiently.
  • Two-pointer technique to expand and select k elements.
  • Tie-breaking rule: when distances are equal, prefer the smaller value.
  • Time and space complexity analysis: O(log n + k) time, O(k) space for output.
  • Handling edge cases: k >= n, x outside range, duplicates in array.
  • Alternative approaches: using a max-heap of size k, but note that it's less efficient for sorted arrays.

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