Posts

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.helper(root, nodes) Solution 2 - Iterative Another strategy is for each node keep in memory his parent. Then you can go up the ancestry tree and find the lowest they share. ...

Challenge You are painting post on a fence of size N. Only K consecutive post can have the same color. Return the number of way you can paint the fence. E.g: N = 3 K = 2 -> will return 6 Solution 1 - Time Limted Exceeded class Solution: def helper(self,n, k, fence) ->int: if len(fence) >= 3 and fence[-3] == fence[-2] == fence[-1]: return if len(fence) == n: self.count += 1 return for i in range(0, k): self.helper(n, k, fence + str(i)) def numWays(self, n: int, k: int) -> int: self.count = 0 self.helper(n, k, "") return self.count The code above will create a recursion tree like so: ...

Challenge Given the head of a singly linked list and two integers, reverse the nodes of the list from position left to position right. E.g: reverseBetween(head, 2, 4) 1 -> 2 -> 3 -> 4 -> 5 Returns 1 -> 4 -> 3 -> 2 -> 5 Solution class Solution: def reverse(self, head, steps): tmp = head prev = None tail = head i = 0 while tmp and i < steps: current = tmp n = current.next current.next = prev prev = current tmp = n i+=1 head = current tail.next =n t = head return head def reverseBetween(self, head: ListNode, left: int, right: int) -> ListNode: tmp=head j = 1 prev = None if right -left ==0: return head while tmp and j < left: prev = tmp tmp=tmp.next j =j+1 a = self.reverse(tmp, right+1 - left) if not prev: return a prev.next = a return head Time complexity: O(n) Space complexity: 1 ...

Challenge Given a non-negative number represented as a string, return the smaller possible integer after removing K digits. E.g "1041" 1 Will output 41 Solution 1 I really liked my first solution, however performances can’t be worst. It’s a brute force approach doing backtracking, basically I tried to remove 3 digits in every possible position. from copy import deepcopy class Solution: def helper(self, num, k, arr, start): if len(arr) == k: self.res.append(deepcopy(arr)) return for i in range(start, len(num)): arr.append(i) self.helper(num, k, arr, i+1) arr.remove(i) return def remove_from_list(self, num, to_remove): num = list(num) r = [] for i, e in enumerate(num): if i not in to_remove: r.append(e) return r def removeKdigits(self, num: str, k: int) -> str: if k == len(num): return "0" self.res = [] self.helper(tuple(num), k, [], 0) r = int(num) for i in self.res: ret = self.remove_from_list(num, i) ret = int("".join(ret)) r = min(r, ret) return str(r) Solution 2 After failing on a lot of different test cases it looks like this greedy implementation below works. ...

Challenge I came across this challenge on leetcode that the goal is to generate a new board after a row, column is selected. Here is an online version of the game. It’s a very BFS like challenge, down below the code. Solution class Solution: def is_valid_coord(self, board, row, col): if row >= 0 and row < len(board) and col >= 0 and col < len(board[0]): return True return False def adjacent_mine(self, board, direction, x, y): adjacent_mine = 0 for nx, ny in direction: new_row = nx + x new_col = ny + y if self.is_valid_coord(board, new_row, new_col) and board[new_row][new_col] == 'M': adjacent_mine += 1 return adjacent_mine def updateBoard(self, board: List[List[str]], click: List[int]) -> List[List[str]]: pos_x, pos_y = click if board[pos_x][pos_y] == 'M': board[pos_x][pos_y] = "X" return board queue = [click] # left down right up direction = [[0,-1], [1,-1], [1,0], [1,1], [0,1], [-1,1], [-1,0], [-1,-1]] seen = set() while queue: x, y = queue.pop(0) if board[x][y] == "E" and self.adjacent_mine(board, direction, x, y) == 0: board[x][y] = 'B' seen.add((x, y)) for nx, ny in direction: if self.is_valid_coord(board, nx+x, ny+y) and (nx+x, ny+y) not in seen: queue.append([nx+x, ny+y]) elif board[x][y] == "E" and self.adjacent_mine(board, direction, x, y) >= 0: board[x][y] = str(self.adjacent_mine(board, direction, x, y)) return board Time Complexity: O(m*n) Space Complexity: O(m+n) ...

Challenge Given a String S return all palindrome partitions. Example 1: Input: s = "abc" Output: [["a","b","c"] Example 2: Input: s = "abb" Output: [["a","bb"],["a", "b", "b"]] Solution Get all subset of the string. Check if this subset is only composed of palindromes If so add it to the result class Solution: def check_palindrome(self, s): stack = [] for e in list(s): stack.insert(0, e) for e in s: i = stack.pop(0) if i != e: return False return True def get_all_subsets(self, start, s, arr): if arr and not 0 in arr: self._set.add(tuple(arr[:])) for i in range(start, len(s)): arr.append(i) self.get_all_subsets(i+1, s, arr) arr.pop() return def cutter(self, s, cuts): res = [] for cut in cuts: cut = list(cut) cut = [0] + cut + [len(s)] tmp = [] for i, e in enumerate(cut): if i > 0: tmp.append(s[cut[i-1]:cut[i]]) ct = 0 for t in tmp: if self.check_palindrome(t): ct +=1 if ct == len(tmp): res.append(tmp) if self.check_palindrome(s): res.append([s]) return res def partition(self, s: str) -> List[List[str]]: if not s: return if len(s) == 1: return [s] self._set = set() self.get_all_subsets(0, s, []) return self.cutter(s, self._set) Time complexity Space Complexity O(2^n) O(n)

Challenge Given the head of a linked list, find all the values that appear more than once in the list and delete the nodes that have any of those values. Return the linked list after the deletions. e.g 1 -> 2 ->3 ->2 returns 1 -> 3 Solution # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def print_list(self, head): tmp = head while tmp: print(tmp.val, end=", ") tmp = tmp.next def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode: tmp = head oc = defaultdict(int) while tmp: oc[tmp.val] += 1 tmp = tmp.next tmp = head prev = head while tmp: if oc[tmp.val] > 1 and tmp == head: head = tmp.next prev = head elif oc[tmp.val] > 1: prev.next = tmp.next else: prev = tmp tmp = tmp.next self.print_list(head) return head Solution 2 - Using dummy node def deleteDuplicatesUnsorted(self, head: ListNode) -> ListNode: tmp = head oc = defaultdict(int) while tmp: oc[tmp.val] += 1 tmp = tmp.next fake = ListNode() fake.next = head prev = fake tmp = head while tmp: if oc[tmp.val] > 1: prev.next = tmp.next else: prev = tmp tmp = tmp.next return fake.next

Challenge Implement a queue (FIFO) using only two stacks. The implemented queue should support all the functions of a normal queue (push, peek, pop, and empty). Solution class MyQueue: def __init__(self): self.stack1 = [] self.stack2 = [] self.mypeek = None def push(self, x: int) -> None: if not self.stack1: self.mypeek = x self.stack1.insert(0, x) return None def pop(self) -> int: while len(self.stack1): val = self.stack1.pop(0) self.stack2.insert(0, val) if self.stack2: ret = self.stack2.pop(0) while len(self.stack2): val = self.stack2.pop(0) self.stack1.insert(0, val) return ret def peek(self) -> int: if self.stack1: self.mypeek = self.stack1[len(self.stack1)-1] return self.mypeek if self.peek else None def empty(self) -> bool: if len(self.stack1) == 0: return True return False

Algo I realized, most of the time, I’m not able to find back my answers from previous coding challenges. I can remember a similar problem or want to have a quick reminder about something and I can’t find it… With this blog, I’m hoping that it will change, I’ll try to keep things nice and tidy. I used to post them on www.blog.nolanemirot.com but I feel it’s more convenient to have another blog for that. ...