Google总部onsite面经

Ryaaaaaaaaaaa 发表于 2018-4-4 22:14
比如说给了一个二维数组
g' g
g'' g'''

必须是两个string相应位置的char confusing么？

Ryaaaaaaaaaaa 发表于 2018-4-4 22:42
emmm..比如有这样一个grid
###########
#        *      # *#

可以从target位置*开始么？感觉就是从每个target位置开始BFS吧，然后可以用这个矩阵存储steps，每次相应grid+下次BFS，最后求grid最小值。

idatascience 发表于 2018-4-5 04:10
必须是两个string相应位置的char confusing么？

恩对的，比如g'og''和g'hg这样就不confusing，因为不是每个char都confusing，但是如果是g'og''和g'og就属于confusing的，因为自己跟自己也算confuse~

idatascience 发表于 2018-4-5 04:13
可以从target位置*开始么？感觉就是从每个target位置开始BFS吧，然后可以用这个矩阵存储steps，每次相应g ...

嗯嗯我当时用的就是这个方法

oio14644 发表于 2018-4-5 03:05
个Array出去两两差值最大的 什么意思？

额...不好意思手癌了...就是给一个Array然后里面的integer两两求差值，返回差值最大的

Ryaaaaaaaaaaa 发表于 2018-4-5 05:57
恩对的，比如g'og''和g'hg这样就不confusing，因为不是每个char都confusing，但是如果是g'og''和g'og就属 ...

这样的话，如果我理解没错的话，考虑到刚开始的两个list，每个list里可能有重复的元素，而且还可能share一些相同的元素，那么就是两个list同时过一遍，生成一个confusingDict。（有一个问题，如果A跟B confuse，B跟C confuse，这两个关系可以直接从list里infer出来，那么，可以根据这个infer A和C是什么关系呢？）， 根据confusingDict来得出string是否是confuse，也是遍历。

idatascience 发表于 2018-4-5 06:10
这样的话，如果我理解没错的话，考虑到刚开始的两个list，每个list里可能有重复的元素，而且还可能share ...

嗯，那个面试小哥的意思是如果list里有A,B和B,C那肯定会有A,C，list会包含所有的confuse对~，我用的方法是map的key存所有character，value是一个set存跟这个character confuse的所有character，面完了之后问了下小哥平时怎么处理这个问题（他平时工作就是研究这方面的），他说差不多就是这样的~

以为第二轮是求约束条件下最短路径问题。。。还在想这问题不是NP的吗哈哈哈

littledog 发表于 2018-4-5 10:35
以为第二轮是求约束条件下最短路径问题。。。还在想这问题不是NP的吗哈哈哈

hhh你的头像很萌

比较好奇楼主第一轮怎么问的，扫地机器人这题可以出的很简单，也可以出的很难
就是要清扫房间中每个位置么？有没有要求所走路径尽可能的短？