ByteDance¶
Table of Contents¶
- 146. LRU Cache (Medium)
- 2. Add Two Numbers (Medium)
- 317. Shortest Distance from All Buildings (Hard) 👑
- 347. Top K Frequent Elements (Medium)
- 39. Combination Sum (Medium)
- 424. Longest Repeating Character Replacement (Medium)
- 560. Subarray Sum Equals K (Medium)
- 10. Regular Expression Matching (Hard)
- 224. Basic Calculator (Hard)
- 56. Merge Intervals (Medium)
- 1171. Remove Zero Sum Consecutive Nodes from Linked List (Medium)
146. LRU Cache¶
from collections import OrderedDict
class DoublyListNode:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
"""
Design and implement a data structure for Least Recently Used (LRU) cache.
It should support the following operations: get and put.
"""
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.head = DoublyListNode()
self.tail = DoublyListNode()
self.head.next = self.tail
self.tail.prev = self.head
def remove(self, node):
node.prev.next = node.next
node.next.prev = node.prev
def add_to_last(self, node):
self.tail.prev.next = node
node.prev = self.tail.prev
node.next = self.tail
self.tail.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_to_last(node)
return node.val
def put(self, key: int, value: int) -> None:
if key in self.cache:
node = self.cache[key]
node.val = value
self.remove(node)
self.add_to_last(node)
else:
node = DoublyListNode(key=key, val=value)
self.cache[key] = node
self.add_to_last(node)
if len(self.cache) > self.cap:
lru = self.head.next
del self.cache[lru.key]
self.remove(lru)
class LRUCacheOrderedDict:
def __init__(self, capacity: int):
self.cache = OrderedDict()
self.cap = capacity
def get(self, key: int):
if key not in self.cache:
return -1
self.cache.move_to_end(key, last=True)
return self.cache[key]
def put(self, key: int, value: int):
if key in self.cache:
self.cache.move_to_end(key, last=True)
elif len(self.cache) >= self.cap:
self.cache.popitem(last=False)
self.cache[key] = value
def test_lru_cache():
cache = LRUCache(2)
cache.put(1, 1)
cache.put(2, 2)
assert cache.get(1) == 1
cache.put(3, 3)
assert cache.get(2) == -1
cache.put(4, 4)
assert cache.get(1) == -1
assert cache.get(3) == 3
assert cache.get(4) == 4
updated = LRUCache(2)
updated.put(1, 1)
updated.put(2, 2)
updated.put(1, 10)
updated.put(3, 3)
assert updated.get(1) == 10
assert updated.get(2) == -1
single = LRUCache(1)
single.put(1, 1)
single.put(2, 2)
assert single.get(1) == -1
assert single.get(2) == 2
def test_lru_cache_ordered_dict():
cache = LRUCacheOrderedDict(2)
cache.put(1, 1)
cache.put(2, 2)
assert cache.get(1) == 1
cache.put(3, 3)
assert cache.get(2) == -1
cache.put(4, 4)
assert cache.get(1) == -1
assert cache.get(3) == 3
assert cache.get(4) == 4
#include <cassert>
#include <iostream>
#include <unordered_map>
using namespace std;
class Node {
public:
int key;
int val;
Node *prev;
Node *next;
Node(int k = 0, int v = 0) : key(k), val(v), prev(nullptr), next(nullptr) {}
};
class LRUCache {
private:
int cap;
unordered_map<int, Node *> cache;
Node *head;
Node *tail;
void remove(Node *node) {
node->prev->next = node->next;
node->next->prev = node->prev;
}
void insert_to_last(Node *node) {
tail->prev->next = node;
node->prev = tail->prev;
tail->prev = node;
node->next = tail;
}
void move_to_last(Node *node) {
remove(node);
insert_to_last(node);
}
public:
LRUCache(int capacity) {
this->cap = capacity;
head = new Node();
tail = new Node();
head->next = tail;
tail->prev = head;
}
int get(int key) {
if (cache.find(key) != cache.end()) {
Node *node = cache[key];
move_to_last(node);
return node->val;
}
return -1;
}
void put(int key, int value) {
if (cache.find(key) != cache.end()) {
Node *node = cache[key];
node->val = value;
move_to_last(node);
} else {
Node *newNode = new Node(key, value);
cache[key] = newNode;
insert_to_last(newNode);
if ((int)cache.size() > cap) {
Node *removed = head->next;
remove(removed);
cache.erase(removed->key);
delete removed;
}
}
}
};
int main() {
LRUCache lru(2);
lru.put(1, 1);
lru.put(2, 2);
assert(lru.get(1) == 1); // returns 1
lru.put(3, 3); // evicts key 2
assert(lru.get(2) == -1); // returns -1 (not found)
lru.put(4, 4); // evicts key 1
assert(lru.get(1) == -1); // returns -1 (not found)
assert(lru.get(3) == 3); // returns 3
assert(lru.get(4) == 4); // returns 4
return 0;
}
2. Add Two Numbers¶
from typing import Optional
from leetpattern.utils import LinkedList, ListNode
class Solution:
def addTwoNumbers(
self, l1: Optional[ListNode], l2: Optional[ListNode]
) -> Optional[ListNode]:
"""Digit Carry Simulation: O(max(m, n)) time, O(max(m, n)) space.
Walk both reversed lists while carrying overflow into the next digit.
"""
dummy = ListNode()
cur = dummy
carry = 0
while l1 or l2 or carry:
v1 = l1.val if l1 else 0
v2 = l2.val if l2 else 0
carry, val = divmod(v1 + v2 + carry, 10)
cur.next = ListNode(val)
cur = cur.next
if l1:
l1 = l1.next
if l2:
l2 = l2.next
return dummy.next
def test_add_two_numbers():
s = Solution()
l1 = LinkedList([2, 4, 3]).head
l2 = LinkedList([5, 6, 4]).head
assert LinkedList(s.addTwoNumbers(l1, l2)).to_array() == [7, 0, 8]
l1 = LinkedList([0]).head
l2 = LinkedList([0]).head
assert LinkedList(s.addTwoNumbers(l1, l2)).to_array() == [0]
l1 = LinkedList([9, 9, 9, 9, 9, 9, 9]).head
l2 = LinkedList([9, 9, 9, 9]).head
assert LinkedList(s.addTwoNumbers(l1, l2)).to_array() == [
8,
9,
9,
9,
0,
0,
0,
1,
]
#include <cassert>
#include <vector>
using namespace std;
struct ListNode {
int val;
ListNode* next;
ListNode() : val(0), next(nullptr) {}
ListNode(int x) : val(x), next(nullptr) {}
ListNode(int x, ListNode* next) : val(x), next(next) {}
};
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode dummy;
ListNode* cur = &dummy;
int carry = 0;
while (l1 || l2 || carry) {
if (l1) {
carry += l1->val;
l1 = l1->next;
}
if (l2) {
carry += l2->val;
l2 = l2->next;
}
cur->next = new ListNode(carry % 10);
cur = cur->next;
carry /= 10;
}
return dummy.next;
}
};
int main() {
Solution sol;
ListNode* l1 = new ListNode(2, new ListNode(4, new ListNode(3)));
ListNode* l2 = new ListNode(5, new ListNode(6, new ListNode(4)));
ListNode* result = sol.addTwoNumbers(l1, l2);
vector<int> expected = {7, 0, 8};
for (int val : expected) {
assert(result != nullptr && result->val == val);
result = result->next;
}
assert(result == nullptr); // End of list
return 0;
}
317. Shortest Distance from All Buildings 👑¶
347. Top K Frequent Elements¶
-
Tags: Array, Hash Table, Divide And Conquer, Sorting, Heap Priority Queue, Bucket Sort, Counting, Quickselect
import heapq
from collections import Counter
from typing import List
# Heap + Counter
def topKFrequent(nums: List[int], k: int) -> List[int]:
minHeap = []
for val, freq in Counter(nums).items():
if len(minHeap) < k:
heapq.heappush(minHeap, (freq, val))
else:
heapq.heappushpop(minHeap, (freq, val))
return [i for _, i in minHeap]
# Counter (Most Common)
def topKFrequentCounter(nums: List[int], k: int) -> List[int]:
commons = Counter(nums).most_common(k)
return [i for i, _ in commons]
nums = [1, 1, 1, 2, 2, 3]
k = 2
print(topKFrequent(nums, k)) # [1, 2]
print(topKFrequentCounter(nums, k)) # [1, 2]
39. Combination Sum¶
from typing import List
def combinationSum(candidates: List[int], target: int) -> List[List[int]]:
n = len(candidates)
res, path = [], []
def dfs(total, start):
if total > target:
return
if total == target:
res.append(path.copy())
return
for i in range(start, n):
total += candidates[i]
path.append(candidates[i])
dfs(total, i)
total -= candidates[i]
path.pop()
dfs(0, 0)
return res
if __name__ == "__main__":
print(combinationSum([2, 3, 5], 8))
# [[2, 2, 2, 2], [2, 3, 3], [3, 5]]
print(combinationSum([2, 3, 6, 7], 7))
# [[2, 2, 3], [7]]
424. Longest Repeating Character Replacement¶
from collections import defaultdict
# Sliding Window - Variable
def characterReplacement(s: str, k: int) -> int:
left = 0
maxCount = 0
counts = defaultdict(int)
maxLen = 0
for right in range(len(s)):
counts[s[right]] += 1
maxCount = max(maxCount, counts[s[right]])
while right - left + 1 - maxCount > k:
counts[s[left]] -= 1
left += 1
maxLen = max(maxLen, right - left + 1)
return maxLen
s = "ABAB"
k = 2
print(characterReplacement(s, k)) # 4
560. Subarray Sum Equals K¶
from collections import defaultdict
from typing import List
# Prefix Sum
def subarraySum(nums: List[int], k: int) -> int:
preSums = defaultdict(int)
preSums[0] = 1
curSum = 0
res = 0
for num in nums:
curSum += num
res += preSums[curSum - k]
preSums[curSum] += 1
return res
nums = [1, 1, 1]
k = 2
print(subarraySum(nums, k)) # 2
#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;
int subarraySum(vector<int>& nums, int k) {
int n = nums.size();
vector<int> prefixSum(n + 1);
for (int i = 0; i < n; i++) {
prefixSum[i + 1] = prefixSum[i] + nums[i];
}
int res = 0;
unordered_map<int, int> cnt;
for (int ps : prefixSum) {
if (cnt.find(ps - k) != cnt.end()) res += cnt[ps - k];
cnt[ps]++;
}
return res;
}
int main() {
vector<int> nums = {1, 1, 1};
int k = 2;
cout << subarraySum(nums, k) << endl; // 2
return 0;
}
10. Regular Expression Matching¶
224. Basic Calculator¶
class Solution:
def calculate(self, s: str) -> int:
"""Stack: O(n) time, O(n) space.
Use stack to save result and sign before '(',
restore after ')'.
"""
stack = []
res = 0
num = 0
sign = 1
for char in s:
if char.isdigit():
num = num * 10 + int(char)
elif char == "+":
res += sign * num
num = 0
sign = 1
elif char == "-":
res += sign * num
num = 0
sign = -1
elif char == "(":
stack.append(res)
stack.append(sign)
res = 0
sign = 1
elif char == ")":
res += sign * num
num = 0
res *= stack.pop()
res += stack.pop()
res += sign * num
return res
def test_calculate():
s = Solution()
for fn in (s.calculate,):
assert fn("1 + 1") == 2
assert fn(" 2-1 + 2 ") == 3
assert fn("(1+(4+5+2)-3)+(6+8)") == 23
assert fn("0") == 0
56. Merge Intervals¶
def merge(intervals: list[list[int]]) -> list[list[int]]:
"""
Merge all overlapping intervals.
| G----H
| E===========F
| C--------D
| A========B
|
|-----------------------------------
Draw the above to explain the process to the interviewer.
Time complexity: O(nlogn) due to sorting.
Space complexity: O(n) for the result list.
"""
n = len(intervals)
if n <= 1:
return intervals
intervals.sort(key=lambda x: x[0])
res = [intervals[0]]
for i in range(1, n):
if intervals[i][0] <= res[-1][1]:
res[-1][1] = max(res[-1][1], intervals[i][1])
else:
res.append(intervals[i])
return res
print(merge([[1, 3], [2, 6], [8, 10], [15, 18]]))
# [[1, 6], [8, 10], [15, 18]]
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// Interval
vector<vector<int>> merge(vector<vector<int>>& intervals) {
sort(intervals.begin(), intervals.end());
vector<vector<int>> res;
for (auto& range : intervals) {
if (!res.empty() && range[0] <= res.back()[1]) {
res.back()[1] = max(res.back()[1], range[1]);
} else {
res.emplace_back(range);
}
}
return res;
}
int main() {
vector<vector<int>> intervals = {{1, 3}, {2, 6}, {8, 10}, {15, 18}};
vector<vector<int>> res = merge(intervals);
for (auto& range : res) {
cout << range[0] << ", " << range[1] << endl;
}
return 0;
}
1171. Remove Zero Sum Consecutive Nodes from Linked List¶
from typing import Optional
from leetpattern.utils import ListNode
# Prefix Sum
def removeZeroSumSublists(head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
cur = head
prefix_sum = 0
seen = {0: dummy}
while cur:
prefix_sum += cur.val
if prefix_sum in seen:
node = seen[prefix_sum].next
temp_sum = prefix_sum
while node != cur:
temp_sum += node.val
del seen[temp_sum]
node = node.next
seen[prefix_sum].next = cur.next
else:
seen[prefix_sum] = cur
cur = cur.next
return dummy.next
head = ListNode().create([1, 2, -3, 3, 1])
print(removeZeroSumSublists(head)) # 3 -> 1