一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 3430|回复: 26
收起左侧

Google new grad 电面面经

[复制链接] |试试Instant~ |关注本帖
lithui 发表于 2015-5-20 00:00:01 | 显示全部楼层 |阅读模式

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

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

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

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”.. visit 1point3acres.com for more.
(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

查看全部评分

本帖被以下淘专辑推荐:

xiexiangyi0 发表于 2015-5-20 11:42:38 | 显示全部楼层
这个面试还行吧,. 鍥磋鎴戜滑@1point 3 acres
. From 1point 3acres bbs
第一题就是遍历所有url并且每次数一个就在全局变量上加一个1,
不能重复访问页面,否则无限循环,那就hash一下就好,相当于mark as visited,所以整个就一个DFS:
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
public class Solution{
    private int total_pages;. 1point3acres.com/bbs
    private Set <String> visited;
    public int counturl (String root_url){
        total_pages=0;
        visited=new HashSet<>();. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
        iterate_all(root_url);. 鍥磋鎴戜滑@1point 3 acres
        return total_pages;.鐣欏璁哄潧-涓浜-涓夊垎鍦
    }
    private void interate_all(url){
        List<String> children = fetchPageAndExtractUrls(url);
        if(children.size()==0) return;
        for(String child: children){. 1point3acres.com/bbs
            if(!visited.contains(child)){
. visit 1point3acres.com for more.                visited.add(child);
                total_pages++;. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
                interate_all(child);
            }
        }
    }
}. more info on 1point3acres.com

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

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

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

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

使用道具 举报

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

这次应该没算错……吧。.1point3acres缃

回复 支持 1 反对 0

使用道具 举报

xiexiangyi0 发表于 2015-5-20 11:45:01 | 显示全部楼层
打错了,我想说最坏情况每一个指令都是loop
回复 支持 反对

使用道具 举报

xiexiangyi0 发表于 2015-5-20 11:46:35 | 显示全部楼层
不过再想想如果是250个嵌套循环就有点恐怖了
回复 支持 反对

使用道具 举报

猴子0523 发表于 2015-5-20 21:33:19 | 显示全部楼层
xiexiangyi0 发表于 2015-5-20 11:46
不过再想想如果是250个嵌套循环就有点恐怖了

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

使用道具 举报

xiexiangyi0 发表于 2015-5-21 02:48:30 | 显示全部楼层
猴子0523 发表于 2015-5-20 21:33. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
250个指令嵌套循环起来就是2^(23*250) 吗
. 鍥磋鎴戜滑@1point 3 acres
嗯,差不多是这样的,反正是理论题,估计就这么答了
回复 支持 反对

使用道具 举报

 楼主| lithui 发表于 2015-5-23 12:50:13 | 显示全部楼层
xiexiangyi0 发表于 2015-5-20 11:42
这个面试还行吧,

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

多谢指点. 受教了.
回复 支持 反对

使用道具 举报

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

使用道具 举报

xiexiangyi0 发表于 2015-8-12 12:09:26 | 显示全部楼层
xanadulord 发表于 2015-5-24 01:15
我怎么觉得第二题是无解呢,在代码里可以随便定义一个loop有多少次循环,这个是无法判断的吧?
. visit 1point3acres.com for more.
有限循环是需要记录你循环了多少次了,这样才能判断何时结束(for loop),最坏情况就是0到2^32这么多个循环(假设32位机)(否则溢出)。无限循环的话就不用记录,所以永远继续循环
回复 支持 反对

使用道具 举报

stellari 发表于 2015-8-12 12:40:38 | 显示全部楼层
我觉得第二题应该这么想:. from: 1point3acres.com/bbs

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

1kilobyte = 2^13 bit, 所以该计算机内存可能存在的不同状态是2^14种。. more info on 1point3acres.com
因为每次instruction都一定会改变内存的状态(因为但凡有一次不改变,那就已经死循环了),所以这个计算机最大能执行的不相同操作是2^14次(因为如果程序在2^14次操作中还没能停机,那第2^14+1次操作一定和之前的2^14次操作中的某一个相同)。
又因为运行速度是1秒10^6 = 2^20次操作,因此在2^(-6) = 0.016秒内,就能够进行2^14次操作。也就是说,如果0.016秒内还没能停下的程序,就永远不会停下了
. Waral 鍗氬鏈夋洿澶氭枃绔,
补充内容 (2015-8-13 20:47):
抱歉,此楼的“状态数”是不正确的。更新过的答案请看16楼
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-8-13 05:46:31 | 显示全部楼层
stellari 发表于 2015-8-12 12:40
我觉得第二题应该这么想:

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

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

使用道具 举报

stellari 发表于 2015-8-13 11:27:06 | 显示全部楼层
UmassJin 发表于 2015-8-13 05:46
不是很明白,这里一个状态表示什么意思?2^13bit RAM,每个bit表示0或者1,所以总共有2^14状态吗?

嗯,我所说的“状态”就是“内存中所有位的0-1状态的集合”,也就是一个2^13维的0-1向量。
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-8-13 12:43:10 | 显示全部楼层
stellari 发表于 2015-8-13 11:27. From 1point 3acres bbs
嗯,我所说的“状态”就是“内存中所有位的0-1状态的集合”,也就是一个2^13维的0-1向量。
. visit 1point3acres.com for more.
好的,多谢啦!那也就是说不管是程序还是参数存在内存中都是以0/1表示,所以可以用一个状态表示
回复 支持 反对

使用道具 举报

UmassJin 发表于 2015-8-13 12:43:19 | 显示全部楼层
stellari 发表于 2015-8-13 11:27
嗯,我所说的“状态”就是“内存中所有位的0-1状态的集合”,也就是一个2^13维的0-1向量。

好的,多谢啦!那也就是说不管是程序还是参数存在内存中都是以0/1表示,所以可以用一个状态表示
回复 支持 反对

使用道具 举报

stellari 发表于 2015-8-13 19:49:11 | 显示全部楼层
UmassJin 发表于 2015-8-13 12:43
好的,多谢啦!那也就是说不管是程序还是参数存在内存中都是以0/1表示,所以可以用一个状态表示

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

回复 支持 反对

使用道具 举报

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

使用道具 举报

jasusy 发表于 2015-8-14 08:03:38 来自手机 | 显示全部楼层
stellari 发表于 2015-8-11 20:40
我觉得第二题应该这么想:

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

嗯,直接跳过代码从内存状态解释靠谱!赞一个
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

stellari 发表于 2015-8-14 18:04:06 | 显示全部楼层
jasusy 发表于 2015-8-14 08:08
嗯,不过这应该是最worst的worst case了

是的,但是题目要求是“prove”,也就是说,等不够这么长时间的话,就不能一口咬定这个程序是死循环还是时间比较长的有限循环。

总感觉这题有点要把面试者的思维往图灵机和停机问题上引的意思。
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 23:24

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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