Posts

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

Challenge You are given an integer array called nums, your task is to return the longest increasing subsequence. E.g [0,1,2,7] is the longest subsequence of the array [0,3,1,6,2,2,7] Solution 1 - Recursion class Solution: def first_solution(self, nums, index, prev, ct): if index > len(nums): self.m = max(self.m, ct) return self.first_solution(nums, index + 1, prev, ct) if index < len(nums) and nums[index] > prev: self.first_solution(nums, index + 1, nums[index], ct + 1) return ct def lengthOfLIS(self, nums: List[int]) -> int: self.m = 0 self.first_solution(tuple(nums), 0, float("-inf"), 0) return self.m Time complexity: O(n^2) ...

Challenge You are given the root of a binary search tree, where exactly two nodes of the tree were swapped by mistake. Recover the tree without changing its structure. Solution # Definition for a binary tree node. # class TreeNode: # def __init__(self, val=0, left=None, right=None): # self.val = val # self.left = left # self.right = right class Solution: def in_order_traversal(self, root): if root is None: return self.in_order_traversal(root.left) self.arr.append([root.val, root]) self.in_order_traversal(root.right) def recoverTree(self, root: Optional[TreeNode]) -> None: """ Do not return anything, modify root in-place instead. """ self.arr = [] self.in_order_traversal(root) i = 0 to_move = [] orderone = sorted([e[0] for e in self.arr]) while i < len(self.arr): if self.arr[i][0] != orderone[i]: to_move.append(self.arr[i]) i += 1 if len(to_move)>1: if to_move[0] > to_move[1]: to_move[0][1].val, to_move[1][1].val = to_move[1][1].val, to_move[0][1].val return Time complexity: O(n) Space complexity: O(n) ...