← SoFi Interview Insights

SoFi·Software Engineer·Technical Phone Screen·Intermediate

Intermediate
May 2026

Summary

SoFi software engineer interview with a coding problem that looked manageable until I actually had to think about the efficient path. The question was well-designed and I can see why they use it.

Questions Asked (1)

Q1

Given two sorted integer arrays and a number K, find the K-th largest unique integer across both arrays combined. Duplicates within or across arrays count as a single value. You should aim for an efficient solution that takes advantage of the sorted order rather than merging and re-sorting.

Algorithms & Data Structures
Author's notes

My first instinct was to dump everything into a set and sort descending, which works but they pushed back immediately asking if I could do better given the inputs are already sorted.

Create a free account to read the full note

AI HintsAI Generated

Suggested Approach

Use a modified binary search to find the K-th largest unique element by leveraging the sorted order of both arrays. At each step, pick a candidate value and count how many unique elements are greater than or equal to it using binary search in both arrays, adjusting the search range based on the count. This achieves O(log(min(m,n)) * log(max_value)) time, or O(log(m+n)) with a more optimized approach.

Pro tip: Clarify upfront whether K is 1-indexed (K=1 means largest) and confirm that duplicates are ignored. Also, mention that if K exceeds the number of unique elements, you should return an appropriate error or sentinel value.

1. Clarify requirements and edge cases

Confirm indexing of K, handling of duplicates, and behavior when K is larger than the number of unique elements. Discuss constraints like array sizes and value ranges.

2. Define a counting function

Design a function that, given a value X, returns the number of unique elements >= X across both arrays. Use binary search to find the first occurrence of X in each array and count elements from there, being careful to avoid double-counting duplicates across arrays.

3. Binary search on the answer

Perform binary search over the possible value range (from min to max of both arrays) to find the smallest value X such that count(X) >= K. That X is the K-th largest unique element.

4. Handle duplicates across arrays

When counting, ensure that if the same value appears in both arrays, it is counted only once. This can be done by checking if the value is present in both arrays and adjusting the count accordingly.

5. Analyze complexity and test

State the time complexity (O(log(range) * (log m + log n))) and space complexity (O(1)). Walk through examples, including edge cases like empty arrays, K=1, and all duplicates.

Key Points to Mention

  • Binary search on the value range rather than on indices to handle duplicates and uniqueness.
  • Counting unique elements >= X efficiently using binary search in each sorted array.
  • Handling duplicates across arrays by checking presence in both and avoiding double-counting.
  • Time complexity: O(log(max_val - min_val) * (log m + log n)), which is efficient for large arrays.
  • Edge cases: K larger than unique count, empty arrays, all elements identical.
  • Alternative approach: two-pointer technique from the end to find K-th largest unique, but it may be O(m+n) and less efficient.

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