Starup Interview Question
SDE-2sCountry: United States
Interview Type: In-Person
public class BiaryTreeValidator {
public static void main(String[] args) {
String[][] inTuples= {{"a", "b"}, {"b","c"},{"a","d"},{"c","e"}, {"e", "a"}};
Map<String, Node> map = new HashMap<>(); //create map from name to node
Set<String> children = new HashSet<>(); //create set for child nodes
boolean valid = true;
for(int i=0; i<inTuples.length; i++) {
String pName = inTuples[i][0];
String cName = inTuples[i][1];
Node pNode = map.get(pName);
if(pNode==null) {
pNode = new Node(pName);
map.put(pName, pNode);
}
Node cNode = map.get(cName);
if(cNode==null) {
cNode = new Node(cName);
map.put(cName, cNode);
}
if(pNode.getLeft()!=null && pNode.getRight()!=null) {
System.out.println(pName+" already has 2 children, so cannot add "+cName);
valid = false;
}else {
if(pNode.getLeft()!=null) {
if(pNode.getLeft().getName().equals(cName)) {
System.out.println(cName + " already exists in "+pName);
valid=false;
}else {
if(isCycled(pNode, cName)) {
System.out.println("cycled");
valid = false;
}else {
pNode.setRight(cNode);
cNode.setParent(pNode);
children.add(cName);
}
}
}else if(pNode.getRight()!=null) {
if(pNode.getRight().getName().equals(cName)) {
System.out.println(cName + " already exists in "+pName);
valid = false;
}else {
if(isCycled(pNode, cName)) {
System.out.println("cycled");
valid = false;
}else {
pNode.setLeft(cNode);
cNode.setParent(pNode);
children.add(cName);
}
}
}else {
if(isCycled(pNode, cName)) {
System.out.println("cycled");
valid = false;
}else {
pNode.setLeft(cNode);
cNode.setParent(pNode);
children.add(cName);
}
}
}
}
//remove all child nodes from map.
Iterator<String> itr1 = children.iterator();
while(itr1.hasNext()) {
String cName = itr1.next();
map.remove(cName);
}
if(map.size()>=2) {
System.out.println("Has more roots than expected.");
valid = false;
}
if(valid) {
Set<String> keys = map.keySet();
Iterator<String> itrX = keys.iterator();
while(itrX.hasNext()) {
Node root = map.get(itrX.next());
System.out.println(printNodes(root).toString());
}
}
}
static boolean isCycled(Node n, String cName) {
if(n==null) return false;
if(n.getName().equals(cName)) return true;
return isCycled(n.getParent(), cName);
}
static StringBuffer printNodes(Node root) {
StringBuffer sb = new StringBuffer();
if(root != null) {
sb.append("(").append(root.getName());
if(root.getLeft()!=null) sb.append(printNodes(root.getLeft()));
if(root.getRight()!=null) sb.append(printNodes(root.getRight()));
}
sb.append(")");
return sb;
}
static class Node{
private String name;
private Node parent;
private Node left;
private Node right;
public Node(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
}
public class BiaryTreeValidator {
public static void main(String[] args) {
String[][] inTuples= {{"a", "b"}, {"b","c"},{"a","d"},{"c","e"}, {"e", "a"}};
Map<String, Node> map = new HashMap<>(); //create map from name to node
Set<String> children = new HashSet<>(); //create set for child nodes
boolean valid = true;
for(int i=0; i<inTuples.length; i++) {
String pName = inTuples[i][0];
String cName = inTuples[i][1];
Node pNode = map.get(pName);
if(pNode==null) {
pNode = new Node(pName);
map.put(pName, pNode);
}
Node cNode = map.get(cName);
if(cNode==null) {
cNode = new Node(cName);
map.put(cName, cNode);
}
if(pNode.getLeft()!=null && pNode.getRight()!=null) {
System.out.println(pName+" already has 2 children, so cannot add "+cName);
valid = false;
}else {
if(pNode.getLeft()!=null) {
if(pNode.getLeft().getName().equals(cName)) {
System.out.println(cName + " already exists in "+pName);
valid=false;
}else {
if(isCycled(pNode, cName)) {
System.out.println("cycled");
valid = false;
}else {
pNode.setRight(cNode);
cNode.setParent(pNode);
children.add(cName);
}
}
}else if(pNode.getRight()!=null) {
if(pNode.getRight().getName().equals(cName)) {
System.out.println(cName + " already exists in "+pName);
valid = false;
}else {
if(isCycled(pNode, cName)) {
System.out.println("cycled");
valid = false;
}else {
pNode.setLeft(cNode);
cNode.setParent(pNode);
children.add(cName);
}
}
}else {
if(isCycled(pNode, cName)) {
System.out.println("cycled");
valid = false;
}else {
pNode.setLeft(cNode);
cNode.setParent(pNode);
children.add(cName);
}
}
}
}
//remove all child nodes from map.
Iterator<String> itr1 = children.iterator();
while(itr1.hasNext()) {
String cName = itr1.next();
map.remove(cName);
}
if(map.size()>=2) {
System.out.println("Has more roots than expected.");
valid = false;
}
if(valid) {
Set<String> keys = map.keySet();
Iterator<String> itrX = keys.iterator();
while(itrX.hasNext()) {
Node root = map.get(itrX.next());
System.out.println(printNodes(root).toString());
}
}
}
static boolean isCycled(Node n, String cName) {
if(n==null) return false;
if(n.getName().equals(cName)) return true;
return isCycled(n.getParent(), cName);
}
static StringBuffer printNodes(Node root) {
StringBuffer sb = new StringBuffer();
if(root != null) {
sb.append("(").append(root.getName());
if(root.getLeft()!=null) sb.append(printNodes(root.getLeft()));
if(root.getRight()!=null) sb.append(printNodes(root.getRight()));
}
sb.append(")");
return sb;
}
static class Node{
private String name;
private Node parent;
private Node left;
private Node right;
public Node(String name) {
this.name = name;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public Node getParent() {
return parent;
}
public void setParent(Node parent) {
this.parent = parent;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
}
}
Thank you for such awesome solution.
If I am not wrong,the time complexity of finding cycle will be O(nlogn) as for each child node it traverses upwards and in worst case O(n^2)..
I was thinking of using graph(DFS) to solve this:
- while adding edges (addEdge(a,b)), I will check two conditions ,whether it already has 2 child nodes and if the the tuple is duplicate
- after this ,DFS of graph to check if there is a cycle, whose time complexity will be O(no of vertices)
But I am not able to check the last condition : finding more than one root.
Any suggestions here how to do that?
Thanks again
def trace(*args):
traceOn = False
if traceOn:
print(*args)
class DataTree:
def __init__(self, comment, *hords):
self._parents = {} # key - parent, value - list of tuples
self._children = {} # key - children, values - its parent
self._faults = []
print("\nDataTree: " + comment + " :: " + str(hords))
for h in hords:
trace(str(h[0]) + "->" + str(h))
p = h[0]
c = h[1]
if p not in self._parents:
self._parents[p] = []
if h in self._parents[p]:
self._faults.append("duplicate: " + str(h))
continue
other_children = self._parents[p]
if len(self._parents[p]) >=2:
self._faults.append("too many children: %u for %s: %s"%(len(other_children)+1, p, str(other_children+list(h))))
continue
if c in self._children:
self._faults.append("more than 1 root for %s. New is %s, but it already has parent %s"%(c, p, str(self._children[c])))
continue
self._children[c] = p
tmp_p = p
cycle = [c]
while tmp_p in self._children:
cycle.append(tmp_p)
if tmp_p == c:
self._faults.append("cycle detected: " + "->".join([str(e) for e in cycle]))
del self._children[c]
break
tmp_p = self._children[tmp_p]
if cycle[0] == cycle[-1] and len(cycle) > 1:
continue
self._parents[p].append(h)
if len(self._faults) > 0:
self._parents = {k: v for k,v in self._parents.items() if len(v) > 0}
def __str__(self):
print("Tree : " + str(self._parents) + "\n" + ("ok" if not self._faults else "NOK: " + "\n"+"\n".join(self._faults)) )
roots = [p for p,c in self._parents.items() if p not in self._children]
res = ["("]
it = 0
trace("roots: " + str(roots))
for root in roots:
tmp_p = root
prev = None
res.append(str(tmp_p))
while tmp_p:
it += 1
if it > 1000:
print("Stop, it=%u"%it)
break
children = self._parents.get(tmp_p)
up = self._children.get(tmp_p, None)
if not children:
left = None
right = None
else:
left = children[0][1] if len(children) > 0 else None
right = children[1][1] if len(children) > 1 else None
trace("print: " + str(tmp_p) + "->" + str(children) + " L=" + str(left) + " R=" + str(right) + " U=" + str(up))
if prev == up or prev == None:
prev = tmp_p
if left:
trace("go left")
tmp_p = left
res.append("(" + str(tmp_p))
else:
trace("go up")
res.append(")")
tmp_p = up
elif prev == left:
prev = tmp_p
if right:
trace("go right")
tmp_p = right
res.append("(" + str(tmp_p))
else:
trace("go up")
res.append(")")
tmp_p = up
elif prev == right:
trace("go up")
prev = tmp_p
res.append(")")
tmp_p = up
return "".join(res)
print(DataTree("ok", (1,2), (2,3)))
print(DataTree("duplicates", (1,2), (1,2)))
print(DataTree("many children", (1,2), (1,3), (1,4), (2,6)))
print(DataTree("more than 1 root", (1,2), (1,4), (5,2)))
print(DataTree("cycle", (1,2), (2,3), (3,1)))
print(DataTree("independent trees", (1,2), (2,3), ('A','B'), ('B','C')))
print(DataTree("joined late", (1,2), (2,3), ('A','B'), ('B','C'), (3,'A')))
print(DataTree("joined with cycle", (1,2), (2,3), ('A','B'), ('B','C'), (3,'A'),('A',1)))
print(DataTree("mix", ('A',2), ('B',5), ('A',2), (6,5), (2,3), ('B',2), (2,7), (7,8), (7,9), (5,'f'), (5,'g')))
Output is:
DataTree: ok :: ((1, 2), (2, 3))
ok
(1(2(3)))
DataTree: duplicates :: ((1, 2), (1, 2))
NOK:
duplicate: (1, 2)
(1(2))
DataTree: many children :: ((1, 2), (1, 3), (1, 4), (2, 6))
NOK:
too many children: 3 for 1: [(1, 2), (1, 3), 1, 4]
(1(2(6))(3))
DataTree: more than 1 root :: ((1, 2), (1, 4), (5, 2))
NOK:
more than 1 root for 2. New is 5, but it already has parent 1
(1(2)(4))
DataTree: cycle :: ((1, 2), (2, 3), (3, 1))
NOK:
cycle detected: 1->3->2->1
(1(2(3)))
DataTree: independent trees :: ((1, 2), (2, 3), ('A', 'B'), ('B', 'C'))
ok
(1(2(3)))A(B(C)))
DataTree: joined late :: ((1, 2), (2, 3), ('A', 'B'), ('B', 'C'), (3, 'A'))
ok
(1(2(3(A(B(C))))))
DataTree: joined with cycle :: ((1, 2), (2, 3), ('A', 'B'), ('B', 'C'), (3, 'A'), ('A', 1))
NOK:
cycle detected: 1->A->3->2->1
(1(2(3(A(B(C))))))
DataTree: mix :: (('A', 2), ('B', 5), ('A', 2), (6, 5), (2, 3), ('B', 2), (2, 7), (7, 8), (7, 9), (5, 'f'), (5, 'g'))
NOK:
duplicate: ('A', 2)
more than 1 root for 5. New is 6, but it already has parent B
more than 1 root for 2. New is B, but it already has parent A
(A(2(3)(7(8)(9))))B(5(f)(g)))
public static void validateTuples(List<List<Character>> list){
- kalyanchakri02 October 17, 2018Deque<Character> deque = new LinkedList<>();
for(Character c : list.get(0)){
deque.add(c);
}
for(int i=1;i<list.size();i++){
List<Character> l = list.get(i);
if(l.get(0)==deque.getFirst()){
deque.addFirst(l.get(1));
}else if(l.get(0)==deque.getLast()){
deque.addLast(l.get(1));
}else{
System.out.println("Invalid Tuple ("+ l.get(0) + "" +l.get(1) + ")");
}
}
}