Clone Graph

Prompt

Given a reference of a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node in the graph contains a val (int) and a list (List[Node]) of its neighbors. The given node will always be the first node with val = 1. You must return the copy of the given node as a reference to the cloned graph.

Solution

First thing’s first, we need to traverse the graph, so either a DFS or BFS will work. Let’s go with a DFS. For each new node on the stack, if it hasn’t been seen yet we need to create a new node that references it, then loop through its neighbors to create new nodes for each of those. But we need to track the new nodes somehow to ensure that we don’t create multiple copies for a single value that has multiple neighbors. Let’s keep the new nodes in a dictionary of node.val: node so that when we get to a node in seen, we can easily return that node’s clone instead. And in fact, we can check the dictionary instead of a seen set.

Space and Time Complexity

This is a classic dfs that is ensured to be connected, which means that we don’t need to do an initial loop through all of the nodes to make sure they’re all hit. If there were no edges, we would not still loop through multiple nodes: to remain connected, a graph with no edges would be only a single node. So I believe the run time is actually O(E), E being the number of edges. Technically it’s E + 1, but it reduces. Space-wise, the visited dictionary is O(V + E).

"""
# Definition for a Node.
class Node:
    def __init__(self, val, neighbors):
        self.val = val
        self.neighbors = neighbors
"""
class Solution:
    def cloneGraph(self, node: 'Node') -> 'Node':
        if not node: return 
        self.visited = {}
        return self.dfs(node)
    
    def dfs(self, node):
        if node.val not in self.visited:
            newNode = Node(node.val, [])
            self.visited[node.val] = newNode
            for nei in node.neighbors:
                newNode.neighbors.append(self.dfs(nei))
            return newNode
        return self.visited[node.val]       

Knight’s Tour

Prompt

You are given a rows * cols chessboard and a knight that moves like in normal chess. Currently knight is at starting position denoted by start_row row and start_col col, and want to reach at ending position denoted by end_row row and end_col col. The goal is to calculate the minimum number of moves that the knight needs to take to get from starting position to ending position. start_row, start_col, end_row and end_col are 0-indexed.

Return an integer. If it is possible to reach from starting position to ending position then return minimum number of moves that the knight needs to take to get from starting position to ending position. If it is not possible to reach from starting position to ending position then return -1.

Solution

It’s looking for the shortest path so I want to go with BFS. We’re given a starting node, so we just need to BFS from there, keeping track of the number of moves at each step. Compare each node we land at to the end node and return the # of moves if we hit it. If the BFS ends and we haven’t found the target, return -1.

Space and Time Complexity

This is a classic BFS except that we only ever start from a single node. So the runtime is at most O(m * n) but stops when it finds the shortest path. In the worst case, space complexity is also O(m * n).

class Solution:
    def knight(self, rows, cols, start_r, start_c, end_r, end_c):
        self.rows, self.cols = rows, cols
        self.start_r, self.start_c = start_r, start_c
        self.end_r, self.end_c = end_r, end_c
        return self.bfs()
    
    def bfs(self):
        seen = set()
        dirs = [(1,2),(-1,2),(-2,1),(-2,-1),(-1,-2),(1,-2),(2,-1),(2,1)]
        q = [(self.start_r, self.start_c, 0)]
        while q:
            x, y, moves = q.pop(0)
            if (x,y) == (self.end_r, self.end_c):
                return moves
            seen.add((x,y))
            for xD, yD in dirs:
                neiX = x + xD
                neiY = y + yD
                if (neiX, neiY) not in seen and 0 <= neiX < self.rows \
                and 0 <= neiY < self.cols:
                    q.append((neiX, neiY, moves + 1))
        return -1

Alien Dictionary

Prompt

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Note

1. You may assume all letters are in lowercase.
2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
3. If the order is invalid, return an empty string.
4. There may be multiple valid order of letters, return any one of them is fine.

Solution

We get some clues about what type of question this is in that letters are going to have to point to the letter that come after them in the alien dict, making this a graph problem. We’re also told that we’re looking for the order of the nodes (and if there is no valid order, i.e. if there is a cycle to return null), which requires a topological sort. So the trick is figuring out how to build the adjacency lists. We need each letter (node) to point to the letter that we know comes after it in the dictionary. Since the words are sorted by their first letters, we can do part of that work by comparing the first letter in each word going through the list in order. However for multiple words that begin with the same letter/s, we will need to loop through them to compare the first non-equal letter in those words. Once we find the first non-equal letter, we must break out of that comparison, because the letters within a given word are not sorted. There are a few special quirks to this we need to keep in mind. We’ll need to loop through all the words but compare one to the word next to it, so we’ll want to loop (# of words - 1) times. within each comparison, we’ll want to loop until we find a character not in common, but we’ll need to ensure that we don’t try to check past the length of the smaller of the two words. So this inner loop will only want to go for (min(len(word1), len(word2)) times. Once we have our adjacency list, however, it is a classic topological sort with a cycle check.

class Solution:
    def alienOrder(self, words: List[str]) -> str:
        self.adj_list = self.buildGraph(words)
        self.order = []
        self.seen = {}
        self.VISITING = -1
        self.VISITED = 0
        for word in words:
            for ch in word:
                if self.buildValidOrder(ch) == -1:
                    return ""
        self.order.reverse()
        return "".join(self.order)
         
    def buildGraph(self, words):
        adj_list = {ch: set() for word in words for ch in word}
        num_words = len(words)
        for i in range(num_words - 1):
            min_chars = min(len(words[i]), len(words[i + 1]))
            for j in range(min_chars):
                if words[i][j] != words[i + 1][j]:
                    adj_list[words[i][j]].add(words[i + 1][j])
                    break
        return adj_list
        
    def buildValidOrder(self, node):
        if node in self.seen:
            if self.seen[node] == self.VISITING:
                return -1
            return
        
        self.seen[node] = self.VISITING
        for nei in self.adj_list[node]:
            if self.buildValidOrder(nei) == -1:
                return -1
            
        self.seen[node] = self.VISITED
        self.order.append(node)

Invert Tree

Prompt

Invert a binary tree. Example:

Input:

     4
   /   \
  2     7
 / \   / \
1   3 6   9

Output:

     4
   /   \
  7     2
 / \   / \
9   6 3   1

Solution

A classic. At each node you have to invert that node’s left and right pointers and then continue in a basic traversal. And that’s it!

Space and Time Complexity

We are doing a simple traversal of the tree, so the runtime is O(n). Because we’re solving recursively, the recursion stack space used is also O(n).

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

class InvertTree:
    def invertTree(self, root: TreeNode) -> TreeNode:
        if root:
            root.left, root.right = root.right, root.left
            self.invertTree(root.left)
            self.invertTree(root.right)
        return root

Search Matrix

Prompt

Write an efficient algorithm that searches for a value in an m x n matrix. In this matrix, integers in each row are sorted from left to right and the first integer of each row is greater than the last integer of the previous row.

Solution

We need to do a binary search to find which row we need, and then from there a classic binary search on the row we came up with. I arbitrarily chose to use the last elements in each row to compare to. The special cases of this problem are that a target may be less than the element being compared, but may still be in that row. Therefore, when start == end, we actually need to check that row.

Space and Time Complexity

This is kind of a hilarious solution. The runtime is O(logn + logm), as is the space complexity.

class SearchMatrix:
    def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]: return False
        self.grid = matrix
        self.t = target
        self.found = False
        rowI = self.findRow(0, len(self.grid) - 1)
        if rowI == -1: return False
        if self.found: return self.found
        self.row = self.grid[rowI]
        self.findNum(0, len(self.row) - 1)
        return self.found
    
    def findRow(self, start, end):
        if start > end:
            return -1
        mid = start + (end - start) //2
        if self.grid[mid][-1] == self.t:
            self.found = True
            return
        if start == end:
            return start
        if self.grid[mid][-1] > self.t:
            return self.findRow(start, mid)
        else:
            return self.findRow(mid + 1, end)
            
    def findNum(self, start, end):
        if start >= end: return
        mid = start + (end - start) //2
        if self.row[mid] == self.t:
            self.found = True
            return
        if self.row[mid] > self.t:
            self.findNum(start, mid)
        else:
            self.findNum(mid + 1, end)    

Construct Binary Tree from Inorder and Postorder Traversal

Prompt

Given inorder and postorder traversal of a tree, construct the binary tree.

Note: You may assume that duplicates do not exist in the tree. For example, given inorder = [9,3,15,20,7], postorder = [9,15,7,20,3], return the following binary tree:

    3
   / \
  9  20
    /  \
   15   7

Solution

The puzzle here is to figure out how to find the order of the nodes. Neither traversal gives you all the info you need. So where to start? Postorder requires that for every parent node, all nodes below that parent (child, grandchild, etc) appear before it. This means that the root of the tree will always be the last item in the list because it is the initial parent. You can then take that value and know in the inorder traversal that everything to the left of the root value (this problem requires that all values in the tree are unique) is the left subtree of the root, and everything to the right is its right subtree. You can then pop the root off of the postorder list and break the inorder list around the root so that you don’t ever look at it twice. Then to find the root of each subtree, repeat the process. You have to start with the right subtree every time, because the postorder traversal was built from left to right, so building it back up requires that you start from the back, ie the right. The root’s right child must be set to whatever the function returns recursively when called on the updated traversals (removing the current root) and the root itself.

Space and Time Complexity

Worst case, this solution is actually O(n^2). For each value from the postorder list, you need to find its index in the inorder list. This is a O(n) procedure, occuring on each of n nodes. If the entire tree is a single branch off to the left, it will need to loop through all of the lower level nodes every time it creates a new node. The average runtime, however, is much better. We are also not using any space other than the recursive stack and the nodes we create. We only actually recurse n times, and there are n nodes (additional, not multiplicative), so the space complexity is O(n).

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

class Solution:
    def buildTree(self, inorder: List[int], postorder: List[int]) -> TreeNode:
        if not inorder: return 
        root = postorder.pop(-1)
        return self.constructBranch(root, inorder, postorder)

    def constructBranch(self, root, inorder, postorder):
        rootNode = TreeNode(root)
        inLen = len(inorder)
        if inLen == 0 or inLen == 1: return rootNode
        inRootI = inorder.index(root)
        if inRootI != inLen - 1:
            inR = inorder[inRootI + 1:]
            root = postorder.pop(-1)
            rootNode.right = self.constructBranch(root, inR, postorder)
        if inRootI != 0:
            inL = inorder[:inRootI]
            root = postorder.pop(-1)
            rootNode.left = self.constructBranch(root, inL, postorder)
        return rootNode

Merge Into Array

Prompt

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array. Note: The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. Do not return anything, modify nums1 in-place instead.

Solution

This one is tricky. You need to utilize the empty space at the end of the first array by inserting BACKWARDS, from the largest to the smallest, so that you don’t need to worry about swapping any numbers/keeping track of stuff.

so set pointers to: nums1[-1] (k), nums1[n-1] (i), nums2[m-1]*j)
for _ in range(n + m): put the > el of nums1[i] and nums2[j] at k,
    -= k and whichever i or j you chose from. 
guards: if j is ever < 0, you're done because the rest of nums1 is
already sorted. if i is ever < 0, you can slice the rest of nums2
into 0-k of nums1
if n == 0: return

Space and Time Complexity

Runtime is O(n + m) because you just loop through all of the nums once, and since we’re using the space already provided for the merging, space is actually O(1).

class MergeIntoArray:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        if n == 0: return nums1
        if m == 0:
            nums1[:] = nums2[:]
            return nums1
        total = len(nums1)
        i = m - 1
        j = n - 1
        k = total - 1
        
        for _ in range(total):
            if j < 0:
                return nums1
            if i < 0:
                nums1[:k + 1] = nums2[:j + 1]
                return nums1
            if nums1[i] > nums2[j]:
                nums1[k] = nums1[i]
                i -= 1
            else:
                nums1[k] = nums2[j]
                j -= 1
            k -= 1
        return nums1

Sort Colors

Prompt

Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. Note: You are not suppose to use the library’s sort function for this problem.

Example:

Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2]

Follow up: A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s. Could you come up with a one-pass algorithm using only constant space?

We need to keep track of where the next sorted element should be, and there are 2 potential places that can be in the list: a new red item or a new white item (we can leave the blue ones be because they’ll all be sorted correctly by the other two colors swapping them into place). So we need a red pointer and white pointer for where the next item of each color should be inserted.

w
r
[2,0,2,1,1,0]      
i                  # nums[i] == 2 skip
i                # nums[i] == 0, swap with r, add one to r and since r is > white rn, move w

w
r
[0,2,2,1,1,0]       
    i              # nums[i] == 2 skip
    i            # nums[i] == 1, swap with w, add one to w
    w
r 
[0,1,2,2,1,0]
        i          # nums[i] == 1, swap with w, add one to w
    w
r  
[0,1,1,2,2,0]
        i        # nums[i] == 0, swap with r and add one to r BUT 2 things.
    w
    r
[0,0,1,2,2,1]       # can't move forward until you ALSO swap the 1, so we should do both checks
                    # each time, if it's 0 then if it's 1. 
                    # ALSO: this time we didn't want to move w forward even though we moved r up
                    # we only want to move w forward on r change if r > w, so set w = max(w, r)
        w
    r               
[0,0,1,1,2,2] # success

Space and Time Complexity

We loop through the list once, and swaps are O(1) so runtime is O(n). Space complexity is O(1).

class SortColors:
    def sortColors(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        if n <= 1: return
        r = w = 0
        for i in range(n):
            if nums[i] == 0:
                nums[r], nums[i] = nums[i], nums[r]
                r += 1
                w = max(r, w)
            if nums[i] == 1:
                nums[w], nums[i] = nums[i], nums[w]
                w += 1

Pancake Sorting

Prompt

Given an array A, we can perform a pancake flip: We choose some positive integer k <= A.length, then reverse the order of the first k elements of A. We want to perform zero or more pancake flips (doing them one after another in succession) to sort the array A.

Return the k-values corresponding to a sequence of pancake flips that sort A. Any valid answer that sorts the array within 10 * A.length flips will be judged as correct.

Solution

The simplest solution I could think of was to find the biggest item, flip it to the front, and then flip the entire list so it gets to the back. Once you’ve done that, you can approach the list as 1 element shorter than before, so that you don’t mess with that last sorted element. If the largest element is already in the correct spot, you don’t want to flip anything. The flip itself just requires reversing some portion of the list.

Space and Time Complexity

This process is super inefficient because you need to loop through the whole list and then loop again each time to find the largest element, so it’s O(n^2). the space used is to track the number of flips, which can’t be more than twice the number of elements in the list, which reduces to O(n).

class Solution:
    def pancakeSort(self, A: List[int]) -> List[int]:
        n = len(A)
        self.arr = A
        if n <= 1: return self.arr
        flips = []
        for i in range(n):
            maxEl, maxI = self.arr[0], 0
            for j in range(n - i):
                if self.arr[j] > maxEl:
                    maxEl, maxI = self.arr[j], j
            if maxI != n - 1 - i:
                self.flip(maxI)
                flips.append(maxI + 1)
                if n - 1 - i != 0:
                    self.flip(n - 1 - i)
                    flips.append(n - i) 
        return flips

    def flip(self, k):
        for i in range((k + 1) //2):
            self.arr[i], self.arr[k - i] = self.arr[k - i], self.arr[i]

Find First Unique Character

Prompt

Given a string, find the first non-repeating character in it and return it’s index. If it doesn’t exist, return -1.

Solution

Frequency counts should always be dicts! But we want to do this in one pass, so the dict should track not only the frequncy of each letter, but also it’s first appearance in the string. That way once we have the frequencies, we can loop through the keys in the dict instead of the letters in the string, which will usually have duplicates and therefore be a longer loop.

                  # index, freq
s = "leetcode" {'l': [0, 1], 'e': [1, 1X 2], 't': [3, 1]} etc ==>
{'l': [0, 1], 'e': [1, 3], 't': [3, 1], 'c': [4, 1], 'o': [5, 1], 'd': [6, 1]}
now we can loop through the dict, keeping track of the min index of letters that appear once.

Space and Time Complexity

We need to go through each letter at least once, so O(n) minimum runtime. Ours loops twice so O(n + n) ==> O(n) with an upper bound of O(n) on space (in the case of every letter being unique, it hits the upper bound).

class FirstUniqChar:
    def firstUniqChar(self, s: str) -> int:
        import math
        chars = {}
        lenS = len(s)
        for i in range(lenS):
            if s[i] in chars:
                chars[s[i]][1] += 1
            else:
                chars[s[i]] = [i, 1]
        minI = math.inf
        for char in chars:
            if chars[char][1] == 1 and chars[char][0] < minI:
                minI = chars[char][0]
        if minI == math.inf:
            return -1
        return minI

LRU Cache

Prompt

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1. put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item. The cache is initialized with a positive capacity. Could you do both operations in O(1) time complexity?

Solution

We need to make a hashmap with O(1) runtime in both methods. But each key must track both a value and its last access. So for put-ting, we must keep track of if slot is the key we’re looking for, if the slot is empty, and the index of the least recently used element. That way, if you get through all slots and don’t find the key or an empty slot, you don’t have to search again for the index to write over. This is still O(n) where n = the size of the array, but not n the number of inputs, and still average case O(1).

I initially tried to implement this with an array the size of the capacity and then tracking the LRU element and lruIndex to overwrite when full (because using the built-in dict felt like cheating). However this method was too slow, so I used an Ordered Dict. They are perfectly designed for this problem, so from there it ended up being quite simple.

class LRUCache:
    def __init__(self, capacity: int):
        from collections import OrderedDict
        self.cache = OrderedDict()
        self.cap = capacity
        self.used = 0

    def get(self, key: int) -> int:
        if key in self.cache:
            val = self.cache.pop(key)
            self.cache[key] = val
            return val
        return -1

    def put(self, key: int, value: int) -> None:
        if key in self.cache:
            self.cache.pop(key)
            self.cache[key] = value
        elif self.used < self.cap:
            self.cache[key] = value
            self.used += 1
        else:
            self.cache.popitem(last=False)
            self.cache[key] = value

Alien Dictionary

Prompt

In an alien language, surprisingly they also use english lowercase letters, but possibly in a different order. The order of the alphabet is some permutation of lowercase letters. Given a sequence of words written in the alien language, and the order of the alphabet, return true if and only if the given words are sorted lexicographicaly in this alien language.

Solution First off, we’re going to have to continuously check the alphabet for ordering, so we should minimize the cost of that by turning that into a dictionary (O(n) to create once, but O(1) to check in each comparison). Now for actually checking the order. We need to compare each word to the one next to it. If at any point something is in the wrong order, return False. If it’s in the right order (word1[x] < word2[x], NOT if they’re equal), we can break out of the loop because they’re good to go. But how to check if they’re the same? I want to keep a boolean flag of same = True, and then if we break because it’s correct, set same = False first. If same and len(word1) > len(word2) we can also return False. If we get all the way through, we can return True.

ex ["wor", "word", "world"] "worldabcefghijkmnpqstuvxyz"
     +++    +++  # same is true but len(word1) < len(word2) so keep going
            +++X    +++X # d > l in order, return false

Space and Time Complexity

The runtime is O(n) to make the hashmap + O(n) for the outer loop * O(m) where m = len(word) so O(n + n*m) –> O(n * m). Space complexity is O(x) where x = len(order) for the dict, so O(n).

class AlienDict:
    def isAlienSorted(self, words: List[str], order: str) -> bool:
        n  = len(words)
        if n <= 1: return True
        alph = {order[i]: i for i in range(len(order))}
        for i in range(n - 1):
            word1, word2 = words[i], words[i + 1]
            m = min(len(word1), len(word2))
            same = True
            for j in range(m):
                if alph[word1[j]] > alph[word2[j]]:
                    return False
                if alph[word1[j]] < alph[word2[j]]:
                    same = False
                    break
            if same and len(word1) > len(word2): return False
        return True

Valid Palindrome

Prompt

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases. Note: For the purpose of this problem, we define empty string as valid palindrome.

Solution

We know that we need to start at each end and compare as we move towards the middle. This suggests the use of a two-pointer solution. We can start a pointer at each end and move each one until they are both pointing to alphanumeric characters. We can then compare these characters (lowered or capitalized, etc), return False if they are different, or continue if they are the same.

     p1
                                   p2
ex: "A man, a plan, a canal: Panama."

s[p2] = "." so subtract one from it and continue until it’s pointing to an alphanumeric character. "A".lower() == "a".lower() so move p1 forward and p2 back and continue.

Space and Time Complexity

This will result in O(n) runtime because we are going through each each element once (and in a single pass, too!). the space complexity is O(1) because no matter how big the input, we are only adding space for the two pointers.

class ValidPalindrome:
    def isPalindrome(self, s: str) -> bool:
        p1 = 0
        p2 = len(s) - 1
        while p1 < p2:
            if not s[p1].isalnum():
                p1 += 1
                continue
            if not s[p2].isalnum():
                p2 -= 1
                continue
            if s[p1].lower() != s[p2].lower():
                return False
            p1 += 1
            p2 -= 1
        return True

Longest Substring

Prompt

Given a string, find the length of the longest substring without repeating characters.

Solution

I don’t want to create a new substring for every new character we encounter. If we have to check if a character is ‘in’ the existing substring, that automatically becomes O(n) with strings and arrays in Python. We don’t need to return the substring itself in this case, just the length, so if we keep track of the indices of each character in a dictionary, is there some way for that to be helpful? (This tripped me up for a while.) The basic idea is that while the next character is not in the substring, add it to the substring. If next character IS in the substring, set maxSub = max(maxSub, len(substring)), and then remove the start of the substring up to the first appearance of that character (this creates a ‘sliding window’ where we track the start and end of the ‘window’ of valid characters, moving end forward when we can and moving start forward when we have to). The dictionary allows us to skip to the offending index without checking every element individually (for example: ‘abcdee’ would need to loop all the way through till it hit the e, whereas with a dictionary tracking {'e': 4}, we could say if e in dict: start = dict[e] and go from there). If the length of the string is 1 or less, it’s automatically that number of unique elements (0 or 1). So for each ending number in range(len(s)), if the letter at that index is in the dict, start needs to change. But it can’t just change to that index in case that index is from a previous substring and would therefore set start BACKWARDS, tracking more elements than it should. So start must become max(dict[s[end]], start). From there, update/set the dictionary to the current index for the current index’s character. Update maxLen = max(maxLen, (end - start + 1)) to account for the current element. Then return the maxLen.

Space and Time Complexity

Because we are utilizing a dictionary (which has O(1) get functionality runtime), everything we do inside the for loop is constant. The loop itself is O(n) runtime, resulting in O(n) total runtime. The space used for the dictionary is dependent on n as well, so the space complexity is O(n).

class LongestSubString:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        if n <= 1:
            return n
        maxLen = start = 0
        sub = {}
        for end in range(n):
            if s[end] in sub:
                start = max(sub[s[end]] + 1, start)
            sub[s[end]] = end
            maxLen = max(maxLen, (end - start + 1))
        return maxLen

Longest Mountain

Prompt

Let’s call any (contiguous) subarray B (of A) a mountain if: B.length >= 3, there exists some 0 < i < B.length - 1 such that B[0] < B[1] < ... B[i-1] < B[i] > B[i+1]> ... > B[B.length - 1] (Note that B could be any subarray of A, including the entire array A). Given an array A of integers, return the length of the longest mountain. Return 0 if there is no mountain.

Solution

We need a pointer to track the start of a mountain and one for the end (with a counter for the max mountain). From the start of the array, look for the first element whose right neighbor is > than it. So p1 starts at 0, p2 starts at 1 (return 0 if len(nums) < 3). Note: plateaus and the end of the array break a mountain, so we should keep a boolean flag for whether or not we have a mountain to count.

ex: [2, 1, 4, 7, 3, 2, 5]
     p1                  # 2 !< 1: not a mountian, move both pointers forward
        p2
        p1               # 1 < 4 mountain begins! mountain = True
           p2            # while (p2 + 1) < n (while still in the array) and while right neighbor
              p2         # > current: keep moving p2 over. 3 !> 7 so stop
                         # did you stop because of a plateau or the end of the array? if so
                         # mountain = False but you still want to keep moving for next mountain. 
                         # so regardless of mountain, keep moving p2 forward while right neighbor
                    p2   # < current. if mountain, set maxMountian to 
                         #  max(maxMountain, (p2 - p1 + 1)), set p1 = p2, p2 += 1 and keep going

Space and Time Complexity

Runtime is O(n), going through each element in the list in one pass. Space is O(1) for the pointers and counter.

class LongestMountain:
    def longestMountain(self, A: List[int]) -> int:
        n = len(A)
        if n < 3: return 0
        p1 = maxMountain = 0
        p2 = 1
        while p2 < n:
            if A[p1] < A[p2]: # start mountain
                mountain = True
                while p2 < (n - 1) and A[p2 + 1] > A[p2]:
                    p2 += 1
                if p2 == (n - 1) or A[p2 + 1] == A[p2]: # plateau or end on incline
                    mountain = False
                # want to loop through whether still in mountain or not to get p2 to next mountain
                while p2 < (n - 1) and A[p2 + 1] < A[p2]:
                    p2 += 1
                if mountain:
                    maxMountain = max(maxMountain, (p2 - p1 + 1))
            p1 = p2
            p2 += 1
        return maxMountain

Simplify File Path

Prompt

Given an absolute path for a file (Unix-style), simplify it. Or in other words, convert it to the canonical path. In a UNIX-style file system, a period . refers to the current directory. Furthermore, a double period .. moves the directory up a level. Note that the returned canonical path must always begin with a slash /, and there must be only a single slash / between two directory names. The last directory name (if it exists) must not end with a trailing /. Also, the canonical path must be the shortest string representing the absolute path.

Solution

We need to maintain the order, and pop off what was JUST seen if we encoutner a ... This suggests we need a stack. We also need to separate the elements by slash (and ignore the slashes themselves for now), so we should split the string at /. Then for each element in THAT list, if it’s needed, push it onto the stack, if it’s a single period do nothing (also do nothing if it’s empty, as a split // will result in empty strings). Or if the element is .., if there are elements in the stack, pop the last one off. Once we loop through the list, we can join the stack back together with a slash, and add an extra one at the front.

"/a/./b/../../c/" --> 
['', 'a', '.', 'b', '..', '..', 'c', ''] # s = skip, a = append to stack, p = pop from stack
  s   a    s    a    p     p     a   s --> [a, b] --> [] --> [c]
now '/' + '/'.join(stack)

Space and Time Complexity

Splitting a string is O(n) runtime. We then loop through the n elements of that string (now list). And joining them back together at the end is another n cost. However, each occurs separately, so are added together O(n + n + n) --> O(n). The space complexity is also O(n), here for the cost of the stack and the list of elements we break the string into.

class SimplifyPath:
    def simplifyPath(self, path: str) -> str:
        stack = []
        dirs = path.split('/')
        for el in dirs:
            if not el or el == '.':
                continue
            if el == '..':
                if stack:
                    stack.pop(-1)
            else:
                stack.append(el)
        return '/' + '/'.join(stack)

Recent Ping Counter

Prompt

Write a class RecentCounter to count recent requests. It has only one method: ping(int t), where t represents some time in milliseconds. Return the number of pings that have been made from 3000 milliseconds ago until now. Any ping with time in [t - 3000, t] will count, including the current ping. It is guaranteed that every call to ping uses a strictly larger value of t than before.

Solution

Observation: because each t is guaranteed to be bigger than the last, we can pop off all the pings that are too old from the front. So it’s a queue! We’ll need a self.pings to keep track of them all.

in
[1, 100, 3001, 3002]     # if there are no pings, add this one and return 1
self.pings = []          # else, while t - self.pings[0] > 3000: self.pings.pop(0);
   in
...100, 3001, 3002]
self.pings = [1]         # add this ping to self.pings, return len(self.pings)
100 - 1 !> 3000 so self.pings == [1, 100] return 2; input = ...3001, 3002] 
3001 - 1 !> 3000 so self.pings == [1, 100, 3001] return 3; input = ...3002] 
3002 - 1 > 3000, pop it so self.pings = [100, 3001]
3002 - 100 !> 3000 so self.pings = [100, 3001, 3002] return 3

Space and Time Complexity

In the case that all pings in the queue must be removed, we loop through all O(n) of them, so that is our runtime. We also have to store those n pings, so our space complexity is O(n) as well.

class RecentCounter:
    def __init__(self):
        self.pings = []

    def ping(self, t: int) -> int:
        if not self.pings:
            self.pings.append(t)
            return 1
        while (t - self.pings[0]) > 3000:
            self.pings.pop(0)
            if not self.pings:
                break
        self.pings.append(t)
        return len(self.pings)

Intersection of 2 Linked Lists

Prompt

Write a program to find the node at which the intersection of two singly linked lists begins.

Solution

A brute force check going through each node in one list and comparing it to each node in the other would result in a O(n^2) runtime, which we don’t want. To combat this, we need to even out the number of nodes we see from each list.

1 -> 2 -> 3 -> 4 -> 
                    5 -> 6 -> 7
          1 -> 2-> 

lenA = 7    # abs(7 - 5) = 2 so hop through longer list twice 
lenB = 5    # how do we know which is longer?

We’ll need to loop through each list individually to count their lengths. Then if list A is longer than B, we can swap their references so that A is always bigger than B in our code. We then get the difference between their lengths, loop that many times through A, the longer list, and then we can start comparing each node. This way if there is a node they both hit, they’ll both hit it at the same time. We can then return it, and if we reach the end of either list without finding an intersection, we can confidently return that there isn’t one.

Space and Time Complexity

Because we have inputs of different sizes, let’s refer to the length of the first array as n and the length of the second array as m. First we loop through each of these to count them (but separately, not nested within the other). This is a O(n + m) operation. Then we loop again, through min(n, m), which does add another but amortizes back down. Everything we do inside our loops is constant time, so our total runtime is O(n + m). The number and size of our variables don’t change based on the size of the lists, so our space complexity is constant, O(1).

class IntersectionOf2LLs:
    def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
        tempA = headA
        tempB = headB
        n = 0
        m = 0
        while tempA:
            n += 1
            tempA = tempA.next
        while tempB:
            m += 1
            tempB = tempB.next
        if m > n:
            tempA = headB
            tempB = headA
        else:
            tempA = headA
            tempB = headB
        hops = abs(n - m)
        for i in range(hops):
            tempA = tempA.next
        while tempA != tempB:
            if not tempA or not tempB:
                return None
            tempA = tempA.next
            tempB = tempB.next
        return tempA

I cohost the Meaning in Code podcast with my friend and colleague Bennett Garner. In it, we discuss the pursuit of fulfillment and a sense of meaning within a software engineering career, where that pursuit has served each of us, and where it sometimes has not.

Topics discussed range from how to identify what brings you fulfillment, to recipes that make work-from-home lunch breaks less absorbed in cleaning dishes.

You can check us out on YouTube or wherever you listen to podcasts.

I have a blog! You can find my most recent articles on Medium. So far I write about software development projects I’ve done in my own time.

I also plan on turning some of my LeetCode solutions, found below in the ‘Problems’ section, into articles to help walk through how to study data structures and algorithms for software engineering interviews. Stay tuned to see what else I write about!

lillie.dev/diagonal-dominoes

‘Diagonal Dominoes’ is a 2-player game (based on a mini-game in the video game of Avatar: The Last Airbender for PS2. I’m that kind of nerd). Each player starts out with 5 tiles, each of 2 colors. After the first move, you can only lay a tile of the same color as the last one put down. The goal is to block your opponent from having a next move, or to place all of your tiles before they do. Player 2 is an AI designed to win if possible, and if not, to choose a move based on how many ways the human player can lose.

I originally built this game as a midterm project for my ‘Algorithmic Game Theory’ class at Connecticut College in 2015. It uses a weighted mini-max algorithm to build the tree of possible moves for the AI player. It is fully functional (and the absolute highlight of my academic career). It was originally built using Python 3 and Zelle’s Graphics package (code here), and I have recently ported it over to React and TypeScript to deploy to the internet. You can play it here!

entertainmentcrossing.lillie.dev

Entertainment Crossing is a single page web app built using Flask, jQuery, BeautifulSoup, and Google’s Search API. Enter the names of any two people with IMDb pages (the entertainment), and receive all the projects that they’ve both worked on (the crossing).

Behind the scenes, the code uses Google’s Search API to look for the entertainers’ IMDb pages. Once/if it finds them, it uses BeautifulSoup to scrape the two pages, and plain old Python to complete the comparison. It then uses jQuery to update the page without reloading.

This site is currently hosted on Amazon’s Elastic Container Service (ECS)! Play with it here. Or take a look at the code, and maybe even contribute to the project with a pull request!

‘One Word Answers to Impossible Questions’ is a small book of philosophical questions with scientifically proven one-word answers, connected to a website that goes deeper into the science and philosophy (and in some cases opinions) behind the book’s answers.

The classic example of this phenomenon is ‘Which came first, the chicken or the egg?’. The answer is egg. But why? Because of the theory of evolution, we know that something not-quite-a-chicken laid an egg with a mutated not-quite-a-chicken in it, the first chicken. Therefore, the egg came first.

This is a work in progress so there’s nothing to check out quite yet, but will eventually be another static site built with Hugo. In the meantime, you can email me directly if you’re interested in learning more!

Best Bet 55 is an app designed to gamify sports betting without putting any money on the line. It’s written with the Django Rest Framework and PostgreSQL in the backend, and React Native and TypeScript in the frontend. It is hosted on AWS, fully Docker-ized to enable use of Amazon’s Elastic Container Service (ECS). The app utilizes an API called therundown to track live game information.

As a Backend developer on a team of six, I have

• Contributed to the Django Rest Framework backend, providing RESTful APIs using high-coverage test driven development

• Owned the follower functionality and login flow from the backend through React Native and TypeScript frontend

• Aided in dockerizing and deploying multiple resources to ECS

• Optimized SQL queries with Prefetch and select_related, pinpointing problems and confirming solutions with Django’s built-in SQL Debugger

• Refactored pure JavaScript and React Native code to utilize TypeScript and React Hooks, minimizing future tech debt

Best Bet is no longer available in the App store, but you can learn more about it here.