Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
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
}
}
/** 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 + " ");
}
}
}
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;
}
}
}
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;
}
}
}
//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;
}
}
- PR December 10, 2016