Common or Noteworthy Problems / (Named) Algorithms Knuth-Morris-Pratt: class Solution(object): https://leetcode.com/problems/implement-strstr
def strStr(self, haystack, needle): if not needle: return 0 if not haystack: return -1 next_arr = self.create_next(needle) i = j = 0 while i < len(haystack) and j < len(needle): if haystack[i] == needle[j]: # Matched, so return the haystack's match start index. if j == len(needle) - 1: return i - len(needle) + 1 i, j = i + 1, j + 1 else: # Slide pattern over. if j: j = next_arr[j-1] else: i += 1 return -1 # Build next jump table. def create_next(self, pattern): next_arr = [0] * len(pattern) pre_i, suf_i = 0, 1 while suf_i < len(pattern): # Found prefix-suffix match. if pattern[pre_i] == pattern[suf_i]: next_arr[suf_i] = pre_i + 1 pre_i, suf_i = pre_i + 1, suf_i + 1 else: if pre_i: pre_i = next_arr[pre_i-1] else: next_arr[suf_i] = 0 suf_i += 1 return next_arr Making change: https://www.interviewcake.com/question/python/coin
Task: Write a function that, given: an amount of money a list of coin denominations computes the number of ways to make amount of money with coins of the available denominations. Code: Bottom-up DP memoization: def change_possibilities_bottom_up(amount, denominations): ways_of_doing_n_cents = [0] * (amount + 1) ways_of_doing_n_cents[0] = 1 for coin in denominations: for higher_amount in xrange(coin, amount + 1): higher_amount_remainder = higher_amount - coin ways_of_doing_n_cents[higher_amount] += ways_of_doing_n_cents[higher_amount_remainder] return ways_of_doing_n_cents[amount] Maximum sum subarray / Kadane's algorithm: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
Task: find the contiguous subarray which has the largest sum Algorithm: "a scan through the array values, computing at each position the maximum (positive sum) subarray ending at that position. This subarray is either empty (in which case its sum is zero) or consists of one more element than the maximum subarray ending at the previous position. The algorithm only needs to keep track of the ending position because the implied starting position is just after the last position at which the sum went negative; a higher sum can always be found by dropping any negative-sum prefix." https://www.wikiwand.com/en/Maximum_subarray_problem
"look for all positive contiguous segments of the array (max_ending_here is used for this). And keep track of maximum sum contiguous segment among all positive segments (max_so_far is used for this). Each time we get a positive sum compare it with max_so_far and update max_so_far if it is greater than max_so_far" http://www.geeksforgeeks.org/largest-sum-contiguous-subarray/
Basically, keep accumulating sum (max_ending_here) until the sum becomes negative, at which point you start over again (e.g., set back to 0). Then max_so_far is max_ending_here if the latter is greater than the previous max_so_far. The key is that no solution will include a negative sum prefix (because the sum could be larger if it just left that prefix off). Pseudocode: Complexity: O(N).
Wiki: def max_subarray(A): max_ending_here = max_so_far = 0 for x in A: max_ending_here = max(0, max_ending_here + x) max_so_far = max(max_so_far, max_ending_here) return max_so_far Not as clean: def maxSubArraySum(a,size): max_so_far = -maxint - 1 max_ending_here = 0 for i in range(0, size): max_ending_here = max_ending_here + a[i] if (max_so_far < max_ending_here): max_so_far = max_ending_here if max_ending_here < 0: return max_so_far Examples: https://leetcode.com/problems/best-time-to-buy-and-sell-stock/ Say you have an array for which the ith element is the price of a given stock on day i. If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit. Example 1: Input: [7, 1, 5, 3, 6, 4] Output: 5 max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price) Example 2: Input: [7, 6, 4, 3, 1] Output: 0 In this case, no transaction is done, i.e. max profit = 0. def maxProfit(self, prices): """ :type prices: List[int] :rtype: int """ max_curr = max_so_far = 0 for i, price in enumerate(prices[1:]): max_curr = max(0, max_curr + price - prices[i]) max_so_far = max(max_so_far, max_curr) return max_so_far Maximum size subarray sum equals k : https://leetcode.com/problems/maximum-size-subarray-sum-equals-k/
Task: Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead. Note: The sum of the entire nums array is guaranteed to fit within the 32-bit signed integer range. Example 1: Given nums = [1, -1, 5, -2, 3], k = 3, return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest) Example 2: Given nums = [-2, -1, 2, 1], k = 1, return 2. (because the subarray [-1, 2] sums to 1 and is the longest) Follow Up: Can you do it in O(n) time? Code: def maxSubArrayLen(self, nums, k): """ :type nums: List[int] :type k: int :rtype: int """ sum_dict = {0: -1} ans = acc = 0 for i, num in enumerate(nums): acc += num if acc not in sum_dict: sum_dict[acc] = i if acc-k in sum_dict: ans = max(ans, i - sum_dict[acc-k]) return ans Maximum depth of binary tree: https://leetcode.com/problems/maximum-depth-of-binary-tree/
Task: Given a binary tree, find its maximum depth. The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node. Code: Recursive: # Definition for a binary tree node. # class TreeNode: # def __init__(self, x): # self.val = x # self.left = None # self.right = None class Solution: # @param {TreeNode} root # @return {integer} def maxDepth(self, root): # Base case: no node. if not root: return 0 # Recursive case: the maximum of the depths of the left and right sides plus the root depth (1). return max(Solution.maxDepth(self, root.left), Solution.maxDepth(self, root.right)) + 1 Iterative: from collections import deque def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ # Iterative method: count number of levels. if not root: return 0 q, depth = deque(), 0 q.append(root) while(True): nodect = len(q) if not nodect: return depth depth += 1 while nodect: node = q.popleft() if node.left: q.append(node.left) if node.right: q.append(node.right) nodect -= 1 Binary tree paths https://leetcode.com/problems/binary-tree-paths/
Task: Given a binary tree, return all root-to-leaf paths. For example, given the following binary tree: All root-to-leaf paths are: ["1->2->5", "1->3"] Code: DFS recursive: def binaryTreePaths(self, root): """ :type root: TreeNode :rtype: List[str] """ if not root: return [] res = [] self.dfs(root, "", res) return res def dfs(self, root, ret_str, res): if not root.left and not root.right: res.append(ret_str + str(root.val)) if root.left: self.dfs(root.left, ret_str + str(root.val) + '->', res) if root.right: self.dfs(root.right, ret_str + str(root.val) + '->', res) DFS iterative (with stack): def binaryTreePaths1(self, root): if not root: res, stack = [], [(root, "")] while stack: node, ls = stack.pop() if not node.left and not node.right: res.append(ls+str(node.val)) if node.right: stack.append((node.right, ls+str(node.val)+"->")) if node.left: stack.append((node.left, ls+str(node.val)+"->")) return res BFS (with queue): def binaryTreePaths2(self, root): if not root: res, queue = [], collections.deque([(root, "")]) while queue: node, ls = queue.popleft() if not node.left and not node.right: res.append(ls+str(node.val)) if node.left: queue.append((node.left, ls+str(node.val)+"->")) if node.right: queue.append((node.right, ls+str(node.val)+"->")) return res Single number: https://leetcode.com/problems/single-number/
Task: Given an array of integers, every element appears twice except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? Code: My non-xor one: def singleNumber(self, nums): """ :type nums: List[int] :rtype: int """ # 1, 1, 2, 3, 3 # 1, 2, 2 # 1, 1, 2, 2, 3 nums.sort() for i, n in enumerate(nums): # If odd number of elements and on last element, must be odd man out. if len(nums) % 2 != 0 and i == len(nums) - 1: return n # Compare every pair. if i % 2 != 0: continue if n != nums[i+1]: return n XOR solutions (xor of the same numbers returns 0; xor of a nonzero number and zero returns the nonzero number): def singleNumber(self, nums): res = 0 for num in nums: return res def singleNumber(self, nums): return reduce(lambda x, y: x ^ y, nums) Reverse linked list: https://leetcode.com/problems/reverse-linked-list/
Task: Reverse a singly linked list. Hint: A linked list can be reversed either iteratively or recursively. Could you implement both? Code: Concise iterative: def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ prev = None curr = head # Change one link at a time. while(curr is not None): # Hold on to next node since will redirect link. next = curr.next # Reverse link direction. curr.next = prev # Update prev pointer. prev = curr # Update curr pointer for next iteration. curr = next # Not curr since will be None. return prev Concise recursive: def reverseList(self, head, prev=None): """ :type head: ListNode :rtype: ListNode """ if not head: return prev # Reverse links, making sure to hold on to the next node. curr = head.next head.next = prev return self.reverseList(curr, head) Worked out example: # 4 -> 1 -> 3 -> None # None <- 4 <- 1 <- 3 # = 3 -> 1 -> 4 -> None # # curr = 1 # head.next = 4.next = None -- None <- 4; curr = 1 -> 3 -> None # return reverseList(curr, head) = reverseList(1 -> 3 -> None, None <- 4) # curr = 3 # head.next = 1.next = 4 -- None <- 4 <- 1; curr = 3 -> None # return reverseList(curr, head) = reverseList(3 -> None, None <- 4 <- 1) # curr = None # head.next = 3.next = 1 -- None <- 4 <- 1 <- 3; curr = None # return reverseList(None, None <- 4 <- 1 <- 3) # not head: return prev = None <- 4 <- 1 <- 3 Naive brute force iterative: def reverseList(self, head): """ :type head: ListNode :rtype: ListNode """ if not head: return None ll_arr = [] node = head while node: ll_arr.append(node.val) node = node.next r_cur = r_head = ListNode(ll_arr[-1]) for ele in list(reversed(ll_arr[:-1])): r_cur.next = ListNode(ele) r_cur = r_cur.next return r_head Valid parentheses: https://leetcode.com/problems/valid-parentheses/
Code: def isValid(self, s): map = {'(': ')', '{': '}', '[': ']'} # Use a list as a stack. stack = [] for i, c in enumerate(s): if c in map: elif c in map.values(): # Also fails if stack is empty -> too many closing parens. if not stack or map[stack.pop()] != c: return False return not stack Remove duplicates from unsorted singly linked list: CTCI 2.1
Code: With buffer / auxiliary data structure: from linkedlist import Node def remove_dupes(head): # Edge case where single node list. if not head.next_node: return head curr, prev = head, Node() dupes = {} while curr: if curr.data in dupes: prev.next_node = curr.next_node else: dupes[curr.data] = 1 prev = curr curr = curr.next_node Without buffer: # Now do it without another data structure. def remove_dupes2(head): if not head.next_node: return head curr, runner = head, head.next_node # Curr, not curr.next, because otherwise would miss last node. while curr: runner = curr while runner.next_node: # Compare using runner.next because no prev pointer. if curr.data == runner.next_node.data: runner.next_node = runner.next_node.next_node else: runner = runner.next_node curr = curr.next_node Two sum: https://leetcode.com/problems/two-sum/
Task: Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution. Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1]. Code: def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ nums_tups = [] for i, num in enumerate(nums): diffs = [n[1] for n in nums_tups] if num in diffs: # diffs and nums are in sync return [diffs.index(num), i] else: nums_tups.append((num, target - num)) Add two numbers: https://leetcode.com/problems/add-two-numbers/
Task: You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself. Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8 Code: def addTwoNumbers(self, l1, l2): """ :type l1: ListNode :type l2: ListNode :rtype: ListNode """ l1_str = '' l2_str = '' while l1.next != None: l1_str += str(l1.val) l1 = l1.next l1_str += str(l1.val) while l2.next != None: l2_str += str(l2.val) l2 = l2.next l2_str += str(l2.val) l1_num, l2_num = int(l1_str[::-1]), int(l2_str[::-1]) sum = l1_num + l2_num sum_str_rev = str(sum)[::-1] # Need a copy of root node to be able to return at the end since modifying while iterating. root = ListNode(0) curr = root for c in sum_str_rev: l_curr = ListNode(int(c)) curr.next = l_curr curr = curr.next return root.next Sparse matrix multiplication: https://leetcode.com/problems/sparse-matrix-multiplication/
Task: Given two sparse matrices A and B, return the result of AB. You may assume that A's column number is equal to B's row number. Example: A = [ ] B = [ [ 7, 0, 0 ], [ 0, 0, 0 ], [ 0, 0, 1 ] ] | 1 0 0 | | 7 0 0 | | 7 0 0 | AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 | Code: def multiply(self, A, B): """ :type A: List[List[int]] :type B: List[List[int]] :rtype: List[List[int]] """ # Matrix is a list of lists where each list is a row. """ if not A or not B: return None AB = [[0 for _ in B[0]] for _ in A] # Iterate through rows of A. for i, row_a in enumerate(A): # 0, 1 #Iterate through cols of A.for j, ele_a in enumerate(row_a): # 0, 1, 2 if ele_a: # Iterate through rows of B. for k, ele_b in enumerate(B[j]): # 0, 1, 2 if ele_b: AB[i][k] += A[i][k] * B[k][j] return AB ZigZag conversion: https://leetcode.com/problems/zigzag-conversion/
Task: The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of rows like this: (you may want to display this pattern in a fixed font for better legibility) P A H N A P L S I I G Y I R And then read line by line: "PAHNAPLSIIGYIR" Write the code that will take a string and make this conversion given a number of rows: string convert(string text, int nRows); convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR". Code: def convert(self, s, numRows): # The key is that the distance down then up (or up then down) to get to the next letter on the current row is symmetric regardless of the horizontal distance traveled / the diagonal. linenum = 1 ret_str = '' ind = 0 # Have to alternate strategy for middle lines. mid_cycle_index = 1 if numRows == 1: return s for i in xrange(len(s)): ret_str += s[ind] # First line. if linenum == 1: elif linenum == numRows: else: if mid_cycle_index % 2 == 1: ind += 2 * (numRows - linenum) else: mid_cycle_index += 1 # Go to next line. if ind >= len(s): linenum += 1 ind = linenum - 1 # ind is 0-based, linenum 1-based mid_cycle_index = 1 return ret_str Meeting rooms: https://leetcode.com/problems/meeting-rooms/
Task: Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), determine if a person could attend all meetings. For example, Given [[0, 30],[5, 10],[15, 20]], return false. Code: # Definition for an interval. # class Interval(object): # def __init__(self, s=0, e=0): # self.start = s # self.end = e def canAttendMeetings(self, intervals): """ :type intervals: List[Interval] :rtype: bool """ if not intervals or len(intervals) == 1: return True intvl_st = sorted(intervals, key=lambda x: x.start) for i, intvl in enumerate(intvl_st[1:]): # i, not i-1, since already skipped first one in intvl_st[1:]. prev = intvl_st[i] if intvl.start < prev.end: return False return True Iterative inorder traversal: https://leetcode.com/problems/closest-binary-search-tree-value/
def inorder_traversal(root): stack = [root] while stack: curr = stack.pop() if not curr.left and not curr.right: else: if curr.right: stack.append(curr.right) stack.append(Node(curr.val)) Dummy leaf node so next time will print right away.
if curr.left: stack.append(curr.left) Rotate a matrix 90 degrees: A[:] = zip(*A[::-1]) Reverse then transpose (rows as cols and vice versa).
Lowest common ancestor: Can just use BST properties, one node needs to be in left subtree (< root value) and the other in the right subtree (> root) Trickier for binary tree Get linked list of binary tree leaves in-place: http://www.geeksforgeeks.org/connect-leaves-doubly-linked-list/
darkmode
No comments