Understand what the interviewer is asking for by using test cases and questions about the problem.
- Established a set (2-3) of test cases to verify their own solution later.
- Established a set (1-2) of edge cases to verify their solution handles complexities.
- Have fully understood the problem and have no clarifying questions.
- Have you verified any Time/Space Constraints for this problem?
HAPPY CASE
Input: nums = [2,2,1]
Output: 1
Input
Input: nums = [4,1,2,1,2]
Output: 4
EDGE CASE (Multiple Spaces)
Input: nums = [1]
Output: 1
Match what this problem looks like to known categories of problems, e.g. Linked List or Dynamic Programming, and strategies or patterns in those categories.
For Array/Strings, common solution patterns include:
Plan the solution with appropriate visualizations and pseudocode.
General Idea: Create a hashset and count each number. Remove numbers seen a second time. There should be a single number left in hashset.
1) Create hashset
2) Count each item
3) Remove numbers seen a second time
4) Return number with a single count
General Idea: Use XOR(Exclusive or) and the same number will return zero. All numbers except for one is a duplicate and we isolate the non-duplicate number according to the binary code.
1) Create total variable
2) XOR each number
3) Return remaining number
⚠️ Common Mistakes
Implement the code to solve the algorithm.
General Idea: Create a hashset and count each number. Remove numbers seen a second time. There should be a single number left in hashset.
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# Create hashset
hashset = set()
# Count each item
for num in nums:
# Remove numbers seen a second time
if num in hashset:
hashset.remove(num)
else:
hashset.add(num)
# Return number with a single count
return list(hashset)[0]
class Solution {
public int singleNumber(int[] nums) {
// Create hashset
HashSet<Integer> set = new HashSet<Integer>();
// Count each item
for(int i : nums) {
// Remove numbers seen a second time
if(set.contains(i)) {
set.remove(i);
} else{
set.add(i);
}
}
// Return number with a single count
for(int i:set) {
return i;
}
return -1;
}
}
General Idea: Use XOR(Exclusive or) and the same number will return zero. All numbers except for one is a duplicate and we isolate the non-duplicate number according to the binary code.
class Solution:
def singleNumber(self, nums: List[int]) -> int:
# Create total variable
ans = 0
# XOR each number
for num in nums:
ans ^= num
# Return remaining number
return ans
class Solution {
public int singleNumber(int[] nums) {
// Create total variable
int ans = 0;
// XOR each number
for(int i=0; i<nums.length; i++){
ans ^= nums[i];
}
// Return remaining number
return ans;
}
}
Review the code by running specific example(s) and recording values (watchlist) of your code's variables along the way.
Evaluate the performance of your algorithm and state any strong/weak or future potential work.
Assume N
represents the number of items in array
General Idea: Create a hashset and count each number. Remove numbers seen a second time. There should be a single number left in hashset.
O(N)
we need to view each item in the arrayO(N)
Hashset uses O(N)
because the hashset may store up to O(N/2) numbers before removing them upon seeing the numbers a second time.General Idea: Use XOR(Exclusive or) and the same number will return zero. All numbers except for one is a duplicate and we isolate the non-duplicate number according to the binary code.
O(N)
we need to view each item in the array