10月28,K神开课讲数据科学,你来吗?


一亩三分地论坛

 找回密码
 获取更多干活,快来注册
Babeltime游戏工作室招工程师、美术和策划
Tubi TV招安卓、前端和机器学习工程师
把贵司招聘信息放这里
查看: 964|回复: 2
收起左侧

Drive.AI SDE OA两题

[复制链接] |试试Instant~ |关注本帖
lijiyao111 发表于 2017-6-12 21:56:44 | 显示全部楼层 |阅读模式

2017(1-3月) 码农类 博士 全职@Drive.AI - 网上海投 - 在线笔试 |Other在职跳槽

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

您需要 登录 才可以下载或查看,没有帐号?获取更多干活,快来注册

x
说一下他家的OA,两题, 两小时time limit。
第一题简单, merge two sorted array, in place.
第二题有些难,类似topological sort,但又不一样。
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
# Description:

In Docker, building an image has dependencies. An image can only be built once its dependency is built (If the dependency is from outside, then the image can be built immediately).

Sometimes, engineers make mistakes by forming a cycle dependency of local images. In this case, ignore the cycle and all the images depending on this cycle.
.鏈枃鍘熷垱鑷1point3acres璁哄潧
Input is vector of pair of images (image, its dependency).

Output the order of images to be built in order.

##Example:
```. Waral 鍗氬鏈夋洿澶氭枃绔,
Example 1:
{{"master", "ubuntu"}, {"numpy", "master"}, {"tensorflow", "numpy"}}
Output: master, numpy, tensorflow

Example 2:
{{"python", "numpy"}, {"numpy", "python"}, {"tensorflow", "ubuntu"}}
Output: tensorflow.鏈枃鍘熷垱鑷1point3acres璁哄潧

Example 3:
{{"b", "c"}, {"c", "d"}, {"a", "b"}, {"d", "e"}, {"e","c"}, {"f", "g"}}
Ouput: f
```


lcq123 发表于 2017-6-30 10:45:12 | 显示全部楼层
请问楼主可不可以用Java
回复 支持 反对

使用道具 举报

chaohubian 发表于 2017-8-26 03:35:38 | 显示全部楼层
  1. class Solution482 {
  2. public:
  3.     vector<string> detectCycle(vector<vector<string>>& image) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  4.         if (image.empty()) {
  5.             return {};
  6.         }
  7.         unordered_map<string, bool> available;
  8.         vector<string> output;. from: 1point3acres.com/bbs
  9.         unordered_map<string, vector<string>> graph;. from: 1point3acres.com/bbs
  10.         buildGraph(image, graph);
  11.         int leng=graph.size();. 1point 3acres 璁哄潧
  12.         unordered_map<string, bool> visited;
  13.         unordered_map<string, bool> recStack;
  14.         for (auto it = graph.begin(); it != graph.end(); ++it) {. Waral 鍗氬鏈夋洿澶氭枃绔,
  15.             //case 1:not visited
  16.             visited[it->first]=false;
  17.             recStack[it->first]=false;
  18.         }
  19.         for (auto it = graph.begin(); it != graph.end(); ++it) {
  20.             if (recStack[it->first]==true) {
  21.                 continue;
  22.             }. 鍥磋鎴戜滑@1point 3 acres
  23.             if (!isCyclicHelper(it->first, graph, visited, recStack)) {
  24.                 available[it->first]=true;
  25.             }
  26.         }
  27.         topoSort(graph, available, output);
  28.         return output;
  29.     }
  30.     void test() {
  31.         vector<vector<string>> graph;. From 1point 3acres bbs
  32.         vector<string> result;.1point3acres缃
  33.         graph={{"master", "ubuntu"}, {"numpy", "master"}, {"tensorflow", "numpy"}};
  34.         result=detectCycle(graph);
  35.         //Output: ubuntu, master, numpy, tensorflow
  36.         for (auto i : result) {. 鍥磋鎴戜滑@1point 3 acres
  37.             cout<<i<<" ";
  38.         }
  39.         cout<<endl;. more info on 1point3acres.com
  40.         graph={{"python", "numpy"}, {"numpy", "python"}, {"tensorflow", "ubuntu"}};
  41.         result=detectCycle(graph);
  42.         //Output: ubuntu, tensorflow
  43.         for (auto i : result) {
  44.             cout<<i<<" ";
  45.         }.1point3acres缃
  46.         cout<<endl;
  47.         graph={{"b", "c"}, {"c", "d"}, {"a", "b"}, {"d", "e"}, {"e","c"}, {"f", "g"}};. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  48.         result=detectCycle(graph);
  49.         //Ouput: g, f
    . 1point 3acres 璁哄潧
  50.         for (auto i : result) {
  51.             cout<<i<<" ";
  52.         }
  53.         cout<<endl;. Waral 鍗氬鏈夋洿澶氭枃绔,
  54.     }
  55. private:
  56.     void topoSort(unordered_map<string, vector<string>> graph, unordered_map<string, bool>& available, vector<string>& result) {
  57.         unordered_map<string, int> state;
  58.         for (auto it = graph.begin(); it != graph.end(); ++it) {
  59.             state[it->first]=0;
  60.         }
  61.         for (auto it = graph.begin(); it != graph.end(); ++it) {
  62.             if (available[it->first]==true) {
  63.                 visit(graph, it->first, result, state);
  64.             }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  65.         }
  66.         return;
  67.     }
  68.    
  69.     void visit(unordered_map<string, vector<string>>& image,
  70.                string it,
  71.                vector<string>& list,
  72.                unordered_map<string, int>& state) {
  73.         if (state[it]==3) {
  74.             return;
  75.         }
  76.         if (state[it]==2) {
  77.             return;
  78.         }
  79.         state[it]=2;
  80.         for (auto neib:image[it]) {
  81.             visit(image, neib, list, state);
  82.         }
  83.         state[it]=3;
  84.         list.push_back(it);
  85.     }
  86.                
    . from: 1point3acres.com/bbs
  87.     void buildGraph(vector<vector<string>>& image, unordered_map<string, vector<string>>& graph) {
  88.         for (int i=0; i<image.size(); i++) {. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
  89.             graph[image[i][0]].push_back(image[i][1]);
  90.         }
  91.     }
  92.    
  93.     bool isCyclicHelper(string v, unordered_map<string, vector<string>>& graph, unordered_map<string, bool>& visited, unordered_map<string, bool>& recStack) {
  94.         if (visited[v]==false) {
  95.             visited[v]=true;
  96.             recStack[v]=true;
  97.             for (auto it=graph[v].begin(); it!=graph[v].end(); ++it) { 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  98.                 if (!visited[*it] && isCyclicHelper(*it, graph, visited, recStack)) {
  99.                     return true;
  100.                 }
  101.                 else if (recStack[*it]==true) {
  102.                     return true;
  103.                 }
  104.             }
  105.         }
  106.         recStack[v]=false;
  107.         return false;
  108.     }
  109. };
  110. 这里的E1 为什么不输出ubuntu, E2 也是, E3 为什么不输出g呢
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2017-9-21 11:36

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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