Thomson Reuters Interview Question Senior Software Development Engineers
Team: Legal
Country: United States
Interview Type: In-Person
public class Node {
boolean endFlag;
Node[] childrens;
boolean isPrefixWord;
char value;
boolean isRoot;
public Node(boolean isRoot, char value) {
childrens = new Node[26];
endFlag = false;
isPrefixWord = false;
this.isRoot = isRoot;
this.value = value;
}
}
public class filterStrings {
public static void main(String args[]) {
Node root = new Node(true,'/');
addWord("/flapp/server/apache", root);
addWord("/d/apps", root);
addWord("/d/apps/pub", root);
addWord("/flapp", root);
addWord("/flocal/firms", root);
addWord("/d/sw/java", root);
addWord("/d/sw/orcl/jdbc", root);
StringBuilder str = new StringBuilder("/");
printTrie(root, str);
}
public static void addWord(String str, Node root) {
char c;
for(int i = 0; i < str.length(); i++ ) {
c = str.charAt(i);
if(c == '/') {
root.isPrefixWord = true;
continue;
}
if(root.childrens[c-'a'] == null) {
root.childrens[c-'a'] = new Node(false,c);
}
root = root.childrens[c-'a'];
if(root.endFlag) {
break;
}
}
root.endFlag = true;
root.isPrefixWord = false;
for(int i =0; i < 26; i++) {
root.childrens[i] = null;
}
}
public static void printTrie(Node root, StringBuilder str) {
if(root.endFlag) {
System.out.println(str);
return;
}
for(int i = 0; i < 26; i++) {
if(root.childrens[i] != null) {
str.append(root.childrens[i].value);
if(root.childrens[i].isPrefixWord)
str.append("/");
printTrie(root.childrens[i], str);
str.deleteCharAt(str.length()-1);
if(root.childrens[i].isPrefixWord)
str.deleteCharAt(str.length()-1);
}
}
}
}
I would answer like this: It seems that each string represents a path. If there are two paths A and B such that B is a subdirectory of A the goal is to return only A. Now, how to implement: (i) All strings (paths) can be represented as a tire. (ii) Create a set of strings 'set'. Then,for each input string, flow the trie. Now, if you find a valid string along the path in the trie stop and add this string into the 'set', proceed the next input string.
The set finally contains only desired paths.
I look it like the smallest substrings are filtered out. It goes like this,
/flapp/server/apache and /flapp -> smallest substring /flapp
/d/apps and /d/apps/pub -> smallest substring /d/apps
/flocal/firms -> No substring
/d/sw/orcl/jdbc -> No substring
/d/sw/java -> No substring
So the resulting strings are
/flapp
/d/apps
/flocal/firms
/d/sw/java
/d/sw/orcl/jdbc
Rough solution in Java. Could definitely be cleaned up somewhat, but it works.
import java.util.ArrayList;
public class FilterDirectories {
public static class Directory {
private String name;
private ArrayList<Directory> subdirs;
public Directory(String name) {
this.name = name;
this.subdirs = new ArrayList<Directory>();
}
public void addSubDir(Directory subdir) {
subdirs.add(subdir);
}
public String getName() {
return name;
}
public ArrayList<Directory> getSubDirs() {
return subdirs;
}
public ArrayList<String> getSubDirNames() {
ArrayList<String> subdirNames = new ArrayList<String>();
for (Directory subdir : subdirs)
subdirNames.add(subdir.getName());
return subdirNames;
}
public Directory findSubDir(String name) {
for (Directory subdir : subdirs)
if (subdir.getName().equals(name)) return subdir;
return null;
}
public void removeSubDirs() {
subdirs.clear();
}
}
public static ArrayList<String> filterDirs(ArrayList<String> paths) {
Directory root = new Directory("root");
for (String path : paths) {
String[] dirs = path.split("/");
System.out.print("String lengths: ");
for (String dir : dirs) {
System.out.print(dir.length() + " ");
}
System.out.println();
insertIntoDirectoryTree(root, dirs, 1);
}
ArrayList<String> filteredDirs = new ArrayList<String>();
for (Directory subdir : root.getSubDirs())
addLeavesToList(subdir, filteredDirs, "");
return filteredDirs;
}
public static void addLeavesToList(Directory d, ArrayList<String> list, String prefix) {
if (d.getSubDirs().isEmpty())
list.add(prefix + "/" + d.getName());
else
for (Directory subdir : d.getSubDirs())
addLeavesToList(subdir, list, prefix + "/" + d.getName());
}
// String s = “/hello/world/foo/bar”
// s.split(“/”) → [“hello”, “world”, “foo”, “bar”]
public static void insertIntoDirectoryTree(Directory d, String[] dirs, int start) {
Directory subdir = d.findSubDir(dirs[start]);
if (subdir == null) {
// create a new Directory and add it as a subdirectory of d
subdir = new Directory(dirs[start]);
d.addSubDir(subdir);
if (start < dirs.length - 1)
insertIntoDirectoryTree(subdir, dirs, start+1);
} else {
if (start < dirs.length - 1)
insertIntoDirectoryTree(subdir, dirs, start+1);
else
subdir.removeSubDirs();
}
}
public static void main(String[] args) {
ArrayList<String> paths = new ArrayList<String>();
paths.add("/flapp");
paths.add("/flapp/server/apache");
paths.add("/d/apps");
paths.add("/d/apps/pub");
paths.add("/flapp");
paths.add("/flocal/firms");
paths.add("/d/sw/java");
paths.add("/d/sw/orcl/jdbc");
ArrayList<String> filteredDirs = filterDirs(paths);
for (String filteredDir : filteredDirs) {
System.out.println(filteredDir);
}
}
}
Rough solution in Java. Could definitely be cleaned up somewhat, but it works.
import java.util.ArrayList;
public class FilterDirectories {
public static class Directory {
private String name;
private ArrayList<Directory> subdirs;
public Directory(String name) {
this.name = name;
this.subdirs = new ArrayList<Directory>();
}
public void addSubDir(Directory subdir) {
subdirs.add(subdir);
}
public String getName() {
return name;
}
public ArrayList<Directory> getSubDirs() {
return subdirs;
}
public ArrayList<String> getSubDirNames() {
ArrayList<String> subdirNames = new ArrayList<String>();
for (Directory subdir : subdirs)
subdirNames.add(subdir.getName());
return subdirNames;
}
public Directory findSubDir(String name) {
for (Directory subdir : subdirs)
if (subdir.getName().equals(name)) return subdir;
return null;
}
public void removeSubDirs() {
subdirs.clear();
}
}
public static ArrayList<String> filterDirs(ArrayList<String> paths) {
Directory root = new Directory("root");
for (String path : paths) {
String[] dirs = path.split("/");
System.out.print("String lengths: ");
for (String dir : dirs) {
System.out.print(dir.length() + " ");
}
System.out.println();
insertIntoDirectoryTree(root, dirs, 1);
}
ArrayList<String> filteredDirs = new ArrayList<String>();
for (Directory subdir : root.getSubDirs())
addLeavesToList(subdir, filteredDirs, "");
return filteredDirs;
}
public static void addLeavesToList(Directory d, ArrayList<String> list, String prefix) {
if (d.getSubDirs().isEmpty())
list.add(prefix + "/" + d.getName());
else
for (Directory subdir : d.getSubDirs())
addLeavesToList(subdir, list, prefix + "/" + d.getName());
}
// String s = “/hello/world/foo/bar”
// s.split(“/”) → [“hello”, “world”, “foo”, “bar”]
public static void insertIntoDirectoryTree(Directory d, String[] dirs, int start) {
Directory subdir = d.findSubDir(dirs[start]);
if (subdir == null) {
// create a new Directory and add it as a subdirectory of d
subdir = new Directory(dirs[start]);
d.addSubDir(subdir);
if (start < dirs.length - 1)
insertIntoDirectoryTree(subdir, dirs, start+1);
} else {
if (start < dirs.length - 1)
insertIntoDirectoryTree(subdir, dirs, start+1);
else
subdir.removeSubDirs();
}
}
public static void main(String[] args) {
ArrayList<String> paths = new ArrayList<String>();
paths.add("/flapp");
paths.add("/flapp/server/apache");
paths.add("/d/apps");
paths.add("/d/apps/pub");
paths.add("/flapp");
paths.add("/flocal/firms");
paths.add("/d/sw/java");
paths.add("/d/sw/orcl/jdbc");
ArrayList<String> filteredDirs = filterDirs(paths);
for (String filteredDir : filteredDirs) {
System.out.println(filteredDir);
}
}
}
public static void main(String[] args) {
//Input String
String arr[] = {
"/flapp/server/apache",
"/d/apps",
"/d/apps/pub",
"/flapp",
"/flocal/firms",
"/d/sw/java",
"/d/sw/orcl/jdbc" };
//Converting String array to ListArray
List<String> ls = new LinkedList<String>();
for(int i = 0 ; i < arr.length; i++){
ls.add(arr[i]);
}
//Looping through the list (nlogn)
for (int i = 0; i < ls.size(); i++) {
for(int j = i+1; j < ls.size(); j++){
if( ls.get(i).contains(ls.get(j))){
ls.remove(i);
}
if(ls.get(j).contains(ls.get(i))){
ls.remove(j);
}
}
}
System.out.println(ls);
public static void main(String[] args) {
//Input String
String arr[] = {
"/flapp/server/apache",
"/d/apps",
"/d/apps/pub",
"/flapp",
"/flocal/firms",
"/d/sw/java",
"/d/sw/orcl/jdbc" };
//Converting String array to ListArray
List<String> ls = new LinkedList<String>();
for(int i = 0 ; i < arr.length; i++){
ls.add(arr[i]);
}
//Looping through the list (nlogn)
for (int i = 0; i < ls.size(); i++) {
for(int j = i+1; j < ls.size(); j++){
if( ls.get(i).contains(ls.get(j))){
ls.remove(i);
}
if(ls.get(j).contains(ls.get(i))){
ls.remove(j);
}
}
}
System.out.println(ls);
Not very efficient answer. But this should work.
public static Set<String> filterString(List<String> array){
Set<String> resultSet = new HashSet<String>();
Set<String> resultSet2 = new HashSet<String>();
for(int i =0; i < array.size(); i++){
for(int j = i+1; j < array.size(); j++ ){
if(array.get(i).contains(array.get(j))){
resultSet.add(array.get(j));
}else if (array.get(j).contains(array.get(i))){
resultSet.add(array.get(i));
}
}
}
boolean contains = false;
for(int i=0;i<array.size();i++){
for(String s : resultSet){
if(array.get(i).contains(s)){
contains = true;
break;
}else{
contains = false;
}
}
if(!contains){
resultSet2.add(array.get(i));
}
}
resultSet.addAll(resultSet2);
return resultSet;
}
static class TrieNode {
String nodeText;
boolean isLeaf;
HashMap<String, TrieNode> children = new HashMap<>();
public void addPath(String str) {
String[] split = str.split("/");
TrieNode toAdd = this;
TrieNode next;
for(String partPath: split) {
next = toAdd.children.get(partPath);
if(next == null) {
next = new TrieNode();
next.nodeText = partPath;
toAdd.children.put(partPath, next);
}
if(next.isLeaf)
return;
toAdd = next;
}
toAdd.isLeaf = true;
}
}
public List<String> compressPath(List<String> strings) {
TrieNode emptyParent = new TrieNode();
for (String str : strings) {
emptyParent.addPath(str.substring(1));
}
List<String> result = new ArrayList<>();
for(TrieNode parentNodes: emptyParent.children.values()) {
dfs(parentNodes, "", result);
}
return result;
}
private void dfs(TrieNode current, String s, List<String> result) {
s = s + "/" + current.nodeText;
if(current.isLeaf) {
result.add(s);
return;
}
for(TrieNode node: current.children.values()) {
dfs(node, s, result);
}
}
1. Add all strings to a trie. While adding them, if we encounter a word that is a prefix to another word, we remove the other word from the Trie. This is done by the following: when inserting the word, when we reach the last character of the end node of the word, and that node has a has children, then remove the children.
- Anonymous January 29, 20152. Iterate through the trie and print out all the end nodes.