Blog

Description Given an integer find the next permutation in given an integer. Examples: 12645 next is 12654 Solution def next_permuation(arr): i = len(arr) -2 while i >= 0 and arr[i] >= arr[i+1]: i -= 1 pivot = i if i >= 0: j = pivot sw = pivot while j < len(arr): if arr[pivot] < arr[j]: sw = j j += 1 arr[pivot], arr[sw] = arr[sw], arr[pivot] res = arr[:pivot+1] + arr[pivot+1:][::-1] return res if __name__ == "__main__": arr = [1, 6, 3, 7, 5] # next permuation is [1, 6, 5, 3, 7] print(next_permuation(arr)) arr = [3, 2, 1] print(next_permuation(arr)) nums = [1, 5, 8, 4, 7, 6, 5, 3, 1] print(next_permuation(nums)) # Output: [1, 5, 8, 5, 1, 3, 4, 6, 7]

Challenge Given an integer array timestamp and an integer windowSize, find the maximum number of requests that occur within any continuous time window of a specified range.The function should return an integer denoting the maximum requests observed in any window of windowSize minutes. Solution def maxRequests(timestamp, windowSize): timestamp.sort() l = 0 r = 1 best = 0 while r < len(timestamp): if timestamp[r] - timestamp[l] >= windowSize : l += 1 best = max(best, r -l + 1) r += 1 return best # Test cases if __name__ == "__main__": # Test case 1: Basic example timestamp1 = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] windowSize1 = 5 print(f"Test 1: timestamp = {timestamp1}, windowSize = {windowSize1}") print(f"Result: {maxRequests(timestamp1, windowSize1)}") print(f"Expected: 5 (requests at times 1,2,3,4,5 or 6,7,8,9,10)\n") # Test case 2: Clustered requests timestamp2 = [1, 2, 3, 10, 11, 12, 13] windowSize2 = 5 print(f"Test 2: timestamp = {timestamp2}, windowSize = {windowSize2}") print(f"Result: {maxRequests(timestamp2, windowSize2)}") print(f"Expected: 4 (requests at times 10,11,12,13)\n") # Test case 3: All requests within window timestamp3 = [1, 2, 3, 4] windowSize3 = 10 print(f"Test 3: timestamp = {timestamp3}, windowSize = {windowSize3}") print(f"Result: {maxRequests(timestamp3, windowSize3)}") print(f"Expected: 4 (all requests fit in window)\n")

Challenge Leetcode 1861 You are given an m x n matrix of characters boxGrid representing a side-view of a box. Each cell of the box is one of the following: A stone ‘#’ A stationary obstacle ‘*’ Empty ‘.’ The box is rotated 90 degrees clockwise, causing some of the stones to fall due to gravity. Each stone falls down until it lands on an obstacle, another stone, or the bottom of the box. Gravity does not affect the obstacles’ positions, and the inertia from the box’s rotation does not affect the stones’ horizontal positions. ...

Challenge Given a sorted integer array, remove duplicate in place that elements appears at most twice. Constraints: The relative order of the elements should be kept the same. Do not allocate extra space for another array. Modify the input array in-place with O(1) extra memory. Don’t change the length of the array return the index of the last element after your operations. Solution 1 class Solution: def removeDuplicates(self, nums: List[int]) -> int: i = 0 ct = 1 diff = 0 my_end = len(nums) while i < my_end: j = i ct = 1 while j < my_end-1: if nums[j] == nums[j+1]: ct += 1 else: break j += 1 if ct > 2: # overwrite start = i + 2 end = i + ct my_end -= end - start z = 0 while end + z < len(nums): nums[start+z] = nums[end+z] z += 1 i += 1 return my_end Solution 2 Soon

Challenge The DNA sequence is composed of a series of nucleotides abbreviated as ‘A’, ‘C’, ‘G’, and ‘T’. For example, “ACGAATTCCG” is a DNA sequence. When studying DNA, it is useful to identify repeated sequences within the DNA. Given a string s that represents a DNA sequence, return all the 10-letter-long sequences (substrings) that occur more than once in a DNA chain. Solution 1 - Iteration class Solution: def findRepeatedDnaSequences(self, s: str) -> List[str]: res = set() _set = set() for i in range(len(s)): seq = s[i:i+10] if seq in _set and seq not in res: res.add(seq) _set.add(seq) return res Time Complexity: 0(n*m) ...

Challenge Given coordinates of two rectangles compute the total area they cover. Solution 1 Use the coordinate to generate the area that overlaps. class Solution: def generates_areas(self, top_left, bottom_right): areas = set() y = top_left[1] while y > bottom_right[1] : x = top_left[0] while x < bottom_right[0]: areas.add(((x,y), (x, y-1), (x+1,y), (x+1, y-1))) x += 1 y -= 1 return areas def computeArea(self, ax1: int, ay1: int, ax2: int, ay2: int, bx1: int, by1: int, bx2: int, by2: int) -> int: rec1 = (ay2 - ay1) * (ax2 - ax1) rec2 = (by2 - by1) * (bx2 - bx1) areas1 = self.generates_areas((ax1,ay2), (ax2, ay1)) areas2 = self.generates_areas((bx1, by2), (bx2, by1)) i = areas1.intersection(areas2) return rec1 + rec2 - len(i) Solution 2 Get the overlap by using min and max, and handle case when then don’t overlap meaning a negative distance. ...

Challenge Given a integer converts it to it’s Roman notation. E.g 14 becomes XIV Solution First I was thinking about adding all conversion in a hash map but it not that will be ask in a real interview scenario. class Solution: def find_representation(self, num, one, five, ten): # if less than 3 rep = "" if 0: return "" if num <= 3: for i in range(num): rep += one # four is five "minus" one if num == 4: rep += one + five # five use five if num == 5: return five # between five and nine use five + one(s) if num > 5 and num < 9: rep = five for i in range(num - 5): rep += one if num == 9: rep += one + ten if num == 10: rep += ten return rep def intToRoman(self, num: int) -> str: thousand = self.find_representation((num % 10000) // 1000, "M","","") hundred = self.find_representation((num % 1000) // 100, "C","D","M") ten = self.find_representation((num % 100) // 10 , "X", "L", "C") ones = self.find_representation(num % 10, "I", "V", "X") return thousand + hundred + ten + ones

Challenge Given two lists of intervals, return the intersection of these two interval lists. Example: list1 = [[0, 2], [5,6], [24, 25]] list2 = [[1,5],[8,13], [25, 26]] OUTPUT = [[1,2],[5,5],[25,25]] Solution #1 - Memory Limit Exceeded class Solution: def interval_intersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]: if not firstList or not secondList: return [] max_val = max(firstList[-1][1],secondList[-1][1]) first = [0 for i in range(0, max_val+1)] second = [0 for i in range(0, max_val+1)] for f in firstList: for i in range(f[0],f[1]): first[i] = 1 for s in secondList: for i in range(s[0],s[1]): second[i] = 1 i = 0 output = [] while i < max_val + 1: if first[i] == second[i] == 1: start_index = i while first[i] == second[i] == 1: i += 1 else: end_index = i output.append([start_index, end_index]) i += 1 i = 0 while i < max_val + 1: if first[i-1] == 0 and first[i] == 1 and second[i-1] == 1 and second[i] == 0: output.append([i,i]) if second[i-1] == 0 and second[i] == 1 and first[i-1] == 1 and first[i] == 0: output.append([i,i]) i += 1 return sorted(output) Memory inefficient because the biggest value of the two lists is used to crate first and second. ...

Challenge … Moist has figured out that the robot’s sorting mechanism is very primitive. It scans the deck of cards from top to bottom. Whenever it finds a card that is lexicographically smaller than the previous card, it moves that card to its correct place in the stack above. This operation costs $1, and the robot resumes scanning down towards the bottom of the deck, moving cards one by one until the entire deck is sorted in lexicographical order from top to bottom. ...

Challenge Given an adjency matrix, find the group of nodes that are connected together. E.g isConnected = [[1,1,0],[1,1,0],[0,0,1]] Will return 2 Data Structure Creating a Disjoin Set data structure using a dictionary. class DisjointSet: def __init__(self, n): self.rank = {i:i for i in range(n)} def __repr__(self): return f"Repr:{self.rank}" def find(self, val): # adding collapsing find original_v = val while self.rank[val] != val: val = self.rank[val] if original_v != val: self.rank[original_v] = val return val def union(self,val1, val2): v1 = self.find(val1) v2 = self.find(val2) self.rank[v2] = v1 Solution class Solution: def findCircleNum(self, isConnected: List[List[int]]) -> int: ds = DisjointSet(len(isConnected[0])) for n, node in enumerate(isConnected): for j, v in enumerate(node): if v == 1 and j !=n: ds.union(n, j) ct = 0 for k,v in ds.rank.items(): if k == v: ct += 1 return ct