一亩三分地论坛

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

扫码关注一亩三分地公众号
查看: 2195|回复: 10
收起左侧

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

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

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

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

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

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

coding的题目如下 . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴

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.
. 鍥磋鎴戜滑@1point 3 acres
For example:. from: 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;. From 1point 3acres bbs
  3.     bool flagComplete;
  4.     vector<GraphNode*> DependsOn;
  5.     .鐣欏璁哄潧-涓浜-涓夊垎鍦
  6. public:
  7.     GraphNode(int inputID) {
  8.         ID = inputID;
  9.         f.1point3acres缃
  10.         dependsOn.clear();. 1point3acres.com/bbs
  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;. visit 1point3acres.com for more.
  21.     unordered_set <int> dependOnSet;
  22.     . more info on 1point3acres.com
  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]);. from: 1point3acres.com/bbs
  29.             targetNodeHash[Target[i]] = toInsert;-google 1point3acres
  30.         }
  31.         .鐣欏璁哄潧-涓浜-涓夊垎鍦
  32.         else {
  33.             toInsert = targetNodeHash[Target[i]];
  34.         }
  35.         
  36.         for (int j = 0; j < DependsOn[i].size(); j++) {
  37.             GraphNode* toDepend;. visit 1point3acres.com for more.
  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. 1point 3acres 璁哄潧
  63.     constructResultRec(targetNodeHash[Target[k]]);
  64. }

  65. void constructResultRec(GraphNode* cur) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  66.     for (int i = 0; i < cur.DependsOn.size(); i++) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  67.         if (cur.DependsOn[i].flagComplete) continue;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  68.         constructResultRec(cur.DependsOn[i])
  69.     }
  70.     . visit 1point3acres.com for more.
  71.     perform(cur.ID);
  72.     cur.flagComplete = true;
  73. }
复制代码

评分

2

查看全部评分

本帖被以下淘专辑推荐:

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

使用道具 举报

 楼主| loveonts 发表于 2016-1-29 00:20:46 | 显示全部楼层
老印 并不给 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
回复 支持 反对

使用道具 举报

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

  2. import java.util.ArrayList;
  3. import java.util.Arrays;. Waral 鍗氬鏈夋洿澶氭枃绔,
  4. import java.util.HashMap;
  5. import java.util.HashSet;
  6. import java.util.LinkedList;
  7. import java.util.List;.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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.         }
  16.        
  17.         public List<Integer> perforInorder() {. from: 1point3acres.com/bbs
  18.                 List<Integer> list = new LinkedList<>();. from: 1point3acres.com/bbs
  19.                 HashSet<Integer> visited = new HashSet<>();
  20.                 for(int target : targets) {       
    . 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  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);
  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.                 }
  34.                 list.add(target);
  35.         } 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  36.        
  37.         public List<Integer> getDependencies(int target) {
  38.                 return performs.get(target);
  39.         }
  40.        
  41.         public static void main(String[] args) {
  42.                 . from: 1point3acres.com/bbs
  43.                 Map<Integer, List<Integer>> performs = new HashMap<>();
  44.                 performs.put(9, new ArrayList<>(Arrays.asList(2,3,4,5,6,7)));. 鍥磋鎴戜滑@1point 3 acres
  45.                 performs.put(8, new ArrayList<>(Arrays.asList(5,6,1,2)));
  46.                 performs.put(7, new ArrayList<>(Arrays.asList(1,3,5)));
  47.                 performs.put(6, new ArrayList<>(Arrays.asList(2)));
  48.                 performs.put(5, new ArrayList<>(Arrays.asList(2)));.1point3acres缃
  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)));
  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{. visit 1point3acres.com for more.
  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. 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,我贴个代码,欢迎拍砖:

或者括号里面是  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, 2016-12-8 08:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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