Hive AI 电面面经

45min电面，面试官是一个白人小哥，前面他介绍了一下公司，然后就开始做题了。

题目是，给你一个盒子，盒子可能是locked or unlocked，然后在盒子的里面，你可能会看到一些硬币，其他盒子，或者钥匙。
求，一共能得到几个硬币。什么都没给你，数据结构方法什么的都要自己写

跟面试官交流，还有写code的时候得到的一些细节：
一把钥匙只能打开一个盒子，而且是特定的某个盒子。
一个盒子里面，可以同时存在硬币，盒子，钥匙
一个盒子里面可以存在多个小盒子
可以会遇到你先遇到一个上锁的盒子，然后后来再别的盒子里发现一把钥匙，你要回过去把上锁的盒子打开

楼主其实还是第一次遇到这种题，比较生疏，写着写着才有了点感觉
写了box和key的data structure，自己写了一些function。
我的解法就是DFS，每次遇到盒子，就先看看能不能打开，然后打开以后把里面的硬币和钥匙都收集起来，然后遇到新的盒子就继续做DFS，但是有一种情况没有考虑就是，先遇到上锁的盒子，后来才遇他的到钥匙，我说那就把没打开的盒子也存起来，每次遇到新的钥匙就会过去把那些盒子再查一遍能不能打开，能打开就dfs？
一共给了半小时写，所以后面没来得及，就匆匆结束了。

面试体验不是很好，面试官小哥在出题以后就不说话了，全程保持安静，只有我一个人在说话，我说什么也不怎么给反馈，有点尴尬，还听到他仿佛在厨房做饭的声音。。。

公司只有90个人，挺小的，好像还在B轮，应该不会去。

有没有人知道类似的题目啊，想看看正确的写法应该是什么样的

PhoebeJL 发表于 2020-4-20 13:19
有没有人知道类似的题目啊，想看看正确的写法应该是什么样的

我觉得这个题bfs比较好。遇到一个盒子就进queue，如果能打开就把里边的小盒子进queue，如果打不开就重新进queue，然后maintain一个key的map，看看哪个盒子能打开哪个打不开。终止条件是queue里所有的盒子都是locked或者queue为空