commit d3f0506fd71be78dc95a09a173281783ec842c69
parent a4d22b3edc2fef7248cb54af161eac2ed5e230b5
Author: Andrew Laack <andrew@laack.co>
Date: Fri, 13 Jun 2025 18:02:54 -0500
Completed 4 more neetcode
Diffstat:
4 files changed, 134 insertions(+), 0 deletions(-)
diff --git a/find-min-in-rotated-sorted-array/findMin.py b/find-min-in-rotated-sorted-array/findMin.py
@@ -0,0 +1,32 @@
+class Solution:
+ def findMin(self, nums: List[int]) -> int:
+
+ # IDEA:
+
+ # Find the cutoff between low and high values.
+ # Consideration; what happens with a list of all the same values?
+ # Rotated 'n' times to the right, but we don't know n
+
+ # BS approach:
+
+ # With BS we have left (lower bound), center, and right (upper bound)
+ # when do we move right? left?
+ # move right when center > right
+ # move left when center > left
+ # we are there when left and right of current are > current
+
+ left = 0
+ right = len(nums) - 1
+
+ while left <= right:
+
+ center = ((right - left) // 2) + left
+
+ if nums[center] > nums[right]:
+ left = center + 1
+ elif nums[center] > nums[left] or nums[center - 1] < nums[center]:
+ right = center - 1
+ else:
+ return nums[center]
+
+ return 0
diff --git a/longest-substring-without-repeating-characters/longest-substring.py b/longest-substring-without-repeating-characters/longest-substring.py
@@ -0,0 +1,25 @@
+class Solution:
+ def lengthOfLongestSubstring(self, s: str) -> int:
+
+ left_ptr = 0
+ right_ptr = 0
+ longest = 0
+ hash_map = {}
+
+ while right_ptr < len(s):
+
+ # if the right side is in the map, remove characters until it is no longer there
+ if s[right_ptr] in hash_map:
+ while s[right_ptr] in hash_map:
+ del hash_map[s[left_ptr]]
+ left_ptr += 1
+ hash_map[s[right_ptr]] = right_ptr
+ else:
+ hash_map[s[right_ptr]] = right_ptr
+ current_len = (right_ptr - left_ptr) + 1
+ if current_len > longest:
+ longest = current_len
+
+ right_ptr += 1
+
+ return longest
diff --git a/search-in-rotated-sorted-array/searchArray.py b/search-in-rotated-sorted-array/searchArray.py
@@ -0,0 +1,32 @@
+# This was really quite hard.
+class Solution:
+ def search(self, nums: List[int], target: int) -> int:
+
+ left = 0
+ right = len(nums) - 1
+
+ while left <= right:
+
+ center = ((right - left) // 2) + left
+
+ if nums[center] == target:
+ return center
+
+ # CENTER IS ON LEFT SIDE
+ if nums[0] <= nums[center]:
+ if target > nums[center]:
+ left = center + 1
+ else:
+ if target < nums[0]:
+ left = center + 1
+ else:
+ right = center - 1
+ else:
+ if target < nums[center]:
+ right = center - 1
+ else:
+ if target >= nums[0]:
+ right = center - 1
+ else:
+ left = center + 1
+ return -1
diff --git a/time-based-key-value-store/time-based.py b/time-based-key-value-store/time-based.py
@@ -0,0 +1,45 @@
+class TimeMap:
+
+ def __init__(self):
+ self.hash_map = {}
+
+ def set(self, key: str, value: str, timestamp: int) -> None:
+ current = []
+ current_val = []
+
+ if key in self.hash_map:
+ current = self.hash_map[key]
+ current_val = self.hash_map[key + " value"]
+
+ current.append(timestamp)
+ current_val.append(value)
+
+ self.hash_map[key] = current
+ self.hash_map[str(key) + " value"] = current_val
+
+ def get(self, key: str, timestamp: int) -> str:
+
+ current = []
+ current_vals = []
+
+ if key in self.hash_map:
+ current = self.hash_map[key]
+ current_vals = self.hash_map[str(key) + " value"]
+
+ # perform binary search to find the biggest timestamp s.t. prev_timestamp <= timestamp
+
+ left = 0
+ right = len(current) - 1
+
+ while left <= right:
+ center = ((right - left) // 2) + left
+ if (current[center] <= timestamp) and (center == len(current) - 1 \
+ or current[(center + 1)] > timestamp):
+ return current_vals[center]
+ elif current[center] > timestamp:
+ right = center - 1
+ else:
+ left = center + 1
+
+
+ return ""
