V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX 提问指南
tongz
V2EX  ›  问与答

一道「算法」面试题

  •  
  •   tongz · 2017-08-18 09:00:58 +08:00 · 3892 次点击
    这是一个创建于 2653 天前的主题,其中的信息可能已经有所发展或是发生改变。

    有一个写字楼有 28 层,每层有 4 个区,每个区有 8 个办公室,有 7 个电梯,每天早高峰有 1 万人上班。怎么做能以最快的速度将早高峰的人送到他们的楼层?(20 分) 1.请做出一些假设 2.请描述你的算法 3.请仿真并实现你的算法 4.请计算出需要的时间

    36 条回复    2017-08-18 16:12:39 +08:00
    tongz
        1
    tongz  
    OP
       2017-08-18 10:01:18 +08:00
    没有大佬来解答吗。。
    v9ox
        2
    v9ox  
       2017-08-18 10:06:26 +08:00 via iPhone
    这不是算法题。
    meepo3927
        3
    meepo3927  
       2017-08-18 10:08:44 +08:00
    这是实际问题吧。
    非常非常实际的问题。
    chisoco
        4
    chisoco  
       2017-08-18 10:10:54 +08:00
    这是建模啊
    chenyu8674
        5
    chenyu8674  
       2017-08-18 10:29:26 +08:00   ❤️ 2
    没明白电梯跟办公室有什么关系,如果只说楼层间运输的话,初步想法为:
    1 号梯:1,2,3,4 层
    2 号梯:1,5,11,17,23 层
    3 号梯:1,6,12,18,24 层
    4 号梯:1,7,13,19,26 层
    5 号梯:1,8,14,20,26 层
    6 号梯:1,9,15,21,27 层
    7 号梯:1,10,16,22,28 层
    保证每层都有电梯直达,有急事的坐进最近的电梯最多上下 3 层楼就能到达目的楼层
    irexy
        6
    irexy  
       2017-08-18 10:30:03 +08:00
    “每层有 4 个区,每个区有 8 个办公室” 这个条件有什么用?
    billion
        7
    billion  
       2017-08-18 10:33:15 +08:00
    1.假设所有电梯全部独立,没有联动
    2.假设有一个人拿着一把刀,如果发现有人点了多个电梯,就砍死他。
    tongz
        8
    tongz  
    OP
       2017-08-18 10:34:30 +08:00
    @meepo3927
    我也纳了闷了,昨天有个朋友面试回来在群里问的,没想出来这题有什么好办法解决。
    tongz
        9
    tongz  
    OP
       2017-08-18 10:36:46 +08:00
    @chenyu8674 和我想的差不多,在这个基础上,有急事的就走楼梯呗。
    Microi
        10
    Microi  
       2017-08-18 10:38:50 +08:00
    电梯限载几人啊?
    tongz
        11
    tongz  
    OP
       2017-08-18 10:41:05 +08:00
    @Microi
    没有这个条件,估计是那条 “请做出一些假设”吧
    davy1995
        12
    davy1995  
       2017-08-18 10:41:53 +08:00 via Android
    @chenyu8674 一楼还要啥电梯
    SuperMild
        13
    SuperMild  
       2017-08-18 10:44:34 +08:00
    在上面限楼层的方案的基础上,再限时段,假设高峰期有 1 个小时,那前半个小时 1 号梯就只上 2 层、3 层,后半个小时就只上 4、5 层,便于员工分流别全挤在一起排队。
    davy1995
        14
    davy1995  
       2017-08-18 10:45:27 +08:00 via Android
    @chenyu8674 早高峰上楼是不是可以把 1 楼去掉,给下楼的留一个带一楼的电梯就好了
    nazor
        15
    nazor  
       2017-08-18 10:49:27 +08:00 via iPhone
    28 正好 7 的倍数,楼层除以 7 取余数决定乘哪个电梯,再规定 1 楼每个电梯都能到达。
    chenyu8674
        16
    chenyu8674  
       2017-08-18 11:05:08 +08:00
    @davy1995 1 楼不停咋上人?
    davy1995
        17
    davy1995  
       2017-08-18 11:14:10 +08:00 via Android
    @chenyu8674 😂我的
    wukongkong
        18
    wukongkong  
       2017-08-18 11:16:34 +08:00
    @billion 好方法~
    jason19659
        19
    jason19659  
       2017-08-18 11:45:54 +08:00
    这一万是不是能挤进一个电梯里
    tongz
        20
    tongz  
    OP
       2017-08-18 11:48:45 +08:00
    @jason19659
    可以,假设一个电梯可以乘坐 10000 人。
    那么其他 6 个电梯围观就可以了。
    GreatHumorist
        21
    GreatHumorist  
       2017-08-18 11:55:57 +08:00 via iPhone   ❤️ 3
    看看硬盘读取算法,基本一致,28 层就是盘片,分区就是扇区,办公室就是存储单元。建议看下操作系统原理。
    misaka19000
        22
    misaka19000  
       2017-08-18 11:56:51 +08:00 via Android
    额,这不就是电梯算法吗,Linux 就是用这个算法进行磁盘任务调度的
    GreatHumorist
        23
    GreatHumorist  
       2017-08-18 11:56:58 +08:00 via iPhone
    不过这个只是比磁盘的磁头多,用磁盘读取算法优化一下应该就可以
    sunjourney
        24
    sunjourney  
       2017-08-18 11:58:33 +08:00
    最好的算法就是你让他们自己选,选一个月以后,大家各自知道各自上哪个电梯了
    shalk
        25
    shalk  
       2017-08-18 12:28:12 +08:00 via iPhone
    这是建模题 条件不充分也很开放
    cokepro
        26
    cokepro  
       2017-08-18 13:03:44 +08:00
    @sunjourney 遗传算法?
    mkdong
        27
    mkdong  
       2017-08-18 13:36:03 +08:00 via iPhone
    @tongz 假设所有人都在一楼工作哈哈哈 7 个电梯一起围观
    skadi
        28
    skadi  
       2017-08-18 14:04:28 +08:00 via Android
    来个 b 树?
    chinvo
        29
    chinvo  
       2017-08-18 14:15:21 +08:00
    让这 1w 人跑楼梯(逃
    misaka20038numbe
        30
    misaka20038numbe  
       2017-08-18 14:29:58 +08:00
    每层有四个区,所以将 4 个电梯分成每个区对应一个专用电梯
    剩 3 个电梯作为公共电梯,4 个区都可用,一个电梯直上另一个电梯就直下,剩一个可上可下。
    tao1991123
        31
    tao1991123  
       2017-08-18 14:55:53 +08:00
    @sunjourney 你这个叫做遗传算法......
    nosugar
        32
    nosugar  
       2017-08-18 15:00:24 +08:00
    windows: \r\n
    unix(linux,mac): \n
    wiki: https://en.wikipedia.org/wiki/Newline
    nosugar
        33
    nosugar  
       2017-08-18 15:00:58 +08:00
    tongz
        34
    tongz  
    OP
       2017-08-18 15:08:53 +08:00
    @GreatHumorist 谢谢,学习了。
    LancerEvo
        35
    LancerEvo  
       2017-08-18 15:19:48 +08:00   ❤️ 1
    我的一点分析,并非解答:


    首先假设早高峰 60 分钟,1 万人,除去 1 层的,7 电梯,平均每个电梯每分钟运 23 人,而正常大小的电梯至少得两趟才能运 23 人,也就是说半分钟一趟,平均楼层 14.5,往返,加开门关门上下人,这个题目是不可能的。

    不过题目允许你自己假设,你可以假设早高峰有俩小时,某个楼层的只能某个时间段来,就完了。

    但我感觉这并不是题目的本意,题目的本意应该是假设所有人同时到,或者在某个时间段内随机到,如何运作电梯最有效,或者所有人总的等待时间最短。

    然后题目里的区和办公室看起来没用,因为题目并没有限定说某个电梯只能到某个区。


    前头的回答里,每层只有一个电梯能到,从而保证每个电梯都停的次数最少,直观感觉是最快的,因为毕竟停、上下人、再启动是最耗时的,但实际中,这是否比有两个电梯都能到达某一层从而减少了等待时间更好,我没验证过。

    之所以我有这个质疑,1 是因为我原来公司正好 28 层,6 电梯,如果没记错是 3 个能到 1-x 层的,另外 3 个是 x 以上高楼层的,实际体验不错,然而另外某人力公司也是在 28 层左右,也是有 6 电梯,但貌似只有 1 个还是 2 个能到 28 层,实际体验很糟糕,总要等很久; 2 是因为实际中貌似很少有某个写字楼只有一个电梯能到某一层的,并且也没见过哪儿是求余来安排的尽量分散的,我猜可能是因为停 2-3-4 层的平均运行速度未必比停 5-10-15 要慢,要想加速可能得停 5-25 这样才能体现出来。记得原来某个公司电梯是 5-19 之间不停,期间速度明显是要快于隔两层停一下的。各大电梯厂商应该想的比我明白,我相信他们的算法就是最优的,即使不是,也是经过很久的时间检验的,比我连实验都没做要强的多。


    只提一句磁盘读取算法的各位,说这个等于没说,估计只知道磁盘读取用的电梯算法但不知道到底算法是啥。

    磁盘读取算法只是请求排序之后先往一头扫,到头以后再往回扫( SCAN )或者从 0 再开始扫( C-SCAN )。早高峰上到头再下到 0 层(或者 1 层,取决于你的哲学观点)这本身就是 C-SCAN,没有任何人傻到想出一个非 C-SCAN 的先停 4 层下人再回到 3 层下人再上到 5 层下人的算法的。

    如果能谈谈单盘片单盘面多磁头的调度,才是本题。


    说多了,我感觉出题人没想到我这么多,233,可能人就是想让你写个代码解决个实际问题看看你 coding 能力。
    silencefent
        36
    silencefent  
       2017-08-18 16:12:39 +08:00
    @chenyu8674 你这个思路只是苦了送外卖 /快递的,因为只考虑上下班不考虑楼层上下
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   2723 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 26ms · UTC 13:28 · PVG 21:28 · LAX 05:28 · JFK 08:28
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.