A trie (pronounced as “try”) or prefix tree is a tree data structure used to efficiently store and retrieve keys in a dataset of strings. There are various applications of this data structure, such as autocomplete and spellchecker.
Implement the Trie class:
Trie() Initializes the trie object.
void insert(String word) Inserts the string word into the trie.
boolean search(String word) Returns true if the string word is in the trie (i.e., was inserted before), and false otherwise.
boolean startsWith(String prefix) Returns true if there is a previously inserted string word that has the prefix prefix, and false otherwise.
Init: class TrieNode {
TrieNode[] children = new TrieNode[26];
boolean wordEnds = false;
}
TrieNode root;
public Trie() {
root = new TrieNode();
}Insert: public void insert(String word) {
TrieNode currentNode = root;
for(int index=0; index<word.length(); index++) {
char c = word.charAt(index);
if (currentNode.children[c-‘a’]==null) {
currentNode.children[c-‘a’] = new TrieNode();
}
currentNode = currentNode.children[c-‘a’];
}
currentNode.wordEnds = true;
}
Search: public boolean search(String word) {
TrieNode currentNode = root;
for(int index=0; index<word.length(); index++) {
char c = word.charAt(index);
if (currentNode.children[c-‘a’] == null)
return false;
currentNode = currentNode.children[c-‘a’];
}
return currentNode.wordEnds;
}
for prefix its same as search except return true at the end
Kth Smallest Element in a BST
Given the root of a binary search tree, and an integer k, return the kth smallest value (1-indexed) of all the values of the nodes in the tree.
Do in-order traversal, stop at the kth node processed and return it’s value
TreeNode currentNode = root;
Stack<TreeNode> stack = new Stack<>();
int number = 0;
while(!stack.isEmpty() || currentNode != null) {
while(currentNode != null) {
stack.push(currentNode);
currentNode = currentNode.left;
}
currentNode = stack.pop();
number++;
if (number == k)
return currentNode.val;
currentNode = currentNode.right;
}
return -1;Subtree of Another Tree
Given the roots of two binary trees root and subRoot, return true if there is a subtree of root with the same structure and node values of subRoot and false otherwise.
A subtree of a binary tree tree is a tree that consists of a node in tree and all of this node’s descendants. The tree tree could also be considered as a subtree of itself.
Helper function for two nodes being same:
private boolean sameNode(TreeNode node1, TreeNode node2) {
if (node1 == null && node2 == null) return true;
if (node1 == null || node2 == null) return false;
if (node1.val != node2.val) return false;
return sameNode(node1.left, node2.left) && sameNode(node1.right, node2.right);
}
Use this with DFS to find if it is a subtree.
if (root == null) return false;
if (sameNode(root, subRoot)) return true;
return isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);O(nodes in tree * nodes in the subRoot) time complexity
Reconstruct itinerary
You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it.
All of the tickets belong to a man who departs from “JFK”, thus, the itinerary must begin with “JFK”. If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string.
For example, the itinerary [“JFK”, “LGA”] has a smaller lexical order than [“JFK”, “LGB”].
You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.
Input: tickets = [[“JFK”,”SFO”],[“JFK”,”ATL”],[“SFO”,”ATL”],[“ATL”,”JFK”],[“ATL”,”SFO”]]
Output: [“JFK”,”ATL”,”JFK”,”SFO”,”ATL”,”SFO”]
Explanation: Another possible reconstruction is [“JFK”,”SFO”,”ATL”,”JFK”,”ATL”,”SFO”] but it is larger in lexical order.
Eulerian circuit: path along the graph that uses one edge exactly once
Construct a graph but use a priority queue to hold next edges so we process them in lexicographic order.
public List<String> findItinerary(List<List<String>> tickets) {
Map<String, PriorityQueue<String>> adj = new HashMap<>();
for (List<String> ticket : tickets) {
String src = ticket.get(0);
String dst = ticket.get(1);
adj.computeIfAbsent(src, k -> new PriorityQueue<>()).offer(dst);
}
List<String> res = new ArrayList<>();
dfs(adj, "JFK", res);
Collections.reverse(res);
return res;
}
private void dfs(Map<String, PriorityQueue<String>> adj,
String src, List<String> res) {
PriorityQueue<String> queue = adj.get(src);
while (queue != null && !queue.isEmpty()) {
String dst = queue.poll();
dfs(adj, dst, res);
}
res.add(src);
}Open the Lock
You have a lock in front of you with 4 circular wheels. Each wheel has 10 slots: ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’. The wheels can rotate freely and wrap around: for example we can turn ‘9’ to be ‘0’, or ‘0’ to be ‘9’. Each move consists of turning one wheel one slot.
The lock initially starts at ‘0000’, a string representing the state of the 4 wheels.
You are given a list of deadends dead ends, meaning if the lock displays any of these codes, the wheels of the lock will stop turning and you will be unable to open it.
Given a target representing the value of the wheels that will unlock the lock, return the minimum total number of turns required to open the lock, or -1 if it is impossible.
Input: deadends = [“0201”,”0101”,”0102”,”1212”,”2002”], target = “0202”
Output: 6
Explanation:
A sequence of valid moves would be “0000” -> “1000” -> “1100” -> “1200” -> “1201” -> “1202” -> “0202”.
Note that a sequence like “0000” -> “0001” -> “0002” -> “0102” -> “0202” would be invalid,
because the wheels of the lock become stuck after the display becomes the dead end “0102”.
Use a BFS and don’t add any dead ends to the queue.
At every step, turn each number in the string up and down and add to the queue.
Set<String> dead = new HashSet<>();
for(String end: deadends)
dead.add(end);
if (dead.contains("0000")) return -1;
Queue<Pair<String, Integer>> queue = new LinkedList<>();
queue.add(new Pair<>("0000", 0));
dead.add("0000");
while(!queue.isEmpty()) {
String state = queue.peek().getKey();
Integer turns = queue.poll().getValue();
if (state.equals(target))
return turns;
char[] currentState = state.toCharArray();
for(int index=0; index < currentState.length; index++) {
char current = currentState[index];
int nextChar = (int)(current-'0'+1)%10; //move to next digit fowards
currentState[index] = (char)(nextChar+'0');
String nextState = new String(currentState);
if (!dead.contains(nextState)) {
queue.add(new Pair<>(nextState, turns+1));
dead.add(nextState);
}
currentState[index] = current;
nextChar = (int)(current-'0'+9)%10; //move to next digit backwards
currentState[index] = (char)(nextChar+'0');
nextState = new String(currentState);
if (!dead.contains(nextState)) {
queue.add(new Pair<>(nextState, turns+1));
dead.add(nextState);
}
currentState[index] = current;
}
}
return -1;Concatenated Words
Given an array of strings words (without duplicates), return all the concatenated words in the given list of words.
A concatenated word is defined as a string that is comprised entirely of at least two shorter words (not necessarily distinct) in the given array.
Input: words = [“cat”,”cats”,”catsdogcats”,”dog”,”dogcatsdog”,”hippopotamuses”,”rat”,”ratcatdogcat”]
Output: [“catsdogcats”,”dogcatsdog”,”ratcatdogcat”]
Explanation: “catsdogcats” can be concatenated by “cats”, “dog” and “cats”;
“dogcatsdog” can be concatenated by “dog”, “cats” and “dog”;
“ratcatdogcat” can be concatenated by “rat”, “cat”, “dog” and “cat”.
- sort words by length to ensure all building blocks for concatenated words potentially exist
- if a word cannot be created by concatenating existing words, then add it to the trie (memoization)
- else add it to result
checking if concatenation can be done:
private boolean isConcatenated(String word, int index) {
if (index >= word.length())
return true;
TrieNode currentNode = root;
//if there is a word at index i, then recursively call this from next index
for(int i=index; i<word.length(); i++) {
char c = word.charAt(i);
if (currentNode.children[c-'a'] == null) return false;
currentNode = currentNode.children[c-'a'];
if (currentNode.wordEndsHere && isConcatenated(word, i+1))
return true;
}
return false;call this with every word and index 0 to begin with.
If there are N words and M is the average length of the word:
sorting takes O(N log N) time, making a trie worst case takes O(NM) time and the recursive isConcatenated can take: O(N * M^2) , so time complexity is: O(N * M^2)
Space complexity is O(N*M)
Binary Tree Cameras
You are given the root of a binary tree. We install cameras on the tree nodes where each camera at a node can monitor its parent, itself, and its immediate children.
Return the minimum number of cameras needed to monitor all nodes of the tree.
Input: root = [0,0,null,0,null,0,null,null,0]
Output: 2
At every node, the choice is to either place a camera or not.
Define three states:
1. Node has a camera on it -> then we can choose any state for it’s children
2. Node has no camera and is monitored by one or more children -> at least one child must have a camera
3. Node doesn’t have camera and is not monitored by any child -> then the children have to be monitored by their children
Final answer -> minimum number needed by either placing a camera at the root or not
DFS function will recurse and return three values:
new int[]{min if node has camera, min if node has no camera and is monitored, min if node is not monitored}
Have:
private int[] search(TreeNode node) {
if (node == null)
// {cannot have camera, needs no monitoring, needs no monitoring}
return new int[]{1<<29, 0, 0};
int[] leftResult = search(node.left);
int[] rightResult = search(node.right);
//state 1: current node has camera ->
//then kids can be in any state as this can monitor them anyway
int withCamera = 1 + getMin(leftResult, rightResult);
//state 2: node has no camera and one of it's children monitors it ->
//so at least one of the kids needs to have a camera in it
int withoutCameraButMonitored = Math.min(leftResult[0]+rightResult[0], Math.min(
leftResult[1]+rightResult[0], leftResult[0]+rightResult[1]
));
//state 3: currentNode is unmonitored ->
//so children don't have a camera but we need to make sure they are monitored
int withoutMonitoring = leftResult[1] + rightResult[1];
return new int[]{withCamera, withoutCameraButMonitored, withoutMonitoring};
}Call it:
int[] result = search(root);
return Math.min(result[0], result[1]);
