FB intern 1st round

上来说了两句直接coding
1. binary tree paths (LC257) 要求打印出path, follow up: 1. 如果所有

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

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

f non empty cells randomly with equal probability.

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

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

求问楼主 第二题怎么做的啊？

如果直接concatenation. 相当于创建一个新的字符串，时间就是linear。一共要做n次concatenation， 所以O(n^2)
full binary tree 一共logn path. 所以是nlogn

楼主请问第一题follow up你是怎么优化时间复杂度的？最好感觉就是O(n)的感觉。

lz是purdue的？

求问第一题follow up

楼主你好，第一题时间复杂度都应该是O(n)？ 优化时间复杂度的话，求问是不是把string 变成stringbulider？ 第二题是Reservoir Sampling？

BRYCEMENG 发表于 2016-12-3 13:32
lz是purdue的？

你选onsite 还是 phone？ 哪个容易一些啊

1451427216 发表于 2016-12-3 14:01
楼主你好，第一题时间复杂度都应该是O(n)？ 优化时间复杂度的话，求问是不是把string 变成stringbulider？  ...

我是用c++， full tree 的话是O(nlogn). node一条线是O(n)

zty920317 发表于 2016-12-3 11:16
楼主请问第一题follow up你是怎么优化时间复杂度的？最好感觉就是O(n)的感觉。

是的，字数字数字数

shijia8888 发表于 2016-12-3 14:01
求问第一题follow up

第一个O(n^2) 如果直接concatenation
第二个O(nlogn)

楼主第一个题dfs的话不是每个节点过一次吗？ 为啥树的形状会影响复杂度，从而会出现nlogn呢？