Google new grad 电面面经

一位阿三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 o

您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

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

不好意思，我之前的答案完全搞错了。2^13（也就是8000）维的向量总共能表示的状态数不是2^14种，而是2^(2^13) = 2^8000 种（就像3维向量能表示的状态数是2^3一样）！在1s执行2^20次的计算机上，最多需要2^(8000 - 20)  ~= 10^2400秒！这数字远远超过宇宙年龄，也就是说，通过观察判定程序是否是无限循环是不实际的。

这次应该没算错……吧。

这个面试还行吧，

第一题就是遍历所有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);
        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);
                total_pages++;
                interate_all(child);
            }
        }
    }
}

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

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

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

这只是我的初步想法，欢迎指教~

打错了，我想说最坏情况每一个指令都是loop

不过再想想如果是250个嵌套循环就有点恐怖了

xiexiangyi0 发表于 2015-5-20 11:46
不过再想想如果是250个嵌套循环就有点恐怖了

250个指令嵌套循环起来就是2^(23*250) 吗

猴子0523 发表于 2015-5-20 21:33
250个指令嵌套循环起来就是2^(23*250) 吗

嗯，差不多是这样的，反正是理论题，估计就这么答了

xiexiangyi0 发表于 2015-5-20 11:42
这个面试还行吧，

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

多谢指点. 受教了.

我怎么觉得第二题是无解呢，在代码里可以随便定义一个loop有多少次循环，这个是无法判断的吧？

xanadulord 发表于 2015-5-24 01:15
我怎么觉得第二题是无解呢，在代码里可以随便定义一个loop有多少次循环，这个是无法判断的吧？

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

我觉得第二题应该这么想：

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

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楼