Jingchi电面

两道题。
1. 纵向打印tree.
      1
    /   \

   2     3

  / \   / \
  4  5  6  2
输出
4

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

游客，您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
color="#222222">挂了，第二问用dp没写明白。

攒人品，求大米！他家面经不多，为了攒人品发一个。

丑猪宝 发表于 2018-1-8 00:26
这个用DP似乎复杂度更高吧。如果直接按概率公式计算的话，C(n,k) cost O (k), (1/2)^n cost O(log n)，总 ...

嗯，你提供了一个很好的思路！感觉可以和面试官讨论，问能否用概率公式。如果批准的话这样时间复杂度低，还更好写。

(1/2)^n cost不是O(n)么？移位n次？

flykite083 发表于 2018-1-7 23:07
它需要你用程序去解。你可以把这个问题去分解， F(n, k) = F(n, k -1) + F(n - 1, k - 1)

这个用DP似乎复杂度更高吧。如果直接按概率公式计算的话，C(n,k) cost O (k), (1/2)^n cost O(log n)，总共复杂度O(k) + O(log n)。

APTX4869_2017 发表于 2018-2-9 04:02
第二题是类似用背包问题的方法做吗？时间复杂度n^2？不清楚诶，真心求教

我去年11月面过这家。。也碰到过这道题。。其实就是k个向上的概率和k-1个向上的概率有关系。。具体的临时有点想不起来了

挂在第二题上面了

dhx1995881 发表于 2018-1-6 10:17
挂在第二题上面了

jingchi 是？

景驰，一个做自动驾驶的小公司

flykite083 发表于 2018-1-7 07:33
景驰，一个做自动驾驶的小公司

请问楼主多长时间通知的结果啊

谢谢分享，在地里jingchi面经感觉不多。请问楼主是怎么准备的，我也准备面，但是据说比一般公司难0-0，没啥底。

daofeng 发表于 2018-1-7 07:57
请问楼主多长时间通知的结果啊

好像面完之后几天吧。

DenHar 发表于 2018-1-7 08:21
谢谢分享，在地里jingchi面经感觉不多。请问楼主是怎么准备的，我也准备面，但是据说比一般公司难0-0，没啥 ...

我当时都没准备。唉，后悔了…………建议多看看dp.

楼主，表示没太看懂第二题。n枚硬币，k个正面，难道不是一个概率题么。
p = c (n, k) * (1 / 2) ^ n
求思路。

jingchi是不是开始要在一个国内的acm网站上写题目啊