NonN-all Flashcards
There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won’t stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the m x n maze, the ball’s start position and the destination, where start = [startrow, startcol] and destination = [destinationrow, destinationcol], return true if the ball can stop at the destination, otherwise return false.
You may assume that the borders of the maze are all walls (see examples).
Input: maze = [[0,0,1,0,0],[0,0,0,0,0],[0,0,0,1,0],[1,1,0,1,1],[0,0,0,0,0]], start = [0,4], destination = [4,4]
Output: true
Explanation: One possible way is : left -> down -> left -> down -> right -> down -> right.
class Solution:
def hasPath(self, maze: List[List[int]], start: List[int], destination: List[int]) -> bool:
ROWS, COLS = len(maze), len(maze[0])
visitedStops = set()
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
#We run dfs from stop sets (the "stop sets when hit walls") basically. We don't care about the cells in the middle to be added to visited, only the cells near walls.
def dfs(r, c):
#If we try to visit the stopSet again, return False
#Since when we run into the stop, we will do a dfs and have attempted.
if (r, c) in visitedStops:
return False
visitedStops.add((r, c))
#If this stop is the destination
if [r, c] == destination:
return True
#Try all possible directions
for dr, dc in directions:
#The ball starts at r, c. Important!
newR, newC = r, c
#Roll as far as we can, until we hit a wall. Let's check if it even makes sense to roll in that
#Particular direction. Let's do that by checking newR + dr, newC + dc in the while loop
#Otherwise we prematurely set newR = newR + dr, newC = newC + dc, and then calling
#dfs on that premature out of bounds position will cause confusion.
#Whereas if we set newR, newC to be r, c above, the dfs(r, c) will just return False since that stop is already in visited.
while newR + dr >= 0 and newR + dr < ROWS and newC + dc >= 0 and newC + dc < COLS and maze[newR + dr][newC + dc] != 1:
newR += dr
newC += dc
#We rolled and hit a stop. Now if the recursive call from this stop returned True, we can return True
if dfs(newR, newC):
return True
return False
return dfs(start[0], start[1])
#Runtime: O(mn) #Visit all the cells potentially.
#Space: O(mn) upper bound but in actuality, it's a combination of 1) number of stops
#2) longest straight path -> recursion stackYou are given the string croakOfFrogs, which represents a combination of the string “croak” from different frogs, that is, multiple frogs can croak at the same time, so multiple “croak” are mixed.
Return the minimum number of different frogs to finish all the croaks in the given string.
A valid “croak” means a frog is printing five letters ‘c’, ‘r’, ‘o’, ‘a’, and ‘k’ sequentially. The frogs have to print all five letters to finish a croak. If the given string is not a combination of a valid “croak” return -1.
Input: croakOfFrogs = “crcoakroak”
Output: 2
Explanation: The minimum number of frogs is two.
The first frog could yell “crcoakroak”.
The second frog could yell later “crcoakroak”.
class Solution:
def minNumberOfFrogs(self, croakOfFrogs: str) -> int:
counts = {} #maps the char to the count
for c in "croak": #initialize counts to zero to start.
counts[c] = 0
CROAK_STRING = "croak"
res, curFrogs = 0, 0
for c in croakOfFrogs:
#1) Count the number of each character. Do this for every character.
counts[c] += 1
#2) Increment/decrement frogs as needed.
if c == "c":
curFrogs += 1
elif c == "k":
curFrogs -= 1
res = max(res, curFrogs)
#length 5 operation
for i in range(len(CROAK_STRING) - 1):
#3) If at any point there are more subsequent letters than previous (more Rs than Cs, etc..), that is an issue, so return -1
#example: crr #<- this is invalid!!
if counts[CROAK_STRING[i + 1]] > counts[CROAK_STRING[i]]:
return -1
#4) At the end, we expect there to be no more croaking frogs
# Invalid example: croakc #this is invalid.
# And that the counts of everything match!
if curFrogs == 0 and all(count == counts["c"] for count in counts.values()):
return res
return -1
#Runtime: O(n) just iterating through the String
#Space: O(5) -> O(1) for the counts map
You have a browser of one tab where you start on the homepage and you can visit another url, get back in the history number of steps or move forward in the history number of steps.
Implement the BrowserHistory class:
BrowserHistory(string homepage) Initializes the object with the homepage of the browser.
void visit(string url) Visits url from the current page. It clears up all the forward history.
string back(int steps) Move steps back in history. If you can only return x steps in the history and steps > x, you will return only x steps. Return the current url after moving back in history at most steps.
string forward(int steps) Move steps forward in history. If you can only forward x steps in the history and steps > x, you will forward only x steps. Return the current url after forwarding in history at most steps.
Input:
[“BrowserHistory”,”visit”,”visit”,”visit”,”back”,”back”,”forward”,”visit”,”forward”,”back”,”back”]
[[“leetcode.com”],[“google.com”],[“facebook.com”],[“youtube.com”],[1],[1],[1],[“linkedin.com”],[2],[2],[7]]
Output:
[null,null,null,null,”facebook.com”,”google.com”,”facebook.com”,null,”linkedin.com”,”google.com”,”leetcode.com”]
Explanation:
BrowserHistory browserHistory = new BrowserHistory(“leetcode.com”);
browserHistory.visit(“google.com”); // You are in “leetcode.com”. Visit “google.com”
browserHistory.visit(“facebook.com”); // You are in “google.com”. Visit “facebook.com”
browserHistory.visit(“youtube.com”); // You are in “facebook.com”. Visit “youtube.com”
browserHistory.back(1); // You are in “youtube.com”, move back to “facebook.com” return “facebook.com”
browserHistory.back(1); // You are in “facebook.com”, move back to “google.com” return “google.com”
browserHistory.forward(1); // You are in “google.com”, move forward to “facebook.com” return “facebook.com”
browserHistory.visit(“linkedin.com”); // You are in “facebook.com”. Visit “linkedin.com”
browserHistory.forward(2); // You are in “linkedin.com”, you cannot move forward any steps.
browserHistory.back(2); // You are in “linkedin.com”, move back two steps to “facebook.com” then to “google.com”. return “google.com”
browserHistory.back(7); // You are in “google.com”, you can move back only one step to “leetcode.com”. return “leetcode.com”
class BrowserHistory:
def \_\_init\_\_(self, homepage: str):
self.history = [homepage]
self.curIndex = 0
self.curLength = 1
#[1, 2, 3]
# i = 2
def visit(self, url: str) -> None:
#Check if we should be appending or replacing
# 3 < 4, we need to append.
if len(self.history) < self.curIndex + 2:
self.history.append(url)
else:
#replace the elt at the next index over
self.history[self.curIndex + 1] = url
#Advance curIndex to the next index
self.curIndex += 1
#Compute the new true length. This is mainly used for the forward operation
self.curLength = self.curIndex + 1
#Example: [1, 2, 3, 4 5]
# i=2
#We replace history with [1, 2, 3, 6 5], then i advances to i = 3
#i=3
#so the curLength is i + 1 after the advance (length 4), since 6 is our last element.
def back(self, steps: int) -> str:
self.curIndex = max(self.curIndex - steps, 0)
return self.history[self.curIndex]
def forward(self, steps: int) -> str:
#Go up to the last element of our curLength. Think of it as basically the "length," so last element is curLength - 1.
self.curIndex = min(self.curIndex + steps, self.curLength - 1)
return self.history[self.curIndex]
#Runtime: O(1) for every single operation, because we "soft delete" for visit
#Space: O(n) for the browser history, which can potentially contain more elements than we want (stale soft-deleted data) That's fine..
Your BrowserHistory object will be instantiated and called as such:
# obj = BrowserHistory(homepage)
# obj.visit(url)
# param_2 = obj.back(steps)
# param_3 = obj.forward(steps)Cousins in Binary Tree
Given the root of a binary tree with unique values and the values of two different nodes of the tree x and y, return true if the nodes corresponding to the values x and y in the tree are cousins, or false otherwise.
Two nodes of a binary tree are cousins if they have the same depth with different parents.
Note that in a binary tree, the root node is at the depth 0, and children of each depth k node are at the depth k + 1.
Input: root = [1,2,3,4], x = 4, y = 3
Output: false
# 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 isCousins(self, root: Optional[TreeNode], x: int, y: int) -> bool:
#Cousins if on the same level but different parents
q = deque() #(the actualNode, parent value)
q.append((root, None)) #no parent initially
while q:
levelMap = {} #key all the node values in current level, value is the parent that it came from.
for _ in range(len(q)):
curNode, parent = q.popleft()
levelMap[curNode.val] = parent
if x in levelMap and y in levelMap and levelMap[x] != levelMap[y]:
return True
if curNode.left:
q.append((curNode.left, curNode.val))
if curNode.right:
q.append((curNode.right, curNode.val))
return False
#O(n)
#O(h)Lowest Common Ancestor of a Binary Tree
Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.
According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes p and q as the lowest node in T that has both p and q as descendants (where we allow a node to be a descendant of itself).”
Input: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
Output: 3
Explanation: The LCA of nodes 5 and 1 is 3.
# Definition for a binary tree node.
# class TreeNode:
# def \_\_init\_\_(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
if not root:
return None
#Goal is to find p or q
#Returns p or q
if root == p or root == q:
return root
#If not found, try to find p and q in subtrees respectively.
##LeftNode and rightNode will return the subtrees that are rooted at p and q respectively, since we have the root == p or root == q condition up above
##The goal is to find p and find q. In both left and right subtrees, we try to find both.
leftNode = self.lowestCommonAncestor(root.left, p, q)
rightNode = self.lowestCommonAncestor(root.right, p, q)
#If able to find both
if leftNode and rightNode:
return root #the root is the LCA
#If not able to find both, so both are on the same side. Therefore, the anchor that we found on the one side is LCA.
if leftNode:
return leftNode
if rightNode:
return rightNode
#Runtime: O(n)
#Space: O(h)Single Element in a Sorted Array
You are given a sorted array consisting of only integers where every element appears exactly twice, except for one element which appears exactly once.
Return the single element that appears only once.
Your solution must run in O(log n) time and O(1) space.
Input: nums = [1,1,2,3,3,4,4,8,8]
Output: 2
class Solution:
def singleNonDuplicate(self, nums: List[int]) -> int:
l, r = 0, len(nums) - 1
while l <= r:
m = l + (r - l) // 2
if ((m - 1) < 0 or nums[m] != nums[m - 1]) and (m + 1 == len(nums) or nums[m] != nums[m + 1]):
return nums[m]
leftSize = m - 1 if nums[m - 1] == nums[m] else m
if leftSize % 2:
r = m - 1
else:
l = m + 1
#O(log n)
#O(1)
#If index m is 3, the values to the left are 0 1 2. So it would be m normally. But if nums[m - 1] = nums[m], then the size is actually m - 1 since we skip the elt to the left.
#What if m - 1 is out of bounds? So in this case, m was 0. Since array is sorted, m - 1 is the last element, so we take m. Therefore, leftSize = m = 0.
The unique number is on the side that has odd number of elts (after duplicate with m crossed out).Implement Minesweeper
- Example Input: 3, 5, [(0,2), (1,2), (2,2)]
- This indicates the number of rows, number of columns, and mine_coordinates
- Implement the following functions:
- def __init__(self, ROWS, COLS, mine_coordinates): initialize the game with these inputs.
- def get_board(self): get the board in its current state
- def reveal(self, r, c): click at r, c, and recursively reveal everything that we can reveal. If bomb, return immediately and print “game over”
class Game:
def \_\_init\_\_(self, ROWS, COLS, mine_coordinates):
self.grid = [[0] * COLS for r in range(ROWS)]
self.mask = [[False] * COLS for r in range(ROWS)]
self.directions = [(0,1), (0, -1), (1,0),(-1, 0), (1, 1), (-1, 1), (1, -1), (-1, -1)]
for r, c in mine_coordinates:
self.grid[r][c] = "B"
self.ROWS = ROWS
self.COLS = COLS
for r in range(ROWS):
for c in range(COLS):
if self.grid[r][c] != "B":
self.grid[r][c] = self.computeNumber(r, c)
#computes the number to store in a particular cell
def computeNumber(self, r, c):
total = 0
for dr, dc in self.directions:
neiR, neiC = r + dr, c + dc
if neiR >= 0 and neiR < self.ROWS and neiC >= 0 and neiC < self.COLS and self.grid[neiR][neiC] == "B":
total += 1
return total
def reveal(self, r, c):
if self.grid[r][c] == "B":
self.mask[r][c] = True
print("Game Over")
return
self.mask[r][c] = True
for dr, dc in self.directions:
neiR, neiC = r + dr, c + dc
#self.mask[neiR][neiC] will be True if already revealed and that acts as our visit set.
if neiR >=0 and neiR < self.ROWS and neiC >= 0 and neiC < self.COLS and not self.mask[neiR][neiC] and self.grid[neiR][neiC] != "B":
self.reveal(neiR, neiC) #recursively reveal
def get_board(self):
visibleBoard = [["-"] * self.COLS for r in range(self.ROWS)]
for r in range(self.ROWS):
for c in range(self.COLS):
if self.mask[r][c]:
visibleBoard[r][c] = self.grid[r][c]
#Otherwise it'll default to a "-"
return visibleBoard
#Runtime: O(mn)
#Space: O(mn)
#Example
# minesweeper = Game(3, 5, [(0, 2), (1, 2), (2, 2)])
# print(minesweeper.get_board())
# minesweeper.reveal(0, 0)
# print(minesweeper.get_board())
# minesweeper.reveal(0, 4)
# print(minesweeper.get_board())
# minesweeper.reveal(0, 2)
# print(minesweeper.get_board())
[['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-'], ['-', '-', '-', '-', '-']]
# [[0, 2, '-', '-', '-'], [0, 3, '-', '-', '-'], [0, 2, '-', '-', '-']]
# [[0, 2, '-', 2, 0], [0, 3, '-', 3, 0], [0, 2, '-', 2, 0]]
# Game Over
# [[0, 2, 'B', 2, 0], [0, 3, '-', 3, 0], [0, 2, '-', 2, 0]]Stone Game, but Parity can be even OR odd.
Alice always goes first
Bob ALWAYS picks the maximum value that’s available from the ends
Return the max sum that Alice can earn from this game
def stoneGame(piles):
dp = {} #(l, r) -> Alice max
def dfs(l, r, isATurn):
if l > r:
return 0
if (l, r) in dp:
return dp[(l, r)]
if isATurn:
dp[(l, r)] = max(piles[l] + dfs(l + 1, r, False), piles[r] + dfs(l, r - 1, False))
return dp[(l, r)]
else:
if piles[l] > piles[r]:
#What remains for Alice is l + 1 to r to choose from
dp[(l, r)] = dfs(l + 1, r, True)
return dp[(l, r)]
else:
#What remains for Alice is l, r - 1 to choose from
dp[(l, r)] = dfs(l, r - 1, True)
return dp[(l, r)]
return dfs(0, len(piles) - 1, True)
#Runtime: O(n^2) for l and r values
#O(n^2) for dp cache
#Even
piles = [3, 7, 2, 1]
print(stoneGame(piles)) # answer is 8
#Odd
piles = [3, 7, 1] #answer is 4
print(stoneGame(piles))
#Odd
piles = [7, 2, 1, 6, 2, 8, 5] #answer should be 22
#A:7 8 6 1 -> 22
#B:5 2 2
print(stoneGame(piles))
#Even
piles = [7, 2, 1, 6, 2, 8, 5, 3] #answer should be 23
#A 7 2 6 8 -> 23
#B 1 2 5 3
print(stoneGame(piles))Predict the Winner
You are given an integer array nums. Two players are playing a game with this array: player 1 and player 2.
Player 1 and player 2 take turns, with player 1 starting first. Both players start the game with a score of 0. At each turn, the player takes one of the numbers from either end of the array (i.e., nums[0] or nums[nums.length - 1]) which reduces the size of the array by 1. The player adds the chosen number to their score. The game ends when there are no more elements in the array.
Return true if Player 1 can win the game. If the scores of both players are equal, then player 1 is still the winner, and you should also return true. You may assume that both players are playing optimally.
Input: nums = [1,5,2]
Output: false
Explanation: Initially, player 1 can choose between 1 and 2.
If he chooses 2 (or 1), then player 2 can choose from 1 (or 2) and 5. If player 2 chooses 5, then player 1 will be left with 1 (or 2).
So, final score of player 1 is 1 + 2 = 3, and player 2 is 5.
Hence, player 1 will never be the winner and you need to return false.
class Solution:
def PredictTheWinner(self, nums: List[int]) -> bool:
dp = {} #(l, r): maxDifference of current player - other player, from numbers between i to j.
def dfs(l, r):
if l == r:
return nums[l]
if (l, r) in dp:
return dp[(l, r)]
#The maximum difference for dp[(l, r)] is. The max we can get from an end, minus the max difference
#that the OTHER player can get that's in the other player's benefit. This is minimax!
dp[(l, r)] = max(nums[l] - dfs(l + 1, r), nums[r] - dfs(l, r - 1))
return dp[(l, r)]
return dfs(0, len(nums) - 1) >= 0
#O(N^2)
#O(N^2)
# def find(i, j):
# if (i, j) not in dp:
# if i == j:
# return nums[i]
# dp[i,j] = max(nums[i]-find(i+1, j), nums[j]-find(i, j-1))
# return dp[i,j]
# return find(0, len(nums)-1) >= 0In a video game player starts at beginning of maze, several paths can take to next level of game. Max points from top to bottom of path? CAN BE NEGATIVE VALUES. Using milestone class game = Milestone(-1, [Milestone(-1, [Milestone(-5), Milestone(-10)]), Milestone(-3, [Milestone(-7)])]).
class Milestone(object):
def \_\_init\_\_(self, points, children = None):
self.points = points
self.children = children or []
# game = Milestone(-1, [Milestone(-1, [Milestone(-5), Milestone(-10)]), Milestone(-3, [Milestone(-7)])]) #expect -7
game = Milestone(1, [Milestone(1, [Milestone(5), Milestone(10)]), Milestone(3, [Milestone(7)])]) #expect 12.
def find_max_points(game):
def dfs(root, curSum):
if not root:
return 0
curSum += root.points
if not root.children:
return curSum
res = -float('inf')
for child in root.children:
res = max(dfs(child, curSum), res)
return res
return dfs(game, 0)
print(find_max_points(game))Find repetitions in paragraph
paragraph = "The hello world. The is the world hello!"
#World: 2 occurrences -> 1 repetition
#The: 3 occurrences -> 2 repetitions
#hello: 2 occurrences -> 1 repetition
import re
def find_repetitions(paragraph):
#\W matches any non-word character (equivalent to [^a-zA-Z0-9_])
paragraph = re.sub("\W", " ", paragraph).lower()
wordList = paragraph.split()
wordToCount = {}
res = 0
for w in wordList:
wordToCount[w] = wordToCount.get(w, 0) + 1
print(wordToCount)
for w in wordToCount:
res += wordToCount[w] - 1
return res
print(find_repetitions(paragraph))How to turn paragraph into lower case, no punctuations, and stripped of spaces? Then get all the words.
import re
paragraph = re.sub(“\W”, “ “, paragraph).lower()
#\W matches any non-word character (equivalent to [^a-zA-Z0-9_])
words = paragraph.split()
print(words
Determine the triangle type. Scalene, Isosceles, Equilateral. Valid triangle if sum of two sides’ lengths >= third.
def getTriangleType(lengths):
a, b, c = lengths
if a + b <= c or a + c <= b or b + c <= a:
return "Not a Triangle"
lengthSet = set(lengths)
if len(lengthSet) == 3:
return "Scalene"
elif len(lengthSet) == 2:
return "Isosceles"
else:
return "Equilateral"Given a stream of blah | blah | tags, perform single and multi-tag search to return all the associated tags with a particular user_input of tags.
Example:
stream = [
“blah|blah|host:a,role:web,region:us-east-1a”,
“blah|blah|host:b,role:web,region:us-east-1b”,
“blah3|blah3|host:a,role:web,region:us-east-1a”,
“blah2|blah2|host:c,role:db,db_role:primary,region:us-east-1e”
]
user_input = [“role:web”] #Expected: {‘host:b’, ‘region:us-east-1a’, ‘region:us-east-1b’, ‘host:a’}
user_input = [“role:db”, “db_role:primary”] #Expected: {‘region:us-east-1e’, ‘host:c’}
user_input = [“host:a”, “host:b”] #Expected: {}
"""
#High-level design is a Hashmap:
#Key: the individual Tag
#Value: set of tag lines that contain the individual tag in full
#So to do multi-tag search:
#We get the sets of tag lines, one set for each multitag
#Perform an intersection of those sets to find the common tag line
#Then finally, iterate through this tag line and take everything that is NOT in the multi-tag search. Set difference?
For example:
hosta: set("blah|blah|host:a, role:web, region:us-east-1a", "blah|blah|host:a, role:web, region:us-east-1a")
hostb: set("blah|blah|host:b, role:web, region:us-east-1b")
roledb: set("host:c, role:db, db_role:primary, region:us-east-1e")
dbrole:primary: set(host:c, role:db, db_role:primary, region:us-east-1e)
"""
stream = [
"blah|blah|host:a,role:web,region:us-east-1a",
"blah|blah|host:b,role:web,region:us-east-1b",
"blah3|blah3|host:a,role:web,region:us-east-1a",
"blah2|blah2|host:c,role:db,db_role:primary,region:us-east-1e"
]
from collections import defaultdict
tagsMap = defaultdict(set)
def populateTagsMap(stream):
for line in stream:
tagsLine = line.split("|")[-1]
allTags = tagsLine.split(",")
#print(allTags)
for tag in allTags:
tagsMap[tag].add(tagsLine)
def getAssociatedTags(userInput):
commonLinesSet = tagsMap[userInput[0]]
if len(userInput) > 1:
for tag in userInput[1:]:
commonLinesSet = commonLinesSet.intersection(tagsMap[tag])
collapsedSet = set()
for line in commonLinesSet:
tags = line.split(",")
for tag in tags:
collapsedSet.add(tag)
remainingTags = collapsedSet.difference(set(userInput))
print(remainingTags)
return remainingTags
user_input = ["role:web"] #Expected: {'host:b', 'region:us-east-1a', 'region:us-east-1b', 'host:a'}
user_input = ["role:db", "db_role:primary"] #Expected: {'region:us-east-1e', 'host:c'}
user_input = ["host:a", "host:b"] #Expected: {}
populateTagsMap(stream)
# print(getAssociatedTags(user_input))
getAssociatedTags(user_input) Path Sum II
Given the root of a binary tree and an integer targetSum, return all root-to-leaf paths where the sum of the node values in the path equals targetSum. Each path should be returned as a list of the node values, not node references.
A root-to-leaf path is a path starting from the root and ending at any leaf node. A leaf is a node with no children.
Input: root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
Output: [[5,4,11,2],[5,8,4,5]]
Explanation: There are two paths whose sum equals targetSum:
5 + 4 + 11 + 2 = 22
5 + 8 + 4 + 5 = 22
# 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 pathSum(self, root: Optional[TreeNode], targetSum: int) -> List[List[int]]:
res = []
def dfs(node, curSum, curPath):
if not node:
return
curSum += node.val
if not node.left and not node.right:
if curSum == targetSum:
newPath = curPath + [node.val]
res.append(newPath)
dfs(node.left, curSum, curPath + [node.val])
dfs(node.right, curSum, curPath + [node.val])
dfs(root, 0, [])
return res
#O(n)
#O(h)
