梦想破碎是没有声音的,它只是缓慢又沉默地离开了。 by 苏更生

标签:谷歌面试题

谷歌CTCI

20.5 给出两个单词,找到它们的最短距离

题目 有一个很大的文本文件,里面包含许多英文单词。给出两个单词,找到它们的最短距离 (以它们之间隔了多少个单词计数)。你能在O(1)的时间内返回任意两个单词间的最短距离吗? 你的解法空间复杂度是多少? 解答 先看一个例子,为了简单起见,我们假设文件里就只有以下两句话。然后, 我们...

Jay13 3年前 (2014-06-24) 6640℃ 4评论 14喜欢

谷歌CTCI

20.4 写一个函数,计算0到n之间2的个数。

题目 写一个函数,计算0到n之间2的个数。 解答 最简单直观的方法就是对于0到n之间的数,一个个地去统计2在它们上出现的个数, 然后累加起来即可。求2在某个数上出现的次数需要O(logn)的时间,一共有n个数, 所以共需要O(nlogn)的时间。 代码如下: ...

Jay13 3年前 (2014-06-24) 5859℃ 2评论 9喜欢

谷歌CTCI

20.3 写一个函数,随机地从大小为n的数组中选取m个整数

题目 写一个函数,随机地从大小为n的数组中选取m个整数。要求每个元素被选中的概率相等。 解答 这道题目和随机洗牌问题类似,只需要随机选取1个元素, 然后在剩下的元素里面随机选取下一个元素,不断这样操作即可。 这样做能保证每个元素选中的概率一样吗?也就是选中每个元素的概率都是1/n...

Jay13 3年前 (2014-06-24) 5662℃ 1评论 8喜欢

谷歌CTCI

20.2 写一个随机洗牌函数

题目 写一个随机洗牌函数。要求洗出的52!种组合都是等概率的。 也就是你洗出的一种组合的概率是1/(52!)。假设已经给你一个完美的随机数发生器。 解答 这是一道非常有名的面试题,及非常有名的算法——随机洗牌算法。 最直观的思路是什么?很简单,每次从牌堆中随机地拿一张出来。那么,...

Jay13 3年前 (2014-06-24) 4772℃ 0评论 7喜欢

谷歌CTCI

20.1 不能使用+号或其它算术运算符求两个数的和

题目 写一个Add函数求两个数的和,不能使用+号或其它算术运算符。 解答 为了解决这个问题,让我们来深入地思考一下,我们是如何去加两个数的。为了易于理解, 我们考虑10进制的情况。比如我们要算759 + 674,我们通常从最低位开始加, 考虑进位;然后加第二位,考虑进位…对于二进...

Jay13 3年前 (2014-06-24) 5111℃ 0评论 12喜欢

谷歌CTCI

15.5 写SQL查询语句查询成绩排名前10%的学生

题目 有一个简单的数据库,存储学生的成绩信息。尝试设计这个数据库,它会是怎样的? 提供一个SQL查询语句来返回光荣榜学生信息(前10%),按照他们的GPA排序。 解答 在一个简单的数据库中,我们至少需要以下三张表:学生表(Students),课程表(Courses), 及课程登记...

Jay13 3年前 (2014-04-03) 9033℃ 0评论 2喜欢

谷歌CTCI

15.3 什么是反范式?它的优缺点是什么?

题目 什么是反范式?它优缺点是什么? 解答 反范式是通过增加冗余数据或数据分组来提高数据库读性能的过程。在某些情况下, 反范式有助于掩盖关系型数据库软件的低效。关系型的范式数据库即使做过优化, 也常常会带来沉重的访问负载。 数据库的范式设计会存储不同但相关的信息在不同的逻辑表, ...

Jay13 3年前 (2014-04-03) 5088℃ 0评论 5喜欢

谷歌CTCI

15.2 SQL的连接有哪些不同的类型?并解释其异同点

题目 SQL的连接有哪些不同的类型?解释它们的不同点及在什么情况下用哪种连接,为什么? 解答 连接(JOIN)将数据库中的两个或多个表组合起来。为了使用连接, 每个表至少要包含一个相同的字段(属性)。不同的连接类型决定了哪些记录会出现在结果集。 假设我们有以下两张表: 一张表列...

Jay13 3年前 (2014-04-03) 2547℃ 1评论 4喜欢

谷歌CTCI

13.9 写一个智能指针类(smart_ptr)

题目 写一个智能指针类(smart_ptr)。 解答 比起一般指针,智能指针会自动地管理内存(释放不需要的内存),而不需要程序员去操心。 它能避免迷途指针(dangling pointers),内存泄漏(memory leaks), 分配失败等情况的发生。智能指针需要为所有实例维...

Jay13 3年前 (2014-03-27) 2549℃ 0评论 2喜欢

谷歌CTCI

13.8 写一个函数,返回传入数据结构的一份完全拷贝

题目 写一个函数,其中一个参数是指向Node结构的指针,返回传入数据结构的一份完全拷贝。 Node结构包含两个指针,指向另外两个Node。 解答 以下算法将维护一个从原结构的地址到新结构的地址的映射, 这种映射可以让程序发现之前已经拷贝的结点,从而不用为已有结点再拷贝一份。 由于...

Jay13 3年前 (2014-03-27) 2355℃ 0评论 1喜欢

谷歌CTCI

13.7 为什么基类中的析构函数要声明为虚析构函数?

题目 为什么基类中的析构函数要声明为虚析构函数? 解答 用对象指针来调用一个函数,有以下两种情况: 如果是虚函数,会调用派生类中的版本。 如果是非虚函数,会调用指针所指类型的实现版本。 析构函数也会遵循以上两种情况,因为析构函数也是函数嘛,不要把它看得太特殊。 当对象出了作用...

Jay13 3年前 (2014-03-27) 3221℃ 0评论 1喜欢

谷歌CTCI

13.6 C++中名字隐藏是指什么?

题目 C++中名字隐藏是什么? 解答 让我们通过一个例子来讲解C++中的名字隐藏。在C++中,如果一个类里有一个重载的方法, 你用另一个类去继承它并重写(覆盖)那个方法。你必须重写所有的重载方法, 否则未被重写的方法会因为名字相同而被隐藏,从而使它在派生类中不可见。 请看例子: ...

Jay13 3年前 (2014-03-27) 3039℃ 1评论 0喜欢

谷歌CTCI

13.5 C语言关键字”volatile”的作用?

题目 谈谈C语言关键字”volatile”的意义(或重要性)? 解答 volatile的意思是”易变的”,因为访问寄存器比访问内存要快得多, 所以编译器一般都会做减少存取内存的优化。volatile 这个关键字会提醒编译器,它声明的...

Jay13 3年前 (2014-03-27) 2632℃ 0评论 1喜欢

谷歌CTCI

13.4 深拷贝和浅拷贝有什么区别,如何使用?

题目 深拷贝和浅拷贝的区别是什么?你会如何使用它们? 解答 浅拷贝并不复制数据,只复制指向数据的指针,因此是多个指针指向同一份数据。 深拷贝会复制原始数据,每个指针指向一份独立的数据。通过下面的代码, 可以清楚地看出它们的区别: struct Tes...

Jay13 3年前 (2014-03-27) 4514℃ 1评论 3喜欢

谷歌CTCI

13.3 C++中的虚函数是如何工作的?

题目 C++中的虚函数是如何工作的? 解答 虚函数依赖虚函数表进行工作。如果一个类中,有函数被关键词virtual进行修饰, 那么一个虚函数表就会被构建起来保存这个类中虚函数的地址。同时, 编译器会为这个类添加一个隐藏指针指向虚函数表。如果在派生类中没有重写虚函数, 那么,派生类...

Jay13 3年前 (2014-03-27) 3229℃ 0评论 2喜欢

谷歌CTCI

13.2 浅析哈希表和STL map

题目 对比哈希表和STL map。哈希表是怎么实现的?如果输入数据规模不大, 我们可以使用什么数据结构来代替哈希表。 解答 对比哈希表和STL map 在哈希表中,实值的存储位置由其键值对应的哈希函数值决定。因此, 存储在哈希表中的值是无序的。在哈希表中插入元素和查找元素的时间复...

Jay13 3年前 (2014-03-27) 3546℃ 1评论 1喜欢

谷歌CTCI

13.1 用C++写一个函数,输出文件的最后k行。

题目 用C++写一个函数,打印输入文件的最后k行。 解答 一种方法是打开文件两次,第一次计算文件的行数N,第二次打开文件,跳过N-K行, 然后开始输出。如果文件很大,这种方法的时间开销会非常大。 我们希望可以只打开文件一次,就可以输出文件中的最后k行。 我们可以开一个大小为k的字...

Jay13 3年前 (2014-03-27) 4144℃ 3评论 1喜欢

谷歌CTCI

12.7 如何设计一个支持TB级别数据的数据库

题目 让你来设计一个能存储TB级数据的数据库,而且要能支持高效的区间查询(范围查询), 你会怎么做? 解答 首先要明确,并不是所有的字段都可以做区间查询。比如对于一个员工, 性别就没有所谓的区间查询;而工资是可以做区间查询的, 例如查询工资大于a元而小于b元的员工。 我们将需要做...

Jay13 3年前 (2014-03-27) 4242℃ 0评论 4喜欢

谷歌CTCI

12.6 10亿个url,每个url对应一个网页,如何检测重复的网页?

题目 你有10亿个url,每个url对应一个非常大的网页。你怎么检测重复的网页? 解答 网页大,数量多,要把它们载入内存是不现实的。 因此我们需要一个更简短的方式来表示这些网页。而hash表正是干这事的。 我们将网页内容做哈希,而不是url,这里不同url可能对应相同的网页内容...

Jay13 3年前 (2014-03-27) 3968℃ 1评论 4喜欢

谷歌CTCI

12.5 如果让你设计一个网络爬虫,你怎么避免陷入无限循环?

题目 如果让你设计一个网络爬虫,你怎么避免陷入无限循环? 解答 看完这题,建议用python写个爬虫,对此就能理解的多一些,而且还可以做出好玩的东西。 话说爬虫为什么会陷入循环呢?答案很简单,当我们重新去解析一个已经解析过的网页时, 就会陷入无限循环。这意味着我们会重新访问那个网...

Jay13 3年前 (2014-03-27) 6541℃ 0评论 0喜欢

谷歌CTCI

12.4 数组去重(限制内存为4kb)

题目 有一个数组,里面的数在1到N之间,N最大为32000.数组中可能有重复的元素(即有的元素 存在2份),你并不知道N是多少。给你4KB的内存,你怎么把数组中重复的元素打印出来。 解答 我们有4KB的内存,一共有4 * 210 * 8位,大于32000,所以我们可以用Bit M...

Jay13 3年前 (2014-03-27) 3181℃ 0评论 3喜欢

谷歌CTCI

12.3 在40亿个整数值中查找特定数据

题目 给你一个文件,里面包含40亿个整数,写一个算法找出该文件中不包含的一个整数, 假设你有1GB内存可用。 如果你只有10MB的内存呢? 解答 我们先来做个算术题,40亿个整数大概有多大? 40 * 10^8 * 4B = 16GB (大约值,因为...

Jay13 3年前 (2014-03-25) 3874℃ 2评论 4喜欢

谷歌CTCI

12.1 股价信息摘要整合方案

题目 如果你要为5000家公司的股价信息整合摘要,你会怎么做? 你要负责摘要的开发,部署,监控和维护。描述你能想到的不同方法, 及为什么你会推荐这些方法。摘要以逗号分隔的格式经由FTP进行交付,每个交易日一次。 每日有1000个用户在web应用程序中使用这些摘要信息。 解答 假设...

Jay13 3年前 (2014-03-25) 2073℃ 0评论 1喜欢

谷歌CTCI

10.1-10.7 程序员面试——数学相关题目

题目10.1 你有一个篮球架,可以在以下游戏中选择一个来玩。 游戏1:投一次球,进了算赢。 游戏2:投三次球,至少要进2个才算赢。 如果命中率是p,那么p是什么值时你会选游戏1来玩?或p是什么值时你会选择游戏2? 解答10.1 命中率是p,那么对于游戏1,赢的概率是p。对于游戏2...

Jay13 3年前 (2014-03-25) 2953℃ 0评论 1喜欢

谷歌CTCI

9.7 写一个函数模拟叠罗汉节目

题目 马戏团设计了这样一个节目:叠罗汉。一群人往上叠,每个人都踩在另一个人的肩膀上。 要求上面的人要比下面的人矮而且比下面的人轻。给出每个人的身高和体重, 写一个函数计算叠罗汉节目中最多可以叠多少人? 例子: 输入(身高 体重):(65, 100) (70, 150) (56, ...

Jay13 3年前 (2014-03-24) 2167℃ 0评论 1喜欢

谷歌CTCI

9.6 在一个矩阵中找出特定的数

题目 给出一个矩阵,其中每一行和每一列都是有序的,写一个函数在矩阵中找出指定的数。 解答 我们假设这个矩阵每一行都是递增的,每一列也都是递增的,并把这些数据存入文件 9.6.in(如下),其中开头的两个数5 5表示该矩阵是5*5的。 5 5 1 2 ...

Jay13 3年前 (2014-03-24) 3194℃ 0评论 2喜欢