FB 全职电面 + Follow-up

前天面的，目前没消息
只做了一题LC17，感觉面的不好，最后Follow-up没写完就问问题了

Follow-up
两种iterative的写法，应该是BFS和DFS两种recursive的写法，同上
What is time and space complexity of iterative BFS solutions, why?

What is time an

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

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

uot;, 3: "f", ..., 10: "x", 11: "y", 12: "z", ...

补充内容 (2017-1-17 02:03):
已跪

1. class Solution {
   
2.     private char[][] map = {{},{},
   
3.                             {'a', 'b', 'c'},
   
4.                             {'d', 'e', 'f'},
   
5.                             {'g', 'h', 'i'},
   
6.                             {'j', 'k', 'l'},
   
7.                             {'m', 'n', 'o'},
   
8.                             {'p', 'q', 'r', 's'},
   
9.                             {'t', 'u', 'v'},
   
10.                             {'w', 'x', 'y', 'z'}};
    
11.     public List<String> letterCombinations(String digits) {
    
12.         List<String> list = new ArrayList<>();
    
13.         if(digits.length() == 0) {
    
14.             return list;
    
15.         }
    
16.         list.add(new String());//tricky point
    
17.         for(int k = 0; k < digits.length(); k++) {
    
18.             List<String> temp = new ArrayList<>();
    
19.             for(int i = 0; i < list.size(); i++) {
    
20.                 for(int j = 0; j < map[digits.charAt(k) - '0'].length; j++) {
    
21.                     String s = list.get(i);
    
22.                     s += map[digits.charAt(k) - '0'][j];
    
23.                     temp.add(s);
    
24.                 }
    
25.             }
    
26.             list = temp;
    
27.         }
    
28.         return list;
    
29.     }
    
30. }

复制代码

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

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

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

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

无论是bfs还是dfs他们的时间复杂度都是 m**n * n, m是3，n是string的长度。 空间复杂度都是 m **n 对吗？

honghunan 发表于 2017-1-15 05:49
无论是bfs还是dfs他们的时间复杂度都是 m**n * n, m是3，n是string的长度。 空间复杂度都是 m **n 对吗？

** 是什么意思？我用Java写的

野生的皮皮鲁 发表于 2017-1-15 06:01
** 是什么意思？我用Java写的

m^n 指数级别

honghunan 发表于 2017-1-15 05:49
无论是bfs还是dfs他们的时间复杂度都是 m**n * n, m是3，n是string的长度。 空间复杂度都是 m **n 对吗？

DFS的空间复杂度可以做到O(n)

honghunan 发表于 2017-1-15 05:49
无论是bfs还是dfs他们的时间复杂度都是 m**n * n, m是3，n是string的长度。 空间复杂度都是 m **n 对吗？

DFS的空间复杂度可以做到O(n)

居然这么多复杂度分析follow-up.. 真是好奇葩啊..

YoYoqiekenow 发表于 2017-2-5 15:06
DFS的空间复杂度可以做到O(n)

怎么做呢？最后一轮都得存这么多吧

我就好奇bfs如何recursive。。。。

迭代和递归有区别吗