Google new grad 电面面经

stellari 发表于 2015-8-12 12:40
我觉得第二题应该这么想：

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

不是很明白，这里一个状态表示什么意思？2^13bit RAM，每个bit表示0或者1，所以总共有2^14状态吗？

UmassJin 发表于 2015-8-13 05:46
不是很明白，这里一个状态表示什么意思？2^13bit RAM，每个bit表示0或者1，所以总共有2^14状态吗？

嗯，我所说的“状态”就是“内存中所有位的0-1状态的集合”，也就是一个2^13维的0-1向量。

stellari 发表于 2015-8-13 11:27
嗯，我所说的“状态”就是“内存中所有位的0-1状态的集合”，也就是一个2^13维的0-1向量。

好的，多谢啦！那也就是说不管是程序还是参数存在内存中都是以0/1表示，所以可以用一个状态表示

stellari 发表于 2015-8-13 11:27
嗯，我所说的“状态”就是“内存中所有位的0-1状态的集合”，也就是一个2^13维的0-1向量。

好的，多谢啦！那也就是说不管是程序还是参数存在内存中都是以0/1表示，所以可以用一个状态表示

UmassJin 发表于 2015-8-13 12:43
好的，多谢啦！那也就是说不管是程序还是参数存在内存中都是以0/1表示，所以可以用一个状态表示

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

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

这次应该没算错……吧。

第二题很赞，关键是像 10楼 说的那样，认识到：
1。计算机本质是一个有限状态机。在无输入的情况下，状态转移关系也是确定的。所以如果遍历了所有状态仍未停止，就永远不会停止。
2。计算机采用程序存储结构。程序和数据都放在内存里，都属于“状态”的一种。因此不管加载什么程序，1中的结论仍然成立。

stellari 发表于 2015-8-11 20:40
我觉得第二题应该这么想：

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

嗯，直接跳过代码从内存状态解释靠谱！赞一个

stellari 发表于 2015-8-13 04:46
不好意思，我之前的答案完全搞错了。2^13（也就是8000）维的向量总共能表示的状态数不是2^14种，而是2^(2^1 ...

嗯，不过这应该是最worst的worst case了

jasusy 发表于 2015-8-14 08:08
嗯，不过这应该是最worst的worst case了

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

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