Deck 2 Flashcards
Number of islands
Idea:
We need to use a graph traversal teechnique to find the continuous block of land cells, mark them visited and append the answer count
BFS solution:
- Define bfs function with row, col as params as follows
- define a deque, add (row, col) to the queue and visited set
- define 2d directions array for 4 directions
- while queue
- pr, pc = popleft()
- for each direction
- calculate final position from popped pr, pc
- if that position is in bounds and is a land and not in visited
- append that position to the queue and add it to visited array
- end if
- end for
- end while
- Define m, n, empty visited set and answer as 0
- for i till m
- for j till n
- if (i, j) is land and not in visited
- run bfs on (i, j) and increment the answer count
Course schedule
Idea:
We run dfs on the course - prerequisite relationship graph, and if we encounter cycle, then their is cyclic dependency, thus not possible to finish the course
DFS solution:
-Define map like { i: [] for i in range(numCourses) } and an empty visited set
-add the prereqs in the above define map
-define dfs function with course as a parameter as follows
-if course in visited, return False
-if prereq of course is empty, return True
-add course to visited
-for every prereq in course prereqs
-if not dfs(prereq), return False
-end if
-end for
-remove course from visited
-assign [] to map of that course to avoid recomputation
-return True
-end func
-iterate through numcourses:
-if not dfs, return False
-end if
-end iterate
-return True
Course schedule 2
Idea:
Topological sort, dfs to fist add prerequisites and then others
Algorithm:
(Cycle set in this code is same as visited set in course schedule 1, visited set to track whether the course has been added to output or not)
-Define the prereq map like this { c: [] for c in range(numCourses)}
-Add the course and prereq to the prereq map
-declare output as empty list and visited and cycle as empty set
-define dfs with course param as follows
-if course in cycle, return False
-if course in visited, return True
-add course to cycle set
-for each pre of prereq[course]
-if not dfs(pre), return False
-end for
-remove course from cycle
-add course to visited
-append course to output
-for each course number
-if not dfs, return []
-end for
-return output
Min Stack
Idea:
We need to maintain the min element in the stack at each point of it
So the option is to have another stack called min_stack
Solution:
During push, push the minimum of the value and the current top of min-stack to the min_stack
LRU cache
Idea:
We will use hashmap and a doubly linked list. Hashmap will be (key, node pointer). And we will have dummy right and left pointers to keep track of the most recent and least recent nodes respectively
Solution:
-Declare Node class with key, val, prev and next
- INIT
-initialize capacity and empty hashmap
-intialize dummy pointers right and left and link them to each other in the beginning - Define utility function insert for inserting node to the right
- Define utility function for removing the node by delinking it from its prev and next nodes
- GET
-if key in map
-remove that node
-insert that node
-return the value
-end if
-return -1 - PUT
-if key in map
-remove that node
-end if
-assign new node to that key in map
-insert that node
-if map len > capacity
-remove lru, i.e. left.next
-delete the key from hash map
-end if
Implement trie (prefix tree)
-Define TrieNode class with children as hashmap and endOfWord boolean as False
- INIT
-initialize root as TrieNode() - INSERT
-define curr as root
-for every char in word
-if char not in curr.children
-curr.children[c] = TrieNode
-end if
-curr = curr.children[char]
-end for
-mark curr.endOfWord = True - SEARCH
-define curr as root
-for every char in word
-if char not in curr.children, return False
-end if
-curr = curr.children[char]
-end for
-return curr.endOfWord - STARTS WITH
-same as SEARCH, just return True instead of endOfWord
Design add and search words data structure
Idea:
Use Trie to store the words data
Use dfs to search the word since there might be wildcard characters
Solution:
-Define TrieNode class with children as empty hashmap and endOfWord boolean as False
- INIT
-initialize root as TrieNode() - ADD WORD
-define curr as root
-for every char in word
-if char not in curr.children
-curr.children[char] = TrieNode()
-end if
-curr = curr.children[char]
-end for
-curr.endOfWord = True - SEARCH
-define dfs function with j and root as param as follows
-curr = root
-for i from j to len(word)
-char = word[i]
-if char is ‘.’
-for every child in children
-if dfs(i + 1, child), return True
-end if
-end for
return False
-end if
-else
-if char not in children, return False
-end if
curr = curr.children[char]
-end else
-return curr.endOfWord
-return dfs(0, self.root)
Longest increasing subsequence
Idea:
We start from the end of the array, and then compare the current element to every element after it, and compute LIS using the already stored LIS of elements further in the array
Algorithm:
-Define lis array of length nums n
-for i from n-1 to 0
-for j from i + 1 to n - 1
-if nums[i] < nums[j]
-lis[i] = max(lis[i], 1 + lis[j])
-end if
-end for
-end for
-return max from lis array
Pacific atlantic water flow
Idea:
Instead of starting from the land grid, we start from the borders, and find which cells can flow into that ocean. We maintain two sets for each ocean and then find the intersection
Algorithm:
-Declare empty sets for both pacific an atlantic oceans
-declare dfs with row, col, visited set and prev_height as params as follows
-if (row, col) in visited set or out of bounds of heights[row][col] < prev_height, return
-end if
-add (r, c) to visited set
-call dfs on its four neighbors and pass the height of (r, c) as param for prev_height
-call dfs for each cell bordering the oceans
-find the cells common in both the sets and add them to an answer array
-return answer
Diameter of binary tree
Algorithm:
-Define self.result as 0
-define dfs function with node as param as follows
-if not node, return 0
-define left_height and right_height as recursive calles to node.left and node.right
-set result as max between itself and (left_height + right_height)
-return 1 + max(left_height, right_height)
-dfs(root)
-return self.result
Reorganize string
Idea:
Use heap and start with the most occurring characters, at each iteration
Algorithm:
-create hashmap of char counts Counter like count = Counter(s)
-construct max_heap = [[-cnt, char] for char, cnt in count]
-heapq.heapify(max_heap)
-while max_heap or prev
-if prev and not max_heap, return “”
-cnt, char = heappop
-answer += char
-cnt += 1
-if prev, then heappush(prev), prev = None
-if cnt < 0, prev = [cnt, char]
-end while
-return answer
Game of life
Idea:
To convert the board in place, we need to find a way to encode the current positions to use it and calculate next state
We will use following
Original | New | State(encoding)
0 | 0 | 0
1 | 0 | 1
0 | 1 | 2
1 | 1 | 3
Algorithm:
-define countNeighbours function with r and c params as follows
-declare neighbours = 0
-for i from r + 1 to r + 2
-for j from c + 1 to c + 2
-if (i == r and j == c) or i < 0 or j < 0 or i == rows or j == cols, continue
-if board[r][c] is 1 or 3, neighbours += 1
-end for
-end for
-return neighbours
-for all rows
-for all cols
-neighbours = countNeighbours(i, j)
-if board[i][j] == 1
-if neighbours is 2 or 3, board[i][j] = 3
-end if
-elif neighbours is 3, board[i][j] = 2
-for all rows
-for all cols
-if board[i][j] == 1, board[i][j] = 0
-elif board[i][j] is 2 or 3, board[i][j] = 1
Minesweeper
Idea:
For an empty square without any adjacent mines, we need to recursively call the function, i.e. simulate clicks on its neighbours
Algorithm:
-Define utility function numMines with board, x and y for params as follows
-num_mines = 0
-for r from x - 1 to x + 1
-for c from c - 1 to c + 1
-if in bounds and (r, c) is mine, inc num_mines
-end for
-end for
-return num_mines
-if not board, return board
-x, y = click
-if (x, y) is mine, assign ‘X’ to (x, y)
-else
-num_mines = numMines(board, x, y)
-if num_mines, assign str(num_mines) at (x, y)
-else
-assign ‘B’ to (x, y)
-for r from x - 1 to x + 1
-for c from y - 1 to y + 1
-if r and c in bounds and (r, c) not ‘B’, call self with board and [r, c] as params
-end for
-end for
-end if else
-end if else
-return board
Design tic-tac-toe
Idea:
One way, create a board, and then mark each position as ‘X’ or ‘O’. Then at every move, check the row, column and the diagonal in question.
Better way, assign -1 and 1 to two player moves, keep adding the move value to the corresponding row, column and diagonal, and if it ever becomes equal to n, we have the winner
Solution:
1. INIT
-declare rows and columns as defaultdict(int)
-declare left_diag, right_diag and n as 0,0 and n respectively
- MOVE
-number is -1 if player is player 1 else 1
-self.rows[row] += number
-self.columns[col] += number
-if row == col, self.left_diag += number
-if row + col == self.n - 1, self.right_diag += 1
-if max(abs(self.rows[row]), abs(self.columns[col]), abs(self.right_diag), abs(self.left_diag)) == self.n, return player
-return 0
Graph valid tree
Idea:
Recursive dfs to see if there are cycles. Maintain a visited array and check if its length equals n (To check if all nodes are connected)
Algorithm:
-if not n, return True (No nodes is also a graph)
-create adjacency list as adj = {i: [] for i in range(n)}
-fill in adjacency list
-declare visited set
-define dfs function with i and prev for params as follows
-if i in visited, return False
-add i to visited
-for every j in adj[i]
-if j == prev, continue
-if not dfs(j, i), return False
-end for
-return True
-return dfs(0, -1) AND n == len(visited)
Reverse bits
Idea:
-We use bitwise AND, bitwise OR and bitwise SHIFTS to extract each of the 31 bit and then reverse it
Algorithm:
-declare answer as 0
-for i till 31
-extract bit as bit = (n»_space; i) & 1
-push the bit to left and OR with answer as answer = answer | (bit «_space;(31 - i))
-end for
-return answer
Sum of two integers
- IN JAVA
Idea:
At the bit level, result of & is one only if one of the bits is 1. This can be done using ^. For the carry, we can use & and then left shift it once. Keep doing this until we don’t have a carry
Algorithm:
-while b is not 0
-int carry = (a & b) «_space;1
-a = a ^ b
-b = carry
-end while
-return a
Word break
Idea:
Bottom Up DP. We start with the end character, then one my one check if any word fits, and then store True in the cache at that position. Eventually, we will have the result at 0th position
Algorithm:
-Declare dp array with Falses for len(s) + 1
-Assign True to last position of dp cache
-for i from len(s) - 1 to 0
-for every word in wordDict
-if i + len(w) <= len(s) and s[i:i + len(w)] == w, dp[i] = dp[i + len(w)]
-if dp[i], break (break coz one word already fits the above condition)
-end for
-end for
-return dp[0]
Spiral matrix
Idea:
Fix the left right top and bottom boundaries, and then print in for loops while the left < right and top < bottom
Algorithm:
-declare empty answer array
-declare left and right as 0 and len(matrix[0])
-declare top and bottom as 0 and len(matrix)
-while left < right and top < bottom
-for i range (left, right), append [top][i] to answer
-top += 1
-for i range (top, bottom), append [i][right - 1] to answer
-right -= 1
-if not (left < right and top < bottom), break
-for i range (right - 1, left - 1, -1), append [bottom - 1][i] to answer
-bottom -= 1
-for i range (bottom - 1, top - 1, -1), append [i][left] to answer
-left += 1
-end while
-return answer
Number of connected components in an undirected graph
Idea:
Build an adjacency list and then run dfs through each node. Maintain a visited set to track the connected components
Algorithm:
-if n is 1, return 1
-declare answer as 0
-declare adjacency list as adj = {node: [] for node in range(n)}
-build adjacency list using edges both ways (n1->n2) and (n2->n1)
-declare empty visited set
-declare dfs function with node for param as follows
-for every neighbor of node
-if neighbor not in visited
-add neighbor to visited and call dfs(neighbor)
-end if
-end for
-end func
-for node in adjacency list
-if node not visited
-add node to visited
-inc num_components
-call dfs(node)
-end if
-end for
-return num_components
