Two Sum and Its Variants
Problem Statement Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order. Example 1: Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums + nums == 9, we return [0, 1].
Random Linked List Node
Problem Statement Given a singly linked list, return a random node’s value from the linked list. Each node must have the same probability of being chosen. Implement the Solution class: Solution(ListNode head): Initializes the object with the integer array nums. int getRandom(): Chooses a node randomly from the list and returns its value. All the nodes of the list should be equally likely to be choosen. Constraints: The number of nodes in the linked list will be in the range [1, 10^4].
Single Number Given a non-empty array of integers nums, every element appears twice except for one. Find that single one. Example 1: Input: nums = [2,2,1] Output: 1 Example 2: Input: nums = [4,1,2,1,2] Output: 4 Example 3: Input: nums =  Output: 1 Using a HashSet (linear space complexity) We can iterate nums and for each number n do the following: If this is the first time we’ve seen n, then we add n to a hashset If the hashset contains n, then n gets removed from the hashset: 1 2 3 4 5 6 7 8 def get_single_number(nums: List[int]) -> int: uniques = set() for n in nums: if n not in uniques: uniques.
Prime Factorization of a Number
Problem Statement How do we find all the prime factors of a given number? For example, when n = 12, the output should be [2, 3]. Notice that 1, 4, 6, 12 are also factors of 12 but they aren’t prime and therefore should be excluded from the output. Solution The following solution is straightforward: 1 2 3 4 5 6 7 8 9 10 def get_prime_factors(n: int) -> List[int]: prime_factors =  prime = 2 while n > 1: while n % prime == 0: if not prime_factors or prime !
Find all prime numbers up to a given number
Problem Statement How do we find all the prime numbers up to a given number? For example, when n = 10, the output should be 4 since there are 4 prime numbers less than 10, namely 2, 3, 5, 7. Naive Approach A naive approach would be to iterate from 2 to n and count the number of primes along the way: 1 2 3 4 5 def count_primes_less_than(n: int) -> int: return sum(is_prime(i) for i in range(2, n)) def is_prime(num: int) -> bool: return all(num % i !