谈谈使用过的几款咖啡机

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
H1B/绿卡遥遥无期
又不想回国
来东南亚最大的互联网集团工作?
码农求职神器Triplebyte:
不用海投
内推多家公司面试
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
查看: 5479|回复: 26
收起左侧

Google new grad 电面面经

[复制链接] |试试Instant~ |关注本帖
我的人缘0
lithui 发表于 2015-5-20 00:00:01 | 显示全部楼层 |阅读模式
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】

2015(1-3月) 码农类General 硕士 全职@Google - 内推 - 技术电面  | Fail | fresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?Sign Up 注册获取更多干货

x
一位阿三PHD面的,问了简单的背景问题和两个技术问题。看完问题之后我就知道和Google今年缘尽于此了。

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.
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?



评分

参与人数 5大米 +69 收起 理由
hj867955629 + 3 小众的题啊。。
wm_thu + 3 谢谢你的介绍!
whdawn + 30
ee07b415 + 3 欢迎来介绍你知道的情况
tailofjune + 30

查看全部评分


上一篇:Palantir 电面
下一篇:F昂赛面经,已挂

本帖被以下淘专辑推荐:

我的人缘0
xiexiangyi0 发表于 2015-5-20 11:42:38 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
这个面试还行吧,

第一题就是遍历所有url并且每次数一个就在全局变量上加一个1,
. 留学申请论坛-一亩三分地不能重复访问页面,否则无限循环,那就hash一下就好,相当于mark as visited,所以整个就一个DFS:

public class Solution{
    private int total_pages;
    private Set <String> visited;
    public int counturl (String root_url){
        total_pages=0;
        visited=new HashSet<>();
        iterate_all(root_url);. 1point 3acres 论坛
        return total_pages;
    }
    private void interate_all(url){
        List<String> children = fetchPageAndExtractUrls(url);
        if(children.size()==0) return;
        for(String child: children){
            if(!visited.contains(child)){
                visited.add(child);. 围观我们@1point 3 acres
                total_pages++;
                interate_all(child);
            }. From 1point 3acres bbs
        }
    }
}

第二题的话要看是多少位计算机了,比如32bit computer,那么一个instruction 32 bit = 4 Byte,所以不可能超过250个指令。(实际上肯定比这个小的多,毕竟还要运行程序是吧)

最坏情况:以一个指令都是个loop,但是不无限的话就要求计数进行循环,那么就看机子支持的最长变量了。

那么假设是integer,那么最坏情况下每个循环2^32数量级,差不多算是2billion吧,那么最慢情况下(250*2billion)/1million per second=500,000秒,那么超过这个就肯定是死循环了。

这只是我的初步想法,欢迎指教~
回复 支持 1 反对 0

使用道具 举报

我的人缘0
stellari 发表于 2015-8-13 20:46:19 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
不好意思,我之前的答案完全搞错了。2^13(也就是8000)维的向量总共能表示的状态数不是2^14种,而是2^(2^13) = 2^8000 种(就像3维向量能表示的状态数是2^3一样)!在1s执行2^20次的计算机上,最多需要2^(8000 - 20)  ~= 10^2400秒!这数字远远超过宇宙年龄,也就是说,通过观察判定程序是否是无限循环是不实际的。

这次应该没算错……吧。
. 牛人云集,一亩三分地
回复 支持 1 反对 0

使用道具 举报

我的人缘0
xiexiangyi0 发表于 2015-5-20 11:45:01 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
打错了,我想说最坏情况每一个指令都是loop
回复 支持 反对

使用道具 举报

我的人缘0
xiexiangyi0 发表于 2015-5-20 11:46:35 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
不过再想想如果是250个嵌套循环就有点恐怖了
回复 支持 反对

使用道具 举报

我的人缘0
猴子0523 发表于 2015-5-20 21:33:19 | 显示全部楼层
  此人我要顶:
 
100% (2) 【我投】
  此人我要踩:
 
0% (0) 【我投】
xiexiangyi0 发表于 2015-5-20 11:46
不过再想想如果是250个嵌套循环就有点恐怖了

250个指令嵌套循环起来就是2^(23*250) 吗
回复 支持 反对

使用道具 举报

我的人缘0
xiexiangyi0 发表于 2015-5-21 02:48:30 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
猴子0523 发表于 2015-5-20 21:33
250个指令嵌套循环起来就是2^(23*250) 吗

嗯,差不多是这样的,反正是理论题,估计就这么答了
回复 支持 反对

使用道具 举报

我的人缘0
 楼主| lithui 发表于 2015-5-23 12:50:13 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
xiexiangyi0 发表于 2015-5-20 11:42
这个面试还行吧,. 一亩-三分-地,独家发布

第一题就是遍历所有url并且每次数一个就在全局变量上加一个1,

多谢指点. 受教了.
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

我的人缘0
xanadulord 发表于 2015-5-24 01:15:00 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
我怎么觉得第二题是无解呢,在代码里可以随便定义一个loop有多少次循环,这个是无法判断的吧?
回复 支持 反对

使用道具 举报

我的人缘0
xiexiangyi0 发表于 2015-8-12 12:09:26 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
xanadulord 发表于 2015-5-24 01:15. 1point3acres
我怎么觉得第二题是无解呢,在代码里可以随便定义一个loop有多少次循环,这个是无法判断的吧?

有限循环是需要记录你循环了多少次了,这样才能判断何时结束(for loop),最坏情况就是0到2^32这么多个循环(假设32位机)(否则溢出)。无限循环的话就不用记录,所以永远继续循环
回复 支持 反对

使用道具 举报

我的人缘0
stellari 发表于 2015-8-12 12:40:38 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
我觉得第二题应该这么想:

因为数据和程序都在内存中,所以,如果在某这两个时间点,内存中的内容处于完全相同的状态,那么从这两个时间点之后的所有状态也一定会完全相同(除非这是台量子计算机)。那么,如果一个程序在开始执行之后,内存先后出现两个完全相同的状态的话,那么这个程序一定是死循环

1kilobyte = 2^13 bit, 所以该计算机内存可能存在的不同状态是2^14种。
因为每次instruction都一定会改变内存的状态(因为但凡有一次不改变,那就已经死循环了),所以这个计算机最大能执行的不相同操作是2^14次(因为如果程序在2^14次操作中还没能停机,那第2^14+1次操作一定和之前的2^14次操作中的某一个相同)。
又因为运行速度是1秒10^6 = 2^20次操作,因此在2^(-6) = 0.016秒内,就能够进行2^14次操作。也就是说,如果0.016秒内还没能停下的程序,就永远不会停下了

补充内容 (2015-8-13 20:47):
抱歉,此楼的“状态数”是不正确的。更新过的答案请看16楼
回复 支持 反对

使用道具 举报

我的人缘0
UmassJin 发表于 2015-8-13 05:46:31 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
stellari 发表于 2015-8-12 12:40
我觉得第二题应该这么想:

因为数据和程序都在内存中,所以,如果在某这两个时间点,内存中的内容处于完 ...

不是很明白,这里一个状态表示什么意思?2^13bit RAM,每个bit表示0或者1,所以总共有2^14状态吗?
回复 支持 反对

使用道具 举报

我的人缘0
stellari 发表于 2015-8-13 11:27:06 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
UmassJin 发表于 2015-8-13 05:46
不是很明白,这里一个状态表示什么意思?2^13bit RAM,每个bit表示0或者1,所以总共有2^14状态吗?
. Waral 博客有更多文章,
嗯,我所说的“状态”就是“内存中所有位的0-1状态的集合”,也就是一个2^13维的0-1向量。
回复 支持 反对

使用道具 举报

我的人缘0
UmassJin 发表于 2015-8-13 12:43:10 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
stellari 发表于 2015-8-13 11:27
嗯,我所说的“状态”就是“内存中所有位的0-1状态的集合”,也就是一个2^13维的0-1向量。
. 留学申请论坛-一亩三分地
好的,多谢啦!那也就是说不管是程序还是参数存在内存中都是以0/1表示,所以可以用一个状态表示
回复 支持 反对

使用道具 举报

我的人缘0
UmassJin 发表于 2015-8-13 12:43:19 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
stellari 发表于 2015-8-13 11:27
嗯,我所说的“状态”就是“内存中所有位的0-1状态的集合”,也就是一个2^13维的0-1向量。
. From 1point 3acres bbs
好的,多谢啦!那也就是说不管是程序还是参数存在内存中都是以0/1表示,所以可以用一个状态表示
回复 支持 反对

使用道具 举报

我的人缘0
stellari 发表于 2015-8-13 19:49:11 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
UmassJin 发表于 2015-8-13 12:43
好的,多谢啦!那也就是说不管是程序还是参数存在内存中都是以0/1表示,所以可以用一个状态表示

是的,就是这样。这道题其实不难,但是需要比较独特的思路——把程序和数据看做一个整体。

回复 支持 反对

使用道具 举报

我的人缘0
wm_thu 发表于 2015-8-14 06:53:22 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
第二题很赞,关键是像 10楼 说的那样,认识到:
1。计算机本质是一个有限状态机。在无输入的情况下,状态转移关系也是确定的。所以如果遍历了所有状态仍未停止,就永远不会停止。. 留学申请论坛-一亩三分地
2。计算机采用程序存储结构。程序和数据都放在内存里,都属于“状态”的一种。因此不管加载什么程序,1中的结论仍然成立。
回复 支持 反对

使用道具 举报

我的人缘0
jasusy 发表于 2015-8-14 08:03:38 来自手机 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
stellari 发表于 2015-8-11 20:40.本文原创自1point3acres论坛
我觉得第二题应该这么想:
.本文原创自1point3acres论坛
因为数据和程序都在内存中,所以,如果在某这两个时间点,内存中的内容处于完 ...
来源一亩.三分地论坛.
嗯,直接跳过代码从内存状态解释靠谱!赞一个
回复 支持 反对

使用道具 举报

我的人缘0
jasusy 发表于 2015-8-14 08:08:23 来自手机 | 显示全部楼层
  此人我要顶:
 
0% (暂未有人投票) 【我投】
  此人我要踩:
 
0% (暂未有人投票) 【我投】
stellari 发表于 2015-8-13 04:46
不好意思,我之前的答案完全搞错了。2^13(也就是8000)维的向量总共能表示的状态数不是2^14种,而是2^(2^1 ...

嗯,不过这应该是最worst的worst case了
回复 支持 反对

使用道具 举报

我的人缘0
stellari 发表于 2015-8-14 18:04:06 | 显示全部楼层
  此人我要顶:
 
100% (3) 【我投】
  此人我要踩:
 
0% (0) 【我投】
jasusy 发表于 2015-8-14 08:08. 1point 3acres 论坛
嗯,不过这应该是最worst的worst case了

是的,但是题目要求是“prove”,也就是说,等不够这么长时间的话,就不能一口咬定这个程序是死循环还是时间比较长的有限循环。
.留学论坛-一亩-三分地
总感觉这题有点要把面试者的思维往图灵机和停机问题上引的意思。
回复 支持 反对

使用道具 举报

游客
请先登录

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-6-24 09:05

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表