首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >几道趣味算法面试题

几道趣味算法面试题

作者头像
后端技术探索
发布2018-09-18 12:24:36
1.8K0
发布2018-09-18 12:24:36
举报
文章被收录于专栏:后端技术探索后端技术探索

文章来源:简书

1. 几道常见趣味算法面试题 1.1 绳子计时问题 1.2 两座岛运输加锁问题 1.3 马比赛问题 1.4 高楼逃生问题 1.5 对单链表排序,用代码实现 1.6 快速找到未知长度的单链表的中间节点2.算法学习建议及方法

1. 几道常见趣味算法面试题

1.1 绳子计时问题

阿里曾面过这道题目,有若干根相同的不均匀的绳子,烧完一根绳子的时间是1小时,问如何计时1小时15分钟?

答案:能计时出15分钟就好办了,可以用两根绳子并排反向放置,同时从两端点着,烧到交接处弄灭,拿出烧剩下的其中任意一根,再从两端同时点着,烧完就是15分钟。

1.2 两座岛运输加锁问题。

A、B两人分别在两座岛上。B生病了,A有B所需要的药。C有一艘小船和一个可以上锁的箱子。可以让C在A和B之间运东西,但东西只能放在箱子里。只要箱子没被上锁,C都会偷走箱子里的东西,不管箱子里有什么。如果A和B各自有一把锁和只能开自己那把锁的钥匙,那么问:A如何把东西安全递交给B?

答案:A把药放进箱子,用自己的锁把箱子锁上。B拿到箱子后,再在箱子上加一把自己的锁。箱子运回A后,A取下自己的锁。箱子再运到B手中时,B取下自己的锁,获得药物。

1.3 马比赛问题

有25匹马,速度都不同,但每匹马的速度都是定值。现在只有5条赛道,无法计时,即每赛一场最多只能知道5匹马的相对快慢。问最少赛几场可以找出25匹马中速度最快的前3名?(百度2008年面试题)

答案:每匹马都至少要有一次参赛的机会,所以25匹马分成5组,一开始的这5场比赛是免不了的。接下来要找冠军也很容易,每一组的冠军在一起赛一场就行了(第6场)。最后就是要找第2和第3名。我们按照第6场比赛中得到的名次依次把它们在前5场比赛中所在的组命名为A、B、C、D、E。即:A组的冠军是第6场的第1名,B组的冠军是第6场的第2名……每一组的5匹马按照他们已经赛出的成绩从快到慢编号: A组:1,2,3,4,5 B组:1,2,3,4,5 C组:1,2,3,4,5 D组:1,2,3,4,5 E组:1,2,3,4,5 从现在所得到的信息,我们可以知道哪些马已经被排除在3名以外。只要已经能确定有3匹或3匹以上的马比这匹马快,那么它就已经被淘汰了,即:A组的2、3名;B组的1、2名,C组的第1名。取这5匹马进行第7场比赛,第7场比赛的前两名就是25匹马中的2、3名。故一共最少要赛7场。

1.4 高楼逃生问题

阿里面试题。如你被困在一幢200米高的大楼的楼顶。你手里有一根150米长的绳子和一把瑞士军刀。你所站的地方有一个铁钩子。往楼下看时,你发现大楼正中间,也就是100米高的位置上,有一个可以落脚的金属支架,上面还有另外一个钩子,问用现在的工具如何安全到达地面。

答案:把绳子割成50米和100米两段。把50米绳子的一端拴在楼顶的钩子上,另一端打一个小环。让100米长的绳子穿过这个环,再把它的两头系在一起形成一个绳圈。沿着绳子爬到落脚点,把100米长的绳子割断并收回来,然后把其中一端拴在钩子上,沿着绳子爬到地面。

1.5 对单链表排序,用代码实现,

腾讯面试题

typedef struct Node {
    int data;
    struct Node *pNext;
} NODE, *PNODE;
//链表的长度
int length_list(PNODE pHead) {
    PNODE p = pHead->pNext;
    int len = 0;
    while (NULL != p) {
        ++len;
        p = p->pNext;
    }
    return len;
}
//对链表排序
void sort_list(PNODE pHead) {
    int i, j, t;
    int len = length_list(pHead);
    PNODE p, q;
    for (i = 0, p = pHead->pNext; i < len - 1; ++i, p = p->pNext) {
        for (j = i + 1, q = p->pNext; j < len; ++j, q = q->pNext) {
            if (p->data > q->data) {
                t = p->data;
                p->data = q->data;
                q->data = t;
            }
        }
    }
}
1.6 快速找到未知长度的单链表的中间节点

腾通讯面试题

普通解法:

遍历一遍单链表以确定单链表的长度L, 然后再次从头结点出发循环L/2次找到单链表的中间节点。 算法复杂度:O(L + L/2)=O(3L/2)。

利用快慢指针原理:

设置两个指针search, mid都指向单链表的头结点。其中search的移动速度是mid的两倍。但*search指向末尾节点的时候,mid正好在中间了。 代码实现(C语言)

typedef int ElemType;
typedef struct Node
{
    ElemType data; //数据域
    struct  Node *next; //指针域
} Node;
typedef struct Node *LinkList;
//快速找到未知长度单链表的中间节点 L:链表的头结点 *e返回的链表中间节点
bool GetMidNode(LinkList L, ElemType *e) {
    LinkList search, mid;
    mid = search = L;
    while (search->next != NULL) {
        if (search->next->next != NULL){
            search = search->next->next;
            mid = mid->next;
        } else {
            search = search->next;
        }
    }
    *e = mid->data;
    return true;
}

2.算法学习建议及方法

算法在求职以及工作后的重要性

求职面试必考(校招+社招),且国内工资越高的面试中算法比重就越大

我分别说一下国内和国外的行情。

国内的话,一般来讲,工资高的公司在面试时算法和数据结构题目的比重较大,工资一般的公司比重较小。当然同样公司的不同岗位,要求也会不同,但总体趋势就是 国内好公司爱考算法和数据结构 。这是目前国内互联网公司的情况。

国外的互联网公司呢,几乎只考算法和数据结构,很多年前就是这样了,一直如此。我相信国内会逐渐变得像国外一样,并不是崇洋媚外,而是算法和数据结构题目真的能考出东西。

先抛开算法,我们来说说面试以及如何准备。

面试中都会考什么呢?

面试中会考察算法,操作系统,数据库,计算机网络,编程语言,项目(校招涉及)/经历(社招中涉及的更多)

如何准备?

操作系统,数据库,计算机网络,编程语言这些都是平时学习,记住了,理解了,不忘记就可以了。

项目或者经历是平时准备的,如果马上面试了再去准备也是很难的,作假在面试中会直接被面试官看穿,所以这个平时就要准备好,如果是校招,那平时就要做一做有用的项目,如果是社招,平时在工作中就要用心做。

算法和数据结构,是真的需要好好写代码才能掌握,不是说看了理解了就真正会的了。算法笔试面试的特点就是没有特点,什么样的题都可能遇到,因为根本没有考纲,面试官就是普通的程序员,他们在工作中或者在网络上遇到什么题不错,就可能考,所以内容真的太多了,而且也无穷尽。这不是一个标准考试,这是能力考试。

所以,我建议大家面试或者笔试前抽出20%的时间去理解和记忆非算法和数据结构的题目,剩下的时间就是去刷题。

今天学习算法变得越来越重要,虽然每个公司行业不同、岗位复杂,但算法能力强是分析能力和解决问题能力的提现。虽然计算机的处理能力越来越强,但好算法的代码执行效率相比起没有优化的代码,已经不能用快多少倍来描述了。计算机科学有自己的衡量标准,也就我们常说的复杂度标准。同时,学习算法对理解底层实现是非常重要的,优秀的程序员专注细节和底层,具备算法能力是起点更是基础。包括今天很多的领域,比如机器学习,深度学习,还有大热的AI领域,想要研究透彻,都离不开算法好的大脑。还有很重要的,加薪和跳槽,算法都起着非常重要的作用。学习算法可不仅仅是刷题,这一过程中自己的思维和想法的提升才是学习算法的最大好处。

我是如何学习算法的?

本科在华中科技大学计算机学院,这一期间能在学业上让自己满意的可能就是没有挂科而已。硕士在芝加哥大学,出国之前就了解到想要在国外找工作的话,面试时几乎只考算法和数据结构的题目,于是开始了刷题,也就是搜集这方面的题,并且用代码实现出来,不断看题解和与高手讨论。 就这样从2010年到今天,刷了7年算法和数据结构的面试题。刚开始其实只是为了找工作才开始刷题,但是半年之后就变成了兴趣。

刚开始刷题的过程中很不顺利,因为很多算法和数据结构,教材也不会讲。而且去网上搜各种各样的分析文章也读不懂,感觉基础差的很远。当时网上的分析文章,也不会像今天这么易懂,高手都是把最核心的点说出来,但是我没摸到人家想说的点之前,就已经不会了。于是就把很多很厚的书拿来啃,书上也看不懂就尽可能的找到高手向人家请教。对书上的题目实现了好几遍,才发现入了门,头脑也开始活泛起来。遇到不会的就查,发现一大片知识不知道就练。在网上发帖被嘲笑的日子,其实非常的涨见识,我很珍视那段岁月。当时在国外,学费也贵,因为钱的刺激和好胜心,居然没有让我变态,而是变成了一种斗志,用了大量的时间好好刷题。刚开始代码实现算法和数据结构的题目真的非常痛苦,因为这部分的内容相比其他方面的知识绝对算高门槛,而我最开始的基础也并不好。现在我经常在网上给同学们讲题,看到同学们表达的抱怨,那简直就是当年的我。暗暗发下心愿,如果有一天讲课,绝对做一个人人都能听懂的好老师。但不管怎么引导,算法学习都是一个脱皮换骨的痛苦过程,但好在会迅速上瘾,坚持半年之后就能一直坚持下去了。

算法和数据结构问题的技术累积需要长时间的投入,因为内容又多又杂又难,很多算法是那种你很怀疑自己再来一辈子也可能想不到的解法。当时作为一个小白,一个算法的意思看懂了,实现起来是如此的难,测试用例总能指出我的幼稚;写了很多代码终于过了这一题,看到高手写的实现,自己又幻灭了,高手写的好棒,自己写的……然后收拾起碎裂一地的三观,重新出发。解了很多题目之后,类似的题目出现,自己还是会想很久。这让我意识到,自己缺乏总结,于是开始了总结的过程,也萌生了写书的冲动。刷完一道题其实是一件很难的事情,因为普通解法很容易,但是最优解真得去耐着性子研究好久,去查资料,去做优化,这个过程很漫长但是足够迷人。

到底应该怎样学习算法,作为过来人,给大家的建议

先跟大家聊聊算法吧。

在网络上流行一句话:算法分三种,竞赛的算法、面试的算法、算法。虽然我觉得这么分非常让人无语,但其实可以去这么理解,因为竞赛、面试和纯理论的要求和限制是不同的,所以算法在不同的要求中展现了不同的样子。

对于竞赛来说,每道题对输入参数和样本量的要求都是非常明确的,同时规定的非常明确的还有空间的限制和运行时间的限制。每一个竞赛选手都非常熟练怎么根据这些提前给好的限制,反推出自己需要实现一个什么样复杂度的解法才能通过。每一行代码包含着前辈和自己思考过的优化。

而对于面试来说,限制往往并不明确,造成这个现象的原因也很好理解。竞赛中当然是分数最重要。在面试的过程中,与面试官的交流和体现自己想事情的方式、体现自己逻辑的严密更重要。所以同一道题,在竞赛中必须写清楚限制,而在面试中一道题刚开始的限制没那么多,目的就是缩短你理解题目的时间,让面试者先写出一点什么,然后和面试官展开讨论,随着讨论的深入,再逐渐的把限制聊清楚。总之在面试的场合就是想看看你想问题的习惯、轨迹以及表达能力是否符合要求。

当然,不管是什么要求下的算法,经常练习算法和数据结构题目对一个人在逻辑上的提升都是显而易见的,在学校参加ACM并取得很好成绩的同学,如果不是表达能力特别差的话,是一定会收获很多offer的,因为思维被锻炼的很好。

对于算法,我给大家的建议

先找到线团,然后进入线团里学着怎么玩。为了进入线团,需要先把基础知识掌握好。《算法和数据结构》(教材),你一定要看完+理解。这里面讲的都是不能再基础的东西了,觉得讲得不好,自己搜维基百科。没办法,如果坚持不下来,你后面就受罪去吧。

然后有一些很经典的书可以迅速让你进入状态,比如我这本《程序员代码面试指南》,还有《剑指offer》,《程序员面试金典》这些好书。我在牛客网上还有一个针对小白的扫盲的课程:直通BAT — 求职算法精品课。

对于线上刷题平台的题目,先不找解答,先自己实现,实现的多烂,复杂度多差,都坚持写完。然后分析出复杂度。接下来去网上找答案,看到复杂度和你一样或比你低的,直接略过。看到比你好的,重点看,一定要理解,然后分析为什么比你的好,如果你真的理解了,你一定能找到别人优化的点。这个过程可能是最奇妙的过程,不要给自己太大压力,这个过程其实可以很欢乐,你有想法并创造出来,练习了自己的coding能力。别人有更好的实现,推翻了你的所有模型和幻想,你幻灭了,却也因此找到了让你血脉喷张方法。这个阶段看似苦,实际上其乐无穷。你在学习别人解法的过程中,又了解了很多算法和数据结构。而且你付出的每一滴汗水,都是结果导向的,可量化的,实实在在的。写写简单的测试函数就可以发现自己方法的运行时间和更好的解法就是没法比。这是一个非常培养自驱力的阶段,这是一个只追求解法更快更强的阶段。你看到很多经典的结构,你学到很多细思极妙的优化。比读那些让你吃力的书更加快乐,也能够一直启发你走下去。你苦苦寻找啊,觉得好的不能再好的方法啊,直到有一天,你突然看到一个更优的解法,相信我,你一定会一整天都在贤者时间里。

我不建议刚开始刷题的人就直接在网络上搜集文章开始学习,因为太散了,而且需要花很多时间去鉴别正确与否。当这些内容都掌握之后,再开始在网上搜集各种各样的题,并与网友参加各种各样的讨论,会比较高效。把底子打好之后,对于专项算法的学习就得心应手了,而且会学的很快。 对于很庞大的算法,我个人的习惯是找例子来引导自己的思路,一点一点的接近算法的核心。唯一需要注意的是,一定要写代码,光看没有用的。对于经典算法的学习,大体上分成几个阶段:

第一阶段:对于某一个具体的算法,首先要搞清楚这个算法解决的问题是什么,可能是实现一个具体的功能,也可能是在某些方面,比如时间复杂度或者空间复杂度方面很卓越,总之搞清楚这个算法被研究出来的目的是什么。

第二阶段:然后就要弄清楚这个算法的生存环境了,也就是看看你此时研究的东西是不是对别的知识有依赖,应该先把底层依赖的知识理解并掌握。这些问题都解决之后,就进入到算法本身的学习,理解一个算法是一件辛苦的事情,刚开始看必然会产生很多的困惑,比如经常会怀疑作者讲述的内容的重要性?这些内容和这个算法有什么联系呢?经常会有这种摸不着头脑的感觉,其实作者做的铺垫都是为了建立起描述算法主要内容的基础,只有接受和理解这些基础,才能逐渐触碰到算法的精髓,所以耐心是很重要的。

第三阶段:算法的主要过程看完之后,往往还是会感到困惑,主要是不知道这个过程好在哪,这就进入了下一个阶段,理解作者对这个过程在功能性或者效率卓越这件事上的解释和证明。这才真正触碰到算法最精髓的部分,也就是深度的理解算法的主要过程所带来的好处,这才是最锻炼人理解能力的地方。

第四阶段:上面几点是算法学习阶段的过程了,接下来就是研究算法的代码实现,自己设计测试用例亲自跑一下代码,以及从代码运行时间的角度分析这个算法的优势,这也是加深对算法的理解的过程。

第五阶段:最后是配合相应的题目练习,让自己通过题目练习的方式,会用、善用学习到的算法,并对这个算法产生一定的敏感程度,具体是指看到某些题目时,能够根据题目的特点,产生与该算法的对应,也就是具备举一反三的能力。

学习永无止境,不管是算法小白,还是有一定的算法基础,提升算法永远都是刚需,我正好要在牛客网即将开一个算法班,针对算法小白的初级班和有一定算法基础的进阶班,如果你想跟我一起学习,也欢迎你报名跟我一起探讨算法,希望所有努力和上心的人都能成为大牛。

本文参与 腾讯云自媒体分享计划,分享自微信公众号。
原始发表:2018-08-23,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 nginx 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 1. 几道常见趣味算法面试题
    • 1.1 绳子计时问题
      • 1.2 两座岛运输加锁问题。
        • 1.3 马比赛问题
          • 1.4 高楼逃生问题
            • 1.5 对单链表排序,用代码实现,
              • 1.6 快速找到未知长度的单链表的中间节点
              • 2.算法学习建议及方法
              相关产品与服务
              数据库
              云数据库为企业提供了完善的关系型数据库、非关系型数据库、分析型数据库和数据库生态工具。您可以通过产品选择和组合搭建,轻松实现高可靠、高可用性、高性能等数据库需求。云数据库服务也可大幅减少您的运维工作量,更专注于业务发展,让企业一站式享受数据上云及分布式架构的技术红利!
              领券
              问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档