Interview Question
StudentsCountry: United States
Interview Type: Written Test
This is simply a tree traversal problem. Using BFS to print out the level in the tree.
Here is a dictionary that has key as parent, and value as its children.
Each time it print out its children value. Note that the root has NULL keyword.
def treePrint():
inp = 'Sam, Ian, technical lead, 2009 / Ian, NULL, CEO, 2007/ Fred, Sam, developer, 2010'
nodes = inp.replace(' ','').split('/')
tree = {}
ceo = []
depth = 0
for node in nodes:
node = node.strip().split(',')
tree[node[1]] = [node[0]] + node[2:]
while len(tree)>0:
if tree.has_key('NULL'):
ceo = (tree.pop('NULL'))
print str(ceo).replace("'","").replace(",","").replace("[","").replace("]","") + "\n"
depth += 1
else:
key = ceo[0]
emp = tree.pop(key)
print depth*'-' + str(emp).replace("'","").replace(",","").replace("[","").replace("]","") + "\n"
ceo = emp
depth +=1
Sample input =
Sam, Ian, technical lead, 2009 / Ian, NULL, CEO,2007/ Fred, Sam, developer, 2010
Build a hash table with key as the manager and the values as their descendents
e.g.
Ian->Sam
Sam->Fred
(Since there was no boss for Ian , we didn't added it but instead recorded it as the top person in the heirarchy).
Now, start with Ian and Print Sam and again using the key Sam we got Fred.
My solution is using list to store employee string and then reorder it base on the supervisor attribute and name attribute. If the supervisor attribute of current index equal to the name of next index, then It's going to swap those 2 employees. Here is my code:
strq = "Sam, Ian, technical lead, 2009 / Ian, NULL, CEO,2007/Fred, Sam, developer, 2010"
def treeEmployee(infoStr):
str1 = infoStr.split("/")
s2 = []
for i in str1:
s2.append(i.split(","))
for i in range(len(s2)):
for j in range(1, len(s2)):
if s2[i][1] == s2[j][0]:
s2[i], s2[j] = s2[j], s2[i]
return s2
import re
import numpy as np
with open('temp.txt','r') as f:
s=f.readlines()[0]
x=np.array(re.findall('(.*?),\s*(.*?),\s*(.*?),\s*(\d+)\s*/?\s*', s))
idx=np.where(x[:,1]=='NULL')[0][0]
k=0
def f(x, idx, k):
print '%s%s'%('_'*k, ' '.join(x[idx,[0,2,3]]))
t=np.where(x[:,1]==x[idx,0])[0]
if (len(t)>0):
for i in t:
f(x,i,k+1)
import csv
with open("list.csv", 'r') as csv_file:
list_reader = csv.reader(csv_file, delimiter=",")
employee_list = {
name: boss.strip() for name, boss, designation, year in list_reader}
mgrs = [k for k, v in employee_list.items() if v == '']
while mgrs:
print ", ".join(mgrs)
mgrs = [k for k, v in employee_list.items() if v in mgrs]
- DW February 10, 2015