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

 分类:谷歌CTCI

google面试题

谷歌CTCI面试系列

谷歌CTCI面试系列
谷歌面试官经典作品(CTCI)目录 1.1 判断一个字符串中的字符是否唯一 1.2 字符串翻转 1.3 去除字符串中重复字符 1.8 利用已知函数判断字符串是否为另一字符串的子串 2.1 从链表中移除重复结点 2.2 实现一个算法从一个单链表中返回倒数第n个元素 2.3 给定链表...

Jay13 3年前 (2014-08-11) 18605℃ 1评论 30喜欢

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

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

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

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喜欢

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

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

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

20.2 写一个随机洗牌函数

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

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

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

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

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

19.11 设计一个算法,找到数组中所有和为指定值的整数对

题目 设计一个算法,找到数组中所有和为指定值的整数对。 解答 时间复杂度O(n)的解法 我们可以用一个哈希表或数组或bitmap(后两者要求数组中的整数非负)来保存sum-x的值, 这样我们就只需要遍历数组两次即可找到和为指定值的整数对。这种方法需要O(n) 的辅助空间。如果直接...

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

19.8 统计给定单词在一本书中出现的次数

题目 设计一个函数,统计给定单词在一本书中的出现次数。 解答 这道题目和19.2是一个思路。如果只需要查询一次, 那就直接做;如果要多次查询,而且要查询各种不同的单词,那就先预处理一遍, 接下来就只需要用O(1)的时间进行查询。 只查询一次 遍历这本书的每个单词,计算给定单词出现...

Jay13 3年前 (2014-06-22) 3045℃ 1评论 6喜欢

19.7 求最大连续子序列和

题目 给出一个整数数组(包含正数和负数),找到数组中最大的连续子序列,并返回和。 例子: 输入: {2, -8, 3, -2, 4, -10} 输出: 5 (即, {3, -2, 4} ) 解答 经典的面试题目,遍历一遍数组,用变量maxsum保存遍历过程中的最大和, 用变量cu...

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

19.5 写一个函数来模拟游戏

题目 游戏规则如下: 4个槽,里面放4个球,球的颜色有4种,红(R ),黄(Y),绿(G),蓝(B)。比如, 给出一个排列RGGB,表示第一个槽放红色球,第二和第三个槽放绿色球,第四个槽放蓝色球。 你要去猜这个排列。比如你可能猜排列是:YRGB。当你猜的颜色是正确的,位置也是正确...

Jay13 3年前 (2014-06-22) 2478℃ 1评论 4喜欢

19.3 写一个算法计算n的阶乘末尾0的个数

题目 写一个算法计算n的阶乘末尾0的个数 解答 首先,算出n的阶乘的结果再去计算末尾有多少个0这种方法是不可取的, 因为n的阶乘是一个非常大的数,分分种就会溢出。我们应当去分析, 是什么使n的阶乘结果末尾出现0。 n阶乘末尾的0来自因子5和2相乘,5*2=10。因此,我们只需要计...

Jay13 3年前 (2014-06-22) 8120℃ 0评论 10喜欢

19.2 设计算法检查某人是否赢得了井字游戏

题目 设计算法检查某人是否赢得了井字游戏。 解答 假设这个检查某人是否赢得了井字游戏的函数为HasWon,那么我们第一步要向面试官确认, 这个函数是只调用一次,还是要多次频繁调用。如果是多次调用, 我们可以通过预处理来得到一个非常快速的版本。 方法一:如果HasWon函数需要被频...

Jay13 3年前 (2014-06-22) 2582℃ 0评论 4喜欢

19.1 不能使用临时变量,交换两个数

题目 写一个函数交换两个数,不能使用临时变量。 解答 交换函数swap是经常用到的函数,小巧简单,以下两种实现方式都不需要使用临时变量: // 实现1 void swap(int &a, int &b){ b = a - ...

Jay13 3年前 (2014-06-22) 3422℃ 3评论 5喜欢

如何得到Google的工作机会?

Question: 1. 你要多强(具体化的描述)才能荣幸加入 Google? 2. 你为去 Google 做过什么努力,或者什么努力帮助你去 Google? Answer 1. Google有什么职位?官网:Teams and Roles分三类: Build Cool Stuf...

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

18.5 线程调度

题目 假设我们有以下代码: class Foo{ public: A(.....); /*当A被调用时,会创建一个新的线程并执行相应的函数*/ B(.....); /*同上*/ C(.....); /*同上*/ }...

Jay13 3年前 (2014-06-21) 2670℃ 1评论 10喜欢

18.3 实现一个单例模式的模板

题目 实现一个单例模式的模板,当给一个类Foo时,你可以通过Singleton::instance() 来得到一个指向Foo类单例的指针。假设我们现在已经有了Lock类,其中有acquire() 和release()两个方法,你要如何使你的实现线程安全且异常安全? 解答 ...

Jay13 3年前 (2014-06-21) 3987℃ 1评论 6喜欢

18.2 你如何测量一次上下文切换所需时间?

题目 你如何测量一次上下文切换所需时间? 解答 这是一个棘手的问题,让我们先从可能的解答入手。 上下文切换(有时也称为进程切换或任务切换)是指CPU 的控制权从一个进程或线程切换到另一个。 (参考资料) 例如让一个正在执行的进程进入等待状态(或终止它),同时去执行另一个正在等待的...

Jay13 3年前 (2014-06-21) 3641℃ 0评论 1喜欢

18.1 线程和进程的区别是什么?

题目 线程和进程的区别是什么? 解答 这是一道出现频率极高的面试题,考察基本概念。 进程可以认为是程序执行时的一个实例。进程是系统进行资源分配的独立实体, 且每个进程拥有独立的地址空间。一个进程无法直接访问另一个进程的变量和数据结构, 如果希望让一个进程访问另一个进程的资源,需要...

Jay13 3年前 (2014-06-21) 9268℃ 0评论 14喜欢

进程与线程的一个简单解释

进程(process)和线程(thread)是操作系统的基本概念,但是它们比较抽象,不容易掌握。 最近,我读到一篇材料,发现有一个很好的类比,可以把它们解释地清晰易懂。 1. 计算机的核心是CPU,它承担了所有的计算任务。它就像一座工厂,时刻在运行。 2. 假定工厂的电力有限...

Jay13 3年前 (2014-06-21) 7918℃ 0评论 55喜欢

17.5 TCP和UDP之间有什么区别?

题目 TCP和UDP之间有什么区别?解释TCP如何处理可靠交付(解释ACK机制),流量控制 (解释TCP发送器/接收器窗口)及拥塞控制。 解答 TCP(传输控制协议):TCP是一个面向连接的协议。从客户端到服务器可以建立一个连接, 然后数据通过这个连接进行传输。TCP协议具有以下...

Jay13 3年前 (2014-06-21) 4325℃ 1评论 3喜欢

17.3 比较IPv4和IPv6协议

题目 比较IPv4和IPv6协议。 解答 IPv4和IPv6是因特网协议,应用于网络层。IPv4是现在应用得最广泛的协议, 而IPv6是因特网的下一代协议。 IPv4是因特网协议的第4个版本,它使用32位寻址技术。IPv6是下一代因特网协议, 用的是128位寻址。 IPv4最多...

Jay13 3年前 (2014-06-21) 2356℃ 0评论 2喜欢

17.4 网络/子网掩码是什么?网络路由是什么?

题目 网络/子网掩码是什么?解释主机A是如何发送消息/包给主机B的当:(a) A,B在同一网络上。 (b) A,B在不同网络上。解释哪一层做出路由决定,是怎么做的? 解答 掩码是一个用于识别网络/子网地址的位模式。IP地址由两部分组成:网络地址和主机地址。 IP地址被分为不同的类...

Jay13 3年前 (2014-06-21) 2982℃ 1评论 0喜欢

17.2 介绍常用路由协议。例如:BGP,OSPF,RIP

题目 介绍常用路由协议。例如:BGP,OSPF,RIP 解答 BGP: Border Gateway Protocol (边界网关协议) BGP是互联网上的一个核心路由协议。当BGP路由器第一次出现在互联网上时, 它会与那些和它能直接通信的其它BGP路由器建立连接。建立连接后的第...

Jay13 3年前 (2014-06-21) 3798℃ 0评论 6喜欢

17.1 解释一下,在你往浏览器中输入一个URL后都发生了什么,要尽可能详细

题目 一步一步解释一下,在你往浏览器中输入一个URL后都发生了什么,要尽可能详细。 解答 这道题目没有所谓的完全的正确答案,这个题目可以让你在任意的一个点深入下去, 只要你对这个点是熟悉的。以下是一个大概流程: 浏览器向DNS服务器查找输入URL对应的IP地址。 DNS服务器返...

Jay13 3年前 (2014-06-21) 10162℃ 1评论 4喜欢

16.10 写一个名为my2DAlloc的函数,用它开辟一个二维数组

题目 写一个名为my2DAlloc的函数,用它开辟一个二维数组。尽可能地少用malloc函数, 并确保可以用arr[i][j]这种形式来访问第i行第j列的元素。 解答 这道题目最简单的方法就是先开一个数组来存储指向每一行的指针, 然后再为每一行动态地分配空间。这是非常常见的动态申...

Jay13 3年前 (2014-06-21) 2311℃ 0评论 1喜欢

16.1 解释术语:虚拟内存、缺页中断、抖动

题目 解释以下术语:虚拟内存,缺页中断,抖动 解答 虚拟内存是计算机系统内存管理的一种技术。它使得应用程序认为它拥有连续的可用的内存 (一个连续完整的地址空间),而实际上,它通常是被分隔成多个物理内存碎片, 还有部分暂时存储在外部磁盘存储器上,在需要时进行数据交换。 与没有使用虚...

Jay13 3年前 (2014-06-21) 5065℃ 0评论 2喜欢

如何用一个月的时间准备google的技术面试

题图:正在滴血的谷歌 最近google在我大陆又火了一把,谷歌不能用了,哎呀,尼玛。还让不让程序员活了。在这个节骨眼上,我也来凑个热闹,对于广大需要谷歌的程序猿们,送上两个字:呵呵 昨天在csdn上看到一位兄台的文章《给所有面试官》,吐槽了下极品面试经历。对于这位兄台所遇到的极品...

Jay13 3年前 (2014-06-07) 8291℃ 2评论 3喜欢