Google Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
def find_ceo(company_struct):
except_ceo = set()
for manager in company_struct:
team = company_struct[manager]
except_ceo |= set(team)
for manager in company_struct:
if manager not in except_ceo:
return manager
def print_team(company_struct, manager=None, depth=0):
if not manager:
manager = find_ceo(company_struct)
print " "*depth + "-" + manager
if manager in company_struct:
for mates in company_struct[manager]:
print_team(company_struct, mates, depth + 1)
print_team(mgmt)
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedHashMap;
import java.util.List;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class Indent {
private static String sep = "->";
private static String data = "{AAA->BBB,CCC,EEE},{CCC->DDD},{XXX->YYY,ZZZ},{DDD->TTT,OOO}";
private static String res = "";
public static void main(String[] args) {
// TODO Auto-generated method stub
List<String> st = indent(data);
recIndentArr(st);
System.out.println(res);
}
public static String repNTimes(String s, int n) {
String rep = "";
for (int i = 0; i < n; i++) {
rep += s;
}
return rep;
}
public static void recIndent(String s) {
String prRes = repNTimes(" ", ind.get(s)) + "-" + s + "\n";
res += prRes;
if (!children.containsKey(s))
return;
List<String> m = children.get(s);
for (String ch: m) {
recIndent(ch);
}
}
public static void recIndentArr(List<String> s) {
for (String sub: s) {
recIndent(sub);
}
}
private static Map<String, List<String>> children = new LinkedHashMap<String, List<String>>();
private static Map<String, Integer> ind = new LinkedHashMap<String, Integer>();
public static List<String> indent(String pat) {
Pattern p = Pattern.compile("\\{.*?\\}");
Matcher mat = p.matcher(pat);
List<String> l = new ArrayList<>();
while (mat.find()) {
l.add(mat.group(0));
}
for (int i = 0; i < l.size(); i++) {
String s = l.get(i).replaceAll("[\\{\\}]", "");
String key = s.split(sep)[0];
String[] vals = s.split(sep)[1].split(",");
if (!ind.containsKey(key)) {
ind.put(key, 0);
}
for (int j = 0; j < vals.length; j++) {
ind.put(vals[j], ind.get(key) + 1);
}
children.put(key, Arrays.asList(vals));
}
List<String> stInds = new ArrayList<>();
for (Map.Entry<String, Integer> me: ind.entrySet()) {
if (me.getValue() == 0) {
stInds.add(me.getKey());
}
}
return stInds;
}
}
var data = {
'AAA': ['BBB', 'CCC', 'EEE'],
'CCC': ['DDD'],
}
function rootManagers (data) {
var subordinates = {}
for (var manager in data) {
if (({}).hasOwnProperty.call(data, manager)) {
data[manager].sort()
for (var i = 0; i < data[manager].length; ++i) {
subordinates[data[manager][i]] = true
}
}
}
var rootLevelManagers = []
for (manager in data) {
if (({}).hasOwnProperty.call(data, manager)) {
if (!subordinates[manager]) {
rootLevelManagers.push(manager)
}
}
}
return rootLevelManagers.sort()
}
//console.log(rootManagers(data))
function print(employee, data, level) {
var A = []
A[level] = '-'
A.push(employee)
A = A.join(' ')
console.log(A)
var subordinates = data[employee]
if (!subordinates) {
return
}
for (var i = 0; i < subordinates.length; ++i) {
print(subordinates[i], data, level + 1)
}
}
function employeeList (data) {
var rootLevelManagers = rootManagers(data)
for (var i = 0; i < rootLevelManagers.length; ++i) {
print(rootLevelManagers[i], data, 0)
}
}
employeeList(data)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
public class ManagerExp {
static void printHierarchy(Node node, String space) {
if(node == null) return;
System.out.println(space+""+node.name);
if(node.list != null) {
for (Node node1 : node.list) {
printHierarchy(node1, space+"-");
}
}
}
static class Node {
String name;
List<Node> list = new ArrayList();
Node(String name) {
this.name = name;
}
}
public static void main(String... args) {
List<Node> all = new ArrayList();
Node n = new Node("Manager1");
Node joe = new Node("Joe");
Node tom = new Node("Tom");
n.list.add(joe);
n.list.add(tom);
all.add(n);
Node linda = new Node("Linda");
Node potter = new Node("Potter");
joe.list.add(linda);
tom.list.add(potter);
Node harry = new Node("Harry");
linda.list.add(harry);
for(Node t : all) {
printHierarchy(t, "-");
}
}
}
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import com.google.common.collect.Lists;
public class CareerCup {
private static Map<String, Integer> managerSpaceMap = new HashMap<>();
public static void printStructure(
Map<String, List<String>> managerEmployeeMap) {
for (Map.Entry<String, List<String>> entry : managerEmployeeMap
.entrySet()) {
String manager = entry.getKey();
if (!managerSpaceMap.containsKey(manager)) {
if (managerSpaceMap.isEmpty()
|| !managerSpaceMap.containsKey(manager)) {
managerSpaceMap.put(manager, 0);
}
printHierarchy(manager, managerSpaceMap.get(manager));
for (String employee : entry.getValue()) {
printHierarchy(employee, managerSpaceMap.get(manager) + 1);
if (isManager(managerEmployeeMap, employee)) {
managerSpaceMap.put(employee,
managerSpaceMap.get(manager) + 1);
handleManager(managerEmployeeMap, employee);
}
}
}
}
}
private static void handleManager(
Map<String, List<String>> managerEmployeeMap, String manager) {
for (String emp : managerEmployeeMap.get(manager)) {
printHierarchy(emp, managerSpaceMap.get(manager) + 1);
if (isManager(managerEmployeeMap, emp)) {
managerSpaceMap.put(emp, managerSpaceMap.get(manager) + 1);
handleManager(managerEmployeeMap, emp);
}
}
}
private static boolean isManager(
Map<String, List<String>> managerEmployeeMap, String employee) {
return managerEmployeeMap.containsKey(employee);
}
private static void printHierarchy(String employee, int spacing) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < spacing; i++) {
sb.append(" ");
}
sb.append("-");
System.out.println(sb.toString() + employee);
}
public static void main(String[] args) {
Map<String, List<String>> map = new HashMap<>();
map.put("AAA", Lists.newArrayList("BBB", "CCC", "EEE"));
map.put("CCC", Lists.newArrayList("DDD"));
map.put("XXX", Lists.newArrayList("YYY", "ZZZ"));
map.put("DDD", Lists.newArrayList("TTT", "OOO"));
map.put("TTT", Lists.newArrayList("MMM", "NNN", "XXX"));
map.put("FFF", Lists.newArrayList("JJJ", "KKK"));
printStructure(map);
}
}
Maybe not the most elenagant, btu short and easy sollution
#include <iostream>
#include <map>
#include <vector>
#include <string>
#include <algorithm>
#define INDENT_CHAR "\t"
using namespace std;
string FindRoot(map <string, vector<string> > input);
void PrintTree(const string root, map <string, vector<string> > input, const string indent);
int main (int argc, char* argv[]){
map <string, vector<string> > input;
vector <string> temp;
temp.push_back("FFF");
temp.push_back("GGG");
input.insert(pair<string, vector<string> > ("DDD", temp));
temp.erase(temp.begin(), temp.end());
temp.push_back("BBB");
temp.push_back("CCC");
temp.push_back("EEE");
input.insert(pair<string, vector<string> > ("AAA", temp));
temp.erase(temp.begin(), temp.end());
temp.push_back("DDD");
input.insert(pair<string, vector<string> > ("CCC", temp));
temp.erase(temp.begin(), temp.end());
temp.push_back("B11");
temp.push_back("B12");
input.insert(pair<string, vector<string> > ("BBB", temp));
string root = FindRoot(input);
if (root != "") PrintTree(root, input,"");
else cout<<"Empty employee list!"<<endl;
}
string FindRoot(map <string, vector<string> > input){
if (input.size() == 0) return "";
map <string, vector<string> >:: iterator it = input.begin();
string root =it->first; it++;
while (it != input.end()){
if (find(it->second.begin(), it->second.end(), root) != it->second.end()) root = it->first;
it++;
}
return root;
}
void PrintTree(const string root, map <string, vector<string> > input, const string indent ){
cout<<indent<<root<<endl;
map <string, vector<string> >::iterator it = input.find(root);
if (it == input.end()) return;
for (int i=0; i < it->second.size(); i++) PrintTree(it->second[i], input, indent+INDENT_CHAR);
}
Solution Using Graph(since no loops, so essentially, its a tree) and DFS:
from pythonds.graphs import Graph, Vertex
def buildGraph(D):
org = Graph()
for key in D.keys():
f = key
for i in range(len(D[key])):
#print(f+'->'+D[key][i])
org.addEdge(f,D[key][i],1)
#print(list(org.getVertex(f).getConnections()))
return org
def print_org(g,u,offset):
#dfs
u = g.getVertex(u)
u.setColor('gray')
space = ' '*offset
print(space+'-'+u.id)
nbrs = list(u.getConnections())
#print(nbrs)
#print(':'+str(len(nbrs))+'employee')
if len(nbrs)==0:
pass
#print('-None')
else:
i = 0
while i<len(nbrs):
print_org(g,nbrs[i].id,offset+1)
i = i+1
u.setColor('black')
return
def main():
D = {
'AAA':['CCC','BBB','EEE'],
'CCC':['DDD']
}
root = 'AAA'
offset = 0
org = buildGraph(D)
print_org(org,root,offset)
if __name__=='__main__':
main()
public static void printCompanyStructure() {
Map<String, List<String>> companyMap = new HashMap<String, List<String>>() {{
put("AAA", new LinkedList<String>() {{add("BBB"); add("CCC"); add("EEE");}});
put("CCC", new LinkedList<String>() {{add("DDD");}});
}};
Set<String> roots = new HashSet<>();
List<String> nodeOrder = new LinkedList<>();
for(Map.Entry<String, List<String>> entry : companyMap.entrySet()) {
roots.add(entry.getKey());
for(String child : entry.getValue()) {
printCompanyStructure(companyMap, child, roots);
}
}
Set<String> hasPrinted = new HashSet<String>();
for(String root : roots) {
printNode(root, 0, companyMap, hasPrinted);
}
}
public static void printNode(
String node, int indentLevel, Map<String, List<String>> companyMap, Set<String> hasPrinted) {
if(hasPrinted.contains(node))
return;
StringBuilder sb = new StringBuilder();
for(int i = 0; i < indentLevel; i++) {
sb.append(" ");
}
sb.append(node);
System.out.println(sb.toString());
hasPrinted.add(node);
if(companyMap.containsKey(node)) {
for(String child : companyMap.get(node)) {
printNode(child, indentLevel + 1, companyMap, hasPrinted);
}
}
}
public static void printCompanyStructure(
Map<String, List<String>> companyMap, String currNode, Set<String> roots) {
if(roots.contains(currNode)) {
roots.remove(currNode);
}
if(companyMap.containsKey(currNode)) {
for(String child : companyMap.get(currNode)) {
printCompanyStructure(companyMap, child, roots);
}
}
}
public static void main(String[] args) {
printCompanyStructure();
}
Java solution.
First find the root..
Then construct the tree.
Print the tree in hierarcy order.
Assumed no cycles.
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
public class Employee {
private HashMap<Character,String> hm;
class TreeNode
{
private char val;
private List<TreeNode> next;
public TreeNode(char val)
{
this.val = val;
next = new ArrayList<TreeNode>();
}
}
public TreeNode buildTree(char root)
{
//create root node
TreeNode t = new TreeNode(root);
String s = hm.get(root);
if(s == null)return t;
for(int i=0;i<s.length();i++)
{
TreeNode next = buildTree(s.charAt(i));
t.next.add(next);
}
return t;
}
public void printTree(TreeNode root,String prefix)
{
if(root == null)return;
if(prefix=="")
System.out.println(root.val);
else
System.out.println(prefix+"=>"+root.val);
if(root.next.size() == 0)
{
//System.out.print(root.val);
return;
}
// System.out.print(" =>");
for(int i=0;i<root.next.size();i++)
printTree(root.next.get(i),prefix+" ");
}
public void solve(char root)
{
for(HashMap.Entry<Character, String> e: hm.entrySet())
{
char k = e.getKey();
String s = e.getValue();
}
}
public char findRoot()
{
HashSet<Character> hs = new HashSet<Character>();
for(Character c: hm.keySet())
{
hs.add(c);
}
for(String s:hm.values())
{
for(int i=0;i<s.length();i++)
{
char c =s.charAt(i);
if(hs.contains(c))
hs.remove(c);
}
}
char root='#';
for(char c:hs)
{
root = c;
}
return root;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Employee e = new Employee();
e.hm = new HashMap<Character,String>();
// e.hm.put('B',"F");
// e.hm.put('C',"DE");
// e.hm.put('A', "BC");
e.hm.put('A',"BCE");
e.hm.put('C',"D");
char root = e.findRoot();
if(root =='#')
{
System.out.println("Error.Root not found\n");
return;
}
else
{
System.out.println("root is : "+root);
}
e.solve(root);
TreeNode r = e.buildTree(root);
e.printTree(r,"");
}
}
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
public class Employee {
private HashMap<Character,String> hm;
class TreeNode
{
private char val;
private List<TreeNode> next;
public TreeNode(char val)
{
this.val = val;
next = new ArrayList<TreeNode>();
}
}
public TreeNode buildTree(char root)
{
//create root node
TreeNode t = new TreeNode(root);
String s = hm.get(root);
if(s == null)return t;
for(int i=0;i<s.length();i++)
{
TreeNode next = buildTree(s.charAt(i));
t.next.add(next);
}
return t;
}
public void printTree(TreeNode root,String prefix)
{
if(root == null)return;
if(prefix=="")
System.out.println(root.val);
else
System.out.println(prefix+"=>"+root.val);
if(root.next.size() == 0)
{
//System.out.print(root.val);
return;
}
// System.out.print(" =>");
for(int i=0;i<root.next.size();i++)
printTree(root.next.get(i),prefix+" ");
}
public void solve(char root)
{
for(HashMap.Entry<Character, String> e: hm.entrySet())
{
char k = e.getKey();
String s = e.getValue();
}
}
public char findRoot()
{
HashSet<Character> hs = new HashSet<Character>();
for(Character c: hm.keySet())
{
hs.add(c);
}
for(String s:hm.values())
{
for(int i=0;i<s.length();i++)
{
char c =s.charAt(i);
if(hs.contains(c))
hs.remove(c);
}
}
char root='#';
for(char c:hs)
{
root = c;
}
return root;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
Employee e = new Employee();
e.hm = new HashMap<Character,String>();
// e.hm.put('B',"F");
// e.hm.put('C',"DE");
// e.hm.put('A', "BC");
e.hm.put('A',"BCE");
e.hm.put('C',"D");
char root = e.findRoot();
if(root =='#')
{
System.out.println("Error.Root not found\n");
return;
}
else
{
System.out.println("root is : "+root);
}
e.solve(root);
TreeNode r = e.buildTree(root);
e.printTree(r,"");
}
}
How about several CEOs ?
package main
import (
"fmt"
"log"
)
func inArray(s string, m []string) bool {
for _, e := range m {
if e == s {
return true
}
}
return false
}
func findCEOs(s map[string][]string) []string {
notCEO := []string{}
CEOs := []string{}
for e := range s {
for _, empl := range s[e] {
notCEO = append(notCEO, empl)
}
}
for e := range s {
if !inArray(e, notCEO) {
CEOs = append(CEOs, e)
}
}
return CEOs
}
func _printStruct(s map[string][]string, CEO string, space string) {
fmt.Println(space + "-" + CEO)
_, ok := s[CEO]
if ok {
for _, e := range s[CEO] {
_printStruct(s, e, space + " ")
}
}
}
func printStruct(s map[string][]string) {
CEOs := findCEOs(s)
if len(CEOs) == 0 {
log.Fatalln("Not CEOs")
}
for _, CEO := range CEOs {
_printStruct(s, CEO, "")
}
}
func main() {
empl := make(map[string][]string)
empl["AAA"] = []string{"BBB", "CCC", "DDD"}
empl["CCC"] = []string{"EEE"}
empl["RRR"] = []string{"FFF"}
printStruct(empl)
}
1. First find the root of all - this could be one or more.
2. Use recursive call to simply print the child.
public static void printParentChild(Map<String, List<String>> map) {
Set<String> keys = map.keySet();
Set<String> stringKeys = new HashSet<>();
for (String str : keys)
stringKeys.add(str);
for (String str : keys) {
List<String> list = map.get(str);
for (String string : list) {
if (stringKeys.contains(string))
stringKeys.remove(string);
}
}
printParentChild(stringKeys, map, 0);
}
private static String getBlank (int num) {
StringBuilder sb = new StringBuilder("");
while (num--!=0)
sb.append(" ");
return sb.toString();
}
private static void printParentChild(Set<String> stringKeys, Map<String, List<String>> map, Integer numBlanks) {
if (stringKeys.isEmpty()) {
return;
}
for (String str : stringKeys) {
System.out.println(getBlank(numBlanks) + str);
if (map.get(str) != null) {
Set<String> foo = new HashSet<String>(map.get(str));
printParentChild(foo, map, ++numBlanks);
--numBlanks;
}
}
}
public void printMap(HashMap<String,List<String>> manEmp){
Set<String> keys = manEmp.keySet();
Set<String>printedKes=new HashSet<String>();
for(String key: keys){
if(!printedKes.contains(key)){
String level ="";
printedKes.addAll(printNestMap(manEmp,key,level));
}
}
}
private Set<String> printNestMap(HashMap<String,List<String>>manEmp, String man, String level){
Set<String>printedKes=new HashSet<String>();
System.out.println(level+"-"+man);
if(manEmp.containsKey(man)){
List<String> nestEmp= manEmp.get(man);
printedKes.add(man);
level+=" ";
for(int i=0;i<nestEmp.size();i++){
printedKes.addAll(printNestMap(manEmp,nestEmp.get(i),level));
}
}
return printedKes;
}
import java.util.*;
class companystructure{
public static void main(String[]args){
HashMap<String,List<String>> map=new HashMap<String,List<String>>();
List<String> l=new ArrayList<String>();
l.add("BBB");
l.add("CCC");
l.add("EEE");
map.put("AAA", l);
/* map.put("CCC", );
map.put("XXX", );
map.put("DDD", );
map.put("TTT", );
map.put("FFF", );
*/
companystructure c=new companystructure();
c. print(map);
}
void print(HashMap<String,List<String>> map){
Set set= map.entrySet();
Iterator iterator = set.iterator();
while(iterator.hasNext()) {
Map.Entry mentry = (Map.Entry)iterator.next();
System.out.println( mentry.getKey() );
System.out.print("\t"+"-");
List l=(List)mentry.getValue();
Map.remove(mentry.getKey());
for(int i=0; i<l.size(); i++){
if(map.contains( l.get(i))){
print(map);
}
else{
System.out.println(l.get(i));
}
}
}
}
}
import java.util.*;
class companystructure{
public static void main(String[]args){
HashMap<String,List<String>> map=new HashMap<String,List<String>>();
List<String> l=new ArrayList<String>();
l.add("BBB");
l.add("CCC");
l.add("EEE");
map.put("AAA", l);
/* map.put("CCC", );
map.put("XXX", );
map.put("DDD", );
map.put("TTT", );
map.put("FFF", );
*/
companystructure c=new companystructure();
c. print(map);
}
void print(HashMap<String,List<String>> map){
Set set= map.entrySet();
Iterator iterator = set.iterator();
while(iterator.hasNext()) {
Map.Entry mentry = (Map.Entry)iterator.next();
System.out.println( mentry.getKey() );
System.out.print("\t"+"-");
List l=(List)mentry.getValue();
Map.remove(mentry.getKey());
for(int i=0; i<l.size(); i++){
if(map.contains( l.get(i))){
print(map);
}
else{
System.out.println(l.get(i));
}
}
}
}
}
My code is relatively simple Java code which uses recursion to try to avoid lots of redundant code. The actual printing is about as complicated as simply finding the top level item(s). No tricky structures. Just working with the HashMap which has been given.
import java.util.*;
public class dependency{
// The following is the driver which gets top Level item(s) and calls a helper to print
public static void printDependency(HashMap<String,ArrayList<String>> in) throws Exception{
//Arraylist to account for future iterations of 2+ top levels
ArrayList<String> topLevel = findTopLevel(in);
if(topLevel.size()!=1 ){
throw new Exception("More or Less than 1 top level item - " + topLevel.size());
}
dependHelper(0, topLevel.get(0),in);
}
public static void dependHelper(int level, String levelLabel,HashMap<String,ArrayList<String>> in){
//Formatting the spaces
for(int i=0;i<level;i++)
System.out.print(" ");
System.out.println("-" + levelLabel);
//Look to see if the current level has any dependencies
ArrayList<String> lowerLevels = in.get(levelLabel);
if(lowerLevels!=null){
for(String s:lowerLevels){
//Recur
dependHelper(level+1, s, in);
}
}
}
public static ArrayList<String> findTopLevel(HashMap<String,ArrayList<String>> in){
//Finds top level items with no dependency
ArrayList<String> retVal = new ArrayList<String>(Arrays.asList(in.keySet().toArray(new String[0])));
ArrayList<String> keys = new ArrayList<String>(retVal);
//For each item in Hashmap, see if it is listed as a child of any other elements
for(String s:keys){
for(String k:keys){
if(in.get(k).contains(s))
//If it is a child of other elements then it has a dependency
retVal.remove(s);
}
}
return retVal;
}
public static void main(String[] args) throws Exception{
HashMap<String,ArrayList<String>> in = new HashMap<String,ArrayList<String>>();
ArrayList<String> a = new ArrayList<String>();
a.add("b");
a.add("c");
a.add("d");
ArrayList<String> b = new ArrayList<String>();
b.add("e");
ArrayList<String> e = new ArrayList<String>();
e.add("f");
ArrayList<String> d = new ArrayList<String>();
d.add("g");
in.put("a", a);
in.put("b", b);
in.put("e", e);
in.put("d",d);
printDependency(in);
}
}
- Chris December 08, 2016