Google面试高频题资源-CSDN文库

google

interview

需积分: 13 74 浏览量 2018-01-17 09:38:37 上传评论收藏 761KB PDF 举报

资源推荐

资源详情

资源评论

电面:

顺序统计树，找第 K 个节点。

1）打印 000 到 123 所有的数，follow up，打印 a 到 b 所有的数（假设每一位都 a<=b）

2）Next permutation

3）栅栏 N 个木片，每一片可以刷两种颜色，相临三片不能同色，问几种刷法。

Q) Write a program to count the total number of pages reachable from a website.

For example, given "nytimes.com", count the number of pages reachable from there. More info on

1point3acres.com

You can assume you are given a function to fetch the page and extract the inner links, e.g.:

List<String> fetchPageAndExtractUrls(String url);

Q) Given a tiny computer with a 1 MHz CPU and 1 KiB of RAM memory

no input;

Only output is an LED light that says “I am done”.

(1 MHz == 1 million instructions per second)

I load an arbitrary unknown program onto this computer.

How long do we have to wait in wall-clock time before we can prove the program has an infinite loop?

有个 x,y 坐标系的 array A[(1，0),(0，1)] 都在一个圆上圆心会给（0，0）

有第二个点的 arrayB[(8,9),(12,-5)] 求问对于每个在 B array 里的点，找出 A 里距离最近的点

第二题把 A 的点换成极坐标 sort 然后 binary search 最后没写完。

N by M grids. red cells and black cells. Compute the # of squares without black cells.!就是 DP。所有

size 的 square 都算，比如一个 2X2 的格子有 5 个 square，3X3 的格子一共有 14 个 square。。。

跟 lc 那道 maximal square 有点类似。

一个无向图，不是全链接，节点上有数字。求最长连续递增数字串的长度.

9-1-2-3-4

| |

2-3

答案是 4：1-2-3-4

a--b c---d e---f g---h

我来讲下第五题，如果一共有 N 个选手，N=2^h，那么我们就需要 h 次比赛才能选出冠军。

用 win

[j] 记录 i 对 j 的, i 赢的 win rate, win[j] + win[j] = 1

如果有 0,1,2,3 四名选手那么这个树里面，可能是这样的{[0]} {[0,3]} {[0,1] [2,3]} 我们把最底层成

为 0 层，root 称为 h 层。那么我们就是考虑 root = 0, root->left = 0, root->left->left = 0, ...root-

>left*n = 0 的可能性

我们现在要考虑的是从第 K 层的结果，推出 k+1 层的结果。

所以用 DP 去做。DP 大小为 H*N = logN *N，DP[j]代表的是在第 i 层(round i) 第 j 个选手没有被淘汰

(win)的概率。由于 tree 的构造你可以知道第 i 层中，活下来的最多为 2^(h-i)个。

特别的 i = 0 的时候， dp[0][j] = 1 for all j。

我们最终是要求 dp[h][0]

好了，现在数学归纳法，假设我们已经求出了第 k 层，就是说我们知道了 dp[k][0],

dp[k][1]...dp[k][n-1]

要用这些数据推出第 k+1 层。

OK 我们考虑 dp[k+1][j] 说明 j 在 k 层肯定没被淘汰，并且与 j 在 k 层的对局 , j 赢了。那么这个概率

就是

dp[k+1][j] = dp[k][j] * ( win[j][x] * dp[k][x]) for all x might fight j in round k+1,

注意这里的 x 不是由 1~N 共 N 个哦，很简单，比如考虑 dp[2][3]，那么 3 在第一轮已经赢了，说明

“2”已经被打死了，所以不可能与 3 再对局。同样的 dp[3][6]里面，和 6 对局的只可能是 0,1,2,3 而不

可能是 4,5,7（都已经死了）。所以这个公式里求 dp[k+1][j] 需要 loop 的所有的 x 一共有连续的 2^k

个（特别的，考虑下 k+1=1 和 k+1=h）：那么我们如何去求出 xstart 呢，. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒

嗗湴

大家画一画图，看下构造就不难得出，如果第 k+1 层 j 是从 right child 胜出的，那么 x 在 j 的左边，

xstart = j/(2^k) *2^k - 2^k, 反之如果是从 left 胜出的，那么 xstart = j/(2^k) *2^k .鐣欏璁哄潧-涓€浜

-涓夊垎鍦

那么就可以写出我们的 loop 了：

input:.1point3acres 缃

int n, h;

int win[n][n];

solution:

int dp[h][n] = {0};.鏈枃鍘熷垱鑷1point3acres 璁哄潧

for all j in 1-n:

dp[0][j] = 1;. visit 1point3acres.com for more.

for(int k = 0; k<h ;k++){

//calculate dp[k+1]

for(int i = 0; i < n; i++){

int offset = i / (2^k) * (2^k);

int fightWithLeft = (i / (2^k)) % 2;

int xstart = offset;.1point3acres 缃

if(fightWithLeft){. 涓€浜-涓夊垎-鍦帮紝鐙鍙戝竷

xstart = offset - 2^k;-google 1point3acres

} 鏉ユ簮涓€浜.涓夊垎鍦拌鍧.

for(int x = xtart; x < xstart + 2^k ; x++){

dp[k+1] += win[x]*dp[k][x];

}

dp[k+1] *= dp[k];

}

return dp[h][0];.鐣欏璁哄潧-涓€浜-涓夊垎鍦

那么这里 Memory : O(h*N) = O(NlogN)

Time Complexity: 在第 k+1 层里，对于每个 i,计算了 2^k 次，所以是 2^k *N 次

那么一共 (2^0 +2^1+...+2^(h-1) )*N = (2^h-1) * N = (N-1) * N

所以是 O(N^2) time

plus one (follow up: 10000 bits num)

!"#$%"%&'()*+'%,-.#/((

0*!,(#1'23%4/(0.$1%56(

7%'23%456(

7%'8'2!&,%956::取得3%4排在!&,%9位置的0.$1%(

不能用".#，只能用最基础的数据结构，(

(

);1<<$%=(输入是>?/@/A/BC(输出是>?/A/@/BC=((就是一个乱序数组/(其中缺少了一个值/(然后输出/(每个

数值都在自己对应的!&,%9上面=(但是移动的时候/(只能把数字放在空缺的位置上/(要求移动的次数最少=(

(

D1%)'!*&(@，(现在同样给两个)'+!&7，(8和E，但是E特别大，可以想象成一个,*F，判断E中是否有)1GH$!)'(

是8的#%+"1'.'!*&，要求是F*&)%F1'!0%()1G($!)'/(

%=7=(8I(>J.J/(JGJC/(EI>JFJ/(JGJ/(J.JC/(+%'1+&(4%)=(K+*"(L#*!&'(B.F+%)(GG)(

>J.J/(JGJC/(EI>JFJ/(JGJ/(J,J/(J.JC/(+%'1+&(&*=(

(

已知一个,.'.()%'(，(包括学生名字(与(学生成绩(例如-!F;.%$(L??((M1F4(N?(分，问(设计一个数据机构(

满足两个操作(。L）(O%'P."%E4Q.&325((@）(1#,.'%E4P."%25=(

(

设计一个$!)'%&%+类，能监听一些消息做一些处理(

(

给一个'+%%，找里面相同的)1G'+%%，面完发现其实网上是有这道题的，但我没怎么答出来，在提示下说出来遍

历R;.);了但是没能写出代码来(

(

STKHN编码，这个是之前面经里有的(

(

给定一些点，求能组成哪些三角形。给定一些边，求能组成哪些三角形(

(

给一个M!)'UK$*.'V/(K$*.'(0/(K$*.'(%/(让<!$'%+得到所有(0H%(UI(,.'.(UI(0R%的,.'.(

这题的坑是不是(K$*.'的(F*"#.+%。不太确定的时候是不是应该7**7$%一下，基础知识不过关啊(

(

就是找连续数列，在树里（非二叉树），(<*$$*W(1#(是一个图。(

总之就是都用,<)走一遍(

(

F*,!&7X(7!0%(.($!)'(*<()'+!&7/(,%<!&%(#+*,1F'(.)X(

#+*,1F'2)L/()@5(I(?(!<()L(.&,()@(;.0%(F;.+.F'*+(*0%+$.#(

(((((((((((((((((((((((((()L=$%&7';(Y()@=$%&7';(!<()L(.&,()@(.+%(,!)'!&F'(

(

<!&,(';%(".9(#+*,1F'(*<(';%($!)'=(

(

刚开始直接想到()'+!&7(#%+"1'.'!*&/ 就说了)*+' 和;.);".#求<+%D1%&F4 的两种办法，但阿三似乎都不满意，

一直问能不能减少*#%+.'!*&(

实在想不出，厚颜无耻的问(F.&(4*1(7!0%("%(.(;!&'，(+%F+1!'%+很不错的提示说G!'".#，眼前一亮呀！

最后就是用G!'(*#%+.'!*&(处理的(

(

美国小伙。写 BigInt 类的你认为需要的接口函数，只写定义就好。然后让实现了 Constructor 和

Comp 函数（比较两个 BigInt）。让写了一大堆 test case。.

3. 同上美国小伙。一个 map{“a":1, "b":2, "c":4}代表每个 string（或者 char，无所谓）的 weight。现

在有个函数 vector<string> genStrings(map m, int cnt)

让你返回一个 vector of string，其中各个 string 出现的概率和之前给的 weight 成比例。比如给

cnt==700，那么里面大概有 100 个”a“， 200 个”b“， 400 个”c“。

问了好久好久的细节问题，比如 time complexity， space complexity，还有 hash function collusion，

还有这个函数怎么测试。Random 函数是给的。

测试的话我就说用个大点的数 iterate 然后数结果。他问如果”a“expect 出现的次数是 1M，现在出

现 1M+1K，你觉得程序有没有 bug。我就说 normal distribution 有个 confidence interval 啊，可以算

出来然后看看啊。

有一个 tree，不是 binary，define weight as 它的子数的点的个数。weight 不是 treenode 的 field

2. 手机 app，response 时间长，怎么处理。解决了怎么测试。不是写代码题。3. 第一题的 tree，会常

改变，要记录什么时间 tree 长什么样，用什么数据结构纪录。纪录很多很多有什么问题，怎么办。

#2:

<235, Obama> 代表在第 235 秒时, obama 得到了一个选票. 你现在有一个 list 的这种数据, 求在第 x

秒时谁的票数最多.

follow up: 你这个函数会被调用多次, 如何优化

Find a sorted subsequence of size 3 in linear time

Given an array of n integers, find the 3 elements such that a[i] < a[j] < a[k] and i < j < k in 0(n) time. If

there are multiple such triplets, then print any one of them.

Examples:

剩余24页未读，继续阅读

评论收藏

内容反馈

yangduo123

粉丝: 0
资源: 10

Google面试高频题

google面试官亲受JAVA面试题

大厂算法面试题库中高频出现的30道典型题

面试官该如何面试应聘者呢

Mysql高频面试题汇总.pdf

clickhouse高频面试题

大数据技术之高频面试题8.0.2.pdf

java面试题_高频题

Java面试高频题.pdf

搜集了众多经典高频前端面试题和大厂前端面试题以及相关代码题 pdf.pdf

SQLServer高频面试题及答案

面试高频题库.md

mysql高频面试题及答案

大数据技术之高频面试题8.0.2.docx

238道大厂前端高频面试题.pdf

2020前端大厂高频面试题.pdf

面试高频题汇总.xmind

2023java八股文高频面试题

Java面试题高频集锦

大数据技术之高频面试题7.5.pdf

面试高频算法习题精讲.rar

大数据技术之高频面试题8.0.8(1)(1).docx

2023 前端二面高频 vue 面试题集锦

Qt 5实现串口调试助手 （源工程文件、0积分下载）

【SystemVerilog】路科验证V2学习笔记（全600页）.pdf

AutoSAR标准协议4.2.2

光伏-储能并网系统仿真.rar

NPPJSONViewer.zip

GD32替换STM32注意事项.pdf

XCP协议的规范文档

最新资源

Qt 5实现串口调试助手（源工程文件、0积分下载）