Enc. Flashcards
1
Q
Binary Tree Longest Consecutive Sequence II
Given a binary tree, find the length(number of nodes) of the longest consecutive sequence(Monotonic and adjacent node values differ by 1) path.
The path could be start and end at any node in the tree
Input:
{1,2,0,3}
Output:
4
Explanation:
1
/ \
2 0
/
3
0-1-2-3
A
from lintcode import (
TreeNode,
)
"""
Definition of TreeNode:
class TreeNode:
def \_\_init\_\_(self, val):
self.val = val
self.left, self.right = None, None
"""
class Solution:
"""
@param root: the root of binary tree
@return: the length of the longest consecutive sequence path
"""
def longest_consecutive2(self, root: TreeNode) -> int:
# write your code here
res = 0
#Returns three values: curIncreasingPath from cur node, curDecreasingPath from cur node, (longest path found ANYWHERE in subtree)
#KEY IDEA: for a node, we only care about whether it's increasing or decreasing, and don't care where it comes from
#So as long as we maintain curInc and curDec, and update those accordingly correctly. The curInc or curDec can be shared across both left and right child since we don't
#care. Example: 1-2 and 1-2-3. We just care that the longest path is 1-2-3 and that's stored in curInc. We don't care that it's on the right.
def dfs(root):
nonlocal res
#can return a third value of 0 here for longest path..
if root is None:
return 0, 0
#(can return longest for res. basically, longest found in left or right subtree)
leftInc, leftDec = dfs(root.left)
rightInc, rightDec = dfs(root.right)
#(third value: longest?)
curInc, curDec = 0, 0
if root.left:
if root.left.val - 1 == root.val:
curInc = max(curInc, leftInc + 1)
elif root.left.val + 1 == root.val:
curDec = max(curDec, leftDec + 1)
if root.right:
if root.right.val + 1 == root.val:
curDec = max(curDec, rightDec + 1)
elif root.right.val - 1 == root.val:
curInc = max(curInc, rightInc + 1)
#Can instead do longest = max(leftLongest, rightLongest, curInc + curDec + 1)
res = max(res, curInc + curDec + 1)
#return curInc, curDec, longest
return curInc, curDec
dfs(root) #can then return dfs()[2]
return res
2
Q
Basic Calculator II
Given a string s which represents an expression, evaluate this expression and return its value.
The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-231, 231 - 1].
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Input: s = “3+222”
Output: 11
A
class Solution:
def calculate(self, s: str) -> int:
stack = []
op = "+"
num = 0
def helper(op, num):
if op == "+":
stack.append(num)
elif op == "-":
stack.append(-num)
elif op == "*":
stack.append(stack.pop() * num)
elif op == "/":
top = stack[-1]
stack.append(int(stack.pop() / num))
for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c in ["+", "-", "*", "/"]: #need this since can be empty spaces
helper(op, num)
op = c
num = 0
#the last num and op
helper(op, num)
return sum(stack)
#O(n)
#O(n)
3
Q
Basic Calculator III
Implement a basic calculator to evaluate a simple expression string.
The expression string contains only non-negative integers, +, -, *, / operators , open ( and closing parentheses ) and empty spaces . The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [-2147483648, 2147483647]
Input：” 6-4 / 2 “
Output：4
Explanation：4/2=2，6-2=4
A
class Solution:
"""
@param s: the expression string
@return: the answer
"""
def calculate(self, s: str) -> int:
op = "+"
num = 0
stack = [] #The idea is stack tracks all the numbers, then we can sum it up at the end.
#when encounter an operation, perform the necessary computation
#+ and - is a push onto stack directly
#mult and div is a mult or div with the top element of a stack
def helper(op, num):
if op == "+":
stack.append(num)
elif op == "-":
stack.append(-num)
elif op == "*":
stack.append(stack.pop() * num)
elif op == "/":
stack.append(int(stack.pop() / num))
#")" will just bleed through it's fine! will happen once op was set to ")", but ")" was already accounted for during the if conditional.
for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c == "(":
stack.append(op) #the operation so far to this point. This is because
#once we come back to this as a "(", we need to remember what operation we need prior to the "(" to evaluate that.
#When entering a parentheses, basically starting a new sequence
op = "+"
num = 0
elif c in ["+", "-", "*", "/", ")"]:
helper(op, num)
#Special handling if it's a ")"
if c == ")":
num = 0
while isinstance(stack[-1], int):
num += stack.pop()
#We now hit left parenthesis
op = stack.pop()
#We now evaluate this operation on the parentheses result.
#Usually it's left to right. We have a num that we're acculumlating from left, and when hit op we operate on it
#Now with parentheses it's slightly different. We use the result op(...) and (....) is on the right, then we do op. Still works tho!
helper(op, num)
op = c #set op to this op char we just saw here. If it's a ")", next time we call helper(op, num) in line 33, nothing happens which is fine!
num = 0
#let's say 1 - 1. We have a final num that is -1. work on that, with op "-" and num 1
helper(op, num)
return sum(stack)
#O(n)
#O(n)
4
Q
Basic Calculator
Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation.
Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().
Input: s = “(1+(4+5+2)-3)+(6+8)”
Output: 23
A
class Solution:
def calculate(self, s: str) -> int:
op = "+"
num = 0
stack = [] #The idea is stack tracks all the numbers, then we can sum it up at the end.
#when encounter an operation, perform the necessary computation
#+ and - is a push onto stack directly
#mult and div is a mult or div with the top element of a stack
def helper(op, num):
if op == "+":
stack.append(num)
elif op == "-":
stack.append(-num)
elif op == "*":
stack.append(stack.pop() * num)
elif op == "/":
stack.append(int(stack.pop() / num))
#")" will just bleed through it's fine! will happen once op was set to ")", but ")" was already accounted for during the if conditional.
for c in s:
if c.isdigit():
num = num * 10 + int(c)
elif c == "(":
stack.append(op) #the operation so far to this point. This is because
#once we come back to this as a "(", we need to remember what operation we need prior to the "(" to evaluate that.
#When entering a parentheses, basically starting a new sequence
op = "+"
num = 0
elif c in ["+", "-", "*", "/", ")"]:
helper(op, num)
#Special handling if it's a ")"
if c == ")":
num = 0
while isinstance(stack[-1], int):
num += stack.pop()
#We now hit left parenthesis
op = stack.pop()
#We now evaluate this operation on the parentheses result.
#Usually it's left to right. We have a num that we're acculumlating from left, and when hit op we operate on it
#Now with parentheses it's slightly different. We use the result op(...) and (....) is on the right, then we do op. Still works tho!
helper(op, num)
op = c #set op to this op char we just saw here. If it's a ")", next time we call helper(op, num) in line 33, nothing happens which is fine!
num = 0
#let's say 1 - 1. We have a final num that is -1. work on that, with op "-" and num 1
helper(op, num)
return sum(stack)
#O(n)
#O(n)
5
Q
Reorganize String
Given a string s, rearrange the characters of s so that any two adjacent characters are not the same.
Return any possible rearrangement of s or return “” if not possible.
Example 1:
Input: s = “aab”
Output: “aba”
Example 2:
Input: s = “aaab”
Output: “”
A
class Solution:
def reorganizeString(self, s: str) -> str:
counts = {}
for c in s:
counts[c] = counts.get(c, 0) + 1
prev = None #[prevCount, prevValue]
maxHeap = [[-count, c] for c, count in counts.items()]
heapq.heapify(maxHeap)
res = []
while maxHeap or prev:
#Holding on to a value but maxHeap is empty
if prev and not maxHeap:
return ""
if maxHeap:
count, value = heapq.heappop(maxHeap)
res.append(value)
count += 1
#Add previous value back to maxHeap
if prev:
heapq.heappush(maxHeap, prev)
prev = None #since it's been added back, let's reset it to None
if count != 0:
prev = [count, value]
return "".join(res)
#O(n log k) where k is number of unique elts
#O(k)
#In this case, k is 26
#
# - Part 1: Whether it’s possible to create a schedule that has a valid interleave.
# - Let’s say we have 11 items with 4 experiences: 6As, 1B, 1C, 3Ds
# - We take the total number of items which is 11. Divide it by 2, and ceil it. ceil(11/2) = 6
# - if ANY experience count exceeds this, we return False. Otherwise, we can return True.
6
Q
Family Tree
A
class Person:
def \_\_init\_\_(self, name):
self.name = name
self.parents = []
self.children = []
def familyTree(parentsToChildren):
nameToNodeMap = {}
for parent, child in parentsToChildren:
if parent not in nameToNodeMap:
parentObj = Person(parent)
nameToNodeMap[parent] = parentObj
nameToNodeMap[parent].children.append(child)
if child not in nameToNodeMap:
childObj = Person(child)
nameToNodeMap[child] = childObj
nameToNodeMpa[child].parents.append(parent)
return nameToNodeMap
def getFamilyRelationsMain(name, relationship):
def getRelationsHelper(name, relationship):
personObj = nameToNodeMap[name]
if relationship == "children":
return personObj.children
elif relationship == "parents":
return personObj.parents
elif relationship == "siblings":
siblings = set()
for parent in personObj.parents:
parentObj = nameToNodeMap[parent]
for child in parentObj.children:
if child != name:
siblings.add(child)
return list(siblings)
elif relationship == "grandparents":
grandparents = []
for parent in personObj.parents:
parentObj = nameToNodeMap[parent]
for grandparent in parentObj.parents:
grandparents.append(grandparent)
return grandparents
elif relationship == "grandchildren":
grandchildren = []
for child in personObj.children:
childObj = nameToNodeMap[child]
for grandchild in childObj.children:
grandchildren.append(grandchild)
relationshipArr = relationship.split()
cuirSet = set()
curSet.add(name)
for relation in relationshipArr:
newSet = set()
for name in curSet:
newSet.update(getRelationsHelper(name, relation))
curSet = newSet
return curSet
7
Q
Transaction DB
A
class DBPart2:
def \_\_init\_\_(self):
self.kvMap = {}
self.inTransaction = False
self.curFrame = {}
def get(self, key):
curMap = self.kvMap if not self.inTransaction else self.curFrame
if key not in curMap:
if key in self.kvMap:
return self.kvMap[key]
else:
print("Tried to get Key DNE")
return
return curMap[key]
def set(self, key, value):
curMap = self.kvMap if not self.inTransaction else self.curFrame
curMap[key] = value
def unset(self, key):
curMap = self.kvMap if not self.inTransaction else self.curFrame
if key not in curMap:
if self.inTransaction:
curMap[key] = None
return
print("Tried to get Key DNE")
return
del curMap[key]
def begin(self):
self.inTransaction = True
def commit(self):
for k, v in self.curFrame.items():
if not v:
del self.kvMap[k]
else:
self.kvMap[k] = v
self.curFrame = {}
self.inTransaction = False
def rollback(self):
self.curFrame = {}
self.inTransaction = False
8
Q
A
