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

Linked list sort

Challenge Given a linked list, your task is to sort it in ascending order. Solution 1 - TLE Using a bubble sort approach. class Solution: def sortList(self, head: Optional[ListNode]) -> Optional[ListNode]: not_sorted = True if not head: return while not_sorted: tmp = head not_sorted = False while tmp.next: if tmp.val > tmp.next.val: tmp.val, tmp.next.val = tmp.next.val, tmp.val not_sorted = True tmp = tmp.next return head Time Complexity: O(n^2) Solution 2 Using a merge sort approach sort approach....

September 1, 2021 · 2 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

Minimum Deletion Cost to Avoid Repeating Letters

Challenge Given a String S and and an array representing the cost of each deletion. You goal is to minimize the cost needed to remove all consecutive repetive characters. Example 1: "aba" [2,3,4] => 0 Example 2: "abaa" [2,3,4,1] => 1 Solution 1 - Brute Force - TLE class Solution: def no_consecutive_letters(self, s): t = "" for e in s: if e !="#": t += e for i in range(1,len(t)): if t[i-1] == t[i]: return False return True def helper(self, s, current_cost, cost, index): if self....

August 21, 2021 · 2 min · Nolan

Valid Move

Challenge You are given a board 8 x 8, a position(x,y) as well of a color. You task is to determine if this move is valid. A move is considered valid, if you have can have (vertically, horizontally or in digonal), starting from this position, a structure like so: color given then opposite N colors then color given. For example [“B”,“W”,“W”,“B”] or [“W”,“B”,“W”] is valid in any direction. This [“B”,“B”,“W”] or [“W”,"....

August 18, 2021 · 2 min · Nolan

Rod Cutting

Challenge Given a rod of length N. You are also given an array that represents the revenue of each cut size. You want to maximize revenue. E.g : [2,3,7,8], piece of length 1 gets you 2$. Solution Top down with Memoization: class Solution: def helper(self, n, cost): if n < 0: return 0 if n == 0: return cost if n in self.memo: return self.memo[n] res = 0 for i in range(1, len(self....

August 6, 2021 · 1 min · Nolan

Catalan Number

Challenge Your task is to print the Nth catalan number. catalan(5) = 42 Solution Bottom up def catalan(n): res = [0 for i in range(n+1)] res[0] = 1 s = 0 for i in range(1, n+1): for j in range(0, i): res[i] += res[j] * res[i-j-1] return res[n] Time Complexity: O(n^2) Top Down def catalan(n): if n == 0 or n ==1: return 1 s = 0 for i in range(n): s += catalan(i) * catalan(n-1-i) return s Time Complexity: O(n!...

August 5, 2021 · 1 min · Nolan

Partition List

Challenge Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x. The order of the initial linked list must be preserved. Solution from copy import deepcopy class Solution: def add_to_list(self, head, node,x): node.next = None if head is None and node.val < x: self.left_part = node self.left_tail = node return elif head is None and node....

August 2, 2021 · 1 min · Nolan

Jump Game

Challenge Given an array of positive intege, each element represents the max length, you need to find the min number of jump in order to reach the end of the array. Input: nums = [2,4,1,1,17] Output: 2 # reach to index 1 and then from there last index. Solution - Recursion (TLE) class Solution: def helper(self, nums, current_index, steps, l, previous): # ending recursion early if already above if len(previous) >= self....

August 1, 2021 · 1 min · Nolan

Lowest Common Ancestors

Challenge Given a binary Tree, find the lowest common ancestor of two nodes. Example: LCA(4,9) => 7 LCA() 3 / \ 7 1 / \ \ 4 9 2 Solution 1 - Recursion class Solution: def helper(self, root, nodes): if not root: return None if root in nodes: return root left = self.helper(root.left, nodes) right = self.helper(root.right,nodes) if left and right: return root if left and right is None: return left if right and left is None: return right def lowestCommonAncestor(self, root: 'TreeNode', nodes: 'List[TreeNode]') -> 'TreeNode': return self....

August 1, 2021 · 2 min · Nolan