一亩三分地论坛

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

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

Twitter电面

[复制链接] |试试Instant~ |关注本帖
lemonie 发表于 2016-1-16 12:30:15 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 硕士 全职@Twitter - 内推 - 技术电面 |Otherfresh grad应届毕业生

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

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

x
互相自我介绍,然后聊了聊简历中的一个项目, 最后就一道题 alien dictionary. 感觉这道题出现的频率蛮高的~
zzx04025 发表于 2016-3-28 08:14:36 | 显示全部楼层
请问lz的alien dictionary能详细讲讲么, 一直看到有人po 这题,却不知道出处在那里==
回复 支持 反对

使用道具 举报

hison7463 发表于 2016-3-29 05:58:14 | 显示全部楼层
电面面alien dictionary。。。
回复 支持 反对

使用道具 举报

slashGu 发表于 2016-3-30 03:48:42 | 显示全部楼层
  1. class Solution {
  2. public:.1point3acres缃
  3.     string alienOrder(vector<string>& words) {
  4.         if(words.size() == 1) return words[0];
  5.         graph g = makeGraph(words);
  6.         return sort(g);
  7.     }
  8. private:. from: 1point3acres.com/bbs
  9.     typedef unordered_map<char, unordered_set<char>> graph;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  10.    
  11.     graph makeGraph(vector<string> words) {
  12.         graph g;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  13.         for(int i = 1; i < words.size(); ++i) {
  14.             bool found = false;
  15.             string word1 = words[i - 1];
  16.             string word2 = words[i];
  17.             int len1 = word1.size(), len2 = word2.size();
  18.             int l = max(len1, len2);
  19.             for(int j = 0; j < l; ++j) {
  20.                 if(j < len1 && g.find(word1[j]) == g.end()) {
  21.                     g[word1[j]] = unordered_set<char>();. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  22.                 }.鐣欏璁哄潧-涓浜-涓夊垎鍦
  23.                 if(j < len2 && g.find(word2[j]) == g.end()) {.鏈枃鍘熷垱鑷1point3acres璁哄潧
  24.                     g[word2[j]] = unordered_set<char>();. 1point3acres.com/bbs
  25.                 }
  26.                 if(j < len1 && j < len2 && word1[j] != word2[j] && found == false) {
  27.                     g[word1[j]].insert(word2[j]);. 1point 3acres 璁哄潧
  28.                     found = true;. 1point3acres.com/bbs
  29.                 }
  30.             }
  31.         }
  32.         return g;
  33.     }. from: 1point3acres.com/bbs
  34.     string sort(graph g) {. more info on 1point3acres.com
  35.         string topo = "";
  36.         vector<bool> visited(256, false), path(256, false);
  37.         for(auto node : g) {. From 1point 3acres bbs
  38.             if(!acyclic(g, node.first, visited, path, topo)) {. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
  39.                 return "";. 1point 3acres 璁哄潧
  40.             }. from: 1point3acres.com/bbs
  41.         }
  42.         reverse(topo.begin(), topo.end());.鐣欏璁哄潧-涓浜-涓夊垎鍦
  43.         return topo;
  44.     }
  45.    
  46.     bool acyclic(graph g, char node, vector<bool> &visited, vector<bool> &path, string &topo) {. 1point 3acres 璁哄潧
  47.         if(path[node]) return false;
  48.         if(visited[node]) return true;
  49.         path[node] = visited[node] = true;
  50.         for(auto n : g[node]) {
  51.             if(!acyclic(g, n, visited, path, topo)) return false;-google 1point3acres
  52.         }
  53.         path[node] = false;
  54.         topo.push_back(node);
  55.         return true;
  56.     }. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
  57.    
  58. };
复制代码
回复 支持 反对

使用道具 举报

lfy249 发表于 2016-4-20 00:58:48 | 显示全部楼层
zzx04025 发表于 2016-3-28 08:14
请问lz的alien dictionary能详细讲讲么, 一直看到有人po 这题,却不知道出处在那里==

http://blog.csdn.net/pointbreak1/article/details/48761705
http://www.cnblogs.com/jcliBlogger/p/4758761.html
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

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

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-9 21:46

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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