《数据科学面试40+真题讲解》,K神本年度最后一次开课


一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
码农求职神器Triplebyte:
不用海投,内推你去多家公司面试
Airbnb 数据科学职位
in analytics and inference
天天打游戏、照样领工资,
你要不要来?
把贵司招聘信息放这里
查看: 1288|回复: 2
收起左侧

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,但又不一样。. more info on 1point3acres.com

# 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).
. From 1point 3acres bbs
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.

Input is vector of pair of images (image, its dependency).. 1point3acres.com/bbs

Output the order of images to be built in order.

##Example:. 1point 3acres 璁哄潧
```
Example 1:
{{"master", "ubuntu"}, {"numpy", "master"}, {"tensorflow", "numpy"}}
Output: master, numpy, tensorflow. more info on 1point3acres.com
. 1point 3acres 璁哄潧
Example 2:-google 1point3acres
{{"python", "numpy"}, {"numpy", "python"}, {"tensorflow", "ubuntu"}}
Output: tensorflow

Example 3:-google 1point3acres
{{"b", "c"}, {"c", "d"}, {"a", "b"}, {"d", "e"}, {"e","c"}, {"f", "g"}}
Ouput: f
```
. Waral 鍗氬鏈夋洿澶氭枃绔,

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;
  9.         unordered_map<string, vector<string>> graph;.1point3acres缃
  10.         buildGraph(image, graph);
  11.         int leng=graph.size();.1point3acres缃
  12.         unordered_map<string, bool> visited;.鐣欏璁哄潧-涓浜-涓夊垎鍦
  13.         unordered_map<string, bool> recStack;
  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;
  22.             }. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  23.             if (!isCyclicHelper(it->first, graph, visited, recStack)) {
  24.                 available[it->first]=true;
  25.             }
  26.         }
  27.         topoSort(graph, available, output);. visit 1point3acres.com for more.
  28.         return output;
  29.     }
  30.     void test() {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  31.         vector<vector<string>> graph;
  32.         vector<string> result;
  33.         graph={{"master", "ubuntu"}, {"numpy", "master"}, {"tensorflow", "numpy"}}; 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
  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
  43.         for (auto i : result) {
  44.             cout<<i<<" ";. 1point 3acres 璁哄潧
  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) {
  51.             cout<<i<<" ";
  52.         }
  53.         cout<<endl;
  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;. 鍥磋鎴戜滑@1point 3 acres
  60.         }. 鍥磋鎴戜滑@1point 3 acres
  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.         }. 鍥磋鎴戜滑@1point 3 acres
  66.         return;
  67.     }
  68.    
  69.     void visit(unordered_map<string, vector<string>>& image,
  70.                string it,
  71.                vector<string>& list,. Waral 鍗氬鏈夋洿澶氭枃绔,
  72.                unordered_map<string, int>& state) {
  73.         if (state[it]==3) {.鐣欏璁哄潧-涓浜-涓夊垎鍦
  74.             return;
  75.         }-google 1point3acres
  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.         }.鏈枃鍘熷垱鑷1point3acres璁哄潧
  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;-google 1point3acres
  96.             recStack[v]=true;. 1point 3acres 璁哄潧
  97.             for (auto it=graph[v].begin(); it!=graph[v].end(); ++it) {-google 1point3acres
  98.                 if (!visited[*it] && isCyclicHelper(*it, graph, visited, recStack)) {
  99.                     return true;
  100.                 }. Waral 鍗氬鏈夋洿澶氭枃绔,
  101.                 else if (recStack[*it]==true) {
  102.                     return true;
  103.                 }
  104.             }
  105.         }
  106.         recStack[v]=false;
  107.         return false;
  108.     }
  109. };-google 1point3acres
  110. 这里的E1 为什么不输出ubuntu, E2 也是, E3 为什么不输出g呢
复制代码
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-11-20 04:08

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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