近期论坛无法登录的解决方案


一亩三分地论坛

 找回密码
 获取更多干活,快来注册

一亩三分地官方iOS手机应用下载
查看: 3779|回复: 19
收起左侧

GOOGLE第二轮电面

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

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

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

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

x
昨天电面,两道题 不算难,求好运~~

1. Given a sorted array of floats, find the index of the number closest to x:
Example: {1.2, 2.5, 9.3}  x = 5,    return 1
. visit 1point3acres.com for more.



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()
. Waral 鍗氬鏈夋洿澶氭枃绔,

评分

2

查看全部评分

本帖被以下淘专辑推荐:

 楼主| lihan96163 发表于 2014-4-13 11:53:40 | 显示全部楼层
关注一亩三分地公众号:
Warald_一亩三分地

我刚开始写的就是N^2地解法,后来他说可以稍微改进了下
. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
我就说可以先把每个单词处理下,用map记录出现的字母(其实遍历单词的话还是要n^2的),说了以后他貌似还比较满意,感觉他没想要我写出太高级地方法来`~
回复 支持 1 反对 0

使用道具 举报

eforms 发表于 2014-4-12 02:43:43 来自手机 | 显示全部楼层
关注一亩三分地微博:
Warald
谢谢楼主,第二题有比你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
第一题 感觉是binary search 比较并且记录最接近结果
第二题 我的感觉是对词进行sort 放到compressed trie ...

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

使用道具 举报

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

使用道具 举报

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

说的很好。. 鍥磋鎴戜滑@1point 3 acres
但感觉还不够。
不需要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
我觉得不需要,我感觉trie的优势只是查找前缀比较快,这题和前缀顺序都无关,不遍历到最后一位也不知道究 ...
. 鐗涗汉浜戦泦,涓浜╀笁鍒嗗湴
对对对,不能赞更多!我刚看到的时候就是这么想的。感觉没别的方法了。。。。-google 1point3acres
但是。。。。。。
你把单词都扔进trie里面的话,那么首先你可以用trie去遍历所有的单词,其次,你可以用trie节省时间;
比如,你试了put不行,那么putty一定不行,也就是说put为前缀的词都不用试了,所以还是可以省时间的。类似剪枝的功效。
回复 支持 反对

使用道具 举报

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

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

使用道具 举报

zhouyoung1124 发表于 2015-7-28 21:58:55 | 显示全部楼层
jiebour 发表于 2015-7-28 12:31
对对对,不能赞更多!我刚看到的时候就是这么想的。感觉没别的方法了。。。。
但是。。。。。。
鏉ユ簮涓浜.涓夊垎鍦拌鍧. 你把单 ...

每次每个词插入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
= =那个第二天我也碰到过,上来想了半天能不能有比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 变形
第二题,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;. 1point 3acres 璁哄潧
       
        int left = 0;
        int right = n - 1;. Waral 鍗氬鏈夋洿澶氭枃绔,
        int mid;

        while(right - left > 1)
        {
                mid = left + (right - left) / 2;. 鐣欏鐢宠璁哄潧-涓浜╀笁鍒嗗湴
                if(x > v[mid])
                        left  = mid;
                else
                        right = mid;. 1point 3acres 璁哄潧

        }

        return fabs(v[right] - x) < fabs(v[left] - x) ? right : left ;
}
回复 支持 反对

使用道具 举报

本版积分规则

关闭

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

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

custom counter

GMT+8, 2017-6-29 07:27

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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