Cover image
Brian T. Liao
Aug 18, 2019 • 24 min read

Interview Cram

Number of Islands

Given a 2-D Array, count the number of islands in it, where land is connected in the NSEW direction

Recursion, Search, Union-Find

Number of Islands (Sol)

https://leetcode.com/problems/number-of-islands/

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0

        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
        return count

    def dfs(self, grid, i, j):
        if i<0 or j<0 or i>=len(grid) or j>=len(grid[0]) or grid[i][j] != '1':
            return
        grid[i][j] = '#'
        self.dfs(grid, i+1, j)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i, j-1)

Coin Change Problem

Given a target of N cents and a collection of coins, how many ways can you form N cents?

Dynamic Programming, Recursion

Coin Change Problem (Sol)

https://leetcode.com/problems/coin-change/

class Solution:
    def coinChange(self, coins: List[int], amount: int) -> int:
        A = [float('inf')] * (amount + 1)
        A[0] = 0
        for i in range(amount + 1):
            for coin in coins:
                if coin <= i:
                    A[i] = min(A[i], 1 + A[i - coin])
        return A[amount] if A[amount] != float('inf') else -1

Minimum Window Substring

Given a string and a collection of characters, find the shortest substring that contains all the characters

Sliding Window

Minimum Window Substring (Sol)

https://leetcode.com/problems/minimum-window-substring/

class Solution(object):
    def minWindow(self, s, t):
        dicT = collections.Counter(t)
        dicS = {}
        rec = set()
        j = 0
        res = float('inf')
        for i, c in enumerate(s):
            if c not in dicS:
                dicS[c] = 1
            else:
                dicS[c] += 1
            if c in dicT and dicT[c] <= dicS[c]:
                rec.add(c)
                while len(rec) == len(dicT):
                    dicS[s[j]] -= 1
                    if s[j] in dicT and dicT[s[j]] > dicS[s[j]]:
                        rec.remove(s[j])
                        if res > i-j+1:
                            start = j
                            end = i
                            res = i-j+1
                    j += 1
        if res == float('inf'):
            return ""
        return s[start:end+1]

Buying and Selling Stock

Given a list of starting and ending days for a stock, maximize your profit

Greedy

Buying and Selling Stock (Sol)

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        max_, temp = 0, 0
        for i in range(1, len(prices)):
            temp += prices[i] - prices[i - 1]
            temp = max(0, temp)
            max_ = max(max_, temp)
        return max_

Range Sum Query

Efficiently compute the sum of the numbers between two indexes of an array

Dynamic Programming

Range Sum Query (Sol)

https://leetcode.com/problems/range-sum-query-immutable/

class NumArray(object):

    def __init__(self, nums):
        """
        :type nums: List[int]
        """
        self.table = nums[:]
        for i in range(1, len(nums)):
            self.table[i] += self.table[i - 1]
        


    def sumRange(self, i, j):
        """
        :type i: int
        :type j: int
        :rtype: int
        """
        if i == 0:
            return self.table[j]
        return self.table[j] - self.table[i - 1]


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# param_1 = obj.sumRange(i,j)

Merge Intervals

Given a list of intervals with a start and end value, merge the intervals

Sorting

Merge Intervals (Sol)

https://leetcode.com/problems/merge-intervals/

class Solution(object):
    def merge(self, intervals):
        """
        :type intervals: List[List[int]]
        :rtype: List[List[int]]
        """
        if len(intervals) < 2:
            return intervals
        intervals.sort(key=lambda x: x[0])
        i = 0
        while i < len(intervals) - 1:
            first = intervals[i]
            print(first)
            second = intervals[i + 1]
            if first[1] >= second[0]:
                intervals.pop(i)
                second[0] = first[0]
                second[1] = max(first[1], second[1])
            else:
                i += 1
        return intervals

Maximum Subarray

Given an array, find the subarray with the maximum sum

Sliding Window

Maximum Subarray (Sol)

https://leetcode.com/problems/maximum-subarray

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(1, len(nums)):
            if nums[i-1] > 0:
                nums[i] += nums[i-1]
        return max(nums)

Range Sum Query Mutable

Given a mutable array of integers, find the sum of elements between i and j

Recursion, Trees

Range Sum Query Mutable (Sol)

https://leetcode.com/problems/range-sum-query-mutable

class Node:
    def __init__(self, low, high):
        self.l = low
        self.h = high
        self.tot = 0
        self.left = None
        self.right = None
    
    def u(self, i, val):
        if self.l == self.h:
            self.tot = val
            return
        m = self.l + (self.h - self.l) // 2
        if i <= m:
            self.left.u(i, val)
        elif i > m:
            self.right.u(i, val)
        self.tot = self.left.tot + self.right.tot
        
    def r(self, l, h):
        if self.l == l and self.h == h:
            return self.tot
        m = self.l + (self.h - self.l) // 2
        if h <= m:
            return self.left.r(l, h)
        elif l > m:
            return self.right.r(l, h)
        else:
            return self.left.r(l, m) + self.right.r(m + 1, h)

class NumArray:

    def __init__(self, nums: List[int]):
        self.head = self._cst(nums, 0, len(nums) - 1)
        

    def update(self, i: int, val: int) -> None:
        self.head.u(i, val)

    def sumRange(self, i: int, j: int) -> int:
        return self.head.r(i, j)            
    def _cst(self, nums, l, h):
        if l > h:
            return None
        if l == h:
            n = Node(l, l)
            n.tot = nums[l]
            return n
        n = Node(l, h)
        m = l + (h - l) // 2
        n.left = self._cst(nums, l, m)
        n.right = self._cst(nums, m + 1, h)
        n.tot = n.right.tot + n.left.tot
        return n


# Your NumArray object will be instantiated and called as such:
# obj = NumArray(nums)
# obj.update(i,val)
# param_2 = obj.sumRange(i,j)

Word Search II

Given a 2-D array of characters and a list of valid words, find the number of words on the board

Recursion, Search, Trees

Word Search II (Sol)

https://leetcode.com/problems/word-search-ii

class TrieNode {
    TrieNode[] next = new TrieNode[26];
    String word;
}

class Solution {
    public List<String> findWords(char[][] board, String[] words) {
        List<String> res = new ArrayList<>();
        TrieNode root = buildTrie(words);
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                dfs (board, i, j, root, res);
            }
        }
        return res;
    }
    
    public void dfs(char[][] board, int i, int j, TrieNode p, List<String> res) {
        char c = board[i][j];
        if (c == '#' || p.next[c - 'a'] == null) return;
        p = p.next[c - 'a'];
        if (p.word != null) {
            res.add(p.word);
            p.word = null;
        }
        board[i][j] = '#';
        if (i > 0) dfs(board, i - 1, j, p, res);
        if (j > 0) dfs(board, i, j - 1, p, res);
        if (i < board.length - 1) dfs(board, i + 1, j, p, res);
        if (j < board[0].length - 1) dfs(board, i, j + 1, p, res);
        board[i][j] = c;
    }
    
    public TrieNode buildTrie(String[] words) {
        TrieNode root = new TrieNode();
        for (String w : words) {
            TrieNode p = root;
            for (char c : w.toCharArray()) {
                int i = c - 'a';
                if (p.next[i] == null) p.next[i] = new TrieNode();
                p = p.next[i];
            }
            p.word = w;
        }
        return root;
    }
}

Task Scheduler

Given an array of tasks an a cooldown period, given an efficient ordering

Greedy, Priority Queue

Task Scheduler (Sol)

https://leetcode.com/problems/task-scheduler/

from heapq import *

class Solution:
    def leastInterval(self, tasks: List[str], n: int) -> int:
        maxFreq = 0
        max_count = 0
        dic = {}
        for task in tasks:
            if task in dic:
                dic[task] += 1
            else:
                dic[task] = 1
            if dic[task] > maxFreq:
                maxFreq = dic[task]
                max_count = 1
            elif dic[task] == maxFreq:
                max_count += 1
        

        return max((maxFreq-1) * (n+1) + max_count, len(tasks))

Non-overlapping Intervals

Given a collection of intervals, find the number of intervals you need to remove to make the rest of the intervals non-overlapping

Greedy, Sorting

Non-overlapping Intervals (Sol)

https://leetcode.com/problems/non-overlapping-intervals

class Solution:
    def eraseOverlapIntervals(self, intervals: List[List[int]]) -> int:
        if not intervals: return 0
        intervals.sort(key=lambda x: x[0])  # sort on start time
        currEnd, cnt = intervals[0][1], 0
        for x in intervals[1:]:
            if x[0] < currEnd:  # find overlapping interval
                cnt += 1
                currEnd = min(currEnd, x[1])  # erase the one with larger end time
            else:
                currEnd = x[1]   # update end time
        return cnt

Preorder Serialization Verification of a Binary Tree

Given a particular kind of preorder serialization of a binary tree, verify that it’s valid

Recursion, Trees

Preorder Serialization Verification of a Binary Tree (Sol)

https://leetcode.com/problems/verify-preorder-serialization-of-a-binary-tree

class Solution:
    def isValidSerialization(self, preorder: str) -> bool:
        # remember how many empty slots we have
        # non-null nodes occupy one slot but create two new slots
        # null nodes occupy one slot
        
        p = preorder.split(',')
        
        #initially we have one empty slot to put the root in it
        slot = 1
        for node in p:
            
            # no empty slot to put the current node
            if slot == 0:
                return False
                
            # a null node?
            if node == '#':
                # ocuppy slot
                slot -= 1
            else:
                # create new slot
                slot += 1
        
        #we don't allow empty slots at the end
        return slot==0

Find the Duplicate Number

Find the duplicate number in an array AND use O(1) space

Search

Find the Duplicate Number (Sol)

https://leetcode.com/problems/find-the-duplicate-number/

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        tortoise = nums[0]
        hare = nums[0]
        while True:
            tortoise = nums[tortoise]
            hare = nums[nums[hare]]
            if tortoise == hare:
                break
        ptr1 = nums[0]
        ptr2 = tortoise
        while ptr1 != ptr2:
            ptr1 = nums[ptr1]
            ptr2 = nums[ptr2]
        return ptr1

Construct a Binary Tree from Preorder and Inorder Serialization

Given the preorder and inorder serialization of a binary tree, construct a tree data structure

Recursion, Search, Trees

Construct a Binary Tree from Preorder and Inorder Serialization (Sol)

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal

# Definition for a binary tree node.
# class TreeNode(object):
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution(object):
    def buildTree(self, preorder, inorder):
        """
        :type preorder: List[int]
        :type inorder: List[int]
        :rtype: TreeNode
        """
        if inorder:
            ind = inorder.index(preorder.pop(0))
            root = TreeNode(inorder[ind])
            root.left = self.buildTree(preorder, inorder[:ind])
            root.right = self.buildTree(preorder, inorder[ind + 1:])
            return root

Decode Ways

Given an encoding from letters to numbers, count the number of ways to decode a string of numbers

Dynamic Programming, Recursion

Decode Ways (Sol)

https://leetcode.com/problems/decode-ways/description/

class Solution(object):
    def numDecodings(self, s):
        """
        :type s: str
        :rtype: int
        """
        
        
        
        # cars
        # [0, 0, 0, 0]
        # 0, 1, 2, 3
        w = [0] * (len(s) + 1)
        w[0] = 1
        if 0 < int(s[0]) <= 9:
            w[1] = 1
        
        print(w)
        for i in range(2, len(s) + 1):
            if 0 < int(s[i - 1]) <= 9:
                w[i] += w[i - 1]
            if int(s[i - 2]) != 0 and int(s[i - 2:i]) <= 26:
                w[i] += w[i - 2]
        print(w)
        return w[len(s)]

Jump Game II

Given a non-negative integer array where each index represents the maxmimum you can iterate forward, minimize the number of jumps to reach the end of the array

Greedy

Jump Game II (Sol)

https://leetcode.com/problems/jump-game-ii/description/

class Solution:
    def jump(self, nums: List[int]) -> int:
        j, ce, cf = 0, 0, 0
        for i in range(len(nums) - 1):
            cf = max(cf, i + nums[i])
            if i == ce:
                j += 1
                ce = cf
        return j

Find the Edit Distance Between Two Words

Given two words, find the minimum number of edits to mutate one word into the other

Dynamic Programming, Recursion

Find the Edit Distance Between Two Words (Sol)

https://leetcode.com/problems/edit-distance/description/

class Solution(object):
    def minDistance(self, word1, word2):
        """
        :type word1: str
        :type word2: str
        :rtype: int
        """
        m = len(word1)
        n = len(word2)
        table = [[0] * (n + 1) for _ in range(m + 1)]

        for i in range(m + 1):
            table[i][0] = i
        for j in range(n + 1):
            table[0][j] = j

        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if word1[i - 1] == word2[j - 1]:
                    table[i][j] = table[i - 1][j - 1]
                else:
                    table[i][j] = 1 + min(table[i - 1][j], table[i][j - 1], table[i - 1][j - 1])
        return table[m][n]
Post by: Brian T. Liao