Deck 1 Flashcards
Longest palindromic substring
Idea:
Start with individual letter, expand using l and r pointers continuously checking if the contained string is palindromic or not. Keep saving the max results
Algorithm:
1. For odd substrings
For each character, start with l and r at i
Bounds check and character equivalence check
Decrement l and increment r
- For even substrings
Same but start with l and r at i and i + 1 respectively
Roman to integer
Idea:
If the value of current character is less than the value of character after it, we have to subtract the current value from the result
Algorithm:
Define hashmap of (character, value)
Iterate through the string
If (i + 1) < len(s) and map(curr) < map(next)
answer -= curr
else
answer += curr
String to integer (atoi)
Idea:
We need to get to the point in the string where actual number (if it exists) starts
Algo:
First init result as 0 and sign as 1
First use strip to remove whitespace
Return 0 if no string at that point
Check the signage and assign the sign appropriately
Run the loop on remaining string
result = result * 10 + int(char)
break if the character is not digit
result = result * sign
Check bounds and return
Two Sum (Unsorted input)
- Create a Hashmap of (value, index)
- Iterate through the array
- If the diff exists, return diff index and current index
- Else add the current to the hashmap
Integer to roman
- Define a list with tuple (symbol, value) in increasing order
- Iterate over above list in decreasing order
- Find count of the current symbol using integer division
- If count, then append symbol to the answer that many times and find the remaining number using mod
- Return answer
Valid paranthesis
- Create hashmap of (closing, opening)
- Iterate through string
- if bracket in map
- if stack and top of stack == map(bracket), then pop
- else return False
- else stack append
- Return true of stack empty else false
Valid sudoku
- Start outer loop till 9
- Define set for horizontal and vertical
- Start inner loop till 9
- Check for (i, j) in horizontal set and (j, i) in vertical set
- Return False if exists
- Add to set if not and the position is not ‘.’
-End both loops
For box check
Define a dictionary
- Start outer loop till 9
- a = i // 3
- Start inner loop till 9
- b = j // 3
- If (a, b) not in dictionary, define it as set
- If (i, j) in the dictionary of (a, b), return False
- Else add (i, j) to the (a, b) dictionary
return True
Combination sum
Idea:
- Draw the recursion tree
- We first need to make decision on first element, either include it or not
- And then based on the bounds and current total, make other decision
Algo:
- Define dfs function with current array and total as param
- If the target is achieved, add the current copy to the answer
- If outside bounds or target exceeded
- return
- Decision 1: add the current candidate, and call dfs on it with new total
- Decision 2: pop the element to remove the recently added candidate and call the dfs on i + 1 element
Call the dfs on zeroth element
Permutations
Recursive idea:
We start with the empty combination, add the last element, then add the other on either side of it. Then we add next element to all possible positions within the above result (i.e. at start, middle, end)
Recursive algo:
- Define base case of if len(array) is 0 then return [[]]
- Call the self function and pass the array without the first element. Retrieve the results in the variable (perm)
- Define result as []
- For each p in perm
- For i in len(p) + 1
- Make a copy of p and insert array[0] at i position
- add the updated copy to answer
- end for
- end for
Return answer
Iterative algo:
- answer = [[]]
- for each number
- new_perm = []
- for each answer
- for each position in answer
- make a copy of answer and insert into position the current number and append to new_perm
- end for
- end for
- answer = new_perm
- end for
return answer
Merge intervals
- Sort intervals by start time
- Iterate through the intervals
- Insert 1st interval in the answer
- For rest, if current interval start is less or equal to last interval end, change last interval time to max of either
- else append to answer
Rotate list
Idea:
We need to find the pivot point at length - k, and then reassign pointers, i.e. join end to the start and return new head
Algorithm
Base case: If not head, return head
Calculate length and tail simultaneously
length = 1, tail = head. Run loop till tail.next
k = k % length
if k is 0, return head
curr = head
loop till length-k-1, curr = curr.next
Reassign pointers:
new_head = curr.next
curr.next = None
tail.next = head
return new_head
Minimum path sum
Idea:
Calculate minimum path sum for all the positions in the grid one by one, and eventually, we will have the minimum path sum for bottom right
Algorithm:
- Define dp array
- dp[i, j] = min(dp[i - 1, j], dp[i, j - 1]) + gri[i, j]
(except if the cell is on boundary, in which case it will be directly sum with either the left one or above one)
- Return dp[m - 1, n - 1]
Word search
Idea:
Run the dfs from each position in the grid recursively and compare the letter in that cell
Algorithm:
Define m and n, define path as empty set
Define dfs function with row, col and index for params as follows:
- if out of bounds or board letter != word index or position already in path set, return False
- Add position to path set
- store OR of dfs in 4 directions in result
- remove position from path
- return result
- Brute force through the board and call dfs, if True, return True
return False
Validate binary search tree
Idea:
We need to check if each node is within the its bounds. The left child has to be within (-inf, parent), right child has to be within (parent, inf)
Algo:
define util function with root, left_bound, right_bound for params as follows
- If not root, return True
- If not within value bounds, return False
- Return OR of recursive call for left and right child, right_bound is parent for left subtree call, left_bound is parent for right subtree call
- call util function over root with bounds as (-inf, inf)
Same tree
Recursive algorithm:
- if not p and not q, return True
- if values not equal or not p or not q, return False
- return AND of recursive calls of left subtree and right subtree
Iterative algorithm:
- Use stack, put (p, q) in stack
- while stack
- pop
- if not p and not q, continue
- if values not equal or not p or not q, return False
- stack append((p.left, q.left)) and append((p.right, q.right))
- end while
-return True
Symmetric tree
Recursive algorithm:
- define util function with l_tree and r_tree for params as follows
- if not l_tree and not r_tree, return True
- if values not equal or not l_tree or not r_tree, return False
- return AND of recursive calls of on (l_tree.left, r_tree.right) and (l_tree.right, r_tree.left)
Iterative algorithm:
- Use stack, put (l_tree, r_tree) in stack
- while stack
- pop
- if not l_tree and not l_tree, continue
- if values not equal or not l_tree or not r_tree, return False
- stack append((l_tree.left, r_tree.right)) and append((l_tree.right, r_tree.left))
- end while
-return True
Binary tree level order traversal
Recursive algo:
- define answer as []
- define dfs with node and depth as params
- if not node, return None
- if len(answer) equals depth, answer.append([])
- answer[depth].append(node.val)
- dfs(node.left, depth + 1)
- dfs(node.right, depth + 1)
call dfs(root, 0)
return answer
Iterative algo:
- Define answer as [] and deque
- put root in deque
- while queue:
- get queue length and define level as []
- for i till queue_length
- ele = queue.popleft()
- if ele, then append left and right to queue and append ele.val to level
- end for
- if level, append level to answer
- end while
return answer
Convert sorted list to binary search tree
Idea:
We need to find a middle, and then split from there. The left part of list will be the left subtree, and right part will be right subtree
Algorithm:
- Define getMiddle function with node as param as follows
- define fast and slow as head and prev as none
- while fast and fast.next, assign fast = fast.next.next, prev = slow, slow = slow.next
- if prev, then prev.next = None
- return slow
In main function:
- if not head, return None
- if not head.next, return TreeNode(head.val)
- middle = getMiddle(head)
- root = TreeNode(middle.val)
- root.right = recursive call(middle.next)
- root.right = recursive call(head)
- return root
Populating next right pointers
Idea:
Similar to BFS. Need to assign the next pointer to the next node in the traversal.
Iterative algo:
- if not root, return root
- define queue and append root
- while queue
- get queue length
- for i till queue length
- node = popleft
- if node
- if i is queue length - 1, then node.next = None
- else node.next = queue[0]
- append node.left and node.right to the queue
- end for
- end while
-return root
Recursive algo:
- Define a dictionary depth_dict
- Define a dfs function with node and depth as params as follows
- if not node, return
- if depth not in depth_dict, depth_dict[depth] = node
- else depth_dict[depth].next = node, depth_dict[depth] = node
- call dfs(node.left, depth + 1) and dfs(node.right, depth + 1)
- call dfs(root, 0)
- return root
Best time to buy and sell stock
Idea:
We need to iteratively find the minimum price at which the stock can be bought and then continue to find the max_profit
Algorithm:
- Define max_profit as 0 and min_price as float(‘inf’)
- iterate through the prices
- if current price less than the min_price, then assign current price to min_price
- else calculate max_profit using max between the current value and (current price - min_price)
- end iterate
-return max_profit
