Implement an iterator over a binary search tree (BST). Your iterator will be initialized with the root node of a BST. Calling next() will return the next smallest number in the BST.
defnext(self) -> int: """ @return the next smallest number """ curr = self.stack.pop() res = curr.val curr = curr.right while curr: self.stack.append(curr) curr = curr.left return res
defhasNext(self) -> bool: """ @return whether we have a next smallest number """ return len(self.stack) > 0
# Your BSTIterator object will be instantiated and called as such: # obj = BSTIterator(root) # param_1 = obj.next() # param_2 = obj.hasNext()
defnext(self) -> int: """ @return the next smallest number """ self.index += 1 return self.nodes_sorted[self.index]
defhasNext(self) -> bool: """ @return whether we have a next smallest number """ return self.index + 1 < len(self.nodes_sorted)
# Your BSTIterator object will be instantiated and called as such: # obj = BSTIterator(root) # param_1 = obj.next() # param_2 = obj.hasNext()
EQ-3
Given two words word1 and word2, find the minimum number of operations required to convert word1 to word2. You have the following 3 operations permitted on a word:
classSolution1: defminDistance(self, word1: str, word2: str) -> int: n,m = len(word1), len(word2) ifn * m == 0: return n + m
d = [[0]*(m+1) for _ in range(n+1)] fori in range(n+1): d[i][0] = i forj in range(m+1): d[0][j] = j
fori in range(1, n+1): forj in range(1, m+1): left = d[i-1][j] + 1 down = d[i][j-1] + 1 left_down = d[i-1][j-1] ifword1[i-1] != word2[j-1]: left_down += 1 d[i][j] = min(left, down, left_down) returnd[n][m]
EQ-4
Design and implement a data structure for Least Frequently Used (LFU) cache. It should support the following operations: get and put. 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 reaches its capacity, it should invalidate the least frequently used item before inserting a new item. For the purpose of this problem, when there is a tie (i.e., two or more keys that have the same frequency), the least recently used key would be evicted. Note that the number of times an item is used is the number of calls to the get and put functions for that item since it was inserted. This number is set to zero when the item is removed.
# YourLFUCache object will be instantiated and called as such: # obj = LFUCache(capacity) # param_1 = obj.get(key) # obj.put(key, value)
EQ-5
Implement a basic calculator to evaluate a simple expression string. The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces. 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].
class Solution: def calculate(self, s: str) -> int: # first define a couple helper methods # operation helper to perform basic math operations s = s + "$"
def helper(stack: list, i: int) -> int: num = 0 sign = '+' while i < len(s): c = s[i] ifc == " ": i += 1 continue
ifc.isdigit(): num = 10 * num + int(c) i += 1 elif c == '(': num, i = helper([], i+1) # Recursion else: ifsign == '+': stack.append(num) ifsign == '-': stack.append(-num) ifsign == '*': stack.append(stack.pop() * num) ifsign == '/': stack.append(int(stack.pop() / num)) num = 0 i += 1 ifc == ')': return sum(stack), i sign = c return sum(stack)
return helper([], 0)
EQ-6
Design a Tic-tac-toe game that is played between two players on a n x n grid. You may assume the following rules:
A move is guaranteed to be valid and is placed on an empty block.
Once a winning condition is reached, no more moves is allowed.
A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.
def __init__(self, n: int): """ Initialize your data structure here. """ self.row = [0for i in range(n)] self.col = [0for i in range(n)] self.major = 0 self.minor = 0 self.n = n
def move(self, row:int, col:int, player: int) -> int: """ Player {player} makes amove at ({row}, {col}). @param row The row of the board. @param col The column of the board. @param player The player, can be either 1or2. @return The current winning condition, can be either: 0: No one wins. 1: Player 1 wins. 2: Player 2 wins. """ p = 1if player == 1else -1
self.row[row] += p self.col[col] += p
if row == col: self.major += p
if row == self.n-1-col: self.minor += p
ifabs(self.row[row]) == self.n orabs(self.col[col]) == self.n or \ abs(self.major) == self.n orabs(self.minor) == self.n: return player
return0
EQ-7
Given a string s, return the last substring of s in lexicographical order.
idx = {c: i for i, c in enumerate(sorted(set(s)))} radix,val, cur, m = len(idx), 0, 0, 0 fori in range(len(s))[::-1]: cur = idx[s[i]] + cur/radix ifcur >= val: m,val = i, cur returns[m:]
classSolution1: deflastSubstring(self, s: str) -> str: i,j, k = 0, 1, 0 n = len(s) whilej + k < n: ifs[i+k] == s[j+k]: k+= 1 continue elifs[i+k] > s[j+k]: j = j + k + 1 else: i = max(i + k + 1, j) j = i + 1 k = 0 returns[i:]
def__init__(self, key=None, value=None): self.key = key self.value = value global hashMap hashMap = {}
defput(self, key: int, value: int) -> None: hashMap[key] = value
defget(self, key: int) -> int: return hashMap[key] if key in hashMap else-1
defremove(self, key: int) -> None: if key in hashMap: del hashMap[key]
classMyHashMap1:
def__init__(self): """ Initialize your data structure here. """ self.table = [-1] * 1000001
defput(self, key: int, value: int) -> None: """ value will always be non-negative. """ self.table[key] = value
defget(self, key: int) -> int: """ Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key """ return self.table[key]
defremove(self, key: int) -> None: """ Removes the mapping of the specified value key if this map contains a mapping for the key """ self.table[key] = -1
# Your MyHashMap object will be instantiated and called as such: # obj = MyHashMap() # obj.put(key,value) # param_2 = obj.get(key) # obj.remove(key)
EQ-9
You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise).
1 2 3 4 5 6 7 8 9 10 11 12
# 48. Rotate Image
# Do not return anything, modify matrix in-place instead.
class Solution: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: if len(s1) + len(s2) != len(s3): return False
current_states = [(0, 0)] for char in s3: if len(current_states) == 0: return False next_states = set() for i, j in current_states: if i < len(s1) and s1[i] == char: next_states.add((i + 1, j)) if j < len(s2) and s2[j] == char: next_states.add((i, j + 1)) current_states = next_states
return len(current_states) > 0
class Solution1: def isInterleave(self, s1: str, s2: str, s3: str) -> bool: stack = [(0,0,0)] seen = {(0,0,0)} while stack: (i,j,k) = stack.pop() if k == len(s3) and i == len(s1) and j == len(s2): return True if i < len(s1) and k < len(s3) and s1[i] == s3[k] and (i+1, j, k+1) not in seen: stack.append((i+1, j, k+1)) seen.add((i+1, j, k+1)) if j < len(s2) and k < len(s3) and s2[j] == s3[k] and ( i, j+1, k+1) not in seen: stack.append(( i, j+1, k+1)) seen.add(( i, j+1, k+1)) return FalseGiven s1, s2, s3, find whether s3 is formed by the interleaving of s1and s2.