Bloomber 算是 地里面经 比较难的题目了

感觉 老印问的问题 不怎么简单 首先 聊了聊实习 问了点C++的基础问题 （virtual function 大二学的 完全 不记得了）

coding的题目如下

An industrial machine uses this table of operation IDs  to orchestrate a complex process.  Each

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

小时 老印说 题是做完了 但他follow up没问完 （关于corner case的）

最后 挂的可能性更大一些吧 毕竟 面试官印度兄弟 加上 follow up 并没有全部答完

1. class GraphNode {
   
2.     int ID;
   
3.     bool flagComplete;
   
4.     vector<GraphNode*> DependsOn;
   
5.    
   
6. public:
   
7.     GraphNode(int inputID) {
   
8.         ID = inputID;
   
9.         f
   
10.         dependsOn.clear();
    
11.     }
    
12. }
    
13. 
    
14. void performInSequence(vector<int> Target, vector<vector<int>> DependsOn) {
    
15.     // Quick check
    
16.     if (Target.empty() || DependsOn.empty()) return;
    
17.     if (Target.size() != DependsOn.size()) return;
    
18.    
    
19.     int nSize = Target.size();
    
20.     unordered_map <int, GraphNode*> targetNodeHash;
    
21.     unordered_set <int> dependOnSet;
    
22.    
    
23.     for (int i = 0; i < nSize; i++) {
    
24.         // Construct graph
    
25.         GraphNode* toInsert;
    
26.         if (targetNodeHash.find(Target[i]) == targetNodeHash.end()) {
    
27.             // We didn't find target[i] in the hash table, initiate a new one
    
28.             toInsert = new GraphNode(Target[i]);
    
29.             targetNodeHash[Target[i]] = toInsert;
    
30.         }
    
31.         
    
32.         else {
    
33.             toInsert = targetNodeHash[Target[i]];
    
34.         }
    
35.         
    
36.         for (int j = 0; j < DependsOn[i].size(); j++) {
    
37.             GraphNode* toDepend;
    
38.             
    
39.             if (targetNodeHash.find(DependsOn[i][j]) != targetNodeHash.end()) {
    
40.                 toDepend = targetNodeHash[DependsOn[i][j]];
    
41.             }
    
42.             
    
43.             else {
    
44.                 toDepend = new GraphNode(DependsOn[i][j]);
    
45.                 targetNodeHash[DependsOn[i][j]] = toDepend;
    
46.             }
    
47.             
    
48.             toInsert.DependsOn.push_back(toDepend);
    
49.             dependOnSet.insert(DependsOn[i][j]);
    
50.         }
    
51.     }
    
52.    
    
53.     // Find the root of the tree
    
54.     int k = 0;
    
55.     for (; k < nSize; k++) {
    
56.         if (dependOnSet.find(Target[k]) != dependOnSet.end()) {
    
57.             // Find it in hash set,
    
58.             continue;
    
59.         }
    
60.         else break;
    
61.     }
    
62.     // root is k
    
63.     constructResultRec(targetNodeHash[Target[k]]);
    
64. }
    
65. 
    
66. void constructResultRec(GraphNode* cur) {
    
67.     for (int i = 0; i < cur.DependsOn.size(); i++) {
    
68.         if (cur.DependsOn[i].flagComplete) continue;
    
69.         constructResultRec(cur.DependsOn[i])
    
70.     }
    
71.    
    
72.     perform(cur.ID);
    
73.     cur.flagComplete = true;
    
74. }
    

复制代码

马上要面了。。。。看到这题觉得慌了。。。我觉得用拓扑排序 但是并不会做。。。。。

老印 并不给 class或任何input 全部是自己定义的

topological sort?
你别说，这个问题在现实工作中真的会遇到，不过BB朋友的做法一般是，for 套 for 查有没有循环。O(N^2)在N不大的时候并不吓人

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

感觉这题不让用Topological Sort有些故意难为人，确实是很标准的TS，我贴个代码，欢迎拍砖：

1. package onsite;
   
2. 
   
3. import java.util.ArrayList;
   
4. import java.util.Arrays;
   
5. import java.util.HashMap;
   
6. import java.util.HashSet;
   
7. import java.util.LinkedList;
   
8. import java.util.List;
   
9. import java.util.Map;
   
10. 
    
11. public class PerformOperations {
    
12.         Map<Integer, List<Integer>> performs;
    
13.         int[] targets;
    
14.         public PerformOperations(Map<Integer, List<Integer>> performs, int[] targets) {
    
15.                 this.performs = performs;
    
16.                 this.targets = targets;
    
17.         }
    
18.        
    
19.         public List<Integer> perforInorder() {
    
20.                 List<Integer> list = new LinkedList<>();
    
21.                 HashSet<Integer> visited = new HashSet<>();
    
22.                 for(int target : targets) {       
    
23.                         if(!visited.contains(target)) topologicalSort(target, visited, list);
    
24.                 }
    
25.                 return list;
    
26.         }
    
27.        
    
28.         private void topologicalSort(int target, HashSet<Integer> visited, List<Integer> list) {
    
29.                 visited.add(target);
    
30.                 List<Integer> dependencies = getDependencies(target);
    
31.                 if(dependencies!=null) {
    
32.                         for(Integer prevPerforms : dependencies) {
    
33.                                 if(!visited.contains(target)) topologicalSort(prevPerforms, visited, list);
    
34.                         }
    
35.                 }
    
36.                 list.add(target);
    
37.         }
    
38.        
    
39.         public List<Integer> getDependencies(int target) {
    
40.                 return performs.get(target);
    
41.         }
    
42.        
    
43.         public static void main(String[] args) {
    
44.                
    
45.                 Map<Integer, List<Integer>> performs = new HashMap<>();
    
46.                 performs.put(9, new ArrayList<>(Arrays.asList(2,3,4,5,6,7)));
    
47.                 performs.put(8, new ArrayList<>(Arrays.asList(5,6,1,2)));
    
48.                 performs.put(7, new ArrayList<>(Arrays.asList(1,3,5)));
    
49.                 performs.put(6, new ArrayList<>(Arrays.asList(2)));
    
50.                 performs.put(5, new ArrayList<>(Arrays.asList(2)));
    
51.                 performs.put(4, new ArrayList<>(Arrays.asList(1,2,3)));
    
52.                 performs.put(3, new ArrayList<>(Arrays.asList(1,2)));
    
53.                 performs.put(2, new ArrayList<>(Arrays.asList(1)));
    
54.                
    
55.                 int[] targets = {1,2,3,4,5,6,7,8,9};
    
56.                
    
57.                 PerformOperations po = new PerformOperations(performs, targets);
    
58.                 List<Integer> res = po.perforInorder();
    
59.                 System.out.println(res);
    
60.         }
    
61. }

复制代码

TS也可以用递归的，之前在ExtraHop面到一道，找一个有向图有没有环，就是DFS，只需要用O(E)的时间复杂度，如果node是N，确实是O(n^2)了。

1. struct Node{
   
2.     int value;
   
3.     vector<Node*> edges;
   
4.     int state=0;
   
5. };
   
6. bool helper(Node *node){
   
7.     node->state=1;
   
8.     for(int i=0;i<node->edges.size();i++){
   
9.         if(node->edges[i]->state==0){  //There are 3 states. 0 is unreached
   
10.             if(helper(node->edges[i]))
    
11.                 return true;
    
12.         }
    
13.         else if(node->edges[i]->state==1){ //1 is reached but not finished all nodes connected to this node.
    
14.             return true;
    
15.         }
    
16.         else if(node->edges[i]->state==2){ //2 is reached and finished all nodes connected to this node.
    
17.             continue;
    
18.         }
    
19.     }
    
20.     node->state=2;
    
21.     return false;
    
22. }
    
23. 
    
24. bool haveCycle(vector<Node *> nodes){
    
25.     for(int i=0;i<nodes.size();i++){
    
26.         if(helper(nodes[i])){
    
27.             return true;
    
28.         }
    
29.     }
    
30.     return false;
    
31. }

复制代码

googlerr 发表于 2016-1-30 11:12
感觉这题不让用Topological Sort有些故意难为人，确实是很标准的TS，我贴个代码，欢迎拍砖：

hi~~  感觉你的topologicalSort  这里面 visited(target)要放到最后 要不你那个里面的迭代进不去啊

googlerr 发表于 2016-1-30 11:12
感觉这题不让用Topological Sort有些故意难为人，确实是很标准的TS，我贴个代码，欢迎拍砖：

或者括号里面是  prevPerforms?......

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies