Google Interview Question for Software Engineers


Country: United States
Interview Type: Phone Interview




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

public class DeleteTreeNode {

    private static class TreeNode {
        int val;
        TreeNode[] child;
        
        public String toString() {
            StringBuilder sb = new StringBuilder();
            
            sb.append("(").append(val);
            if (child != null) {
                for (TreeNode childd: child) {
                    if (childd == null) continue;
                    
                    // otherwise
                    sb.append(childd.toString());
                }
            }
            sb.append(")");
            
            return sb.toString();
        }
    }
    
    public static void main(String[] args) {
        TreeNode t10 = new TreeNode(); t10.val = 10;
        TreeNode t9 = new TreeNode(); t9.val = 9; t9.child = new TreeNode[] { t10 };
        TreeNode t8 = new TreeNode(); t8.val = 8;
        TreeNode t7 = new TreeNode(); t7.val = 7;
        
        TreeNode t6 = new TreeNode(); t6.val = 6; t6.child = new TreeNode[] { t9 };
        TreeNode t5 = new TreeNode(); t5.val = 5; t5.child = new TreeNode[] { t7, t8 };
        
        TreeNode t4 = new TreeNode(); t4.val = 4; t4.child = new TreeNode[] { t5, t6 };        
        TreeNode t3 = new TreeNode(); t3.val = 3;
        TreeNode t2 = new TreeNode(); t2.val = 2;
        
        TreeNode t1 = new TreeNode(); t1.val = 1; t1.child = new TreeNode[] { t2, t3, t4 };

        HashSet<TreeNode> set = new HashSet<TreeNode>();
        set.add(t4); set.add(t5); set.add(t9);
        
        System.out.println(delete(t1, set));
    }
    
    private static List<TreeNode> delete(TreeNode root, HashSet<TreeNode> set) {

        List<TreeNode> result = new LinkedList<TreeNode>();

        if (set == null || set.isEmpty()) {
            result.add(root);
            return result;
        }

        // otherwise
        doDelete(root, set, result, true);
        
        return result;
    }
     
    private static TreeNode doDelete(TreeNode root, HashSet<TreeNode> set, List<TreeNode> result, boolean isOrphan) {
            
        boolean childrenAreOrphans = false;

        childrenAreOrphans = set.remove(root);
        if (isOrphan && !childrenAreOrphans) result.add(root);        
            
        if (!childrenAreOrphans && set.isEmpty()) return root;
        
        // otherwise
        if (root.child != null) {
            for (int i = 0; i < root.child.length; i++) {
                root.child[i] = doDelete(root.child[i], set, result, childrenAreOrphans);
            }
        }
        
        return childrenAreOrphans? null: root;
    }
}

- PR December 10, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

In ZoomBA, this is how you write it :

def TreeNode : { 
  val : null , // value 
  child : list() // list of children 
}

def find_parents( cur, nodes , map ){
  // check if cur.child and nodes has intersection ?
  children = cur.child & nodes 
  if ( !empty( children ) ){
    // append to the map : key -> child, value -> parent 
    map |= dict( children ) -> { [ $.o , cur ] }
    nodes -= children // remove parented children 
  } 
  for ( child : cur.child ){
    find_parents ( child, nodes, )
  }
}

def delete( root , nodes ){
  parents = dict()
  // populate parents 
  find_parents ( root, nodes, parents )
  // populated now 
  for ( pair : parents ){
    // remove the child 
    pair.value.child -= pair.key
    // re-parent childs children into parent  
    pair.value.child += pair.key.child 
  }
}

- NoOne December 09, 2016 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

/** Time complexity is O(n) */

import java.util.*;

class TNode {
    int val;
    ArrayList<TNode> childList;

    public TNode(int val, ArrayList<TNode> arrayList) {
        this.val = val;
        this.childList = arrayList;
    }
}

public class DeleteOperationInNArray {

    private static TNode construct() {
        TNode node = new TNode(Integer.MAX_VALUE, new ArrayList<TNode>());
        node.childList.add(new TNode(20, new ArrayList<TNode>()));

        TNode n = new TNode(30, new ArrayList<TNode>());
        TNode n1 = new TNode(15, null);
        n.childList.add(n1);

        n1 = new TNode(5, null);
        n.childList.add(n1);
        n1 = new TNode(6, null);
        n.childList.add(n1);
        node.childList.get(0).childList.add(n);

        n = new TNode(40, new ArrayList<TNode>());

        n1 = new TNode(7, null);
        n.childList.add(n1);
        n1 = new TNode(8, null);
        n.childList.add(n1);
        n1 = new TNode(9, null);
        n.childList.add(n1);

        node.childList.get(0).childList.add(n);

        n = new TNode(50, new ArrayList<TNode>());
        n1 = new TNode(20, null);
        n.childList.add(n1);
        n1 = new TNode(6, null);
        n.childList.add(n1);
        n1 = new TNode(8, null);
        n.childList.add(n1);

        node.childList.get(0).childList.add(n);

        return node;
    }

    private static void delete(TNode head, int val, ArrayList<TNode> result) {
        ArrayList<TNode> list = head.childList;
        if (list != null) {
            for (int i = 0; i < list.size(); i++) {
                TNode node = list.get(i);
                if (node.val == val) {
                    if (node.childList != null && !node.childList.isEmpty()) {
                        head.childList.addAll(node.childList);
                    }
                    result.add(node);
                    head.childList.remove(i);
                } else {
                    delete(node, val, result);
                }
            }
        }

    }

    public static void main(String[] args) {
        TNode head = construct();
        
        int val = 20;// element to be deleted
        
        ArrayList<TNode> result = new ArrayList<TNode>();// holds the result
        delete(head, val, result);
        
        for (TNode node : result) {
            System.out.print(node.val + " ");
        }
    }

}

- hcr January 01, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class DeleteTreeNode {

private static class TreeNode {
int val;
TreeNode[] child;

/*ublic String toString() {
StringBuilder sb = new StringBuilder();

sb.append("(").append(val);
if (child != null) {
for (TreeNode childd: child) {
if (childd == null) continue;

// otherwise
sb.append(childd.toString());
}
}
sb.append(")");

return sb.toString();
// }*/
}

public static void main(String[] args) {
TreeNode t10 = new TreeNode(); t10.val = 10;
TreeNode t9 = new TreeNode(); t9.val = 9; t9.child = new TreeNode[] { t10 };
TreeNode t8 = new TreeNode(); t8.val = 8;
TreeNode t7 = new TreeNode(); t7.val = 7;

TreeNode t6 = new TreeNode(); t6.val = 6; t6.child = new TreeNode[] { t9 };
TreeNode t5 = new TreeNode(); t5.val = 5; t5.child = new TreeNode[] { t7, t8 };

TreeNode t4 = new TreeNode(); t4.val = 4; t4.child = new TreeNode[] { t5, t6 };
TreeNode t3 = new TreeNode(); t3.val = 3;
TreeNode t2 = new TreeNode(); t2.val = 2;

TreeNode t1 = new TreeNode(); t1.val = 1; t1.child = new TreeNode[] { t2, t3, t4 };

HashSet<TreeNode> set = new HashSet<TreeNode>();
set.add(t4); set.add(t5); set.add(t9);

System.out.println(delete(t1, set));
}

private static List<TreeNode> delete(TreeNode root, HashSet<TreeNode> set) {

List<TreeNode> result = new LinkedList<TreeNode>();

if (set == null || set.isEmpty()) {
result.add(root);
return result;
}

// otherwise
return doDelete(root, set, result);


}

private static List<TreeNode> doDelete(TreeNode root, HashSet<TreeNode> set, List<TreeNode> result) {



if(root.child==null){

return result;
}
if(set.isEmpty()) return result;

else{

for(int i=0; i<root.child.length; i++) {

TreeNode childd= root.child[i];
if(childd!=null && set.contains(childd)){

result.add(root);

//TreeNode t = new TreeNode();
//t.child=childd.child;
int k=0;

int length= root.child.length;
for(int p=i; p<childd.child.length; p++){
root.child[length] =root.child[p+1];
length++;

}
root.child[i]=childd.child[0];
for(int z=i+1; z<childd.child.length; z++){

root.child[z]=childd.child[k];
k++;

}


// root.child=ArrayUtils.removeElement(root.child, childd);
int x=i;

set.remove(childd);
doDelete( root.child[x].child[0] , set , result);


}

else{ doDelete( root.child[i], set , result);


}

}
return result;
}

}

}

- sai January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import java.util.*;

public class DeleteTreeNode {

    private static class TreeNode {
        int val;
        TreeNode[] child;
        
        /*ublic String toString() {
            StringBuilder sb = new StringBuilder();
            
            sb.append("(").append(val);
            if (child != null) {
                for (TreeNode childd: child) {
                    if (childd == null) continue;
                    
                    // otherwise
                    sb.append(childd.toString());
                }
            }
            sb.append(")");
            
            return sb.toString();
       // }*/
    }
    
    public static void main(String[] args) {
        TreeNode t10 = new TreeNode(); t10.val = 10;
        TreeNode t9 = new TreeNode(); t9.val = 9; t9.child = new TreeNode[] { t10 };
        TreeNode t8 = new TreeNode(); t8.val = 8;
        TreeNode t7 = new TreeNode(); t7.val = 7;
        
        TreeNode t6 = new TreeNode(); t6.val = 6; t6.child = new TreeNode[] { t9 };
        TreeNode t5 = new TreeNode(); t5.val = 5; t5.child = new TreeNode[] { t7, t8 };
        
        TreeNode t4 = new TreeNode(); t4.val = 4; t4.child = new TreeNode[] { t5, t6 };        
        TreeNode t3 = new TreeNode(); t3.val = 3;
        TreeNode t2 = new TreeNode(); t2.val = 2;
        
        TreeNode t1 = new TreeNode(); t1.val = 1; t1.child = new TreeNode[] { t2, t3, t4 };

        HashSet<TreeNode> set = new HashSet<TreeNode>();
        set.add(t4); set.add(t5); set.add(t9);
        
        System.out.println(delete(t1, set));
    }
    
    private static List<TreeNode> delete(TreeNode root, HashSet<TreeNode> set) {

        List<TreeNode> result = new LinkedList<TreeNode>();

        if (set == null || set.isEmpty()) {
            result.add(root);
            return result;
        }

        // otherwise
     return    doDelete(root, set, result);
        
       
    }
     
    private static List<TreeNode> doDelete(TreeNode root, HashSet<TreeNode> set, List<TreeNode> result) {
            
            
        
        if(root.child==null){
            
            return result;
        }
        if(set.isEmpty()) return result;
        
        else{
            
           for(int i=0; i<root.child.length; i++) {
               
              TreeNode childd= root.child[i];
               if(childd!=null && set.contains(childd)){
                   
                   result.add(root);
                   
                   //TreeNode t = new TreeNode();
                   //t.child=childd.child;
                  int k=0;
                  
                int length= root.child.length;
                  for(int p=i; p<childd.child.length; p++){
                     root.child[length] =root.child[p+1];
                      length++;
                      
                  }
                  root.child[i]=childd.child[0];
                   for(int z=i+1; z<childd.child.length; z++){
                       
                      root.child[z]=childd.child[k];
                      k++;
                       
                   }
                  
               
           // root.child=ArrayUtils.removeElement(root.child, childd); 
                int x=i;
                 
                 set.remove(childd);
                doDelete( root.child[x].child[0] , set , result);
                
                   
               }
               
              else{  doDelete( root.child[i], set , result);
               
               
           }
            
           } 
         return result;  
        }  
       
}     
        
}

- sai January 17, 2017 | Flag Reply
Comment hidden because of low score. Click to expand.
-1
of 1 vote

//Time Complexity: O(n^2) where n is the number of nodes in the tree. Space complexity: O(n)
 //Modified your Node class as I couldn't figure out how to accomodate deleting a single node with the structure that was given.
private class TreeNode{
	int val;
	List<TreeNode> child;
	
	private TreeNode(int v){
		val = v;
	}

}
//Assumption: List of nodes returned should be the root node (if it's not one of the deletion candidates) otherwise the children of the root node.
 private List<TreeNode> delete(TreeNode rt, HashSet<TreeNode> set){
	if(rt == null || set == null || set.isEmpty()){
		throw new IllegalArgumentException();
	}
	List<TreeNode> result = new ArrayList<TreeNode>();

	for(TreeNode n: set){
		if(n == rt){
			result.addAll(rt.child);
			return result;
		}
		boolean result = deleteNode(rt,n);
		if(!result){
			throw new IllegalArgumentException();//if target node isn't present in the tree.
		}
	}
	result.add(rt);
	return result;
 }
 private boolean deleteNode(TreeNode rt, TreeNode t){
 
	int targetIdx = -1;
	for(int i = 0; i < rt.child; i++){
		if(rt.get(i) == t){
			targetIdx = i;
			break;
		}
	}
	if(targetIdx != -1){
		rt.child.remove (targetIdx);
		rt.child.addAll(t.child);
		return true;
	}else{
	
		for(TreeNode n: rt.child){
			boolean r = deleteNode(n,t);
			if(r){
				return true;
			}
		}
		return false;
	}	
}

- divm01986 December 09, 2016 | Flag Reply


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