Position: L3
Location: MTV
Given a DOM as a tree e.g <p> this <i> is </i> text</p> and a text (e.g. istext). Return the nodes that make up the given text.
So the tree would look like:
public List<Node> getNodes(Node root, String searchText) {
// your code goes here
}My Solution using Java
class Node {
String text;
List<Node> children
}
class Word {
int start;
int end;
}I recursed through the nodes and created a string using the stringbuilder. I then used a hashmap to store the start and end of the given text in a HashMap. Then I used a sliding window to match the searchText to the stringbuilder. If there was a match then I did a 2 pointer approach starting from the beginning of the matched string and check in my HashMap for a word using start and end and added it to the List
public List<Node> getNodes(Node root, String searchText) {
StringBuilder sb = new StringBuilder();
HashSet<Word> map = new HashMap<>();
buildString(root, sb, map);
// at this point sb ="thisistext"
// map = {{0,5},{5,7},{7,11}} -> forgive indice mismatch but the general idea is correct
// do sliding window to match searchText against sb
int i = 0;
for (i; i < sb.length() - searchText.length(); i++) {
if (sb.substring(i, searchText.length()).equals(searchText)) {
break;
}
}
int start = i;
int end = i + 1;
List<Node> res = new ArrayList<>();
while (start <= end && end < searchText.length()) {
Word curr = new Word(start, end);
if (map.contains(curr) {
res.add(map.get(curr));
start = end;
continue;
}
end++;
}
return res;
}
public void buildString(Node root, StringBuilder sb, HashSet<Word> map) {
if (root == null) return;
if (root.text != null) {
map.put(new Word(sb.length(), sb.length() + root.text.length());
sb.append(root.text);
}
for (Node child : root.children()) {
buildString(child, sb, map);
}
}I said that the alg would run in O(n) where n is number of nodes and the string matching/two pointer approach would run in O(m). They seemed happy with this solution.