w****x
发帖数: 2483 | 1 struct NODE
{
vector vecGUID;
NODE* nodes[256];
NODE() { memset(nodes, 0, sizeof(nodes)); }
};
void _inner_get_guid(NODE* pNode, const char* str, int k, vector& vec)
{
if (NULL == pNode)
return;
if (k <= 0)
{
vec = pNode->vecGUID;
return;
}
_inner_get_guid(pNode->nodes[*str], str+1, k-1, vec);
}
vector getGUID(const char* str, NODE* pRoot, int k)
{
vector vecRet;
if (NULL == pRoot || NULL == str || *str == 0 || k <= 0)
return vecRet;
_inner_get_guid(pRoot, str, k, vecRet);
return vecRet;
}
int GetTimes(const char* str, NODE* pRoot, int k)
{
if (NULL == pRoot || NULL == str || k <=0)
return -1;
int nLen = strlen(str);
if (nLen < k) return 0;
hash_map mp;
int nRet = 0;
for (int i = 0; i < nLen-k+1; i++)
{
vector vec = getGUID(str + i, pRoot, k);
for (vector::iterator it = vec.begin(); it != vec.end(); it++)
{
if (mp.find(*it) == mp.end())
mp[*it] = 1;
else mp[*it]++;
nRet = max(nRet, mp[*it]);
}
}
return nRet;
}
void _inner_insert_trie(NODE* pNode, const char* p, int guid)
{
if (NULL == p || pNode == NULL ||*p == 0)
return;
if (pNode->nodes[*p] == NULL)
pNode->nodes[*p] = new NODE();
pNode->nodes[*p]->vecGUID.push_back(guid);
_inner_insert_trie(pNode->nodes[*p], p+1, guid); //p+1 not p++
}
NODE* BuildTrie(const char* strs[], int guids[], int n)
{
if (strs == NULL || n <= 0)
return NULL;
NODE* pRoot = new NODE();
for (int i = 0; i < n; i++)
{
const char* p = strs[i];
while (*p != 0)
_inner_insert_trie(pRoot, p++, guids[i]);
}
return pRoot;
}
void test()
{
const char* strs[] = {
"abcdeacdefjgs",
"fabcesdef",
"13fsdfas",
"dageqwe",
"sadgwerq",
"asfgeqwr",
};
int guids[] = {0, 1, 2, 3, 4, 5};
NODE* pRoot = BuildTrie(strs, guids, 6);
int x = GetTimes("abcdef", pRoot, 3);
}
刚才手写花了大概25分钟, 两个小bug, 当场是预处理有一半没写完（现场大概提供30
分钟）.
bug free是不追求了, 预处理没写完实在不因该, 想想自己居然从来没动手写过一个
trie...
忽然想起当年二爷在西雅图说的现场build trie树是基本要求， 当时想想没当回事，
果然关键时刻挂球了， 对二爷的敬仰又深了一层啊... |
p*****2
发帖数: 21240 | |
l*********8
发帖数: 4642 | 3 f吧
【在 p*****2 的大作中提到】
: 你这是哪公司的哪题呀？
|
p*****2
发帖数: 21240 | 4
什么题呀？
【在 l*********8 的大作中提到】
: f吧
|
t****a
发帖数: 1212 | 5 :-)，我也跟帖凑个热闹
把楼主的code重写了一遍，生成graphviz兼容的prefix tree然后产生出png图来。
总共只用了10行左右代码来产生前缀树。
code和结果图参见
http://kangtu.me/~kangtu/study/interview.html#sec-12 |
w****x
发帖数: 2483 | 6
很牛X啊， 难道是传说中的Python语言？
【在 t****a 的大作中提到】
: :-)，我也跟帖凑个热闹
: 把楼主的code重写了一遍，生成graphviz兼容的prefix tree然后产生出png图来。
: 总共只用了10行左右代码来产生前缀树。
: code和结果图参见
: http://kangtu.me/~kangtu/study/interview.html#sec-12
|
t****a
发帖数: 1212 | 7 不好意思阿，画出来的图貌似不对。我再琢磨琢磨。
【在 w****x 的大作中提到】
:
: 很牛X啊， 难道是传说中的Python语言？
|
k***x
发帖数: 6799 | 8 这种题目要是以前没见过，现场思考，再写code，还能来得及么。。。
【在 w****x 的大作中提到】
: struct NODE
: {
: vector vecGUID;
: NODE* nodes[256];
:
: NODE() { memset(nodes, 0, sizeof(nodes)); }
: };
: void _inner_get_guid(NODE* pNode, const char* str, int k, vector& vec)
: {
: if (NULL == pNode)
|
w****x
发帖数: 2483 | 9
这题肯定没人见过， 思考因该很快就可以想到，10秒，就是code出来比较麻烦，再加
上给面试官解释，不过够强的话也可以做到。
【在 k***x 的大作中提到】
: 这种题目要是以前没见过，现场思考，再写code，还能来得及么。。。
|
F**********0
发帖数: 442 | 10 看不懂，啥语言？
【在 w****x 的大作中提到】
: struct NODE
: {
: vector vecGUID;
: NODE* nodes[256];
:
: NODE() { memset(nodes, 0, sizeof(nodes)); }
: };
: void _inner_get_guid(NODE* pNode, const char* str, int k, vector& vec)
: {
: if (NULL == pNode)
|
|
|
h*****n
发帖数: 188 | 11 兄弟.. clojure自己玩玩还行..
面试是真心不行啊..
【在 t****a 的大作中提到】
: 不好意思阿，画出来的图貌似不对。我再琢磨琢磨。
|
y*******g
发帖数: 6599 | 12 我们team有用clojure
【在 h*****n 的大作中提到】
: 兄弟.. clojure自己玩玩还行..
: 面试是真心不行啊..
|
h*****n
发帖数: 188 | 13 赞！
【在 y*******g 的大作中提到】
: 我们team有用clojure
|
t****a
发帖数: 1212 | 14 勉强hack好了，不过还是弄不明白这里头的执行顺序，太诡异了，真不能随便用全局变
量阿。
http://kangtu.me/~kangtu/study/interview.html#sec-12
有愿意改进的朋友请指点指点
PS: 画digraph需要给结点赋予唯一的名称，而生成一个hashmap表示这个树就没这个限
制，容易多了。
【在 y*******g 的大作中提到】
: 我们team有用clojure
|
w****x
发帖数: 2483 | 15
呵呵， 挺有意思
【在 t****a 的大作中提到】
: 勉强hack好了，不过还是弄不明白这里头的执行顺序，太诡异了，真不能随便用全局变
: 量阿。
: http://kangtu.me/~kangtu/study/interview.html#sec-12
: 有愿意改进的朋友请指点指点
: PS: 画digraph需要给结点赋予唯一的名称，而生成一个hashmap表示这个树就没这个限
: 制，容易多了。
|
t****a
发帖数: 1212 | 16 为什么不能用clojure面试呢？
【在 h*****n 的大作中提到】
: 兄弟.. clojure自己玩玩还行..
: 面试是真心不行啊..
|
p*****2
发帖数: 21240 | |
y*******g
发帖数: 6599 | 18 主要是没几个面试官会。不容易判断水平
而且应用的实在太少。公司还是希望能判断出你的skill set是否match。
【在 t****a 的大作中提到】
: 为什么不能用clojure面试呢？
|
p*****2
发帖数: 21240 | 19
我发现大牛你怎么啥都会呀？
【在 y*******g 的大作中提到】
: 主要是没几个面试官会。不容易判断水平
: 而且应用的实在太少。公司还是希望能判断出你的skill set是否match。
|
c********t
发帖数: 5706 | 20 太牛了，拜服。
现场如果碰到这个题，俺只能从包里掏出算法书抄build trie
【在 t****a 的大作中提到】
: 勉强hack好了，不过还是弄不明白这里头的执行顺序，太诡异了，真不能随便用全局变
: 量阿。
: http://kangtu.me/~kangtu/study/interview.html#sec-12
: 有愿意改进的朋友请指点指点
: PS: 画digraph需要给结点赋予唯一的名称，而生成一个hashmap表示这个树就没这个限
: 制，容易多了。
|
|
|
t****a
发帖数: 1212 | 21 有道理阿...
我个人认为做data scientist到哪里几乎都得单枪匹马，还得高效率，所以养成就什么
快用什么的习惯，lisp / R / python组合 + literate programming我现在觉得是写
code最少的组合。
相比python和R，对付大规模计算的时候得上lisp，写的快run的也快。不过这些都是理
论知识，lisp菜鸟一枚。
linkedin的data scientist们都用啥兵器阿？
【在 y*******g 的大作中提到】
: 主要是没几个面试官会。不容易判断水平
: 而且应用的实在太少。公司还是希望能判断出你的skill set是否match。
|
y*******g
发帖数: 6599 | 22 囧，除了android和ios我没有一个能算会的。都是皮毛
现在正在努力学习javascript
【在 p*****2 的大作中提到】
:
: 我发现大牛你怎么啥都会呀？
|
l*****a
发帖数: 14598 | 23 有点OOD的思想好不？
拿这些C的东西来，不太合适
【在 w****x 的大作中提到】
: struct NODE
: {
: vector vecGUID;
: NODE* nodes[256];
:
: NODE() { memset(nodes, 0, sizeof(nodes)); }
: };
: void _inner_get_guid(NODE* pNode, const char* str, int k, vector& vec)
: {
: if (NULL == pNode)
|
y*******g
发帖数: 6599 | 24 不知道，下次和他们聊聊
感觉不同公司/team对这个title的理解不太一样 我接触的一个感觉就用pig什么
【在 t****a 的大作中提到】
: 有道理阿...
: 我个人认为做data scientist到哪里几乎都得单枪匹马，还得高效率，所以养成就什么
: 快用什么的习惯，lisp / R / python组合 + literate programming我现在觉得是写
: code最少的组合。
: 相比python和R，对付大规模计算的时候得上lisp，写的快run的也快。不过这些都是理
: 论知识，lisp菜鸟一枚。
: linkedin的data scientist们都用啥兵器阿？
|
p*****2
发帖数: 21240 | 25
这么说来你是完美的mobile大牛了。膜拜。
【在 y*******g 的大作中提到】
: 囧，除了android和ios我没有一个能算会的。都是皮毛
: 现在正在努力学习javascript
|
y*******g
发帖数: 6599 | 26 前端没前途，变得太快，天天忙于应付导致没什么设计，构架方面的积累。就记一些
api和有效期几个月的trick而已。
随便一个intern干2，3个月就到我的水平了。
二爷指点指点方向
【在 p*****2 的大作中提到】
:
: 这么说来你是完美的mobile大牛了。膜拜。
|
w****x
发帖数: 2483 | 27
面试官当时很轻描淡写的提了一下“可能有预处理加快效率”，但是说自己看着办，当
时马上想到trie了
【在 p*****2 的大作中提到】
: 这题一定要用trie吗？
|
w****x
发帖数: 2483 | 28
时间太紧张了，还得设计class接口什么的...
【在 l*****a 的大作中提到】
: 有点OOD的思想好不？
: 拿这些C的东西来，不太合适
|
t****a
发帖数: 1212 | 29 不敢当，偶就是个菜鸟初学者。这板上的题目好多都不会呢。
【在 c********t 的大作中提到】
: 太牛了，拜服。
: 现场如果碰到这个题，俺只能从包里掏出算法书抄build trie
|
l*****a
发帖数: 14598 | 30 就一个insert就够了
【在 w****x 的大作中提到】
:
: 时间太紧张了，还得设计class接口什么的...
|
|
|
l*****a
发帖数: 14598 | 31 其实二爷也根本没方向
没看还四处打听调查吗？
【在 y*******g 的大作中提到】
: 前端没前途，变得太快，天天忙于应付导致没什么设计，构架方面的积累。就记一些
: api和有效期几个月的trick而已。
: 随便一个intern干2，3个月就到我的水平了。
: 二爷指点指点方向
|
g**u
发帖数: 583 | 32
Mind to elaborate the question?
what's the guid used for? and what's the k used for?
thanks
【在 w****x 的大作中提到】
: struct NODE
: {
: vector vecGUID;
: NODE* nodes[256];
:
: NODE() { memset(nodes, 0, sizeof(nodes)); }
: };
: void _inner_get_guid(NODE* pNode, const char* str, int k, vector& vec)
: {
: if (NULL == pNode)
|
p*****2
发帖数: 21240 | 33
我比你惨多了。折腾来折腾去还是在C里边转悠。外边流行的技术什么都不会。
【在 y*******g 的大作中提到】
: 前端没前途，变得太快，天天忙于应付导致没什么设计，构架方面的积累。就记一些
: api和有效期几个月的trick而已。
: 随便一个intern干2，3个月就到我的水平了。
: 二爷指点指点方向
|
t*******2
发帖数: 292 | 34 学好C语言，走遍天下都不怕啊
【在 p*****2 的大作中提到】
:
: 我比你惨多了。折腾来折腾去还是在C里边转悠。外边流行的技术什么都不会。
|
p*****2
发帖数: 21240 | 35
我不知道我对题目理解的对不对，但是我可能先说说简单的算法，看他怎么说。
【在 w****x 的大作中提到】
:
: 时间太紧张了，还得设计class接口什么的...
|
p*****2
发帖数: 21240 | 36
问个OO问题就歇菜。
【在 t*******2 的大作中提到】
: 学好C语言，走遍天下都不怕啊
|
t****a
发帖数: 1212 | 37 光用pig的话做BI的工作都勉强，不用说探索性数据分析，建模和原型开发了。
Linkedin的scientists，肯定有绝活在手的。
【在 y*******g 的大作中提到】
: 不知道，下次和他们聊聊
: 感觉不同公司/team对这个title的理解不太一样 我接触的一个感觉就用pig什么
|
i***e
发帖数: 452 | 38 哥们， 你写的那么牛逼是不是让人觉得你背了答案呢？ 一般这种题目总要是说你的解
题思路。 然后让你实现一个insertion function或者是一个lookup的function. 这个
考察才算是合理范围之类的. 还有为啥guid都出来了？ 原题是什么来找？ |
w****x
发帖数: 2483 | 39
啊, 有人说hash table就可以了, 反正我说用trie那位老兄也不反对, 他说的题目很模
糊, 那个strs数组原来还说是存数据库里的, 存数据库不就是guid做索引吗, 还好我据
理力争化简成了数组. 不可能背答案, 这老兄说是他们工作中碰到的问题.
【在 i***e 的大作中提到】
: 哥们， 你写的那么牛逼是不是让人觉得你背了答案呢？ 一般这种题目总要是说你的解
: 题思路。 然后让你实现一个insertion function或者是一个lookup的function. 这个
: 考察才算是合理范围之类的. 还有为啥guid都出来了？ 原题是什么来找？
|
