Blog

Welcome to my algo blog

  • This blog will hold coding challenges I came across.

Remove duplicates in sorted array

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

March 13, 2022 · 1 min · Nolan

Repeated DNA sequence

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

March 7, 2022 · 1 min · Nolan

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