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 的大作中提到】
: 很简单，就是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 的大作中提到】
:
: 前移
: what if v[i]+v[j]
|
l**a
发帖数: 43 | 4 你的hash算法中没必要对所有元素算一遍hashvalue吧
进来一个元素a，它的hashvalue就是sum-a，如果a已经在hashtable中，就找到返回，复
杂度为n，而你的是2n，没有本质区别，但如果挑毛病的话就是这里了
前移
【在 H*M 的大作中提到】
: 很简单，就是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 的大作中提到】
: i++
|
c******o
发帖数: 1277 | 6 想过hash function没？
怎么保证O(1) time? 不是那么直接就用的吧？
我做过 java的， 要重载 hashCode()和equals()才算对 |
H*M
发帖数: 1268 | 7 int 的 hash function干吗要自己写
【在 c******o 的大作中提到】
: 想过hash function没？
: 怎么保证O(1) time? 不是那么直接就用的吧？
: 我做过 java的， 要重载 hashCode()和equals()才算对
|
H*M
发帖数: 1268 | 8 没有相差n那么多。你只是可以提前返回，worst是一样的。
你每次要先寻找在不在，然后insert,两个操作。我过两遍，每次一个操作。
我想问的是，有没有更efficient的方法？
，复
【在 l**a 的大作中提到】
: 你的hash算法中没必要对所有元素算一遍hashvalue吧
: 进来一个元素a，它的hashvalue就是sum-a，如果a已经在hashtable中，就找到返回，复
: 杂度为n，而你的是2n，没有本质区别，但如果挑毛病的话就是这里了
:
: 前移
|
a********a
发帖数: 219 | 9 第二个如果有duplicate sum/2并且sum&1==0你就fail了。
前移
【在 H*M 的大作中提到】
: 很简单，就是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 的大作中提到】
: 第二个如果有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 的大作中提到】
: 你现场就写出怎么工整的程序？
: 还fail？
: 不过你都是pass by value, 这样传一个container 效率太低了， 至少要传reference.
|
c******o
发帖数: 1277 | 13 java 的hash function default 是内部地址，是在大部分情况下不能有效率的用的。
hashtable 不考hashfunction 哪能靠啥啊。。。
【在 H*M 的大作中提到】
: 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 的大作中提到】
: java 的hash function default 是内部地址，是在大部分情况下不能有效率的用的。
: hashtable 不考hashfunction 哪能靠啥啊。。。
|
H*M
发帖数: 1268 | 15 有可能吧
dup的情况没考虑是个败笔.
我当时写了第一个版本的,就又自作聪明的说了第二个,一起写了.
有可能是我linux command答得不好
他问我什么命令查linux里面的process,我说pid,脑子进水了,一直都用得,是ps.
【在 g*******y 的大作中提到】
: 参数而且最好还是const &，最flexible
: 我觉得你应该处理duplicate的情况，这个写起来难度没有啥变化(hash count)，强加
: 一个没有dup的假设太强了一些
: 另外我觉得这些都是小问题，会不会是别的原因fail？
:
: reference.
|
H*M
发帖数: 1268 | 16 我觉得hash就考你说的几个概念就差不多了吧
perfect hashing都过了,从来没看到过被问过的.
cockoo hshing没听说过.
perfect,
【在 g*******y 的大作中提到】
: 写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 的大作中提到】
: 写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 的大作中提到】
: 比如说这道题就很好啊，你能做个根据信息得到的比较好的uniform distribution的，
: 放在作为key的class里，又简单，又好。
: 我不知道c++如何，但是要是你在java里做，自己定义一个key class和hash function
: 必不可少。
:
: perfect,
|
c******o
发帖数: 1277 | 19 google电话面试，考了，还就是最后讨论了写的hash function
当然还考了一另外的算法题。
【在 H*M 的大作中提到】
: 关键是这得考点不是hash function本身吧
:
: function
|
v*****e
发帖数: 497 | 20 第一个算法明显行不通，会miss掉很多可能的组合 |
|
|
H*M
发帖数: 1268 | 21 give one case I will send u a 包子
【在 v*****e 的大作中提到】
: 第一个算法明显行不通，会miss掉很多可能的组合
|
D****t
发帖数: 422 | 22 Good luck for job hunting
前移
【在 H*M 的大作中提到】
: 很简单，就是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 的大作中提到】
: 很简单，就是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 的大作中提到】
: 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 的大作中提到】
: 第一个算法明显行不通，会miss掉很多可能的组合
|
f*****e
发帖数: 2992 | 27 二分法查找是不是应该有序?
如果排序后再查找,时间复杂度也是O(nlgn)吧?
【在 q******x 的大作中提到】
: 我来献丑了：一个很笨很直观的方法。
: 以sum/2为pivot对原array进行快排序排列
: 一边比sum/2大
: 一边比sum/2小
: 对较少一边的数x依次得到sum-x
: 看另一边用二分法查找是否有该sum-x
|
v*****e
发帖数: 497 | 28 惭愧，是我当时想错了。理论上没问题，只有考虑array 元素里有无重复就行了。
sorry
【在 H*M 的大作中提到】
: give one case I will send u a 包子
|
