一些简单的面试题精选(1)

屌丝又“扬言”要找工作了,所以要赶紧准备一下面试。实际上,按照我之前“找工作”的惯例,面试官都很注重项目经验,而对于算法、设计之类的问题,由于我遇到的这些面试官水平堪忧所以基本都难不倒我。不过,还是要准备一下,说不定下次面试的时候挂掉了呢?

下面我就选一些很简单的面试题,看看乃会不会在这些简单的问题上挂掉。

 

问题 1:写一个单例模式的 getInstance 方法。

问题分析:幼儿园级别的弱智问题,应该随手写出来。

回答 1-1:由于是单例模式,所以不论怎样都应该只有一个实例。万一两个线程同时访问这个方法咋办?那么当然就要加锁控制啦,用 Java 的话直接给方法加上 synchronized 好了,意思差不多的。So easy!

    private static DownloadService mInstance;
    
    public static synchronized DownloadService getInstance() {
        if (mInstance == null)
            mInstance = new DownloadService();
        
        return mInstance;
    }

分析 1-1:由于只有创建时才有竞争条件,因此每次访问这个方法都加锁是没必要的,这样写显然会被挂掉。

回答 1-2:对于已经有实例的情况下,直接返回就好了,没必要加锁;如果需要创建,则就需要加锁了。

    private static volatile DownloadService mInstance;

    public static DownloadService getInstance() {
        if (mInstance != null)
            return mInstance;
        
        synchronized (DownloadService.class) {
            if (mInstance == null)
                mInstance = new DownloadService();
            
            return mInstance;
        }

    }

分析 1-2:OK,可以做下一题了。

备注:根据 KC 提醒,mInstance 需要加上 volatile 修饰,以应对 Memory Barrier。

 

问题 2:有一个单链表,给你头结点以及一个指定结点的指针,要求删除这个结点。

问题分析:没技术含量的脑残问题,要求急速回答。

回答 2-1:先找到这个结点的前一个结点,然后把前一个结点的指针指向需要删除结点的下一个结点就好啦!

分析 2-1:由于是单链表,要找到前一个结点只能通过头结点,因此时间复杂度是 O(n),显然掉到陷阱里去了!

回答 2-2:哦,既然不能遍历找到前一结点,那么就采用“狸猫换太子”的方法好了。将要删除结点的数据置为下一结点的数据,并修改当前结点的指针指向再下一个结点,最后删除下一个结点。Done!

分析 2-2:聪明!不过肯定还要考虑一下特殊情况,否则给乃头结点的指针干啥?

回答 2-3:如果是尾结点,则不能狸猫换太子。这种情况只能用头结点找出前一个结点了,不过大部分情况仍然是 O(1)。

分析 2-3:下一题。

 

问题 3:乃有一个系统里面有 1000 亿条用户名,现在要求找出某个用户,如何设计这个系统。

问题分析:特么这也叫做面试题?哪有这么多用户?全球的人每个人注册 10 个账号都没这么多!目测只有算上外星人才够。真特么脑残的题!

回答 3:这么多记录全部存在内存里面是不行的,因此只能放在外部存储设备上。实际上能问这样的问题的面试官,也主要是想考察一下乃分析问题的能力,谁也不可能在短时间内给出一个合理的方案。

这么一大堆记录如果存储在硬盘上,如果是 SSD 硬盘的话倒还不错。但目前 SSD 硬盘相当昂贵,买这么大一块要花不少钱,如果乃像领导申请这么多预算目测会被喷死,因此放在机械硬盘上是一个经济上可行的方式。机械硬盘的随机访问显然相当耗时,一般需要 10-100 毫秒,如果采用二分法,1000 亿条记录大约需要 37 次硬盘访问,即使一些记录命中缓存,那么平均每条记录需要 0.2 – 2 秒的访问时间,这显然是不行的。

回忆一下以前学的 B+ 树,正好就是为这种硬盘访问所“量身定制”的。硬盘的读取方式是按块读取,这就意味着读取 1 字节和 512 字节没有啥区别,而 B+ 树的每个结点都有 N 个孩子结点。采用这种方式,我们的硬盘访问次数能够压缩在 8 次左右,勉强能够满足需求。

至于 Trie 树,在这种情况下不如 B+ 树好,因为有这么多记录那意味着名字都很长,访问次数会明显高于 B+ 树。

然而实际上这么多记录只用一台机器处理通常是不可取的,最好是采用分布式的解决方案。例如乃可以采用分布式的哈希表,或者使用 MapReduce 之类的来解决这个问题。这个老夫今后再总结一下。

一些简单的面试题精选(1)”的一个响应

      1. 玛德人家是要你设计这个系统啊,你都不看题目的么?

  1. 第一个问题里的Singleton不能这么写,会有memory barrier的问题(broken double-checked locking pattern),你要么把instance用volatile标记,强制fence,要么用一个inner class 包一下(这种情况的thread sfaty由 JVM的classloader保证)
    参见 http://stackoverflow.com/a/16106598/1746503

    第三个问题,用trie肯定是不行的。。这货内存开销大的一笔。。典型的空间换时间,而且你还要保证大部分的string都是有common prefix/postfix

    1. 确实应该加上 volatile,这个是疏忽了。关于 static 里面初始化的方式,虽然简单但有时候我们并不希望在类初始化时就创建实例。

发表评论

Fill in your details below or click an icon to log in:

WordPress.com 徽标

You are commenting using your WordPress.com account. Log Out /  更改 )

Google+ photo

You are commenting using your Google+ account. Log Out /  更改 )

Twitter picture

You are commenting using your Twitter account. Log Out /  更改 )

Facebook photo

You are commenting using your Facebook account. Log Out /  更改 )

Connecting to %s