一亩三分地论坛

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

一亩三分地官方iOS手机应用下载
查看: 1090|回复: 4
收起左侧

Twitter电面

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

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

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

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

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

使用道具 举报

hison7463 发表于 2016-3-29 05:58:14 | 显示全部楼层
关注一亩三分地微博:
Warald
电面面alien dictionary。。。
回复 支持 反对

使用道具 举报

slashGu 发表于 2016-3-30 03:48:42 | 显示全部楼层
  1. class Solution {
  2. public:
  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:
  9.     typedef unordered_map<char, unordered_set<char>> graph;.1point3acres缃
  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];. visit 1point3acres.com for more.
  17.             int len1 = word1.size(), len2 = word2.size();. from: 1point3acres.com/bbs
  18.             int l = max(len1, len2);. 鍥磋鎴戜滑@1point 3 acres
  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()) {
  24.                     g[word2[j]] = unordered_set<char>();. Waral 鍗氬鏈夋洿澶氭枃绔,
  25.                 }
  26.                 if(j < len1 && j < len2 && word1[j] != word2[j] && found == false) {
  27.                     g[word1[j]].insert(word2[j]);
  28.                     found = true;
  29.                 }
  30.             }
  31.         }
  32.         return g;
  33.     }
  34.     string sort(graph g) {
  35.         string topo = "";
  36.         vector<bool> visited(256, false), path(256, false);
  37.         for(auto node : g) {
  38.             if(!acyclic(g, node.first, visited, path, topo)) {
  39.                 return "";
  40.             }
  41.         }
  42.         reverse(topo.begin(), topo.end());
  43.         return topo;
    .鏈枃鍘熷垱鑷1point3acres璁哄潧
  44.     }
  45.     . more info on 1point3acres.com
  46.     bool acyclic(graph g, char node, vector<bool> &visited, vector<bool> &path, string &topo) {
  47.         if(path[node]) return false;. 鍥磋鎴戜滑@1point 3 acres
  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;
  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
求职神器indeed - 在全球最大的求职网站找找适合你的工作?
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2017-3-31 03:28

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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