一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 639|回复: 17
收起左侧

狗狗店面

[复制链接] |试试Instant~ |关注本帖
翔在天空 发表于 2016-9-24 10:49:22 | 显示全部楼层 |阅读模式

() @ - -  |

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
今天下午的新鲜面经,来回馈一下地里的小伙伴,顺便求过求大米~. visit 1point3acres.com for more.
1. 给一个string让encode,比如“aaabb”->“a3b2”
然后嘴跑两个testcase后follow up问这种encode方法有什么问题
2. 给一个整数n, 以1/2^n的概率返回1,其余返回0
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
补充内容 (2016-9-26 00:50):.鐣欏璁哄潧-涓浜-涓夊垎鍦
求加大米

补充内容 (2016-10-1 00:39):
已过,拿到onsite,求大米

评分

2

查看全部评分

Sayings 发表于 2016-9-24 12:50:20 | 显示全部楼层
第二题:
random 0-1的数,如果小于0.5 n=n-1 再递归算一遍  直到n=0, 返回1. 这个思路对吗?
代码差不多这样.1point3acres缃

  1.         public int solution(int n){
  2.                 if(n == 0) return 1;
  3.                 double rand = Math.random();
  4.                 int ans;. Waral 鍗氬鏈夋洿澶氭枃绔,
  5.                 if(rand<=0.5){
  6.                         ans = solution(n-1);. visit 1point3acres.com for more.
  7.                 }else{
  8.                         ans = 0;
  9.                 }. 1point3acres.com/bbs
  10.                 return ans;
  11.         }
复制代码
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-24 13:00:47 | 显示全部楼层
Sayings 发表于 2016-9-24 12:50
第二题:
random 0-1的数,如果小于0.5 n=n-1 再递归算一遍  直到n=0, 返回1. 这个思路对吗?
代码差不多 ...
-google 1point3acres
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
回复 支持 反对

使用道具 举报

 楼主| 翔在天空 发表于 2016-9-25 00:13:59 | 显示全部楼层
ytsr 发表于 2016-9-24 13:00
just return rand()%(2^n)==0

补充内容 (2016-9-24 13:02):
. 1point 3acres 璁哄潧
我开始给的这个rand()%(2^n)==0的解法,但是明显n太大会overflow
回复 支持 反对

使用道具 举报

 楼主| 翔在天空 发表于 2016-9-25 00:15:38 | 显示全部楼层
Sayings 发表于 2016-9-24 12:50
第二题:
random 0-1的数,如果小于0.5 n=n-1 再递归算一遍  直到n=0, 返回1. 这个思路对吗?. 1point3acres.com/bbs
代码差不多 ...
. Waral 鍗氬鏈夋洿澶氭枃绔,
这个基本对吧,但是不用递归的,就循环n次,每次rand 0或者1,然后加和,最后和为0的话返回1,否则返回0就好
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-9-25 01:29:42 | 显示全部楼层
第一题单个字符的时候怎么encode?比如abc要是变成a1b1c1那不是更长吗?
回复 支持 反对

使用道具 举报

ytsr 发表于 2016-9-25 01:38:27 | 显示全部楼层
翔在天空 发表于 2016-9-25 00:13
我开始给的这个rand()%(2^n)==0的解法,但是明显n太大会overflow

既然你知道会overflow那就处理overflow的case就行了。
一共需要n/32个随机数。无非是分段处理.鏈枃鍘熷垱鑷1point3acres璁哄潧

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

使用道具 举报

Romeobaby 发表于 2016-9-25 01:51:15 | 显示全部楼层
chestnut9919 发表于 2016-9-25 01:29. From 1point 3acres bbs
第一题单个字符的时候怎么encode?比如abc要是变成a1b1c1那不是更长吗?

好聪明  能从这个角度想
回复 支持 反对

使用道具 举报

Sayings 发表于 2016-9-25 03:54:55 | 显示全部楼层
翔在天空 发表于 2016-9-25 00:15
这个基本对吧,但是不用递归的,就循环n次,每次rand 0或者1,然后加和,最后和为0的话返回1,否则返回0 ...
. visit 1point3acres.com for more.
嗯是的~最近递归instinct
写完后发现iterative就好了~
回复 支持 反对

使用道具 举报

 楼主| 翔在天空 发表于 2016-9-25 22:55:56 | 显示全部楼层
chestnut9919 发表于 2016-9-25 01:29
第一题单个字符的时候怎么encode?比如abc要是变成a1b1c1那不是更长吗?

这个问题我也问面试官了,她表示就是a1b1c1
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-9-25 22:58:23 | 显示全部楼层
翔在天空 发表于 2016-9-25 22:55
这个问题我也问面试官了,她表示就是a1b1c1

所以这种encode方法有什么问题呢?
回复 支持 反对

使用道具 举报

 楼主| 翔在天空 发表于 2016-9-25 23:05:15 | 显示全部楼层
chestnut9919 发表于 2016-9-25 22:58. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
所以这种encode方法有什么问题呢?
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
就是如果这个string里面原本有数字的话,比如"aa3bbb5"之类的,你就不知道encode以后哪些是表示字符长度的数字啦
回复 支持 反对

使用道具 举报

chestnut9919 发表于 2016-9-26 00:50:08 | 显示全部楼层
翔在天空 发表于 2016-9-25 23:05
就是如果这个string里面原本有数字的话,比如"aa3bbb5"之类的,你就不知道encode以后哪些是表示字符长度 ...

对哦!那楼主说怎么解决呢?这个部分需要code嘛 感觉好麻烦啊
回复 支持 反对

使用道具 举报

 楼主| 翔在天空 发表于 2016-9-26 00:51:42 | 显示全部楼层
chestnut9919 发表于 2016-9-26 00:50
对哦!那楼主说怎么解决呢?这个部分需要code嘛 感觉好麻烦啊

和树的decode差不多,加个special character就好了,比如 #
回复 支持 反对

使用道具 举报

regist1234 发表于 2016-9-26 00:58:50 | 显示全部楼层
  1. <p>for (int i=0;i<n;i++)</p><p>  if (rand()%2==0)</p><p>    return 0;</p><p>return 1</p>
复制代码
回复 支持 反对

使用道具 举报

regist1234 发表于 2016-9-26 01:00:20 | 显示全部楼层
for (int i=0;i<n;i++)
  if (rand()%2==0)
    return 0;
return 1. 1point3acres.com/bbs

为什么在论坛里都成了乱码。。。
回复 支持 反对

使用道具 举报

zgbb 发表于 2016-9-26 02:43:09 | 显示全部楼层
  1. public int generateOneOrZero(int n) {. 1point3acres.com/bbs
  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, 第三行多余忘记删除了
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-6 08:58

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表