• 和为某个值的数对

    和为某个值的数对

    一系列数,比如 1 2 3 4 5,和为 3 的数对只有 (1,2);和为 5 的数对有 (1,4)、(2,3)。现在问题是给 u 个序列和一个 sum,求出和为 sum 的所有数对。

    笨方法

    循环遍历序列的值 i,对于每个 i 再循环遍历 j (i ≠ j),如果 i + j == sum 那么就是一对。时间复杂度是 O(n2)。为了放置 (i,j) 和 (j,i) 都出现,可以让 j 从 i+1 开始遍历。

    好方法

    对于该题目,顺序遍历一遍是少不了的,在遍历到 i 的时候,其实 me 们关心的是 sum-i 是否存在。对于上面的笨思路是重复遍历了序列一遍,那么如果 me 们能高效地知道某一个元素是否在序列中,那么就有比较高效的解法。前面不管是使用数组/vector,还是使用 list,都需要 O(n) 的查找时间,如果选取 set 或是 map,则可以将查找的时间降得更低。me 赶脚更自然的结构应该是 set,虽然使用 map 也可以。

  • n的划分数

    求 n 的划分数

    将 n 表示成更小的自然数的和,叫做 n 的一个划分,比如 3 = 2 + 1, 3 = 1 + 1 + 1 ,(3 算不算 3 的一个划分不是重点,假定算吧)。下面是 6 的划分:

    6 的划分:( 11 个)
    = 6
    = 5 + 1
    = 4 + 2 
    = 4 + 1 + 1
    = 3 + 3 
    = 3 + 2 + 1 
    = 3 + 1 + 1 + 1
    = 2 + 2 + 2 
    = 2 + 2 + 1 + 1 
    = 2 + 1 + 1 + 1 + 1
    = 1 + 1 + 1 + 1 + 1 + 1
    

    可以数出来 1、2、3、4、5、6、7 的划分数分别是:1、2、3、5、7、11、15。现在问题就是如何求任意一个 n 的划分数,以及划分是神马 ?

  • 2014蘑菇街笔试题目

    Forums: 

    一、选择题

    1. 小于 20131015 的自然数中(包括 0)能被 3、5、7 整除的数有多少个 ?
    2. 一个单向链表,结点的 link 域指向下一个结点,现在要在 p 结点后插入一个新的结点 q,问正确操作是 ? (p、q 都是结点指针)
    3. 一副扑克牌,54 张,现在平均分成 3 堆,问大小王在同一堆的概率是多少 ?
    4. 下面哪些语句是错误的 ? A. a+=++a; B. a+=a++; C. (a++) += a; D. (++a) += a;

    二、推理题

    甲乙丙三个人打乒乓,每次两个人对打另外一个人做裁判,输的人下局当裁判。现在打了一上午,甲打了 x 局,乙打了 y 局,丙做裁判了 5 局,问第三局的比赛情况是怎么样的 ? (x, y 具体数字忘记了,O__O"…)

  • 2014百度笔试(10月13号)题目

    Forums: 

    一、简答题( 30 分 = 3 × 10 分)

    1. 请描述下 OSI 七层模型(开放式互连参考模型) ?
    2. 请列举下不同进程之间共享数据的方式(至少列出三种) ?
    3. 请描述下 TCP 和 UDP 的差别,并且各列举一个上层协议 ?

    二、算法与程序设计题( 45 分 = 3 × 15 分)

    1. 给出数据 A = [a0 , a1 , a2 , ... , an] (其中 n 可变),打印出该数值元素的所有组合。
    2. 有这样的数组 A,大小为 n,相邻元素的绝对值都是 1,比如 A = [4, 5, 6, 5, 6, 7, 8, 9, 10, 9]。现在给定 A 和一个目标整数 t,请找到 t 在 A 中的位置。
    3. 有一棵二叉树,定义树的高度为从根到叶子节点的最长距离,树的宽度为每层节点的最大值,树的面积定义为高度与宽度的乘积。写一个函数计算一个二叉树的面积。

    三、系统设计题( 25 分)

  • 2014蘑菇街面试

    Forums: 

    2014蘑菇街面试

    不提面试过程了,往事不堪回首,直接罗列一些问的问题吧。

    1. 说说 hadoop 和 Hive。(me 简历上有写使用 hive 的经历)
    2. 用过 Spring、Hibernate,说说项目中用过的缓存 ?
    3. Java 多线程,除了 Thread、Runnable 之外,有没有使用过 Callable 和 concurrency 这些东西 ?
    4. Java 集合类,有哪些 ? 使用过哪些 ? 有没有用过 SkipList ?
    5. 懂 JVM 吗 ?
    6. 精通 C++ 的 STL 嚒 ? 还是说也只是会用 ?
    7. 有参与过神马开源项目 ? 或是阅读过开源代码 ?
    8. 除了... 之外,平时对新技术是否关心 ?
    9. u 说了很多“本来想学,但是因为某些原因就没有学”,是神马原因 ? 时间限制 ? 平时加班严重么 ?
  • 百度面试问题

    Forums: 

    面经神马的暂时就不发了,心情有些抑郁,主要把面试的题目 record 下来,然后找找解答(不提项目有关的问题)。

    一面

    1. 说说 TCP 建立连接的三次握手,断开连接的四次握手 ? 为什么要这么设计 ?
    2. 懂哪些 linux 命令,或是说哪些比较熟 ?
    3. 给 u 两个 linux 绝对路径,路径中可能存在 // (多个斜杠)、/./、/../ 这些情况,请写程序判断是否是两个相同路径 ? (暂不考虑是否真的有这些路径,也不考虑 .a 这样的目录或是文件名)
    4. 在 40 亿个数中,找出 top k 个;
    5. 在一系列数中,找出和为某个固定值的数对,比如 1 2 3 4 5 和为4 的数对有 (1 3);

    二面

  • 2014华为面试

    Forums: 

    介个... 尼玛,(注意形象!),8:20 面试,ipad 闹钟定到 7:00,等 me 睁开眼的时候已经 7:40 了,O__O"… 早饭都赶不上吃,直接洗洗就骑车出发,路上赶脚都没有睡醒。还好 20 之前到达香格里拉酒店(面试地点)。看见俩熟人。听说今天很多面试,人人、蘑菇街、华为、百度...

    说正事。应该都是两面,一轮技术面,一轮 boss 面。me 每一面都不超过 20 分钟。赶脚太快了。一面是一个房间,里面很多座位,然后一对一面试;赶脚很噪杂,me 赶脚都听不清说话,O__O"… 二面是一个大房间,还是一对一,me 二面的时候里面貌似就俩三人在面试。一面是技术面,二面几乎不问技术,项目也问的不是很细致。

    一面那个人只问了三个技术问题

  • 2014年微软校招笔试题目

    Forums: 

    2014年微软校招笔试题目

    今年微软校招也真 tm 坑爹,10:00 - 12:00 笔试,10 点零几分才开始发答题卡,等卷子发完了发现考场三四十人没有卷子,O__O"… 后来卷子是一点一点发的,等 me 们拿到卷子,已经 10:30 以后了。虽然后来 me 们又加时了半个小时,不过精神损失是补不回来的。me 们当时吐槽,等 me 们卷子发下来的时候做得快的都交卷了。

    20 道选择题,100 分;一道编程题,50 分。两个小时。选择题每题 5 分,完全答对 5 分,半对 3 分,不选 0 分,错选 - 3 分,这个规定 me 已经麻木了。

  • 华为机试题目

    Forums: 

    在暑假实习之前网申了一次华为,暑假通知机试,后来没有去,本来也不抱太大希望来着,前两天通知今天机试。好吧,去就去吧,体验一下人生,~~~~(>_<)~~~~ 机试很不顺利,也可能是很久不写程序了,也可能是其他原因,尼玛,3 道题真正最对的只有一道,O__O"… 第一题最简单的计算题,例子的数据手算也算不对,纠结了太长时间。第二题倒是先做完。第三题,直到最后提交,8 个测试中有 3 个没有通过,晚上重写了下程序,才发现循环变量 i 在内层被修改了,O__O"… ,坑爹丫!!!

    早上坐车也,尼玛(咳咳,注意素质 !),晕车 ! 差点在车上吐了,O__O"… 后来坐到前面吹吹风勉强撑到滨江。机器上竟然是用的 VC6.0,最初的那台机器竟然一编译就崩溃 ! 换一台机器,尼玛,隔壁房间打电话的大哥能低调一点不,大家都听到了,~~~~(>_<)~~~~ 十二点回来,吃个饭,一下午身体不舒服。晚上参加百度宣讲,突然发现 me 学校的美女还是不少的,以前咋都米发现呢,~~~~(>_<)~~~~ (喂喂,跑题了...) 。

    下面是今天笔试的 3 道题,题目不涉及数据结构和算法,练练手还是不错的。

  • linux 的环境变量和一些文件

    linux 下 me 们很多时候是在 shell 中操作,即使装了桌面环境(Gnome 或是 KDE 或是 Xfce)。想设置环境变量(可能最常用的是 PATH )之类的操作,基本是在 shell 中设置;一些配置信息的修改也是在 shell 中。本篇就是介绍几个环境变量,以及几个文件,因为一些在 shell 中的配置只有放到文件中才是长久有效的。

    环境变量 PS1

    PS1 据说是 Prompt String One 的缩写,它的设定决定了命令提示的显示。windows 下的命令提示一般是:C:\Users\asus> 这样的;linux 下的一般是:[ant@ilovers ~]$ 这样的;me 相信有些人可能无意中看到过:[dp-bash4.2]$ 如此的。如果显示 bash4.2 类似的,往往是因为 PS1 设置的不大对或是没有设置,而系统使用了默认的设置,大眼一看应该是 bash 加上其版本号。

Pages