微软今天的笔试题目 zz from 88 :: connecting dots of life

connecting dots of life 不再迷失的Jet hotbit@163.com .: 发表评论 :. .: 最后更新 :. future days Hey! Jude 会议纪要 我的小白老妹 工作中是不是应该做杂事? 闲聊空间 前两天看到的一句话 讲一个挺逗的事情 健康 贴张老照片 :: << 无题 | 首页 | [转载]路黑风高——我的找工被摔实录 >> 微软今天的笔试题目 zz from 88 本来以 为 MS 不会消息的我 , 今天按 时 参加了微 软 的第三 轮 笔 试 , 也 应该 是今年校园招聘的最 后一 轮 笔 试 了 . 并没有特 别 想 进 MS 的意思 , 不 过 如果有机会 进 研究院 ,Why not? 笔 试 和我以前听 说 的不太一 样 , 也 许 就是 这样 吧眼 见为实 , 亲 身体会 过 才会有真 实 的感受 . 不 过总 体感 觉 微 软 的笔 试 是比 较 全面的 , 他 们 看重的并不是死板的 书 本 , 的确是你的解决 问题 和 观 察的能力 . 题 目不少 , 时间 如果不抓 紧 , 也 许 来不及 ... 共分 为 五部分 第一部分 选择题 , 是多 项选择题 , 第二 题 分是 逻辑题 也是多 项选择题 , 第三部分是 编 程 , 这 次 只考了一 题 , 第三四部分是 设计 , 第三部分是 测试 ... 所有的内容大部分 focus 在数据 结 构和 C/C++ 上 . 不 过 微 软 的确是和 别 的公司不太一 样 , 有些 题 目 给 我留下了很深的印象 ... 从 选择题说 起吧 . 1. ∑ aq^i=, 高中的等比数列求和公式 2. 排序算法 复杂 度 问题 , 最差的是 O(n^2), 平均是 O(nlogn 的是 还 有 类 的 继 承与虚函数 问题 , 记 得很清楚的一些 题 ■下面的程序 输 出是什 么 , 在 X86 机器上 void main() { char *pBytes=new char[100]; int * pInt; pInt = (int *)pBytes; pInt++; *pInt = 0X20304050; pBytes += 5; printf("%d",*pBytes); } 答案是 64, 因 为 在 X86 机器上 int 是按 little endian 来存 储 的 , 在内存中的存 储顺 序是 05 04 03 02, 从低地址到高地址 .. 这题错 了 , 心服口服 . ■哈夫曼 编码对 一些字符 进 行 编码 , 已知一个字符的 编码 是 10011, 那 么 , 哪些 编码 不可能是 一个字符 编码 . 这题 一 开 始 给 蒙了一下 , 以 为 要考哈夫曼的 detail, 不 过 后来被我 发现 了一个 问题 , 哈夫曼 编 码 只会 对 叶子 结 点 进 行 , 那 么 非叶子 结 点一定不会 进 行 编码 , 因此 1,1001 这样 的一定不是字 符的 编码 ■两个 unsigned 类 型的整数 a,b, 如果已知 a+b=c 发 生了 overflow, 这时 c 满 足什 么 条件 . 这 是一道很有意思的 题 目 , 我 们 来仔 细 看看吧 . 设 一个 unsigned int 的最大能表示的整数是 D, 那 么 一定有 D 是全 1 的二 进 制数 , (1)a+~a=D,b+~=D 这时 c 中存的数是 a+b-(D+1) 由一中的式子有 c=a+b-(D+1)=a+(D-b)-1=a-~b-1,c-a=-~b-1<0 同理 c=a+b-(D+1)=b-(D-a)-1=b-~a-1,c-b=-~a-1,c<a,c<b 正确的答案是 c<a,c<b ■ 还 有一 题 是考位操作 , 我 发现 位操作是所有做 软 件都 爱 考的 , 一定要注意啦 . ■ 还 有一 题 是 问树 如果知道哪两 种 遍 历顺 序就可以重构 这 个二叉 树 , 必 须 有中序遍 历 和前序 或后序 组 合成 , 还 好数据 结 构的 东东还 算 记 住了 ■ 还 有一 题 是 问 windows API 可是什 么 函数 , 我没有 头绪 只 选 了 类 的静 态 函数和全局函数 ■ 还 有一 题 是 问时 程通 讯 的 问题 , 放弃 , 偶就是 对进 程 这东东 不太清楚 , 没 办 法 , 认 命吧 . 第二部分是 逻辑 , 对 中国学生来 说 , 绝对 的是 EASY 啊 ... 十五分 钟 搞定 .... 共有四个大 题 ... 第三部分是 编 程 , 是找出一个二叉 树 中任意两个 节 点的最年 轻 的 ancestor, 我用了一部分 伪 码 , 不知道有没有 问题 , 不 过 两点是肯定 ,1 是一定要用遍 历 ,2. 通 过 遍 历 的 顺 序来找 . 我是 这样 做的 , 不 过 算法不算很 elegant 1> 前序遍 历 , 将 结 果 记 入一个 Queue. 2> 再用一次 递归 找到从 ROOT 到 Node1 和 Node2 的路径 , 有了前面的 结 果 , 只要不断判断被找的 节 点与根 节 点的 对应 的 Queue 里的 顺 序就可以了 , 在 Queue 之前的就是 root 的 left tree, 在 Q ueue 之后的就是 root 的 right tree, 一直找到 对应 的 节 点 , 我 这 里的 path 也是用两个 Queue 来 记录 的 3> 比 较 两条 path, 最后一个相同的 记录 就是了 , 至少有一个 , 那就是 root. ■接下来的我 觉 得没有什 么 意思了 , 第四部分是 设计题 目 , 1 是 问 你 对 微 软 拼音有什 么 改 进 的建 议 , 为 什 么 要改 进 , 我第一句就写了 .I am really sorr y for not providing useful information. 因 为 我很少用拼音 , 大部分 时间 用五笔 , 就算用 拼音也不用微 软 拼音 , 它的反 应 那个叫慢啊 .... 2 是 问 你如果你在写 paper 时 , 你和你的 导师 有不同意 见 , 你会怎 么办 ? 那 还 用 问 ,data support 啊 .... ■第五部分是 测试 , 共两 题 1. 找 错 并改正 , 我 还记 得原 题 #define mkUpper(c) ((c)-'a'+'A') void StringUpper(char *str) { while(str) { *str= mkUpper(*str); str++; } } void main() { char *a = "eaFadfd"; StringUpper(a); } ... 好大两个坑啊 ,1.str 指 针啥时 候会 为 空呢 ? 如果 输 入参数地址不 为 空 , 那 么 str 永 远 不空 的 ..2. 那个宏倒是把小写字母改成大写了 , 那 么 大写字母呢 ? 如果是 c='A', 那就是 'A'-'a'+ 'A' 错 哪去了都不知道了 .... 我改正了一下 .. #define mkUpper(c) ((c)-'a'+'A') void StringUpper(char *str) { if(str!=NULL) { while(*str !='\0') { if(*str-'a'<=26 &&*str-'a'>=0 ) *str = mkUpper(*str); str++; } 杰 | 引用(trackback0) | 编辑 □ 评论

原始快照:web.archive.org