狗狗店面

今天下午的新鲜面经，来回馈一下地里的小伙伴，顺便求过求大米~
1. 给一个string让encode，

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

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

-10-1 00:39):
已过，拿到onsite，求大米

第二题：
random 0-1的数，如果小于0.5 n=n-1 再递归算一遍  直到n=0, 返回1. 这个思路对吗？
代码差不多这样

1.         public int solution(int n){
   
2.                 if(n == 0) return 1;
   
3.                 double rand = Math.random();
   
4.                 int ans;
   
5.                 if(rand<=0.5){
   
6.                         ans = solution(n-1);
   
7.                 }else{
   
8.                         ans = 0;
   
9.                 }
   
10.                 return ans;
    
11.         }

复制代码

1. public int generateOneOrZero(int n) {
   
2.         Random rd  = new Random();
   
3.         int sum = 0;
   
4.         for (int i = 0; i < n; i++) {
   
5.             if (rd.nextDouble() < 0.5) {
   
6.                 return 0;
   
7.             }
   
8.         }
   
9.         return 1;
   
10.     }

复制代码

补充内容 (2016-9-26 02:45):
typo, 第三行多余忘记删除了

Sayings 发表于 2016-9-24 12:50
第二题：
random 0-1的数，如果小于0.5 n=n-1 再递归算一遍  直到n=0, 返回1. 这个思路对吗？
代码差不多 ...

这个基本对吧，但是不用递归的，就循环n次，每次rand 0或者1，然后加和，最后和为0的话返回1，否则返回0就好

Sayings 发表于 2016-9-24 12:50
第二题：
random 0-1的数，如果小于0.5 n=n-1 再递归算一遍  直到n=0, 返回1. 这个思路对吗？
代码差不多 ...

just return rand()%(2^n)==0

补充内容 (2016-9-24 13:02):
当然得看n的范围了，n太大的话，得用多个随机数了。小于32，一个就够了

补充内容 (2016-9-24 13:03):
2^n, i.e., 1<<n

ytsr 发表于 2016-9-24 13:00
just return rand()%(2^n)==0

补充内容 (2016-9-24 13:02):

我开始给的这个rand()%(2^n)==0的解法，但是明显n太大会overflow

第一题单个字符的时候怎么encode？比如abc要是变成a1b1c1那不是更长吗？

翔在天空 发表于 2016-9-25 00:13
我开始给的这个rand()%(2^n)==0的解法，但是明显n太大会overflow

既然你知道会overflow那就处理overflow的case就行了。
一共需要n/32个随机数。无非是分段处理

补充内容 (2016-9-25 02:13):
但是n太大的话这么弄也有问题，因为伪随机数是不可能产生两个连续的0的。

chestnut9919 发表于 2016-9-25 01:29
第一题单个字符的时候怎么encode？比如abc要是变成a1b1c1那不是更长吗？

好聪明  能从这个角度想

翔在天空 发表于 2016-9-25 00:15
这个基本对吧，但是不用递归的，就循环n次，每次rand 0或者1，然后加和，最后和为0的话返回1，否则返回0 ...

嗯是的～最近递归instinct
写完后发现iterative就好了～

chestnut9919 发表于 2016-9-25 01:29
第一题单个字符的时候怎么encode？比如abc要是变成a1b1c1那不是更长吗？

这个问题我也问面试官了，她表示就是a1b1c1