- Introductions (10 mins)
- Tell me about the most difficult production issue you faced and how you solved it. (10 mins)
- validate binary search tree -> done with coding in 5 mins
- given a dictionary of words, find all words having matching prefix
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class Dictionary {
TrieNode root;
public Dictionary() {
this.root = new TrieNode('\0');
}
public void add(String word) {
TrieNode current = root;
for (int i = 0; i < word.length(); i++) {
Character key = word.charAt(i);
if (root.next.containsKey(key)) {
current = root.next.get(key);
} else {
TrieNode newNode = new TrieNode(key);
root.next.put(key, newNode); // mistake -> should have been current
current = newNode;
}
}
current.isEnd = true;
current.word = word;
}
public List<String> queryPrefix(String prefix) {
List<String> res = new ArrayList<>();
TrieNode current = root;
for (int i = 0; i < prefix.length(); i++) {
Character key = prefix.charAt(i);
if (root.next.containsKey(key)) {
current = root.next.get(key); // mistake -> should have been current
}
if (current.isEnd) {
res.add(current.word);
}
}
dfs(current, res);
return res;
}
public void dfs(TrieNode root, List<String> res) {
if (root == null)
return;
if (root.isEnd) {
res.add(root.word);
}
for (Map.Entry<Character, TrieNode> entry : root.next.entrySet()) {
dfs(entry.getValue(), res);
}
}
}
public class Solution {
public static void main(String[] args) {
Dictionary dict = new Dictionary();
dict.add("abcdef");
dict.add("abcijk");
System.out.println(dict.queryPrefix("abc"));
}
}
// represents a dictionary
// method 1 -> add a word to dictionary (a-z)
// method 2 -> query method list of all the words that match with the given prefix
class TrieNode {
Character c;
HashMap<Character, TrieNode> next;
String word;
boolean isEnd;
public TrieNode(Character c) {
this.c = c;
this.next = new HashMap<>();
this.isEnd = false;
}
}Verdict : Rejected
Is the job market so brutal that even 2 lines of code cant be incorrect ?
Comments (7)


