一亩三分地论坛

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

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

Bloomberg 刚出炉的电面

[复制链接] |试试Instant~ |关注本帖
chenyangtc 发表于 2016-1-9 04:38:54 | 显示全部楼层 |阅读模式

2016(1-3月) 码农类 本科 全职@Bloomberg - 网上海投 -  |Failfresh grad应届毕业生

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

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

x
今天电面,题目很奇怪,以前没见过,是设计题
设计一个函数int f(const char *s),有俩char *s1,s2
f(s1)==f(s2)仅在俩字符串相等时成立,
还有一个限制条件是这个函数只能用在10000个以内的不同的字符串上
想半天没想出来咋办。跪了

评分

1

查看全部评分

tltzhsajsdr 发表于 2016-1-9 09:52:54 | 显示全部楼层
实现个hash function,字符串相等才得到同样的值,10000个以内的字符串都不有碰撞。
设string里都是小写字母和数字,共36个,int值当做unsigned,一共只有2^32种值,除以10000,等于43万左右,所以可用于编码的空间就是43万左右。以36为底Log43万,约等于4,大约是每个字符串不超过4个字符,才可以实现这个要求。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

wcongying 发表于 2016-1-9 14:38:58 | 显示全部楼层
tltzhsajsdr 发表于 2016-1-9 09:52. 1point3acres.com/bbs
实现个hash function,字符串相等才得到同样的值,10000个以内的字符串都不有碰撞。
设string里都是小写字 ...

谢谢解释这题
回复 支持 1 反对 0

使用道具 举报

wcongying 发表于 2016-1-9 06:57:51 | 显示全部楼层
这道题我知道java怎么做。如果是java很简单。如果是C是不是考察C的特点?
回复 支持 反对

使用道具 举报

 楼主| chenyangtc 发表于 2016-1-9 07:03:32 | 显示全部楼层
wcongying 发表于 2016-1-9 06:57
这道题我知道java怎么做。如果是java很简单。如果是C是不是考察C的特点?

java怎么做啊?先让我用c、后来java也没想出来
回复 支持 反对

使用道具 举报

wcongying 发表于 2016-1-9 08:05:08 | 显示全部楼层
如果Input都是string,那就用 “equal()"这个方法判断即可。还是Input是字符串数组?
回复 支持 反对

使用道具 举报

 楼主| chenyangtc 发表于 2016-1-9 08:26:32 | 显示全部楼层
wcongying 发表于 2016-1-9 08:05
如果Input都是string,那就用 “equal()"这个方法判断即可。还是Input是字符串数组?
. Waral 鍗氬鏈夋洿澶氭枃绔,
不是 是要自己设计一个返回int型的函数,让返回值相同

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

zeehw 发表于 2016-1-9 14:11:33 | 显示全部楼层
顶楼上 实际上是让你实现hash funtion

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

Czon 发表于 2016-1-10 00:32:45 | 显示全部楼层
zeehw 发表于 2016-1-9 14:11
顶楼上 实际上是让你实现hash funtion

同意, 不过预先不知道hash function算法当场自己设计还是挺麻烦的
回复 支持 反对

使用道具 举报

tltzhsajsdr 发表于 2016-1-10 02:04:51 | 显示全部楼层
Czon 发表于 2016-1-10 00:32
同意, 不过预先不知道hash function算法当场自己设计还是挺麻烦的
. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
我觉得这里可能需要和面试官讨论一下,例如限定字符串长度什么的,如果不限定长度,int的空间就是那么大,你用更大的空间映射到int,是一定会有conflict的. 涓浜-涓夊垎-鍦帮紝鐙鍙戝竷
这种一一映射有个很简单的做法是把进制转换,例如36个字符,当做36进制,举个例子a19b,a代表10,b代表11,z代表35,然后转为10进制,就是b * 36 ^ 0 + 9 * 36 ^ 1 + 1 * 36 ^2 + a * 36 ^ 3

补充内容 (2016-1-10 02:14):
有一个typo,a * 36 ^ 3应该是10 * 36 ^ 3
回复 支持 反对

使用道具 举报

Czon 发表于 2016-1-10 02:38:36 | 显示全部楼层
tltzhsajsdr 发表于 2016-1-10 02:04
我觉得这里可能需要和面试官讨论一下,例如限定字符串长度什么的,如果不限定长度,int的空间就是那么大 ...

对,lintcode上有这个方法,知道了只要implement的时候避免overflow, 不知道的话当场想还是比较麻烦
回复 支持 反对

使用道具 举报

tltzhsajsdr 发表于 2016-1-10 02:45:41 | 显示全部楼层
Czon 发表于 2016-1-10 02:38
对,lintcode上有这个方法,知道了只要implement的时候避免overflow, 不知道的话当场想还是比较麻烦

回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-11 18:45

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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