一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推多家公司面试
Airbnb 数据科学职位
in analytics and inference
游戏初创公司
招聘工程师、Designer和游戏策划
游戏初创公司DreamCraft招聘工程师、UIUX Designer和游戏策划
电商初创公司Good Days
招聘SDE/UI/TPM实习生
把贵司招聘信息放这里
查看: 1465|回复: 4
收起左侧

Drive.AI SDE OA两题

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

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

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

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

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. 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
. from: 1point3acres.com/bbs
Input is vector of pair of images (image, its dependency).

Output the order of images to be built in order.

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

Example 2:
{{"python", "numpy"}, {"numpy", "python"}, {"tensorflow", "ubuntu"}}
Output: tensorflow

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


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

使用道具 举报

chaohubian 发表于 2017-8-26 03:35:38 | 显示全部楼层
  1. class Solution482 {
  2. public:. 1point 3acres 璁哄潧
  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;
  9.         unordered_map<string, vector<string>> graph;
  10.         buildGraph(image, graph);
  11.         int leng=graph.size();
  12.         unordered_map<string, bool> visited;
  13.         unordered_map<string, bool> recStack;. from: 1point3acres.com/bbs
  14.         for (auto it = graph.begin(); it != graph.end(); ++it) {
  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;. 1point 3acres 璁哄潧
  22.             }
  23.             if (!isCyclicHelper(it->first, graph, visited, recStack)) {
  24.                 available[it->first]=true;
  25.             }. visit 1point3acres.com for more.
  26.         }
  27.         topoSort(graph, available, output);
  28.         return output;
  29.     }
  30.     void test() {.1point3acres缃
  31.         vector<vector<string>> graph;
  32.         vector<string> result;
  33.         graph={{"master", "ubuntu"}, {"numpy", "master"}, {"tensorflow", "numpy"}};. Waral 鍗氬鏈夋洿澶氭枃绔,
  34.         result=detectCycle(graph);
  35.         //Output: ubuntu, master, numpy, tensorflow
  36.         for (auto i : result) {
  37.             cout<<i<<" ";
  38.         }
  39.         cout<<endl;
  40.         graph={{"python", "numpy"}, {"numpy", "python"}, {"tensorflow", "ubuntu"}};
  41.         result=detectCycle(graph);. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  42.         //Output: ubuntu, tensorflow. 1point 3acres 璁哄潧
  43.         for (auto i : result) {
  44.             cout<<i<<" ";
  45.         }
  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
  50.         for (auto i : result) {.1point3acres缃
  51.             cout<<i<<" ";
  52.         }
  53.         cout<<endl;
  54.     }. From 1point 3acres bbs
  55. private:
  56.     void topoSort(unordered_map<string, vector<string>> graph, unordered_map<string, bool>& available, vector<string>& result) {. 鍥磋鎴戜滑@1point 3 acres
  57.         unordered_map<string, int> state;
  58.         for (auto it = graph.begin(); it != graph.end(); ++it) {. 1point3acres.com/bbs
  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;. 1point3acres.com/bbs
  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) {. from: 1point3acres.com/bbs
  74.             return;
  75.         }. from: 1point3acres.com/bbs
  76.         if (state[it]==2) {
  77.             return;. visit 1point3acres.com for more.
  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.                
  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;. 1point 3acres 璁哄潧
  107.         return false;
  108.     }
  109. };.鏈枃鍘熷垱鑷1point3acres璁哄潧
  110. 这里的E1 为什么不输出ubuntu, E2 也是, E3 为什么不输出g呢. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
复制代码
回复 支持 反对

使用道具 举报

Urumic 发表于 5 天前 | 显示全部楼层
所以就是说,一个图里面的第一个元素都不用放在结果里对吗?
回复 支持 反对

使用道具 举报

Urumic 发表于 5 天前 | 显示全部楼层

层主可以解释一下那三个状态吗?
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2018-1-20 03:50

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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