Zoho Interview Question
SDE1sCountry: United States
Interview Type: Written Test
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <sstream>
#include <string>
using namespace std;
int findGrandChild()
{
string str;
vector<pair<string, string>> v = { {"xx","yy"},{"yy","zz"},{"dd","yy"},{"mm","jj"} };
cin >> str;
vector<string> xx;
int total = 0;
for_each(v.begin(), v.end(), [&xx, &str](pair<string, string>& p) { if (p.second == str) { xx.push_back(p.first); } });
for_each(v.begin(), v.end(), [&xx, &total](pair<string, string>& p) { if (find(xx.begin(), xx.end(), p.second) != xx.end()) { total++; } });
return total;
}
int main()
{
cout << findGrandChild() << endl;
return 0;
}
Here is a Python solution. The input format is the name of the person we want to inquire about on the first line followed by any number of lines each containing a "<son> <father>" pair.
person = input()
father_of = {}
father_son_pair = input().split()
while father_son_pair:
father_of[father_son_pair[0]] = father_son_pair[1]
father_son_pair = input().split()
num_grandchildren = 0
for son, father in father_of.items():
if person == father:
num_grandchildren += list(father_of.values()).count(son)
print(num_grandchildren)
//Time complexity:O(N) where N is the number of entries in the array. Space: O(N).
public int numGrandchildren(String[][] mat,String gf)
{
if(mat==null||mat.length==0||gf==null||gf.length()==0)
{
return 0;
}
HashMap<String,ArrayList<String>> mp=new HashMap<String,ArrayList<String>>();
for(int i=0;i<mat.length;i++)
{
String father=mat[i][1];
if(!mp.containsKey(father))
{
mp.put(father,new ArrayList<String>());
}
mp.get(father).put(mat[i][0]);
}
int num=0;
ArrayList<String> ls=mp.get(gf);//Iterate through child of grandfather.
for(String s:ls)
{
int k=mp.containsKey(s)?mp.get(s).size():0;//For each child count the number of children.
num+=k;
}
return num;
}
import java.util.*;
public class GrandChild {
public static void main(String[] args) {
// TODO Auto-generated method stub
String Dim[][] = {{"luke","wayne"},{"wayne","rooney"},{"rooney","ronaldo"},{"shaw","rooney"}};
String childRonaldo = "";
int count = 0;
//Sting childRonaldo;
Scanner in = new Scanner(System.in);
System.out.println("Enter Name");
String str = in.nextLine();
for (int i=0;i<Dim.length;i++)
{
// System.out.println("name entered: " + str);
if (Dim[i][1].equals(str))
{
//System.out.println(Dim[i][0]);
childRonaldo = Dim[i][0];
System.out.println("Child of " + str + " : " + childRonaldo);
break;
}
}
for (int k=0;k<Dim.length;k++)
{
if (Dim[k][1]== childRonaldo)
{
count++;
}
}
System.out.println("No: of Grand children " + str + " : " + count);
}
}
package CareerCup;
import java.util.ArrayList;
import java.util.HashMap;
/*
* Given a two dimensional array of string like
* <"luke", "shaw">
* <"wayne", "rooney">
* <"rooney", "ronaldo">
* <"shaw", "rooney">
*
* where the first string is "child" second string is "father".
* And given "ronaldo" we have to find his no of grandchildren. Here
* "ronaldo" has 2 grand children. So our output should be 2.
*/
public class GrandChildAlgo {
HashMap<String, ArrayList<String>> fatherSonMap = new HashMap<>();
public void constructFatherSonMap(String[][] famArray) {
for(int i = 0; i < famArray.length; i++) {
String father = famArray[i][1];
father = father.trim();
if(fatherSonMap.containsKey(father)) {
ArrayList<String> sonLst = fatherSonMap.get(father);
sonLst.add(famArray[i][0]);
} else {
ArrayList<String> sonList = new ArrayList<String>();
sonList.add(famArray[i][0]);
fatherSonMap.put(father, sonList);
}
}
System.out.println(fatherSonMap);
}
public void getGrandChildren( String gpName) {
ArrayList<String> gChildren = new ArrayList<>();
if (fatherSonMap.isEmpty()) {
System.out.println("Map is empty");
return;
}
ArrayList<String> children = fatherSonMap.get(gpName);
for(String child : children) {
gChildren.addAll(fatherSonMap.get(child));
}
System.out.println(gChildren);
}
public static void main(String[] args) {
String[][] familyArray = {
{"luke", "shaw"}, {"wayne", "rooney"}, {"rooney", "ronaldo"}, {"shaw", "rooney"}
};
GrandChildAlgo gcObj = new GrandChildAlgo();
gcObj.constructFatherSonMap(familyArray);
gcObj.getGrandChildren("ronaldo");
}
}
Create tree with the following where list has all immediate child.
public class tNode
{
public List<tNode> Children { get; set; }
public string Name { get; set; }
}
Insert with something like this:
Insert(tNode current, string parentName, string childName)
{
if (current == null) //do not insert if parent not found
return;
if(current.Name == parentName) //parent found, insert child here
{
current.Children.Add(new tNode(childName));
}
else
{
foreach(tNode child in current.Children)
{
Insert(child, parentName, childName);
}
}
}
Search children with this:
private List<tNode> GetChildren(tNode current, string parentName)
{
Queue<tNode> q = new Queue<tNode>();
if (current == null)
return null;
q.Enqueue(current);
while(q.Count != 0)
{
tNode tmp = q.Dequeue();
if (tmp.Name == parentName) //found
return tmp.Children;
else
{
foreach (tNode child in tmp.Children)
{
q.Enqueue(child);
}
}
}
Count all children under a parent with this:
public int CountNumberOfDescendents(string nodeName)
{
List<tNode> children = GetChildren(nodeName);
Queue<tNode> q = new Queue<tNode>();
int count = 0;
foreach(tNode child in children)
{
q.Enqueue(child);
count++;
}
while(q.Count != 0)
{
tNode tmp = q.Dequeue();
foreach(tNode child in tmp.Children)
{
q.Enqueue(child);
count++;
}
}
return count;
}
public int CountNumberOfDescendents(string nodeName)
{
List<tNode> children = GetChildren(nodeName);
Queue<tNode> q = new Queue<tNode>();
int count = 0;
foreach(tNode child in children)
{
q.Enqueue(child);
count++;
}
while(q.Count != 0)
{
tNode tmp = q.Dequeue();
foreach(tNode child in tmp.Children)
{
q.Enqueue(child);
count++;
}
}
return count;
}
Create tree with parent child relationship.
Node class something like this:
public class tNode
{
public List<tNode> Children { get; set; }
public string Name { get; set; }
Insert something like this:
Insert(tNode current, string parentName, string childName)
{
if (current == null) //do not insert if parent not found
return;
if(current.Name == parentName) //parent found, insert child here
{
current.Children.Add(new tNode(childName));
}
else
{
foreach(tNode child in current.Children)
{
Insert(child, parentName, childName);
}
}
Search something like this:
List<tNode> GetChildren(tNode current, string parentName)
{
Queue<tNode> q = new Queue<tNode>();
if (current == null)
return null;
q.Enqueue(current);
while(q.Count != 0)
{
tNode tmp = q.Dequeue();
if (tmp.Name == parentName) //found
return tmp.Children;
else
{
foreach (tNode child in tmp.Children)
{
q.Enqueue(child);
}
}
}
return null;
}
Count all children under a node like this:
public int CountNumberOfDescendents(string nodeName)
{
List<tNode> children = GetChildren(nodeName);
Queue<tNode> q = new Queue<tNode>();
int count = 0;
foreach(tNode child in children)
{
q.Enqueue(child);
count++;
}
while(q.Count != 0)
{
tNode tmp = q.Dequeue();
foreach(tNode child in tmp.Children)
{
q.Enqueue(child);
count++;
}
}
return count;
}
children_father_rel = [['luke', 'show'], ['wayne', 'rooney'], ['rooney', 'ronaldo'], ['shaw', 'rooney']]
child_input_key = []
def find_father_position(input_key):
"""
Find the input key in the two dimension array
:param: inputKey: input key which need to be find
:return: None
"""
for first_indx, rel_arr in get_each_rel():
if get_input_indx(input_key, first_indx):
return first_indx
return None
def get_input_indx(input_key, first_indx):
"""
Get the indx input key in children_father_rel
:param: input_key: input key which need to be find
:param: first_indx: first index of the multidimention array
:param: second_indx: second index of the multidemention array
:return: return True if match neither False
"""
return True if input_key in children_father_rel[first_indx] else False
def get_each_rel():
"""
Get each father and children relation
:param: None
:return: None
"""
first_indx = 0
for children_father in children_father_rel:
yield (first_indx, children_father)
first_indx += 1
def find_number_of_childs(input_key):
"""
Find number of childs in the 2d array
:param: input_key: input_key or father as input
:return: return the number of childs
"""
while find_father_position(input_key):
child_indx = find_father_position(input_key)
if children_father_rel[child_indx][0] in child_input_key:
break
child_input_key.append(children_father_rel[child_indx][0])
input_key = children_father_rel[child_indx][0]
return child_input_key
if __name__ == '__main__':
input_key = 'ronaldo'
find_number_of_childs(input_key)
print child_input_key
import java.util.ArrayList;
import java.util.HashMap;
class GrandChildCount{
//To recurse the method only once
int flag=0;
int findGrandChildCount(String[][] arr, String father){
String child = "";
HashMap<String,String> childFatherMap = new HashMap<String,String>();
int arrLen = arr.length;
for(int i=0; i<arrLen; i++){
if(arr[i][1] == father){
childFatherMap.put(arr[i][0],father);
child = arr[i][0];
}
}
//To recurse the method only once
if(flag==0){
flag++;
return findGrandChildCount(arr,child);
}
return childFatherMap.size();
}
}
public class R_02_S_001_04_GrandChildCount_Practice_05 {
public static void main(String[] args){
String[][] strArr = {{"luke", "shaw"},{"wayne", "rooney"},{"rooney", "ronaldo"},{"shaw", "rooney"}};
GrandChildCount obj = new GrandChildCount();
String fatherName = "ronaldo";
String childName = "";
int grandChildCount = obj.findGrandChildCount(strArr,fatherName);
System.out.println("Grand Children count for "+fatherName+" is "+grandChildCount);
}
}
import java.util.ArrayList;
import java.util.HashMap;
class GrandChildCount{
//To recurse the method only once
int flag=0;
int findGrandChildCount(String[][] arr, String father){
String child = "";
HashMap<String,String> childFatherMap = new HashMap<String,String>();
int arrLen = arr.length;
for(int i=0; i<arrLen; i++){
if(arr[i][1] == father){
childFatherMap.put(arr[i][0],father);
child = arr[i][0];
}
}
//To recurse the method only once
if(flag==0){
flag++;
return findGrandChildCount(arr,child);
}
return childFatherMap.size();
}
}
public class R_02_S_001_04_GrandChildCount_Practice_05 {
public static void main(String[] args){
String[][] strArr = {{"luke", "shaw"},{"wayne", "rooney"},{"rooney", "ronaldo"},{"shaw", "rooney"}};
GrandChildCount obj = new GrandChildCount();
String fatherName = "ronaldo";
String childName = "";
int grandChildCount = obj.findGrandChildCount(strArr,fatherName);
System.out.println("Grand Children count for "+fatherName+" is "+grandChildCount);
}
}
class GrandChildCount{
//To recurse the method only once
int flag=0;
int findGrandChildCount(String[][] arr, String father){
String child = "";
HashMap<String,String> childFatherMap = new HashMap<String,String>();
int arrLen = arr.length;
for(int i=0; i<arrLen; i++){
if(arr[i][1] == father){
childFatherMap.put(arr[i][0],father);
child = arr[i][0];
}
}
//To recurse the method only once
if(flag==0){
flag++;
return findGrandChildCount(arr,child);
}
return childFatherMap.size();
}
}
public class R_02_S_001_04_GrandChildCount_Practice_05 {
public static void main(String[] args){
String[][] strArr = {{"luke", "shaw"},{"wayne", "rooney"},{"rooney", "ronaldo"},{"shaw", "rooney"}};
GrandChildCount obj = new GrandChildCount();
String fatherName = "ronaldo";
String childName = "";
int grandChildCount = obj.findGrandChildCount(strArr,fatherName);
System.out.println("Grand Children count for "+fatherName+" is "+grandChildCount);
}
} }}}
class GrandChildCount{
//To recurse the method only once
int flag=0;
int findGrandChildCount(String[][] arr, String father){
String child = "";
HashMap<String,String> childFatherMap = new HashMap<String,String>();
int arrLen = arr.length;
for(int i=0; i<arrLen; i++){
if(arr[i][1] == father){
childFatherMap.put(arr[i][0],father);
child = arr[i][0];
}
}
//To recurse the method only once
if(flag==0){
flag++;
return findGrandChildCount(arr,child);
}
return childFatherMap.size();
}
}
public class R_02_S_001_04_GrandChildCount_Practice_05 {
public static void main(String[] args){
String[][] strArr = {{"luke", "shaw"},{"wayne", "rooney"},{"rooney", "ronaldo"},{"shaw", "rooney"}};
GrandChildCount obj = new GrandChildCount();
String fatherName = "ronaldo";
String childName = "";
int grandChildCount = obj.findGrandChildCount(strArr,fatherName);
System.out.println("Grand Children count for "+fatherName+" is "+grandChildCount);
}
}
class GrandChildCount{
//To recurse the method only once
int flag=0;
int findGrandChildCount(String[][] arr, String father){
String child = "";
HashMap<String,String> childFatherMap = new HashMap<String,String>();
int arrLen = arr.length;
for(int i=0; i<arrLen; i++){
if(arr[i][1] == father){
childFatherMap.put(arr[i][0],father);
child = arr[i][0];
}
}
//To recurse the method only once
if(flag==0){
flag++;
return findGrandChildCount(arr,child);
}
return childFatherMap.size();
}
}
public class R_02_S_001_04_GrandChildCount_Practice_05 {
public static void main(String[] args){
String[][] strArr = {{"luke", "shaw"},{"wayne", "rooney"},{"rooney", "ronaldo"},{"shaw", "rooney"}};
GrandChildCount obj = new GrandChildCount();
String fatherName = "ronaldo";
String childName = "";
int grandChildCount = obj.findGrandChildCount(strArr,fatherName);
System.out.println("Grand Children count for "+fatherName+" is "+grandChildCount);
}
}
class GrandChildCount{
//To recurse the method only once
int flag=0;
int findGrandChildCount(String[][] arr, String father){
String child = "";
HashMap<String,String> childFatherMap = new HashMap<String,String>();
int arrLen = arr.length;
for(int i=0; i<arrLen; i++){
if(arr[i][1] == father){
childFatherMap.put(arr[i][0],father);
child = arr[i][0];
}
}
//To recurse the method only once
if(flag==0){
flag++;
return findGrandChildCount(arr,child);
}
return childFatherMap.size();
}
}
public class R_02_S_001_04_GrandChildCount_Practice_05 {
public static void main(String[] args){
String[][] strArr = {{"luke", "shaw"},{"wayne", "rooney"},{"rooney", "ronaldo"},{"shaw", "rooney"}};
GrandChildCount obj = new GrandChildCount();
String fatherName = "ronaldo";
String childName = "";
int grandChildCount = obj.findGrandChildCount(strArr,fatherName);
System.out.println("Grand Children count for "+fatherName+" is "+grandChildCount);
}
}
class GrandChildCount{
//To recurse the method only once
int flag=0;
int findGrandChildCount(String[][] arr, String father){
String child = "";
HashMap<String,String> childFatherMap = new HashMap<String,String>();
int arrLen = arr.length;
for(int i=0; i<arrLen; i++){
if(arr[i][1] == father){
childFatherMap.put(arr[i][0],father);
child = arr[i][0];
}
}
//To recurse the method only once
if(flag==0){
flag++;
return findGrandChildCount(arr,child);
}
return childFatherMap.size();
}
}
public class R_02_S_001_04_GrandChildCount_Practice_05 {
public static void main(String[] args){
String[][] strArr = {{"luke", "shaw"},{"wayne", "rooney"},{"rooney", "ronaldo"},{"shaw", "rooney"}};
GrandChildCount obj = new GrandChildCount();
String fatherName = "ronaldo";
String childName = "";
int grandChildCount = obj.findGrandChildCount(strArr,fatherName);
System.out.println("Grand Children count for "+fatherName+" is "+grandChildCount);
}
}
Here is a Python solution. The input format is the name of the person we want to inquire about on the first line followed by any number of lines each containing a "<son> <father>" pair.
- craig burgler June 23, 2016