I just had my phone interview today. The question that I got was the following:

https://leetcode.com/problems/single-number/
Given an array nums of integers, one element appears once, and all other elements appear twice. Return the element that appears once in the array.

Example:

Input:
nums = [3, 5, 9, 2, 8, 5, 2, 9, 3]

Output:
8

I solved the question in O(n)-time | O(n)-space by using a hashmap to keep track of all number counts, iterating through hashmap values, and returning key where value equals 1. Like so:

def findUnique(nums):
	num_counts = numsToDic(nums, {})
	for key, value in num_counts.items():
		if value == 1:
			return key
	return None
	
def numsToDic(nums, dic):
	for num in nums:
		if num not in dic:
			dic[num] = 1
		else:
			dic[num] += 1
	return dic

The interviwer then asked how I would optimize the solution. I solved using the dynamic sliding window technique in O(n)-time | O(1)-space. My solution was to sort array, have two pointers at current number i and second number i + 1, if first number doesn't equal second number check third number i + 2. If second number doesn't equal third number then we're dealing with unique number and return second number. I also solved for edge cases were unique number is at the beginning/end of the array. Like so:

Interviewer said to assume array was sorted.

def findUnique(nums):
	for i in range(len(nums) - 2):
		first_num = nums[i]
		second_num = nums[i + 1]
		# Case unique number at beginning
		if first_num != second_num and i == 0:
			return first_num
		# Case unique number at end
		if i + 2 == len(nums) - 1:
			if second_num != nums[i + 2]:
				return nums[i + 2]
			else:
				break
		if first_num != second_num and second_num != nums[i + 2]:
			return second_num
	return None

The interviewer then said that I am calculating some numbers twice and how would I optimize? At this point I was runing out of time so I gave a hail mary solution using a current set - previous set on a sliding window that I didn't have to code.

I'm still waiting on my results.