论坛首页 招聘求职论坛

请教两道面试题

浏览 18417 次
精华帖 (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)
0 请登录后投票
   发表时间: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都说了,有的时候就是看有些人不顺眼啊。需要理由么?看人不顺眼是每个人的权力。

0 请登录后投票
   发表时间: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都没有,偶懒的和你这样的人继续扯淡,拜…………

 

0 请登录后投票
   发表时间:2008-11-05  
要说到使用hash算法,这里说个自己的想法:
但是我觉得最终还是不能逃脱KMP的算法,它是一个微观处理内部字符的结果。

当然你这里有个超大型的数量集合,那也就是存在还需要在这个基础上再次获得一个高效的算法,这里想到:链式散列存储方式:

我们知道hash表的查找其实就是一个实质的数组形式,通过key-value的方式来得到。其中:在内存中的地址无非就是采用key和hash的方式来获得索引号。这样就可以对应我们的value。但是当中的一旦存在有所谓的冲突,就是LZ这里相同情况,改如何解决?很简单,不同的话通过散列分布到各个内存当中,一旦冲突,即可把冲突的链接到上次一相同或者说冲突的后面链接位置。同时通过一个累加器来获得冲突多少次。

以上就是一个大概的描述!
0 请登录后投票
   发表时间:2008-11-05  
KMP的方式最好的时间复杂度,如果没有记错应该是:O(1)
0 请登录后投票
   发表时间: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干嘛的么?

 

 

0 请登录后投票
   发表时间:2008-11-05  
yeshucheng 写道
KMP的方式最好的时间复杂度,如果没有记错应该是:O(1)

继续扯!!怎么无知且无畏的人那么多,当个程序员,连基本的google都不做,就敢扯。
0 请登录后投票
   发表时间:2008-11-05  
你承认就好,哥哥,kmp是偶提出来的,你本来就不知道,给你普及下有错吗,好了,你别打扰偶了,和你说话真累,你就学yeshucheng拿出一个具体的流程再找偶也不迟呀:)
9 请登录后投票
   发表时间:2008-11-05  
bcccs 写道
yeshucheng 写道
KMP的方式最好的时间复杂度,如果没有记错应该是:O(1)

继续扯!!怎么无知且无畏的人那么多,当个程序员,连基本的google都不做,就敢扯。

呵呵,应该是O(m+n)
0 请登录后投票
   发表时间:2008-11-05  
下一站,火星 写道
你承认就好,哥哥,kmp是偶提出来的,你本来就不知道,给你普及下有错吗,好了,你别打扰偶了,和你说话真累,你就学yeshucheng拿出一个具体的流程再找偶也不迟呀:)


kmp是查找子串的,比较两个短信是否相同需要查找子串?
0 请登录后投票
论坛首页 招聘求职版

跳转论坛:
Global site tag (gtag.js) - Google Analytics