锁定老帖子 主题:请教两道面试题
精华帖 (0) :: 良好帖 (0) :: 隐藏帖 (0)
|
|
---|---|
作者 | 正文 |
发表时间:2008-11-05
JavaWHB 写道 bcccs 写道 下一站,火星 写道 貌似很正确的扯淡,很多语言内置的字符串匹配都是基于KMP算法
基数排序是非比较排序算法,算法的时间复杂度是O(n)。从表面上看具有不小的优势.但事实上可能有些出入,因为基数排序的n可能具有比较大的系数K,你可以看到这些短信是一行一条,数据项的规模不是很大,实际情况下短信一般也是几十个字符甚至几个字符,所以根本没必要用Radix Sort! 且不说什么效率,偶现在怀疑你设计的方法的健壮性,偶的方法简单明了,即使用面向对象的语言也可以轻松实现,那么你是否能给一个清晰的过程,而不是随便说说,什么hash,什么二次hash,什么retrieve tree,偶想知道你的准确的过程………… /*** *strcmp.c - routine to compare two strings (for equal, less, or greater) * * Copyright (c) Microsoft Corporation. All rights reserved. * *Purpose: * Compares two string, determining their lexical order. * *******************************************************************************/ #include <cruntime.h> #include <string.h> #ifdef _MSC_VER #pragma function(strcmp) #endif /* _MSC_VER */ /*** *strcmp - compare two strings, returning less than, equal to, or greater than * *Purpose: * STRCMP compares two strings and returns an integer * to indicate whether the first is less than the second, the two are * equal, or whether the first is greater than the second. * * Comparison is done byte by byte on an UNSIGNED basis, which is to * say that Null (0) is less than any other character (1-255). * *Entry: * const char * src - string for left-hand side of comparison * const char * dst - string for right-hand side of comparison * *Exit: * returns -1 if src < dst * returns 0 if src == dst * returns +1 if src > dst * *Exceptions: * *******************************************************************************/ int __cdecl strcmp ( const char * src, const char * dst ) { int ret = 0 ; while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst) ++src, ++dst; if ( ret < 0 ) ret = -1 ; else if ( ret > 0 ) ret = 1 ; return( ret ); } 来,今天开完会,没事,专治各种信口开河。 对于不懂的东西,虚心一些,会死么?虽然我可以让你永远以为你算法很厉害,不过我很无聊,我决定用别的方式玩。 能给个java版的吗?这句没看明白: while( ! (ret = *(unsigned char *)src - *(unsigned char *)dst) && *dst) ++src, ++dst; 上面的意思就是要保证:1<=pos(出现在被查找字符串位置)<=length(src) |
|
返回顶楼 | |
发表时间:2008-11-05
最后修改:2008-11-05
下一站,火星 写道
bcccs 写道
下一站,火星 写道
bcccs 写道
下一站,火星 写道
bcccs 写道
下一站,火星 写道
to JavaWHB:这段代码又不是他写的,估计他也不是很明白…………
to 老刑:java是不是kmp不重要,这里只是举个python perl的例子,重要的是你要搞明白,java的内置算法肯定是经过优化的,难道sun公司的人是吃白饭的? 这个题目是面试题,主要是说清楚你的思路,在真实的开发中和你拿个算法玩是2回事,关键的是你能拿出一套清晰可行的方案,再去扯什么效率的问题,我面试的时候最讨厌什么都是貌似什么凭感觉,概念满天飞,可行性呢?有几个公司花钱供你去研究理论算法的? 如果你给我钱,我可以给你写一个也无所谓。你听不懂hash,听不懂retrieve tree,听不懂二次hash,其实你需要读书,而不是装X
哈哈,你直接说你说不清不就得了,我前面已经给出了一个相当简洁的思路,你说我哪里装X了?而且即使偶装X又如何?
另外可以告诉你,你需要去补习python的知识,内置的api很多来源于库,不仅仅指语言的内核,基本上所有的语言都有KMP库函数支持,还要偶花钱请你写?偶还不放心呢:)
你没有看到我贴给你语言内核,啥叫string_eq?不过你这么理解kmp,很让人欣慰啊。。。呵呵
得,你先心理自我安慰一下吧,我真不知道你想说什么,你要是有本事就今晚上写一个小程序试试,看你那么牛的,对吧?
对了,偶现在可不敢说你的算法不好,反正是你主动找偶的,但其实和偶一毛钱的关系也没有:)
只是无聊,看你比较讨厌,就玩玩。
老大,我怎么讨厌了?我只是给出一个简洁的方法和你有关系吗?其实你的方法不是不行,就是太麻烦了,在真实的场景下偶肯定不会做,成本上吃不消:)
robbin都说了,有的时候就是看有些人不顺眼啊。需要理由么?看人不顺眼是每个人的权力。 |
|
返回顶楼 | |
发表时间:2008-11-05
bcccs 写道
下一站,火星 写道
bcccs 写道
下一站,火星 写道
bcccs 写道
下一站,火星 写道
bcccs 写道
下一站,火星 写道
to JavaWHB:这段代码又不是他写的,估计他也不是很明白…………
to 老刑:java是不是kmp不重要,这里只是举个python perl的例子,重要的是你要搞明白,java的内置算法肯定是经过优化的,难道sun公司的人是吃白饭的? 这个题目是面试题,主要是说清楚你的思路,在真实的开发中和你拿个算法玩是2回事,关键的是你能拿出一套清晰可行的方案,再去扯什么效率的问题,我面试的时候最讨厌什么都是貌似什么凭感觉,概念满天飞,可行性呢?有几个公司花钱供你去研究理论算法的? 如果你给我钱,我可以给你写一个也无所谓。你听不懂hash,听不懂retrieve tree,听不懂二次hash,其实你需要读书,而不是装X
哈哈,你直接说你说不清不就得了,我前面已经给出了一个相当简洁的思路,你说我哪里装X了?而且即使偶装X又如何?
另外可以告诉你,你需要去补习python的知识,内置的api很多来源于库,不仅仅指语言的内核,基本上所有的语言都有KMP库函数支持,还要偶花钱请你写?偶还不放心呢:)
你没有看到我贴给你语言内核,啥叫string_eq?不过你这么理解kmp,很让人欣慰啊。。。呵呵
得,你先心理自我安慰一下吧,我真不知道你想说什么,你要是有本事就今晚上写一个小程序试试,看你那么牛的,对吧?
对了,偶现在可不敢说你的算法不好,反正是你主动找偶的,但其实和偶一毛钱的关系也没有:)
只是无聊,看你比较讨厌,就玩玩。
老大,我怎么讨厌了?我只是给出一个简洁的方法和你有关系吗?其实你的方法不是不行,就是太麻烦了,在真实的场景下偶肯定不会做,成本上吃不消:)
robbin都说了,有的时候就是看有些人不顺眼啊。需要理由么?
感觉你是个没有头脑的人,动不动就是谁谁谁说的什么话,自己一点idea都没有,偶懒的和你这样的人继续扯淡,拜…………
|
|
返回顶楼 | |
发表时间:2008-11-05
要说到使用hash算法,这里说个自己的想法:
但是我觉得最终还是不能逃脱KMP的算法,它是一个微观处理内部字符的结果。 当然你这里有个超大型的数量集合,那也就是存在还需要在这个基础上再次获得一个高效的算法,这里想到:链式散列存储方式: 我们知道hash表的查找其实就是一个实质的数组形式,通过key-value的方式来得到。其中:在内存中的地址无非就是采用key和hash的方式来获得索引号。这样就可以对应我们的value。但是当中的一旦存在有所谓的冲突,就是LZ这里相同情况,改如何解决?很简单,不同的话通过散列分布到各个内存当中,一旦冲突,即可把冲突的链接到上次一相同或者说冲突的后面链接位置。同时通过一个累加器来获得冲突多少次。 以上就是一个大概的描述! |
|
返回顶楼 | |
发表时间:2008-11-05
KMP的方式最好的时间复杂度,如果没有记错应该是:O(1)
|
|
返回顶楼 | |
发表时间:2008-11-05
下一站,火星 写道
bcccs 写道
下一站,火星 写道
bcccs 写道
下一站,火星 写道
bcccs 写道
下一站,火星 写道
bcccs 写道
下一站,火星 写道
to JavaWHB:这段代码又不是他写的,估计他也不是很明白…………
to 老刑:java是不是kmp不重要,这里只是举个python perl的例子,重要的是你要搞明白,java的内置算法肯定是经过优化的,难道sun公司的人是吃白饭的? 这个题目是面试题,主要是说清楚你的思路,在真实的开发中和你拿个算法玩是2回事,关键的是你能拿出一套清晰可行的方案,再去扯什么效率的问题,我面试的时候最讨厌什么都是貌似什么凭感觉,概念满天飞,可行性呢?有几个公司花钱供你去研究理论算法的? 如果你给我钱,我可以给你写一个也无所谓。你听不懂hash,听不懂retrieve tree,听不懂二次hash,其实你需要读书,而不是装X
哈哈,你直接说你说不清不就得了,我前面已经给出了一个相当简洁的思路,你说我哪里装X了?而且即使偶装X又如何?
另外可以告诉你,你需要去补习python的知识,内置的api很多来源于库,不仅仅指语言的内核,基本上所有的语言都有KMP库函数支持,还要偶花钱请你写?偶还不放心呢:)
你没有看到我贴给你语言内核,啥叫string_eq?不过你这么理解kmp,很让人欣慰啊。。。呵呵
得,你先心理自我安慰一下吧,我真不知道你想说什么,你要是有本事就今晚上写一个小程序试试,看你那么牛的,对吧?
对了,偶现在可不敢说你的算法不好,反正是你主动找偶的,但其实和偶一毛钱的关系也没有:)
只是无聊,看你比较讨厌,就玩玩。
老大,我怎么讨厌了?我只是给出一个简洁的方法和你有关系吗?其实你的方法不是不行,就是太麻烦了,在真实的场景下偶肯定不会做,成本上吃不消:)
robbin都说了,有的时候就是看有些人不顺眼啊。需要理由么?
感觉你是个没有头脑的人,动不动就是谁谁谁说的什么话,自己一点idea都没有,偶懒的和你这样的人继续扯淡,拜…………
我本来就是个没有头脑的人,不像你,把string equal掰出来一个kmp,知道kmp干嘛的么?
|
|
返回顶楼 | |
发表时间:2008-11-05
yeshucheng 写道 KMP的方式最好的时间复杂度,如果没有记错应该是:O(1)
继续扯!!怎么无知且无畏的人那么多,当个程序员,连基本的google都不做,就敢扯。 |
|
返回顶楼 | |
发表时间:2008-11-05
你承认就好,哥哥,kmp是偶提出来的,你本来就不知道,给你普及下有错吗,好了,你别打扰偶了,和你说话真累,你就学yeshucheng拿出一个具体的流程再找偶也不迟呀:)
|
|
返回顶楼 | |
发表时间:2008-11-05
bcccs 写道 yeshucheng 写道 KMP的方式最好的时间复杂度,如果没有记错应该是:O(1)
继续扯!!怎么无知且无畏的人那么多,当个程序员,连基本的google都不做,就敢扯。 呵呵,应该是O(m+n) |
|
返回顶楼 | |
发表时间:2008-11-05
下一站,火星 写道 你承认就好,哥哥,kmp是偶提出来的,你本来就不知道,给你普及下有错吗,好了,你别打扰偶了,和你说话真累,你就学yeshucheng拿出一个具体的流程再找偶也不迟呀:)
kmp是查找子串的,比较两个短信是否相同需要查找子串? |
|
返回顶楼 | |