H*M 发帖数: 1268 | 1 很简单,就是check 一个array里面有没有两个元素和为sum,
我用了两种方法,一个是sort之后,keep两个指针i,j一头一尾,相加如果小于sum就前移
,否则就后移。O(nlgn) time
另一种方法是hash table.其中一个trick就是要确信没有自己加自己。这个是唯一一个
主意点吧。O(n) with O(n) space
我写的代码如下。fail掉了。不知道为什么。
谁有什么很牛的算法更有效么?谢了。
bool checkIfTwoElementsSumToNum(vector v, int sum)
{
if(v.size() == 0)
return false;
sort(v.begin(), v.end());
unsigned i = 0,j = v.size() - 1;
while(i < j)
{
if(v[i] + v[j] == sum)
r |
S*********N 发帖数: 6151 | 2
前移
what if v[i]+v[j]
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 很简单,就是check 一个array里面有没有两个元素和为sum, : 我用了两种方法,一个是sort之后,keep两个指针i,j一头一尾,相加如果小于sum就前移 : ,否则就后移。O(nlgn) time : 另一种方法是hash table.其中一个trick就是要确信没有自己加自己。这个是唯一一个 : 主意点吧。O(n) with O(n) space : 我写的代码如下。fail掉了。不知道为什么。 : 谁有什么很牛的算法更有效么?谢了。 : bool checkIfTwoElementsSumToNum(vector v, int sum) : { : if(v.size() == 0)
|
H*M 发帖数: 1268 | 3 i++
【在 S*********N 的大作中提到】![](/moin_static193/solenoid/img/up.png) : : 前移 : what if v[i]+v[j]
|
l**a 发帖数: 43 | 4 你的hash算法中没必要对所有元素算一遍hashvalue吧
进来一个元素a,它的hashvalue就是sum-a,如果a已经在hashtable中,就找到返回,复
杂度为n,而你的是2n,没有本质区别,但如果挑毛病的话就是这里了
前移
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 很简单,就是check 一个array里面有没有两个元素和为sum, : 我用了两种方法,一个是sort之后,keep两个指针i,j一头一尾,相加如果小于sum就前移 : ,否则就后移。O(nlgn) time : 另一种方法是hash table.其中一个trick就是要确信没有自己加自己。这个是唯一一个 : 主意点吧。O(n) with O(n) space : 我写的代码如下。fail掉了。不知道为什么。 : 谁有什么很牛的算法更有效么?谢了。 : bool checkIfTwoElementsSumToNum(vector v, int sum) : { : if(v.size() == 0)
|
S*********N 发帖数: 6151 | 5
just curious,
find any or all ?? if there are same numbers.
perhaps make some frog-jump? just for discussion.
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : i++
|
c******o 发帖数: 1277 | 6 想过hash function没?
怎么保证O(1) time? 不是那么直接就用的吧?
我做过 java的, 要重载 hashCode()和equals()才算对 |
H*M 发帖数: 1268 | 7 int 的 hash function干吗要自己写
【在 c******o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 想过hash function没? : 怎么保证O(1) time? 不是那么直接就用的吧? : 我做过 java的, 要重载 hashCode()和equals()才算对
|
H*M 发帖数: 1268 | 8 没有相差n那么多。你只是可以提前返回,worst是一样的。
你每次要先寻找在不在,然后insert,两个操作。我过两遍,每次一个操作。
我想问的是,有没有更efficient的方法?
,复
【在 l**a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你的hash算法中没必要对所有元素算一遍hashvalue吧 : 进来一个元素a,它的hashvalue就是sum-a,如果a已经在hashtable中,就找到返回,复 : 杂度为n,而你的是2n,没有本质区别,但如果挑毛病的话就是这里了 : : 前移
|
a********a 发帖数: 219 | 9 第二个如果有duplicate sum/2并且sum&1==0你就fail了。
前移
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 很简单,就是check 一个array里面有没有两个元素和为sum, : 我用了两种方法,一个是sort之后,keep两个指针i,j一头一尾,相加如果小于sum就前移 : ,否则就后移。O(nlgn) time : 另一种方法是hash table.其中一个trick就是要确信没有自己加自己。这个是唯一一个 : 主意点吧。O(n) with O(n) space : 我写的代码如下。fail掉了。不知道为什么。 : 谁有什么很牛的算法更有效么?谢了。 : bool checkIfTwoElementsSumToNum(vector v, int sum) : { : if(v.size() == 0)
|
H*M 发帖数: 1268 | 10 说的很对,我assume的是没有重复的,所以用的hash_map
我记得有个hash_multimap?
【在 a********a 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第二个如果有duplicate sum/2并且sum&1==0你就fail了。 : : 前移
|
|
|
a**x 发帖数: 154 | 11 你现场就写出怎么工整的程序?
还fail?
不过你都是pass by value, 这样传一个container 效率太低了, 至少要传reference. |
g*******y 发帖数: 1930 | 12 参数而且最好还是const &,最flexible
我觉得你应该处理duplicate的情况,这个写起来难度没有啥变化(hash count),强加
一个没有dup的假设太强了一些
另外我觉得这些都是小问题,会不会是别的原因fail?
reference.
【在 a**x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 你现场就写出怎么工整的程序? : 还fail? : 不过你都是pass by value, 这样传一个container 效率太低了, 至少要传reference.
|
c******o 发帖数: 1277 | 13 java 的hash function default 是内部地址,是在大部分情况下不能有效率的用的。
hashtable 不考hashfunction 哪能靠啥啊。。。
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : int 的 hash function干吗要自己写
|
g*******y 发帖数: 1930 | 14 写hash function太detailed了吧
就拿乘法hashing function来说,你背得下来(sqrt(5)-1)/2的32位小数?
其他的一些hash函数(除法,universal),也涉及到找合适的质数
另外是不是还要考考hash的几种解决冲突的方法,chain,Open addressing, perfect, 还有什么随机版本的cockoo hashing
对于hashing有个不错的了解就行了,面试时间写个比library还好的版本不太现实吧
另外,我不太懂java,也许java的hash需要一些customize的处理
不过lz明显写的是C++嘛,摆在那里的库不用干嘛。。。这个题目本身重点就不是hash,hash只是实现算法的一个工具。
不过我提一点,直接用C++的库的hash,对于比较多的数据实际上达不到O(1)性能的insert,这个可以跟面试官侃一侃,如果有时间的话
【在 c******o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : java 的hash function default 是内部地址,是在大部分情况下不能有效率的用的。 : hashtable 不考hashfunction 哪能靠啥啊。。。
|
H*M 发帖数: 1268 | 15 有可能吧
dup的情况没考虑是个败笔.
我当时写了第一个版本的,就又自作聪明的说了第二个,一起写了.
有可能是我linux command答得不好
他问我什么命令查linux里面的process,我说pid,脑子进水了,一直都用得,是ps.
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 参数而且最好还是const &,最flexible : 我觉得你应该处理duplicate的情况,这个写起来难度没有啥变化(hash count),强加 : 一个没有dup的假设太强了一些 : 另外我觉得这些都是小问题,会不会是别的原因fail? : : reference.
|
H*M 发帖数: 1268 | 16 我觉得hash就考你说的几个概念就差不多了吧
perfect hashing都过了,从来没看到过被问过的.
cockoo hshing没听说过.
perfect,
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 写hash function太detailed了吧 : 就拿乘法hashing function来说,你背得下来(sqrt(5)-1)/2的32位小数? : 其他的一些hash函数(除法,universal),也涉及到找合适的质数 : 另外是不是还要考考hash的几种解决冲突的方法,chain,Open addressing, perfect, 还有什么随机版本的cockoo hashing : 对于hashing有个不错的了解就行了,面试时间写个比library还好的版本不太现实吧 : 另外,我不太懂java,也许java的hash需要一些customize的处理 : 不过lz明显写的是C++嘛,摆在那里的库不用干嘛。。。这个题目本身重点就不是hash,hash只是实现算法的一个工具。 : 不过我提一点,直接用C++的库的hash,对于比较多的数据实际上达不到O(1)性能的insert,这个可以跟面试官侃一侃,如果有时间的话
|
c******o 发帖数: 1277 | 17 比如说这道题就很好啊,你能做个根据信息得到的比较好的uniform distribution的,
放在作为key的class里,又简单,又好。
我不知道c++如何,但是要是你在java里做,自己定义一个key class和hash function
必不可少。
perfect,
【在 g*******y 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 写hash function太detailed了吧 : 就拿乘法hashing function来说,你背得下来(sqrt(5)-1)/2的32位小数? : 其他的一些hash函数(除法,universal),也涉及到找合适的质数 : 另外是不是还要考考hash的几种解决冲突的方法,chain,Open addressing, perfect, 还有什么随机版本的cockoo hashing : 对于hashing有个不错的了解就行了,面试时间写个比library还好的版本不太现实吧 : 另外,我不太懂java,也许java的hash需要一些customize的处理 : 不过lz明显写的是C++嘛,摆在那里的库不用干嘛。。。这个题目本身重点就不是hash,hash只是实现算法的一个工具。 : 不过我提一点,直接用C++的库的hash,对于比较多的数据实际上达不到O(1)性能的insert,这个可以跟面试官侃一侃,如果有时间的话
|
H*M 发帖数: 1268 | 18 关键是这得考点不是hash function本身吧
function
【在 c******o 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 比如说这道题就很好啊,你能做个根据信息得到的比较好的uniform distribution的, : 放在作为key的class里,又简单,又好。 : 我不知道c++如何,但是要是你在java里做,自己定义一个key class和hash function : 必不可少。 : : perfect,
|
c******o 发帖数: 1277 | 19 google电话面试,考了,还就是最后讨论了写的hash function
当然还考了一另外的算法题。
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 关键是这得考点不是hash function本身吧 : : function
|
v*****e 发帖数: 497 | 20 第一个算法明显行不通,会miss掉很多可能的组合 |
|
|
H*M 发帖数: 1268 | 21 give one case I will send u a 包子
【在 v*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一个算法明显行不通,会miss掉很多可能的组合
|
D****t 发帖数: 422 | 22 Good luck for job hunting
前移
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 很简单,就是check 一个array里面有没有两个元素和为sum, : 我用了两种方法,一个是sort之后,keep两个指针i,j一头一尾,相加如果小于sum就前移 : ,否则就后移。O(nlgn) time : 另一种方法是hash table.其中一个trick就是要确信没有自己加自己。这个是唯一一个 : 主意点吧。O(n) with O(n) space : 我写的代码如下。fail掉了。不知道为什么。 : 谁有什么很牛的算法更有效么?谢了。 : bool checkIfTwoElementsSumToNum(vector v, int sum) : { : if(v.size() == 0)
|
q******s 发帖数: 289 | 23 I have been asked about the same question during an onsite interview. Here
is my solution:
Use the sum to subtract each unit of the array to get another array. Then
the problem becomes finding a pair of units that shows up in both arrays but
with different indices.
前移
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 很简单,就是check 一个array里面有没有两个元素和为sum, : 我用了两种方法,一个是sort之后,keep两个指针i,j一头一尾,相加如果小于sum就前移 : ,否则就后移。O(nlgn) time : 另一种方法是hash table.其中一个trick就是要确信没有自己加自己。这个是唯一一个 : 主意点吧。O(n) with O(n) space : 我写的代码如下。fail掉了。不知道为什么。 : 谁有什么很牛的算法更有效么?谢了。 : bool checkIfTwoElementsSumToNum(vector v, int sum) : { : if(v.size() == 0)
|
H*M 发帖数: 1268 | 24 多此一举.不是还是要 finding a pair of units that shows up in both arrays but
with diff index
but
【在 q******s 的大作中提到】![](/moin_static193/solenoid/img/up.png) : I have been asked about the same question during an onsite interview. Here : is my solution: : Use the sum to subtract each unit of the array to get another array. Then : the problem becomes finding a pair of units that shows up in both arrays but : with different indices. : : 前移
|
q******x 发帖数: 104 | 25 我来献丑了:一个很笨很直观的方法。
以sum/2为pivot对原array进行快排序排列
一边比sum/2大
一边比sum/2小
对较少一边的数x依次得到sum-x
看另一边用二分法查找是否有该sum-x |
m*****k 发帖数: 731 | 26 u sure?
【在 v*****e 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 第一个算法明显行不通,会miss掉很多可能的组合
|
f*****e 发帖数: 2992 | 27 二分法查找是不是应该有序?
如果排序后再查找,时间复杂度也是O(nlgn)吧?
【在 q******x 的大作中提到】![](/moin_static193/solenoid/img/up.png) : 我来献丑了:一个很笨很直观的方法。 : 以sum/2为pivot对原array进行快排序排列 : 一边比sum/2大 : 一边比sum/2小 : 对较少一边的数x依次得到sum-x : 看另一边用二分法查找是否有该sum-x
|
v*****e 发帖数: 497 | 28 惭愧,是我当时想错了。理论上没问题,只有考虑array 元素里有无重复就行了。
sorry
【在 H*M 的大作中提到】![](/moin_static193/solenoid/img/up.png) : give one case I will send u a 包子
|