IXL Learning Phone interview 面经

刚面完IXL phone interview， 是个中国小哥， 人很好，问了两道题。
第一道题 generate random Fibonacci num

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

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

rn 6, 1 / 11 = 0.090909 return 09；

1. public int generate(int n){
   
2.      if (n <= 1) return 1;
   
3.      List<Integer> res = new ArrayList<>();
   
4.      res.add(1);
   
5.      res.add(1);
   
6.      int i = 1;
   
7.      while (res.get(i) <= n){
   
8.            i++;
   
9.            res.add(res.get(i - 1) +res.get(i - 2));
   
10.      }
    
11.      Random rd = new Random();
    
12.      return res.get(rd.nextInt(i));
    
13. }
    
14. 
    
15. public String generate (int n){
    
16.      long rem = 1;
    
17.      StringBuilder sb = new StringBuilder();
    
18.      Map<Long, Integer> map = new HashMap<>();
    
19.      while (rem != 0){
    
20.           if (map.containsKey(rem)) {
    
21.                return sb.toString().substring(map.get(rem));
    
22.           } else {
    
23.                map.put(rem, res.length());
    
24.                rem *= 10;
    
25.                res.append(rem / n);
    
26.                rem %= n;
    
27.           }
    
28.      }
    
29.      return "0";
    
30. }

复制代码

斐波那契那道题 LZ的解法不是空间最优， 面试官想强行挑刺的话， 还是可以fail掉的

遇到原题的同学不要直接复制code哦！谢谢

今天刚收到邮件约了这周四的电面，lz能不能加一下我微信（私信给您了）...想再问一下电面

请问楼主斐波那契那道题有没有follow up呢？谢谢楼主啦！

Urumic 发表于 2018-1-29 07:32
请问楼主斐波那契那道题有没有follow up呢？谢谢楼主啦！

没有哈， 直接就过了

qwqw 发表于 2018-2-5 14:20
斐波那契那道题 LZ的解法不是空间最优， 面试官想强行挑刺的话， 还是可以fail掉的

请问下这题怎么优化空间呢，从1到n，去二叉找第m个斐波那契数小于等于n，然后从random.nextInt(m)去随机生成一个斐波那契数? 请教一下。。

写了一个第一题的方法。我是用一个包含2个元素的int[] 来储存前两个元素，随着运算次数动态更新，是每一次1位置的都是最新的。然后维护一个count来记录下一共计算了多少个值，从而计算取到的概率，参考就是蓄水池方法。请大家指教哈~

1. 
   
2. public static int generate(int n){
   
3.                 if(n < 1) return 0;
   
4.                 int count = 1, res = 0;
   
5.                 int[] f = new int[2];
   
6.                 f[0] = 0; f[1] = 1;
   
7.                 Random r = new Random();
   
8.                 while(f[1] <= n){
   
9.                         if(r.nextInt(count) == 0) res = f[1];
   
10.                         int t = f[0];
    
11.                         f[0] = f[1];
    
12.                         f[1] = f[0] + t;
    
13.                         count++;
    
14.                 }
    

复制代码