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¶
"""
- Design and implement a data structure for **Least Recently Used (LRU) cache**. It should support the following operations: get and put.
- [lru](https://media.geeksforgeeks.org/wp-content/uploads/20240909142802/Working-of-LRU-Cache-copy-2.webp)
- 
| Data structure | Description |
| ------------------ | ----------------------------- |
| Doubly Linked List | To store the key-value pairs. |
| Hash Map | To store the key-node pairs. |
"""
from collections import OrderedDict
# Doubly Linked List
class Node:
def __init__(self, key=0, val=0):
self.key = key
self.val = val
self.prev = None
self.next = None
class LRUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.cache = {}
self.head = Node()
self.tail = Node()
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 move_to_last(self, node):
self.remove(node)
self.add_to_last(node)
def get(self, key: int) -> int:
if key not in self.cache:
return -1
node = self.cache[key]
self.move_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.move_to_last(node)
return None
if len(self.cache) == self.cap:
del self.cache[self.head.next.key]
self.remove(self.head.next)
node = Node(key=key, val=value)
self.cache[key] = node
self.add_to_last(node)
# OrderedDict
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
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
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
print("LRU Cache passed")
print("LRU Cache Ordered Dict passed")
#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
def add_two_numbers(l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
"""Add two numbers represented by linked lists."""
dummy = ListNode()
cur = dummy
carry = 0
while l1 or l2:
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
if carry:
cur.next = ListNode(val=carry)
return dummy.next
def test_add_two_numbers():
l1 = LinkedList([2, 4, 3]).head
l2 = LinkedList([5, 6, 4]).head
added = add_two_numbers(l1, l2)
assert LinkedList(added).to_array() == [7, 0, 8]
#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¶
# Stack
def calculate(s: str) -> int:
stack = []
result = 0
number = 0
sign = 1
for char in s:
if char.isdigit():
number = number * 10 + int(char)
elif char == "+":
result += sign * number
number = 0
sign = 1
elif char == "-":
result += sign * number
number = 0
sign = -1
elif char == "(":
stack.append(result)
stack.append(sign)
result = 0
sign = 1
elif char == ")":
result += sign * number
number = 0
result *= stack.pop() # pop sign
result += stack.pop() # pop previous result
result += sign * number
return result
print(calculate("(1+(4+5+2)-3)+(6+8)")) # 23
56. Merge Intervals¶
"""
- Merge all overlapping intervals.
<iframe width="560" height="315" src="https://www.youtube.com/embed/44H3cEC2fFM?si=J-Jr_Fg2eDse3-de" title="YouTube video player" frameborder="0" allow="accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share" referrerpolicy="strict-origin-when-cross-origin" allowfullscreen></iframe>
"""
from typing import List
# Intervals
def merge(intervals: List[List[int]]) -> List[List[int]]:
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