Databricks¶
Table of Contents¶
- 362. Design Hit Counter (Medium) 👑
- 751. IP to CIDR (Medium) 👑
- 348. Design Tic-Tac-Toe (Medium) 👑
- 213. House Robber II (Medium)
- 198. House Robber (Medium)
- 1146. Snapshot Array (Medium)
- 2096. Step-By-Step Directions From a Binary Tree Node to Another (Medium)
- 933. Number of Recent Calls (Easy)
362. Design Hit Counter 👑¶
from collections import deque
class HitCounter:
def __init__(self):
self.hits = deque()
def hit(self, timestamp: int) -> None:
self.hits.append(timestamp)
def getHits(self, timestamp: int) -> int:
# Remove hits that are older than 5 minutes (300 seconds)
while self.hits and self.hits[0] <= timestamp - 300:
self.hits.popleft()
return len(self.hits)
obj = HitCounter()
obj.hit(1)
obj.hit(2)
obj.hit(3)
print(obj.getHits(4)) # 3
obj.hit(300)
print(obj.getHits(300)) # 4
print(obj.getHits(301)) # 3
751. IP to CIDR 👑¶
348. Design Tic-Tac-Toe 👑¶
213. House Robber II¶
"""
- Return the maximum amount of money that can be robbed from the houses arranged in a circle.
- Circular → Linear: `nums[0]` and `nums[-1]` cannot be robbed together.
- Rob from `0` to `n - 2`
| n | `nums[n]` | `dp[n-2]` | `dp[n-1]` | `dp[n-2] + nums[n]` | `dp[n]` |
| :-: | :-------: | :-------: | :-------: | :-----------------: | :-----: |
| 0 | 2 | - | 2 | - | 2 |
| 1 | 7 | - | 7 | - | 7 |
| 2 | 9 | 2 | 7 | 11 | 11 |
| 3 | 3 | 7 | 11 | 10 | 11 |
- Rob from `1` to `n - 1`
| n | `nums[n]` | `dp[n-2]` | `dp[n-1]` | `dp[n-2] + nums[n]` | `dp[n]` |
| :-: | :-------: | :-------: | :-------: | :-----------------: | :-----: |
| 1 | 7 | - | - | - | 7 |
| 2 | 9 | - | 7 | - | 9 |
| 3 | 3 | 7 | 9 | 10 | 10 |
| 4 | 1 | 9 | 10 | 10 | 10 |
"""
from typing import List
# DP
def rob(nums: List[int]) -> int:
if len(nums) <= 3:
return max(nums)
def robLinear(nums: List[int]) -> int:
dp = [0 for _ in range(len(nums))]
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
for i in range(2, len(nums)):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
# circle -> linear
a = robLinear(nums[1:]) # 2nd house to the last house
b = robLinear(nums[:-1]) # 1st house to the 2nd last house
return max(a, b)
nums = [2, 7, 9, 3, 1]
print(rob(nums)) # 11
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
// DP
int robDP(vector<int>& nums) {
int n = nums.size();
if (n <= 3) return *max_element(nums.begin(), nums.end());
vector<int> dp1(n, 0), dp2(n, 0);
dp1[0] = nums[0];
dp2[1] = max(nums[0], nums[1]);
for (int i = 2; i < n - 1; i++) {
dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);
}
dp2[1] = nums[1];
dp2[2] = max(nums[1], nums[2]);
for (int i = 3; i < n; i++) {
dp1[i] = max(dp1[i - 1], dp1[i - 2] + nums[i]);
}
return max(dp1[n - 2], dp2[n - 1]);
}
// DP (Space Optimized)
int robDPOptimized(vector<int>& nums) {
int n = nums.size();
if (n <= 3) return *max_element(nums.begin(), nums.end());
int f1 = nums[0];
int f2 = max(nums[0], nums[1]);
int res1;
for (int i = 2; i < n - 1; i++) {
res1 = max(f2, f1 + nums[i]);
f1 = f2;
f2 = res1;
}
f1 = nums[1];
f2 = max(nums[1], nums[2]);
int res2;
for (int i = 3; i < n; i++) {
res2 = max(f2, f1 + nums[i]);
f1 = f2;
f2 = res2;
}
return max(res1, res2);
}
int main() {
vector<int> nums = {2, 3, 2};
cout << robDP(nums) << endl; // 3
cout << robDPOptimized(nums) << endl; // 3
nums = {1, 2, 3, 1};
cout << robDP(nums) << endl; // 4
cout << robDPOptimized(nums) << endl; // 4
return 0;
}
198. House Robber¶
from functools import cache
from typing import List
class Rob:
"""
dp[i] = max(dp[i-1], dp[i-2] + nums[i])
"""
def incursive(self, nums: List[int]) -> int:
"""
time complexity: O(n)
space complexity: O(n)
"""
n = len(nums)
if n <= 2:
return max(nums)
# init
dp = [0 for _ in range(n)]
dp[0], dp[1] = nums[0], max(nums[0], nums[1])
# update
for i in range(2, n):
dp[i] = max(dp[i - 1], dp[i - 2] + nums[i])
return dp[-1]
def incursive_optimized(self, nums: List[int]) -> int:
"""
time complexity: O(n)
space complexity: O(1)
"""
f0, f1 = 0, 0
for num in nums:
f0, f1 = f1, max(f1, f0 + num)
return f1
def memoization(self, nums: List[int]) -> int:
"""
time complexity: O(n)
space complexity: O(n)
"""
n = len(nums)
@cache
def dp(i: int) -> int:
if i < 0:
return 0
return max(dp(i - 1), dp(i - 2) + nums[i])
return dp(n - 1)
if __name__ == "__main__":
nums = [2, 7, 9, 3, 1]
rob = Rob()
assert rob.incursive(nums) == 12
assert rob.incursive_optimized(nums) == 12
assert rob.memoization(nums) == 12
#include <iostream>
#include <vector>
using namespace std;
int rob(vector<int> &nums) {
int prev = 0, cur = 0, temp = 0;
for (int num : nums) {
temp = cur;
cur = max(cur, prev + num);
prev = temp;
}
return cur;
}
int main() {
vector<int> nums = {2, 7, 9, 3, 1};
cout << rob(nums) << endl; // 12
return 0;
}
1146. Snapshot Array¶
2096. Step-By-Step Directions From a Binary Tree Node to Another¶
from typing import Optional
from binarytree import Node as TreeNode
class GetDirections:
def lca(self, root: Optional[TreeNode], startValue: int, destValue: int) -> str:
path_s, path_t = [], []
def dfs(node, target, path):
if not node:
return False
if node.val == target:
return True
path.append("L")
if dfs(node.left, target, path):
return True
path.pop()
path.append("R")
if dfs(node.right, target, path):
return True
path.pop()
return False
dfs(root, startValue, path_s)
dfs(root, destValue, path_t)
i = 0
while i < len(path_s) and i < len(path_t) and path_s[i] == path_t[i]:
i += 1
UP = "U" * (len(path_s) - i)
DOWN = "".join(path_t[i:])
return UP + DOWN