- Merge Two Sorted Lists
You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists into one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.
Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode()
tail = dummy
while list1 and list2:
if list1.val < list2.val:
tail.next = list1
list1 = list1.next
else:
tail.next = list2
list2 = list2.next
tail = tail.next
if list1:
tail.next = list1
else:
tail.next = list2
return dummy.next- Subarray Sum Equals K
Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.
A subarray is a contiguous non-empty sequence of elements within an array.
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
res = 0
curSum = 0
prefixSums = {0 : 1}
for n in nums:
curSum += n
diff = curSum - k
res += prefixSums.get(diff, 0)
prefixSums[curSum] = 1 + prefixSums.get(curSum, 0)
return res- Valid Anagram
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
from collections import Counter
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
return Counter(s) == Counter(t)
- Validate IP Address
Given a string queryIP, return “IPv4” if IP is a valid IPv4 address, “IPv6” if IP is a valid IPv6 address or “Neither” if IP is not a correct IP of any type.
A valid IPv4 address is an IP in the form “x1.x2.x3.x4” where 0 <= xi <= 255 and xi cannot contain leading zeros. For example, “192.168.1.1” and “192.168.1.0” are valid IPv4 addresses while “192.168.01.1”, “192.168.1.00”, and “192.168@1.1” are invalid IPv4 addresses.
A valid IPv6 address is an IP in the form “x1:x2:x3:x4:x5:x6:x7:x8” where:
1 <= xi.length <= 4
xi is a hexadecimal string which may contain digits, lowercase English letter (‘a’ to ‘f’) and upper-case English letters (‘A’ to ‘F’).
Leading zeros are allowed in xi.
For example, “2001:0db8:85a3:0000:0000:8a2e:0370:7334” and “2001:db8:85a3:0:0:8A2E:0370:7334” are valid IPv6 addresses, while “2001:0db8:85a3::8A2E:037j:7334” and “02001:0db8:85a3:0000:0000:8a2e:0370:7334” are invalid IPv6 addresses.
class Solution:
def validIPAddress(self, queryIP: str) -> str:
def isIPv4(ip):
parts = ip.split(".")
if len(parts) != 4:
return False
for part in parts:
# empty or non-digit
if not part or not part.isdigit():
return False
# leading zeros
if len(part) > 1 and part[0] == '0':
return False
# range check
if not (0 <= int(part) <= 255):
return False
return True
def isIPv6(ip):
parts = ip.split(":")
if len(parts) != 8:
return False
hex_digits = "0123456789abcdefABCDEF"
for part in parts:
if not (1 <= len(part) <= 4):
return False
for ch in part:
if ch not in hex_digits:
return False
return True
if queryIP.count('.') == 3 and isIPv4(queryIP):
return "IPv4"
elif queryIP.count(':') == 7 and isIPv6(queryIP):
return "IPv6"
else:
return "Neither"- Missing Number
Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.
class Solution:
def missingNumber(self, nums):
n = len(nums)
expected = n * (n + 1) // 2
actual = sum(nums)
return expected - actual
- Contains Duplicate
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
if not nums:
return False
counter = {}
for i in range(len(nums)):
if nums[i] not in counter:
counter[nums[i]] = 1
else:
counter[nums[i]] += 1
for key, value in counter.items():
if value >= 2:
return True
return False- Find the Duplicate Number
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and using only constant extra space.
class Solution:
def findDuplicate(self, nums):
# Step 1: Find intersection point
slow = nums[0]
fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow == fast:
break
# Step 2: Find entrance to cycle
slow = nums[0]
while slow != fast:
slow = nums[slow]
fast = nums[fast]
return slow- Minimum Difference Between Adjacent Elements
Find the minimum absolute difference between any two adjacent elements
class Solution:
def minDifference(self, nums):
min_diff = float(‘inf’)
for i in range(1, len(nums)):
diff = abs(nums[i] - nums[i - 1])
min_diff = min(min_diff, diff)
return min_diff- Group Anagrams
Given an array of strings strs, group the anagrams together. You can return the answer in any order.
from collections import defaultdict
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
groups = defaultdict(list)
for word in strs:
sorted_word = ''.join(sorted(word))
groups[sorted_word].append(word)
return list(groups.values())- Valid Parentheses
Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.
An input string is valid if:
Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.
Every close bracket has a corresponding open bracket of the same type.
class Solution:
def isValid(self, s: str) -> bool:
stack = []
mapping = {
‘)’: ‘(‘,
‘}’: ‘{‘,
‘]’: ‘[’
}
for char in s:
if char in mapping:
# closing bracket
if not stack or stack[-1] != mapping[char]:
return False
stack.pop()
else:
# opening bracket
stack.append(char)
return len(stack) == 0- Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object.
void push(int val) pushes the element val onto the stack.
void pop() removes the element on the top of the stack.
int top() gets the top element of the stack.
int getMin() retrieves the minimum element in the stack.
You must implement a solution with O(1) time complexity for each function.
class MinStack:
def \_\_init\_\_(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
if self.stack[-1] == self.min_stack[-1]:
self.min_stack.pop()
self.stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]- Max Stack
class Node:
def __init__(self, val):
self.val = val
self.prev = None
self.next = None
class MaxStack:
def \_\_init\_\_(self):
self.head = Node(0) # dummy head
self.tail = Node(0) # dummy tail
self.head.next = self.tail
self.tail.prev = self.head
self.map = {} # val -> list of nodes
self.max_val = float('-inf')
def _add(self, node):
prev = self.tail.prev
prev.next = node
node.prev = prev
node.next = self.tail
self.tail.prev = node
def _remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def push(self, x: int) -> None:
node = Node(x)
self._add(node)
if x not in self.map:
self.map[x] = []
self.map[x].append(node)
self.max_val = max(self.max_val, x)
def pop(self) -> int:
node = self.tail.prev
self._remove(node)
self.map[node.val].pop()
if not self.map[node.val]:
del self.map[node.val]
if node.val == self.max_val:
self.max_val = max(self.map.keys(), default=float('-inf'))
return node.val
def top(self) -> int:
return self.tail.prev.val
def peekMax(self) -> int:
return self.max_val
def popMax(self) -> int:
max_val = self.max_val
node = self.map[max_val].pop()
self._remove(node)
if not self.map[max_val]:
del self.map[max_val]
self.max_val = max(self.map.keys(), default=float('-inf'))
return max_val- Daily Temperatures
Given an array of integers temperatures represents the daily temperatures, return an array answer such that answer[i] is the number of days you have to wait after the ith day to get a warmer temperature. If there is no future day for which this is possible, keep answer[i] == 0 instead.
class Solution:
def dailyTemperatures(self, temperatures):
n = len(temperatures)
result = [0] * n
stack = [] # stores indices
for i, temp in enumerate(temperatures):
# resolve previous colder days
while stack and temperatures[stack[-1]] < temp:
prev_index = stack.pop()
result[prev_index] = i - prev_index
stack.append(i)
return result- Logger Rate Limiter
Design a logger system that receives a stream of messages along with timestamps. Each message should be printed only if it has not been printed in the last 10 seconds.
Implement the Logger class:
Logger() Initializes the logger object.
bool shouldPrintMessage(int timestamp, string message)
Returns true if the message should be printed.
Returns false if the message should not be printed.
Each timestamp is given in seconds.
Timestamps are non-decreasing (important constraint)
class Logger:
def \_\_init\_\_(self):
self.last_seen = {}
def shouldPrintMessage(self, timestamp: int, message: str) -> bool:
if message not in self.last_seen:
self.last_seen[message] = timestamp
return True
if timestamp - self.last_seen[message] >= 10:
self.last_seen[message] = timestamp
return True
return False- Design Hit Counter
Design a hit counter that counts the number of hits received in the past 5 minutes (300 seconds).
Implement the HitCounter class:
HitCounter() Initializes the object.
void hit(int timestamp)
Records a hit at the given timestamp (in seconds).
int getHits(int timestamp)
Returns the number of hits in the past 300 seconds (including current timestamp).
🔒 Constraints
Timestamps are monotonically increasing (non-decreasing)
Multiple hits can occur at the same timestamp
from collections import deque
class HitCounter:
def \_\_init\_\_(self):
self.queue = deque()
def hit(self, timestamp: int) -> None:
self.queue.append(timestamp)
def getHits(self, timestamp: int) -> int:
# remove outdated hits
while self.queue and timestamp - self.queue[0] >= 300:
self.queue.popleft()
return len(self.queue)- Number of Recent Calls
You have a RecentCounter class which counts the number of recent requests within a certain time frame.
Implement the RecentCounter class:
RecentCounter() Initializes the counter with zero recent requests.
int ping(int t) Adds a new request at time t, where t represents some time in milliseconds, and returns the number of requests that has happened in the past 3000 milliseconds (including the new request). Specifically, return the number of requests that have happened in the inclusive range [t - 3000, t].
It is guaranteed that every call to ping uses a strictly larger value of t than the previous call.
from collections import deque
class RecentCounter:
def \_\_init\_\_(self):
self.queue = deque()
def ping(self, t: int) -> int:
self.queue.append(t)
# remove outdated requests
while self.queue and self.queue[0] < t - 3000:
self.queue.popleft()
return len(self.queue)- LRU Cache
Design a data structure that follows the constraints of a Least Recently Used (LRU) cache.
Implement the LRUCache class:
LRUCache(int capacity) Initialize the LRU cache with positive size capacity.
int get(int key) Return the value of the key if the key exists, otherwise return -1.
void put(int key, int value) Update the value of the key if the key exists. Otherwise, add the key-value pair to the cache. If the number of keys exceeds the capacity from this operation, evict the least recently used key.
The functions get and put must each run in O(1) average time complexity.
class Node:
def __init__(self, key, val):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def \_\_init\_\_(self, capacity: int):
self.capacity = capacity
self.cache = {} # key -> node
# dummy nodes
self.head = Node(0, 0)
self.tail = Node(0, 0)
self.head.next = self.tail
self.tail.prev = self.head
# remove node
def _remove(self, node):
prev, nxt = node.prev, node.next
prev.next = nxt
nxt.prev = prev
# add node to front
def _add(self, node):
nxt = self.head.next
self.head.next = node
node.prev = self.head
node.next = nxt
nxt.prev = node
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self._remove(node)
self._add(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
self._remove(self.cache[key])
node = Node(key, value)
self.cache[key] = node
self._add(node)
if len(self.cache) > self.capacity:
# remove LRU (tail.prev)
lru = self.tail.prev
self._remove(lru)
del self.cache[lru.key]- LFU Cache
Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the LFUCache class:
LFUCache(int capacity) Initializes the object with the capacity of the data structure.
int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.
To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.
When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.
The functions get and put must each run in O(1) average time complexity.
from collections import defaultdict, OrderedDict
class LFUCache:
def \_\_init\_\_(self, capacity: int):
self.capacity = capacity
self.key_to_val_freq = {} # key -> (val, freq)
self.freq_to_keys = defaultdict(OrderedDict)
self.min_freq = 0
def _update(self, key):
val, freq = self.key_to_val_freq[key]
# remove from current freq list
del self.freq_to_keys[freq][key]
if not self.freq_to_keys[freq]:
del self.freq_to_keys[freq]
if self.min_freq == freq:
self.min_freq += 1
# add to next freq
self.freq_to_keys[freq + 1][key] = None
self.key_to_val_freq[key] = (val, freq + 1)
def get(self, key: int) -> int:
if key not in self.key_to_val_freq:
return -1
self._update(key)
return self.key_to_val_freq[key][0]
def put(self, key: int, value: int) -> None:
if self.capacity == 0:
return
if key in self.key_to_val_freq:
self.key_to_val_freq[key] = (value, self.key_to_val_freq[key][1])
self._update(key)
return
# evict if needed
if len(self.key_to_val_freq) >= self.capacity:
# pop LRU from min_freq
k, _ = self.freq_to_keys[self.min_freq].popitem(last=False)
del self.key_to_val_freq[k]
if not self.freq_to_keys[self.min_freq]:
del self.freq_to_keys[self.min_freq]
# insert new key
self.key_to_val_freq[key] = (value, 1)
self.freq_to_keys[1][key] = None
self.min_freq = 1- Design HashMap
Design a HashMap without using any built-in hash table libraries.
Implement the MyHashMap class:
MyHashMap() initializes the object with an empty map.
void put(int key, int value) inserts a (key, value) pair into the HashMap. If the key already exists in the map, update the corresponding value.
int get(int key) returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key.
void remove(key) removes the key and its corresponding value if the map contains the mapping for the key.
class MyHashMap:
def \_\_init\_\_(self):
self.size = 1000
self.buckets = [[] for _ in range(self.size)]
def _hash(self, key):
return key % self.size
def put(self, key: int, value: int) -> None:
index = self._hash(key)
bucket = self.buckets[index]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key: int) -> int:
index = self._hash(key)
bucket = self.buckets[index]
for k, v in bucket:
if k == key:
return v
return -1
def remove(self, key: int) -> None:
index = self._hash(key)
bucket = self.buckets[index]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket.pop(i)
return- Design HashSet
Design a HashSet without using any built-in hash table libraries.
Implement MyHashSet class:
void add(key) Inserts the value key into the HashSet.
bool contains(key) Returns whether the value key exists in the HashSet or not.
void remove(key) Removes the value key in the HashSet. If key does not exist in the HashSet, do nothing.
class MyHashSet:
def \_\_init\_\_(self):
self.size = 1000
self.buckets = [[] for _ in range(self.size)]
def _hash(self, key):
return key % self.size
def add(self, key: int) -> None:
index = self._hash(key)
bucket = self.buckets[index]
if key not in bucket:
bucket.append(key)
def remove(self, key: int) -> None:
index = self._hash(key)
bucket = self.buckets[index]
if key in bucket:
bucket.remove(key)
def contains(self, key: int) -> bool:
index = self._hash(key)
bucket = self.buckets[index]
return key in bucket- Implement Stack Using Queues
Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).
Implement the MyStack class:
void push(int x) Pushes element x to the top of the stack.
int pop() Removes the element on the top of the stack and returns it.
int top() Returns the element on the top of the stack.
boolean empty() Returns true if the stack is empty, false otherwise.
Notes:
You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.
from collections import deque
class MyStack:
def \_\_init\_\_(self):
self.q = deque()
def push(self, x: int) -> None:
self.q.append(x)
# rotate queue to make x the front
for _ in range(len(self.q) - 1):
self.q.append(self.q.popleft())
def pop(self) -> int:
return self.q.popleft()
def top(self) -> int:
return self.q[0]
def empty(self) -> bool:
return len(self.q) == 0- Merge Intervals
Given an array of intervals where intervals[i] = [starti, endi], merge all overlapping intervals, and return an array of the non-overlapping intervals that cover all the intervals in the input.
class Solution:
def merge(self, intervals):
intervals.sort(key=lambda x: x[0])
merged = []
for interval in intervals:
# if no overlap, add new interval
if not merged or merged[-1][1] < interval[0]:
merged.append(interval)
else:
# merge intervals
merged[-1][1] = max(merged[-1][1], interval[1])
return merged- Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
from collections import Counter
import heapq
class Solution:
def topKFrequent(self, nums, k):
count = Counter(nums)
heap = []
for num, freq in count.items():
heapq.heappush(heap, (freq, num))
if len(heap) > k:
heapq.heappop(heap)
return [num for freq, num in heap]- K Closest Points to Origin
Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).
The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).
You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).
import heapq
class Solution:
def kClosest(self, points, k):
heap = []
for x, y in points:
dist = x*x + y*y
heapq.heappush(heap, (dist, [x, y]))
result = []
for _ in range(k):
result.append(heapq.heappop(heap)[1])
return result
