Algo

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