找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 6776|回复: 53
收起左侧

[Microsoft] Microsoft Interview Question for SD

[复制链接]

1150

主题

172

精华

3556

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3556
发表于 2-23-2017 03:56 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x

Given a dictionary that contains mapping of employee and his/her manager like this0 I6 t( F c% F$ ?8 q' n
! i) x" m! V# \
Dictionary employees = new Dictionary()# s, T$ C# U% B0 ] i
{ D) j5 P8 O# q
{ "A","C" }, ) p1 C! B0 |$ `
{ "B","C" },( K# k" A3 A- m, L5 N4 k
{ "C","F" }, ) G# o- z1 E. |: j1 V" J1 \
{ "D","E" }, z. r3 O; M5 s0 H) T
{ "E","F" }, + l. u9 f4 M" u# Y
{ "F","F" } . d" X& D, o2 L- D- C3 E% {0 A
}; 1 s5 R- y. {* q/ A
% w# K4 x) G3 j# m
Write a function to get no of employees under each manager in the hierarchy not just their direct reports.9 z, ^: G5 e. o. q, o
In the above dictionary the root node/ceo is listed as reporting to himself. # S! H, s, o; J3 t, k
2 b( @( y( ?! D7 l
Output should be a Dictionary that contains this ! [$ k" J2 N1 T; a/ o* x& B3 _- D7 M4 ~( ]
+ n' R9 `, T. \6 B0 S
A - 0 - m7 ~8 V% V& h4 G* X- K( Q. n _
B - 0 ' M, B" N( k# q( I) O
C - 2' J: k+ k5 ~( G7 W" s. L; b! A
D - 08 P- \9 l( ?+ ^# Y( v) K
E - 1 ; g2 r& n9 ]2 Z/ |' j/ I0 F
F - 5

205

主题

158

精华

1806

积分

顶级会员

Rank: 6Rank: 6

积分
1806
发表于 2-23-2017 03:56 PM | 显示全部楼层

Based on the input data it would make it possible to build the tree in O(n) time, using a HashMap lets you jump directly to a node instead of traversing there from the tree's root node:" e9 I- e' N% P! v7 g4 _
- U% C l! h) J6 }% A/ ]9 H
1. build tree of designated company hierarchy based on input map, use an auxiliary9 Y- z0 |& u3 D1 J6 K! o, F
Map of <String, TreeNodeEmp> representing each employee and also for adding the direct employees of a specific manager.4 q$ u1 z. [' M, t" a0 d
complexity: O(n)- e! {0 d8 n* n
+ H" Y" K, n. n& u
2. Once tree is built, calculate counts of Direct employees and total employees under each employee. - f1 V1 T7 z* B) ^. v, u' ~/ i$ z
! O: H+ ?) ]: Q3 d- p8 q
Once calculated subsequent operations for read will be O(1) such as counting total direct and indirect employees for any given employee, whenever tree is changed (nodes inserted or deleted) subtree counts of left or right branch starting from root should be recalculated. 2 i, S A+ M6 @: l/ P
2 z2 l- \3 U: O# v9 E) m
Solution in Java:

public class Solution {+ r' v% z# d3 p2 P

1 y+ V; Z0 ]0 ]6 u% A! v0 }public static void main(String[] args) {
; A) ~$ O* u4 |5 A" W8 s	printAllEmployeesOfAllManagers();
! N4 k2 k6 e3 L& V, _5 l}! `5 a7 \1 A  X9 m
  v) I; R7 S( E# X& f) p. O
public static void printAllEmployeesOfAllManagers() {
# P/ D5 |+ d# b$ h  B- [, g& z& ~6 z	Map<String, String> dataSet = new HashMap<>();
1 G' i4 s7 ~: K% W8 \" \	dataSet.put("A", "C");
  E6 j- _$ Z! e7 D5 N+ H# U' L! D	dataSet.put("B", "C");6 V) v7 j- W/ o  y: ~2 T
	dataSet.put("C", "F");
' \4 b, P$ o, o- P& g. N, {& v4 s. k	dataSet.put("D", "E");$ K+ K/ \7 U3 i: p/ I
	dataSet.put("E", "F");& G7 S* ^. a* U% d, w- h+ F+ v- Z
	dataSet.put("F", "F");
  K9 x! T8 D+ B: L( i( T) r
3 Z3 c6 E1 t. w3 L3 K9 M	Map<String, TreeNodeEmp> empTreeNodeMap = new HashMap<>();6 G" E# e5 _8 `( v* Z
	TreeNodeEmp root = buildHierarchyTreeOfCompany(dataSet, empTreeNodeMap);
, W. A0 B  w* y% S5 \	calculateCountsOfTree(root); : ~' O( l4 }% W0 p+ ?; C
	Map<String, Integer> output = new HashMap<>();
$ k  i; d1 z  n. }( y7 P/ q' Y: @; g$ s) o$ I+ \
	for (Map.Entry<String, TreeNodeEmp> empEntry : empTreeNodeMap3 M, g% _* g1 u3 ?! c+ r+ ]. T
			.entrySet()) {
1 f: |) D" ~1 r* _, X+ W- y		String empName = empEntry.getKey();
% k$ |  W. y/ d8 J		TreeNodeEmp emp = empEntry.getValue();
' A% Y& K$ u! p5 c; Q+ S. \		output.put(empName, emp.countTotalEmployees);
- a* K& J- [0 F5 W	}! J, y" e/ [( L8 _$ e
	printResults(output);* ]7 k; U( {! w+ [1 z
}% _8 W) l+ e) |3 a# Z

# S+ Q+ `4 w6 {! v/ b. b1 d% R* `public static void printResults(Map<String, Integer> results) {
0 B  q7 u, m3 N	for (Map.Entry<String, Integer> r : results.entrySet()) {
' Y6 T$ q" X7 K" g4 ~7 q( ?( c		System.out.println(r.getKey() + " - " + r.getValue());- B) J" @" y9 Z0 X7 B
	}0 ?; z, b% ~* c. r, i
}+ u- r1 f# F& R9 i' A& k
! |9 f$ n- l6 p  W" y
public static void calculateCountsOfTree(TreeNodeEmp root) {
+ Z2 O. k7 N+ ?' K5 Z	if(root == null) {5 k# M$ `- T/ I1 _, v+ R
		return;
5 f; ^- l- g% J; }	}
9 p. L+ I& H5 @3 Z% }! l	root.countDirectEmployees = root.children.size();
( i! X9 h: I( c" D	root.countTotalEmployees = getCountEmployeesOfManager(root) - 1;1 @" v1 A) p% R& }. _
	for (TreeNodeEmp emp : root.children) {, B, }- h+ w5 c- A% q" w. @) t' ~
		calculateCountsOfTree(emp);6 ~+ S* A) i% Z: z
	}
' h; `5 |% [$ X# L/ w0 F}' a( J8 W. ?" \
, W( c6 `3 X1 ^3 {1 A" m) G7 i: m
public static Integer getCountEmployeesOfManager(TreeNodeEmp root) {
# D" v, C5 V/ g% H% [5 Q	if(root == null) {* l8 t( W9 r; ?% I
		return 0;5 K, U0 p) Y* R0 i, X
	}2 e6 [  D) b3 D  p, f; b
	int count = 1;' K6 S2 Y6 Q  M5 j0 m9 g' h
	for (TreeNodeEmp emp : root.children) {3 A# V, K* F3 m: I- ]0 m$ l
		count += getCountEmployeesOfManager(emp);
0 V. O# l4 _; p5 P4 ]	}9 W. l# Q; V! e& g. c, g5 U
	return count;
" Y7 Y& j& X7 T}3 m2 d& N+ G1 y* k- i

4 }5 r! L! S" p6 Vpublic static TreeNodeEmp buildHierarchyTreeOfCompany(
$ X: B! q8 L2 c# H		Map<String, String> empMap, Map<String, TreeNodeEmp> empTreeNodeMap) {2 q3 }8 U6 N$ Y  S
	Map<String, List<TreeNodeEmp>> auxMgrEmpList = new HashMap<>();" y- ~. I1 G7 y9 q$ q9 U5 |
	List<TreeNodeEmp> listEmps = null;) F0 P1 c1 F& z
	TreeNodeEmp emp = null, mgr = null, root = null;
1 |4 J3 p/ m/ C	String nameEmp, managerName;7 M4 W7 T0 n; h
- i! z  ~# N7 F6 H& P
	for (Map.Entry<String, String> empMapEntry : empMap.entrySet()) {* u. T5 \5 A, V" C6 l
			nameEmp = empMapEntry.getKey();
- N( p- z1 U& ?% e			managerName = empMapEntry.getValue();
( G* {" u5 @5 L2 r8 e
- D0 T$ o$ u$ W3 \( {			if (!empTreeNodeMap.containsKey(nameEmp)) {$ E  s; _4 d+ B# y) B6 V% g
				emp = new TreeNodeEmp(nameEmp, managerName);5 L+ G; O: ^1 s0 i
- f# ^* w0 b% l8 Y* Y
				// check for who was added before and have this as a manger" q) H8 {# \. u" ~, `1 u* i/ Y0 I; B
				if(auxMgrEmpList.containsKey(nameEmp)) {
3 y# W  z" }8 Z1 p* K; M( p				   emp.children.addAll(auxMgrEmpList.get(nameEmp));	1 x& E. x) A% H, r
				}										
  C# R' K7 o5 u% i				empTreeNodeMap.put(nameEmp, emp);
2 Y3 X3 u- _3 K; Z$ l			}
" {  Q' ~. L6 {1 C			
% h2 v/ X! y8 H			if (nameEmp.equals(managerName)) {
2 C2 R7 ~2 o9 g+ I) p) [				root = emp;
1 m- E' V9 N6 x" v7 a			} else if (empTreeNodeMap.containsKey(managerName)) {
. a& W3 J9 W; ^3 B" I				mgr = empTreeNodeMap.get(managerName);8 |- L% E. q# p# Q  u( u
				mgr.children.add(emp);
2 `0 n0 _! F) e) n+ m) k& p+ I4 P			} else if (!auxMgrEmpList.containsKey(managerName)){
, u0 \' a! `6 l				listEmps = new ArrayList<>();
- ^! Y1 P" n3 r* k1 b				listEmps.add(emp);
" X: h* z6 R( t! _3 O				auxMgrEmpList.put(managerName, listEmps);
, f* p5 p/ M: N3 T			} else {! v( g- O$ q- H5 K; `- d! @7 _# T" t
				listEmps = auxMgrEmpList.get(managerName);
5 {( Q4 E* t2 n" Q$ g0 l				listEmps.add(emp);+ ?8 I  j( [- u7 c! }8 I$ M
				auxMgrEmpList.put(managerName, listEmps);					' j/ a' t+ F! q  |9 q# r# {
			}8 z6 @8 j/ ]7 k! `0 i' F( H9 v
$ d1 `1 h9 i3 Y0 d& b  O
	}/ d; {2 N0 F+ X8 X& s* W$ _

: `( g0 f! V% U	return root;! a0 e. Y9 k- }& [& ~! B% l+ C
}
6 ?/ @' e1 x5 J0 }  w. T% N' d! A5 w
class TreeNodeEmp {
% L8 Z- V9 s5 |8 P; G8 l0 C	String name;* O1 n9 x5 M1 N5 ?7 r7 D+ {, E
	String managerName;- y, a4 k; B2 u  X2 B
	Integer countDirectEmployees;
0 r! a: Y3 o" A0 q3 j! U* F	Integer countTotalEmployees;# |/ F* c2 ~$ w
	Set<TreeNodeEmp> children;
1 L; @* r. u$ y1 _8 \; y4 @2 ]2 H9 q2 d
	public TreeNodeEmp(String name, String managerName) {) K; z( `0 V2 `% g
		this.name = name;) {* T2 c( X3 v; }+ W: k3 \5 b
		this.managerName = managerName;* r1 K+ H8 }; n* f5 ^
		children = new HashSet<>();, K6 C) ]& c/ \  _) n
		countDirectEmployees = 0;7 F+ D( x+ u) Z+ p# P9 p
		countTotalEmployees = 0;2 y$ Y1 f: d- [5 }: A
	}
: M+ k! x6 r/ m% T9 g2 P5 I/ P! y4 E/ Q/ V; E8 {: g( Y7 n0 l
}	
/ O% L4 ^; [2 c/ w3 p  R
/ c# U! \2 Q, ]1 @}

回复 支持 反对

使用道具 举报

1190

主题

195

精华

3811

积分

神级会员

Rank: 7Rank: 7Rank: 7

积分
3811
发表于 2-23-2017 03:56 PM | 显示全部楼层
& a4 B% o0 q/ W. Y6 O
' ?) Z: a8 V1 c3 ~ 1 _9 M" }; |5 B; r) d( o6 Q
0
5 P# D5 Y" }8 v. L) j/ W9 c
- l- x$ T# L- Y7 ]+ {- o . b6 K. m" s0 c' `% U
of 0 votes
5 d& G* D& J6 x" b- W- r1 ~
" e5 Z* X# U& n5 z+ z
6 _( \, Y8 l. z& ^, L( k4 f * Y7 i( }( n! t* r* R% I

Creating your tree would indeed by O(n), but I think counting the reporting employees would be O(n log n) since you need every employee (n) and have to traverse the tree to get the count (log n). For the CEO F, this means traversing the whole tree again, but for leaves it is constant.

We might be able to get to O(n) if we add a count of reports to the TreeNodeEmp class that is computed once after the tree is complete. We would track the leaves of the tree while it is being created and then traverse up towards the root with a queue. At each node reports would equal children.size() + sum of reports in the children.

回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表