一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

一亩三分地官方iOS手机应用下载
查看: 2659|回复: 10
收起左侧

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

[复制链接] |试试Instant~ |关注本帖
loveonts 发表于 2016-1-29 00:20:02 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Bloomberg - 网上海投 - 技术电面 |Otherfresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

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

coding的题目如下
. From 1point 3acres bbs
An industrial machine uses this table of operation IDs  to orchestrate a complex process.  Each row in the table starts with the "target" operation ID, followed by a list of dependencies.   Each dependency is the ID of an operation which must complete before the target operation can be started.

For example:. 1point3acres.com/bbs
Target        Depends on:
112             47,39
47             39, 191.鐣欏璁哄潧-涓浜-涓夊垎鍦


给了 perform(int Target) API 要求 按顺序 要求 执行

我用的算法是 搭建graph(实际上 类似于tree的graph) 然后DFS

当中 老印hint了1-2次 (比较关键的一次是 我一开始想用BFS 结果老印建议 DFS更好) follow up了一些 代码里面的小问题 面了一个小时 老印说 题是做完了 但他follow up没问完 (关于corner case的)

最后 挂的可能性更大一些吧 毕竟 面试官印度兄弟 加上 follow up 并没有全部答完
  1. class GraphNode {
  2.     int ID;
  3.     bool flagComplete;
  4.     vector<GraphNode*> DependsOn;. visit 1point3acres.com for more.
  5.    
  6. public:. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  7.     GraphNode(int inputID) {. visit 1point3acres.com for more.
  8.         ID = inputID;
  9.         f
  10.         dependsOn.clear();. 1point 3acres 璁哄潧
  11.     }
  12. }

  13. void performInSequence(vector<int> Target, vector<vector<int>> DependsOn) {
  14.     // Quick check
  15.     if (Target.empty() || DependsOn.empty()) return;
  16.     if (Target.size() != DependsOn.size()) return; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  17.     . more info on 1point3acres.com
  18.     int nSize = Target.size();. 鍥磋鎴戜滑@1point 3 acres
  19.     unordered_map <int, GraphNode*> targetNodeHash;
  20.     unordered_set <int> dependOnSet;
  21.    
  22.     for (int i = 0; i < nSize; i++) {. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  23.         // Construct graph
  24.         GraphNode* toInsert;
  25.         if (targetNodeHash.find(Target[i]) == targetNodeHash.end()) {
  26.             // We didn't find target[i] in the hash table, initiate a new one
  27.             toInsert = new GraphNode(Target[i]);
  28.             targetNodeHash[Target[i]] = toInsert;
  29.         }
  30.         
  31.         else {
  32.             toInsert = targetNodeHash[Target[i]];
  33.         }
  34.         
  35.         for (int j = 0; j < DependsOn[i].size(); j++) {. From 1point 3acres bbs
  36.             GraphNode* toDepend;
  37.             
  38.             if (targetNodeHash.find(DependsOn[i][j]) != targetNodeHash.end()) {
  39.                 toDepend = targetNodeHash[DependsOn[i][j]];
  40.             }
  41.             
  42.             else {
  43.                 toDepend = new GraphNode(DependsOn[i][j]);
  44.                 targetNodeHash[DependsOn[i][j]] = toDepend;
  45.             }
  46.             
  47.             toInsert.DependsOn.push_back(toDepend);
  48.             dependOnSet.insert(DependsOn[i][j]);
  49.         }
  50.     }
  51.    
  52.     // Find the root of the tree
  53.     int k = 0;
  54.     for (; k < nSize; k++) {
  55.         if (dependOnSet.find(Target[k]) != dependOnSet.end()) {
  56.             // Find it in hash set,
  57.             continue;
  58.         }
  59.         else break; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  60.     }
  61.     // root is k
  62.     constructResultRec(targetNodeHash[Target[k]]);
  63. }

  64. void constructResultRec(GraphNode* cur) {
  65.     for (int i = 0; i < cur.DependsOn.size(); i++) {.1point3acres缃
  66.         if (cur.DependsOn[i].flagComplete) continue;
  67.         constructResultRec(cur.DependsOn[i])
  68.     }
  69.    
  70.     perform(cur.ID);
    . From 1point 3acres bbs
  71.     cur.flagComplete = true;
  72. }-google 1point3acres
复制代码

评分

2

查看全部评分

本帖被以下淘专辑推荐:

何打发123 发表于 2016-1-29 01:10:06 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地
马上要面了。。。。看到这题觉得慌了。。。我觉得用拓扑排序 但是并不会做。。。。。
回复 支持 0 反对 2

使用道具 举报

 楼主| loveonts 发表于 2016-1-29 00:20:46 | 显示全部楼层
关注一亩三分地微博:
Warald
老印 并不给 class或任何input 全部是自己定义的
回复 支持 反对

使用道具 举报

孤笑客 发表于 2016-1-29 23:58:05 | 显示全部楼层
topological sort?
你别说,这个问题在现实工作中真的会遇到,不过BB朋友的做法一般是,for 套 for 查有没有循环。O(N^2)在N不大的时候并不吓人
回复 支持 反对

使用道具 举报

 楼主| loveonts 发表于 2016-1-30 00:06:45 | 显示全部楼层
孤笑客 发表于 2016-1-29 23:58
topological sort?
你别说,这个问题在现实工作中真的会遇到,不过BB朋友的做法一般是,for 套 for 查有没 ...

面试的时候 面试官 并没有让我用topological sort 他让我用的是DFS (递归形式)的来解 这一部分 我一开始想用TOPOLOGICAL SORT 他直接说 你用树遍历的算法来解 然后 他又hint了一下DFS
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-1-30 11:12:39 | 显示全部楼层
感觉这题不让用Topological Sort有些故意难为人,确实是很标准的TS,我贴个代码,欢迎拍砖:
  1. package onsite;

  2. import java.util.ArrayList;
  3. import java.util.Arrays;
  4. import java.util.HashMap;
  5. import java.util.HashSet;
  6. import java.util.LinkedList;
  7. import java.util.List;
  8. import java.util.Map;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

  9. public class PerformOperations {
  10.         Map<Integer, List<Integer>> performs;
  11.         int[] targets;
  12.         public PerformOperations(Map<Integer, List<Integer>> performs, int[] targets) {
  13.                 this.performs = performs;
  14.                 this.targets = targets;
  15.         }-google 1point3acres
  16.        
  17.         public List<Integer> perforInorder() {
  18.                 List<Integer> list = new LinkedList<>();
  19.                 HashSet<Integer> visited = new HashSet<>();
  20.                 for(int target : targets) {        . from: 1point3acres.com/bbs
  21.                         if(!visited.contains(target)) topologicalSort(target, visited, list);
  22.                 }
  23.                 return list;
  24.         }
  25.        
  26.         private void topologicalSort(int target, HashSet<Integer> visited, List<Integer> list) {
  27.                 visited.add(target);. visit 1point3acres.com for more.
  28.                 List<Integer> dependencies = getDependencies(target);
  29.                 if(dependencies!=null) {
  30.                         for(Integer prevPerforms : dependencies) {
  31.                                 if(!visited.contains(target)) topologicalSort(prevPerforms, visited, list);
  32.                         }
  33.                 }. more info on 1point3acres.com
  34.                 list.add(target);
  35.         }. From 1point 3acres bbs
  36.        
  37.         public List<Integer> getDependencies(int target) {
  38.                 return performs.get(target);
  39.         }
  40.        
  41.         public static void main(String[] args) {
  42.                
  43.                 Map<Integer, List<Integer>> performs = new HashMap<>();
  44.                 performs.put(9, new ArrayList<>(Arrays.asList(2,3,4,5,6,7)));
  45.                 performs.put(8, new ArrayList<>(Arrays.asList(5,6,1,2)));
  46.                 performs.put(7, new ArrayList<>(Arrays.asList(1,3,5)));. from: 1point3acres.com/bbs
  47.                 performs.put(6, new ArrayList<>(Arrays.asList(2)));
  48.                 performs.put(5, new ArrayList<>(Arrays.asList(2)));
  49.                 performs.put(4, new ArrayList<>(Arrays.asList(1,2,3)));
  50.                 performs.put(3, new ArrayList<>(Arrays.asList(1,2)));
  51.                 performs.put(2, new ArrayList<>(Arrays.asList(1)));.鏈枃鍘熷垱鑷1point3acres璁哄潧
  52.                
  53.                 int[] targets = {1,2,3,4,5,6,7,8,9};
  54.                
  55.                 PerformOperations po = new PerformOperations(performs, targets);
  56.                 List<Integer> res = po.perforInorder();
  57.                 System.out.println(res);
  58.         }
  59. }
复制代码
回复 支持 反对

使用道具 举报

zxl9171 发表于 2016-2-2 06:55:43 | 显示全部楼层
TS也可以用递归的,之前在ExtraHop面到一道,找一个有向图有没有环,就是DFS,只需要用O(E)的时间复杂度,如果node是N,确实是O(n^2)了。
  1. struct Node{. more info on 1point3acres.com
  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.. visit 1point3acres.com for more.
  17.             continue;
  18.         }
  19.     }-google 1point3acres
  20.     node->state=2;
  21.     return false;. 1point3acres.com/bbs
  22. }

  23. bool haveCycle(vector<Node *> nodes){
  24.     for(int i=0;i<nodes.size();i++){
  25.         if(helper(nodes[i])){
  26.             return true;
  27.         }
  28.     }
  29.     return false;
  30. }
复制代码
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-2-22 05:39:48 | 显示全部楼层
googlerr 发表于 2016-1-30 11:12
感觉这题不让用Topological Sort有些故意难为人,确实是很标准的TS,我贴个代码,欢迎拍砖:

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

使用道具 举报

何打发123 发表于 2016-2-22 05:42:04 | 显示全部楼层
googlerr 发表于 2016-1-30 11:12
感觉这题不让用Topological Sort有些故意难为人,确实是很标准的TS,我贴个代码,欢迎拍砖:
. 1point 3acres 璁哄潧
或者括号里面是  prevPerforms?......
回复 支持 反对

使用道具 举报

何打发123 发表于 2016-2-22 06:05:38 | 显示全部楼层
googlerr 发表于 2016-1-30 11:12
感觉这题不让用Topological Sort有些故意难为人,确实是很标准的TS,我贴个代码,欢迎拍砖:

private void topologicalSort(int target, HashSet<Integer> visited, List<Integer> list) {
                if(visited.contains(target) ) return;
                List<Integer> dependencies = getDependencies(target);
                if(dependencies!=null) {
                        for(Integer prevPerforms : dependencies) {
                               topologicalSort(prevPerforms, visited, list);
                        }
                }
               visited.add(target);
               if(targets.contains(target) )  list.add(target);
        }


改了一下 不知道对不对吖@@
回复 支持 反对

使用道具 举报

googlerr 发表于 2016-2-22 10:14:37 | 显示全部楼层
何打发123 发表于 2016-2-22 06:05
private void topologicalSort(int target, HashSet visited, List list) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
                if(visited ...

思路是:先在performInorder主函数里面对尚未访问的节点调用TS函数。进入TS函数后,先将该节点加入已访问节点,然后遍历该节点的所有尚未访问的关联节点。这样既不会重复也不会遗漏。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2017-3-26 20:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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