📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
回复: 4
跳转到指定楼层
上一主题 下一主题
收起左侧

Drive.AI SDE OA两题

全局:

2017(1-3月) 码农类General 博士 全职@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, e
您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式
游客,您好!
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Popular Interview Questions from Top Companies
uot;c", "d"}, {"a", "b"}, {"d", "e"}, {"e","c"}, {"f", "g"}}
Ouput: f
```



上一篇:脸熟巨水的电面。。。
下一篇:瑞信非主流onsite
🔗
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;
  10.         buildGraph(image, graph);
  11.         int leng=graph.size();
  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);
  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<<" ";
  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;
  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.                
  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呢
复制代码
回复

使用道具 举报

🔗
Urumic 2018-1-15 06:45:00 | 只看该作者
全局:
所以就是说,一个图里面的第一个元素都不用放在结果里对吗?
回复

使用道具 举报

🔗
Urumic 2018-1-15 09:02:33 | 只看该作者
全局:

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

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

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