[职场感言] 工作一年了,聊聊三件事

一亩三分地论坛

 找回密码
 Sign Up 注册获取更多干货
E轮2.5亿美元融资
K12教育独角兽一起作业
北京-诚聘人工智能/教育/大数据岗
坐标湾区
Games Startup
招聘游戏开发工程师
游戏初创公司招聘工程师、UIUX Designer和游戏策划
码农求职神器Triplebyte:
不用海投
内推多家公司面试
把贵司招聘信息放这里
查看: 4257|回复: 19
收起左侧

GOOGLE第二轮电面

[复制链接] |试试Instant~ |关注本帖
lihan96163 发表于 2014-4-12 01:24:39 | 显示全部楼层 |阅读模式

2014(1-3月) 码农类General 硕士 全职@Google - 网上海投 - 技术电面  | Other |

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

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

x
昨天电面,两道题 不算难,求好运~~
. From 1point 3acres bbs
1. Given a sorted array of floats, find the index of the number closest to x:.本文原创自1point3acres论坛
Example: {1.2, 2.5, 9.3}  x = 5,    return 1


. 一亩-三分-地,独家发布

2. Of the pairs of words in the dictionary that have no letters in common, find one that maximizes the product of the words' lengths.

cat
dog
feed
pull
space

pair = word1, word2
length = word1.size() * word2.size()


评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| lihan96163 发表于 2014-4-13 11:53:40 | 显示全部楼层

我刚开始写的就是N^2地解法,后来他说可以稍微改进了下

我就说可以先把每个单词处理下,用map记录出现的字母(其实遍历单词的话还是要n^2的),说了以后他貌似还比较满意,感觉他没想要我写出太高级地方法来`~
回复 支持 1 反对 0

使用道具 举报

eforms 发表于 2014-4-12 02:43:43 来自手机 | 显示全部楼层
谢谢楼主,第二题有比你n^2更好的solution吗?
回复 支持 反对

使用道具 举报

eforms 发表于 2014-4-12 02:45:00 来自手机 | 显示全部楼层
第二题有比n^2更好的solution吗?
回复 支持 反对

使用道具 举报

lhn9021 发表于 2014-4-12 10:36:10 | 显示全部楼层
第一题 感觉是binary search 比较并且记录最接近结果
第二题 我的感觉是对词进行sort 放到compressed trie 然后词的结尾记录词的长度 问题就变成找2个最长的从root到null的路径 最小公共节点是root 的问题 O(n*mlogm+m). 一亩-三分-地,独家发布

补充内容 (2014-4-12 10:37):
如果你加入trie的时候记录比较两个最长路径的话 就直接是O(n*mlogm)
回复 支持 反对

使用道具 举报

 楼主| lihan96163 发表于 2014-4-13 11:55:17 | 显示全部楼层
lhn9021 发表于 2014-4-12 10:36 来源一亩.三分地论坛.
第一题 感觉是binary search 比较并且记录最接近结果
第二题 我的感觉是对词进行sort 放到compressed trie ...

嗯嗯 第一题是二分法,第二题没想过trie
. 一亩-三分-地,独家发布
感觉你的还蛮高级哈哈
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-27 08:26:07 | 显示全部楼层
lhn9021 发表于 2014-4-12 10:36. visit 1point3acres for more.
第一题 感觉是binary search 比较并且记录最接近结果
第二题 我的感觉是对词进行sort 放到compressed trie ...

但是,你怎么避免重复啊?比如就三个次,but,cat,hit,应该是返回0,因为找不到这样的词。. From 1point 3acres bbs
但是你的方法是只找从root到leaf的。。。。。
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-7-27 12:50:05 | 显示全部楼层
第二题可以把每个单词化成26-bit的数字分别对应(a - z),出现了这位就置为1,没出现就这位就是0,存在一个Map< String , Integer >里,这样比较的时候只要 (a & b) == 0 就说明没有重复,然后用key的长度求积
Mobile Apps Category (English)728x90
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-28 06:47:14 | 显示全部楼层
zhouyoung1124 发表于 2015-7-27 12:50. Waral 博客有更多文章,
第二题可以把每个单词化成26-bit的数字分别对应(a - z),出现了这位就置为1,没出现就这位就是0,存在一个Ma ...

说的很好。
但感觉还不够。
不需要trie嘛?
时间复杂度呢?
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-7-28 09:12:14 | 显示全部楼层
jiebour 发表于 2015-7-28 06:47
说的很好。
但感觉还不够。
不需要trie嘛?
. 留学申请论坛-一亩三分地
我觉得不需要,我感觉trie的优势只是查找前缀比较快,这题和前缀顺序都无关,不遍历到最后一位也不知道究竟共有哪些字母。用bit的话单词比较复杂度是1,遍历dic两两比较总共也就是n^2, 所以O(n^2)
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-28 12:31:18 | 显示全部楼层
zhouyoung1124 发表于 2015-7-28 09:12. 1point 3acres 论坛
我觉得不需要,我感觉trie的优势只是查找前缀比较快,这题和前缀顺序都无关,不遍历到最后一位也不知道究 ...

对对对,不能赞更多!我刚看到的时候就是这么想的。感觉没别的方法了。。。。
但是。。。。。。
你把单词都扔进trie里面的话,那么首先你可以用trie去遍历所有的单词,其次,你可以用trie节省时间;
比如,你试了put不行,那么putty一定不行,也就是说put为前缀的词都不用试了,所以还是可以省时间的。类似剪枝的功效。
回复 支持 反对

使用道具 举报

wenqiang88 发表于 2015-7-28 13:36:23 | 显示全部楼层
lhn9021 发表于 2014-4-12 10:36-google 1point3acres
第一题 感觉是binary search 比较并且记录最接近结果
第二题 我的感觉是对词进行sort 放到compressed trie ...

如果只是第一个字母不相等,后面的字母相等呢?这个最小公共节点也是root吧
回复 支持 反对

使用道具 举报

zhouyoung1124 发表于 2015-7-28 21:58:55 | 显示全部楼层
jiebour 发表于 2015-7-28 12:31
对对对,不能赞更多!我刚看到的时候就是这么想的。感觉没别的方法了。。。。. visit 1point3acres for more.
但是。。。。。。
你把单 ...

每次每个词插入trie以及比较的时间应该会比用bit大一些,假定单词长度是 L的话
trie的话插入要花L次,查找还要要花L次,还要多用一个数据结构,感觉还是挺不合算的
用bit的话每个词转化成bit做L次计算,两词之间做位与操作耗时O(1),感觉相对会略快
回复 支持 反对

使用道具 举报

Nevermindeaf 发表于 2015-7-28 23:40:59 | 显示全部楼层
= =那个第二天我也碰到过,上来想了半天能不能有比n^2更好的答案,结果面试官说她从来没见有人能想出比n^2更好的答案。。。于是白浪费了几分钟
回复 支持 反对

使用道具 举报

jiebour 发表于 2015-7-29 02:07:42 | 显示全部楼层
Nevermindeaf 发表于 2015-7-28 23:40
= =那个第二天我也碰到过,上来想了半天能不能有比n^2更好的答案,结果面试官说她从来没见有人能想出比n^2 ...

你应该早早说话。。。。。。
回复 支持 反对

使用道具 举报

woshiee123 发表于 2015-8-14 06:44:02 | 显示全部楼层
Nevermindeaf 发表于 2015-7-28 23:40. 1point3acres
= =那个第二天我也碰到过,上来想了半天能不能有比n^2更好的答案,结果面试官说她从来没见有人能想出比n^2 ...

所以是位运算么 ?
回复 支持 反对

使用道具 举报

hj867955629 发表于 2015-8-27 15:40:49 | 显示全部楼层
jiebour 发表于 2015-7-28 12:31
对对对,不能赞更多!我刚看到的时候就是这么想的。感觉没别的方法了。。。。
但是。。。。。。
你把单 ...

这个地方trie没啥用吧?两个单词不同位置的同一字母,在trie中怎么检测?
回复 支持 反对

使用道具 举报

zdcx 发表于 2016-5-7 17:59:27 | 显示全部楼层
顶顶顶顶顶顶顶顶顶顶达到
回复 支持 反对

使用道具 举报

xiee 发表于 2016-6-11 23:26:56 | 显示全部楼层
第一题,binary search 变形. 围观我们@1point 3 acres
第二题,Arrays.sort(, new Compartory()), 比较 length
回复 支持 反对

使用道具 举报

logist 发表于 2016-9-25 00:43:40 | 显示全部楼层
第一题貌似简单,但一些细微问题好像比较重要,贴出自己的代码,欢迎指正.
//查找float数列中最接近x的位置
int FindFloat(vector<float> v, int x)
{
        if(v.empty())
                return -1;

        int n = v.size();
        if(x < v[0]). 留学申请论坛-一亩三分地
                return 0;
        if(x > v[n - 1])
                return n - 1;
       
        int left = 0;
        int right = n - 1;. from: 1point3acres
        int mid;

        while(right - left > 1)
        {
                mid = left + (right - left) / 2;
                if(x > v[mid])
                        left  = mid;
                else
                        right = mid;

        } 来源一亩.三分地论坛.

        return fabs(v[right] - x) < fabs(v[left] - x) ? right : left ;. 围观我们@1point 3 acres
}
回复 支持 反对

使用道具 举报

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

关闭

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

手机版|小黑屋|一亩三分地论坛声明

custom counter

GMT+8, 2018-5-24 20:19

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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