J.P. Morgan Quantitative Researcher Interview Experience — Second-Round Video Interview and the Lonely Number Coding Question

This is a fairly old Analyst role. The position is Quant Researcher, and this was the second round, a video interview.

I want to share one JPMC coding question: Lonely Number.

The problem: given an integer array, return all the lonely numbers. A number x is a lonely number if its neighbors x-1 and x+1 are both not in the input array.

Example: Input: [3, 7, 9, 4], Output: [7, 9]

Reasoning: 3 is not lonely, because 4 is in the array. 7 is lonely, because neither 6 nor 8 is in the array. 9 is lonely, because neither 8 nor 10 is in the array. 4 is not lonely, because 3 is in the array.

My approach:

If sorting is allowed, sort the array first and then iterate once. After sorting you only need to look at the numbers right before and after the current one and check whether x-1 or x+1 is there.

Python:

def lonely_numbers(nums):
    nums.sort()
    result = []
    for i, num in enumerate(nums):
        left_ok = i == 0 or nums[i - 1] != num - 1
        right_ok = i == len(nums) - 1 or nums[i + 1] != num + 1
        if left_ok and right_ok:
            result.append(num)
    return result

Time complexity is O(n log n), mainly from the sorting.

If the interviewer does not allow sorting, you can use an OrderedDict, or a dict that keeps insertion order. Put all the numbers in first, then iterate over each number and directly check whether x-1 and x+1 are in the dictionary.

Python:

def lonely_numbers(nums):
    lookup = dict.fromkeys(nums)
    result = []
    for num in lookup:
        if num - 1 not in lookup and num + 1 not in lookup:
            result.append(num)
    return result

This gives O(n) average time complexity and O(n) space complexity.

In the interview you can also confirm how duplicates are handled. For example with [7, 7], is 7 still lonely? By the definition in the problem, it only requires that x-1 and x+1 are absent, so it should still count, but it is best to clarify with the interviewer.

Overall the problem is not hard. If you give the sort solution first, the interviewer may follow up by asking what to do if you cannot sort, and that is when you bring up the OrderedDict / hash map approach.