Rectangle areas

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....

February 13, 2022 · 1 min · Nolan

Integer to roman number

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....

February 8, 2022 · 1 min · Nolan

Interval list intersection

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....

February 8, 2022 · 2 min · Nolan

Moist - Kick start 2013 Practice round

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....

February 7, 2022 · 2 min · Nolan

Disjoint Set

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....

October 10, 2021 · 1 min · Nolan

Longest Increasing Subsequence

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....

October 1, 2021 · 2 min · Nolan

Recover BST

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....

September 24, 2021 · 1 min · Nolan

Find duplicate subtrees

Challenge Given the root of a binary tree, return all duplicate subtrees. You only need to return the root of any of them. 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 __init__(self): self.all_node = [] self.ans = [] self.s = set() def preorder(self, root, arr): arr.append(root.val) if root....

September 10, 2021 · 1 min · Nolan

Valid Word Abbreviation

Challenge Given two params a word and it’s abbreviation return True if the abbreviation is valid. Examples: "kubernetes" "k8s" => True "apple" "a2e" => False Solution This is the kind of implementation challenges easy to get wrong and/or forgot edge cases… class Solution: def validWordAbbreviation(self, word: str, abbr: str) -> bool: i = 0 tmp = "" if len(abbr) > 1 and abbr.isdecimal(): return False index = 0 while i < len(abbr): number = "" while i < len(abbr) and abbr[i]....

September 9, 2021 · 1 min · Nolan

House Robber

Challenge The array nums represent the value inside each house. What is stopping you to rob everything is that you cannot rob two consecutive houses without triggering the alarm. Determine the maxium amout of money you can rob without triggering the alarm. Solution 1 - Recursion class Solution: def helper(self, index, nums, val): if index > len(nums)-1: self.m = max(self.m, val) return self.helper(index+1, nums, val) self.helper(index+2, nums, nums[index] + val) def rob(self, nums: List[int]) -> int: self....

August 23, 2021 · 1 min · Nolan