CareerCup

  • Questions
  • Forum
  • Resume Tips
  • RSS
  • Sign In

Starup Interview Question for SDE-2s


Country: United States
Interview Type: In-Person



Comment hidden because of low score. Click to expand.
0
of 0 vote

public static void validateTuples(List<List<Character>> list){

Deque<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) + ")");
}
}
}

- kalyanchakri02 October 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}
}

}

- yankeson2013 October 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
		}
	}

}

- yankeson2013 October 17, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Ankita October 19, 2018 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

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')))

- Diana November 04, 2018 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)))

- Diana November 04, 2018 | Flag


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More