r********7
发帖数: 102 | 1 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
String>）.
description 是一个非常长的String， 例如一段话。 要求其中不能有negative
words。如果有 则输出哪里negative word。 没有则输出good。
回答 把description分成每一个word，然后比对 negative words
followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
做。
2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
例如 531226.
O(1)空间。 回答了用 bit运算 （XOR方法）。 followup 有没有其他方法，就想不
出来了。
3.给一个很大的数组，取前k个最小的数。
我回答 建一个priority queue， 长度为k， 然后遍历整个数组，每次都维护priority
queue。 但是每有一个元素，worst case就要比较k次才能发现哪个是最大的。 复杂
度是O(k*n)。
面试官 不满意。
感觉这1,3两道题比较类似，都是有一个是大数据， 然后进行比较。 遇到这样的就歇
菜，完全没啥思路。
顺便问一下 第一题能用 suffix树吗？ 个人感觉那样是不是更复杂了呢？ |
m******e
发帖数: 82 | 2 2. O(n)时间O(1)空间复原数组
3. 用优先队列不应该是O(nlogk)吗 |
f*****e
发帖数: 2992 | 3 第二题怎么用xor做？O(N)时间复杂度倒是可以。
【在 r********7 的大作中提到】
: 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
: 1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
: String>）.
: description 是一个非常长的String， 例如一段话。 要求其中不能有negative
: words。如果有 则输出哪里negative word。 没有则输出good。
: 回答 把description分成每一个word，然后比对 negative words
: followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
: 做。
: 2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
: 例如 531226.
|
A*********c
发帖数: 430 | 4 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
negative words当成pattern。
空格是pattern的一部分，无所吧。
第二题就是多了一个数字少了一个数字。
抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
找出2XOR4的一个非0位，就是2和4不一样的bit位置
再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。
【在 r********7 的大作中提到】
: 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
: 1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
: String>）.
: description 是一个非常长的String， 例如一段话。 要求其中不能有negative
: words。如果有 则输出哪里negative word。 没有则输出good。
: 回答 把description分成每一个word，然后比对 negative words
: followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
: 做。
: 2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
: 例如 531226.
|
r********7
发帖数: 102 | 5 谢了，第二题有没有 其他方法啊。 我跟面试官说的用xor运算，但是他说一个integer
最多32位，要是有32位以上的长度就不行了。 问有没有其他方法。
【在 A*********c 的大作中提到】
: 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
: negative words当成pattern。
: 空格是pattern的一部分，无所吧。
: 第二题就是多了一个数字少了一个数字。
: 抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
: 找出2XOR4的一个非0位，就是2和4不一样的bit位置
: 再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
: 第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
: 对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。
|
r********7
发帖数: 102 | 6 还有就是EPI那书好多啊，要怎么看呢？有没有着重看的地方？
【在 A*********c 的大作中提到】
: 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
: negative words当成pattern。
: 空格是pattern的一部分，无所吧。
: 第二题就是多了一个数字少了一个数字。
: 抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
: 找出2XOR4的一个非0位，就是2和4不一样的bit位置
: 再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
: 第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
: 对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。
|
A*********c
发帖数: 430 | 7 不太明白。为什么不行呢？int64_t XOR也可以呀。
有一些求和的算法会溢出吧。更危险了。
EPI我也刚开始看，随便翻的。碰到有意思的题目就做一道耍耍呗。题太多了。
integer
【在 r********7 的大作中提到】
: 谢了，第二题有没有 其他方法啊。 我跟面试官说的用xor运算，但是他说一个integer
: 最多32位，要是有32位以上的长度就不行了。 问有没有其他方法。
|
h*********o
发帖数: 230 | 8 找到 2OR4 后，后面怎么找。。。
【在 A*********c 的大作中提到】
: 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
: negative words当成pattern。
: 空格是pattern的一部分，无所吧。
: 第二题就是多了一个数字少了一个数字。
: 抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
: 找出2XOR4的一个非0位，就是2和4不一样的bit位置
: 再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
: 第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
: 对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。
|
A*********c
发帖数: 430 | 9 这个数字不是2就是4，那么把原来数组linear scan一遍，和这个元素比较。找到了就
是重复的，没找到就是缺的那个。
【在 h*********o 的大作中提到】
: 找到 2OR4 后，后面怎么找。。。
|
h****g
发帖数: 105 | 10 第二题： O(n)遍历数组求和，假设多的数字是a，miss的数字数b，那么求的和是sum(
Zn)+a-b. 第二遍就平方之和，结果是sqr(Zn)+a^2-b^2. 然后可以得到a+b. a和b也
可以求出来了，这题偏向数学吧。
第三题应该是对的，用一个长度为k的heap来读入streaming当中的数，只是复杂度应该
是O（nlogk） |
|
|
h*********o
发帖数: 230 | 11 比如 数组 5,3,2,2,4,6
全部xor一遍 应该是 1^2 对吗？
从右边第一位不相同。 按照第一位是否相同得到，3^5 跟2^2^4^6. 这里怎么知道1 跟
2？
【在 A*********c 的大作中提到】
: 这个数字不是2就是4，那么把原来数组linear scan一遍，和这个元素比较。找到了就
: 是重复的，没找到就是缺的那个。
|
A*********c
发帖数: 430 | 12 第一遍是1^2。最低位不同。就是奇偶数。比如说选奇数。
现在说第二步。
XOR A[i]中所有的奇数，以及全集中所有的奇数。
就是1^3^5^3^5得到1.
所以这个1是1OR2.
同样的，如果你遍历所有的偶数，就是2^4^6 ^ 2^2^4^6就会得到2.
总之你会得到重复的或者丢失的数字。
【在 h*********o 的大作中提到】
: 比如 数组 5,3,2,2,4,6
: 全部xor一遍 应该是 1^2 对吗？
: 从右边第一位不相同。 按照第一位是否相同得到，3^5 跟2^2^4^6. 这里怎么知道1 跟
: 2？
|
w*******e
发帖数: 285 | 13
第三题如果k很大，接近于n的话，复杂度就变成nlgn了，你可以用nth_element先找到
第k大的数，然后再用这个数partition，小于它的数就都在前面了，复杂度都是o(n).
【在 r********7 的大作中提到】
: 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
: 1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
: String>）.
: description 是一个非常长的String， 例如一段话。 要求其中不能有negative
: words。如果有 则输出哪里negative word。 没有则输出good。
: 回答 把description分成每一个word，然后比对 negative words
: followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
: 做。
: 2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
: 例如 531226.
|
h*********o
发帖数: 230 | 14 哦 要全集。。。这边 lost了
多谢 哈哈
【在 A*********c 的大作中提到】
: 第一遍是1^2。最低位不同。就是奇偶数。比如说选奇数。
: 现在说第二步。
: XOR A[i]中所有的奇数，以及全集中所有的奇数。
: 就是1^3^5^3^5得到1.
: 所以这个1是1OR2.
: 同样的，如果你遍历所有的偶数，就是2^4^6 ^ 2^2^4^6就会得到2.
: 总之你会得到重复的或者丢失的数字。
|
l*******g
发帖数: 82 | 15 第一题，suffixtree的话要看如何分词了。而且，suffixtree主要是搜索和搜索的精确
度有帮助，如果已经有neg词典的话就map就好了，然后先确定nag词，然后左右察看临
近词，比如is, not, yet, but之类的。这个感觉更像是machine learning sentiment
analysis。
第二题，那个数学的做法，那位再受累解释一下。没太明白。
第三题我觉得可以用conqure merge的做法，一般题目说有一个大数组，大文件，潜台
词就是最好提供一个可以parallel的处理方式，而且不要试图用用memory来存储太多东
西。
前些天面的EBay， onsite。
【在 r********7 的大作中提到】
: 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
: 1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
: String>）.
: description 是一个非常长的String， 例如一段话。 要求其中不能有negative
: words。如果有 则输出哪里negative word。 没有则输出good。
: 回答 把description分成每一个word，然后比对 negative words
: followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
: 做。
: 2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
: 例如 531226.
|
c********p
发帖数: 1969 | |
y*****g
发帖数: 10 | 17 不可以用hash吗
integer
【在 r********7 的大作中提到】
: 谢了，第二题有没有 其他方法啊。 我跟面试官说的用xor运算，但是他说一个integer
: 最多32位，要是有32位以上的长度就不行了。 问有没有其他方法。
|
s****g
发帖数: 43 | 18 =======To Lonelybug:
About the mathematical solution:
Let b be the missing number, a be the duplicate number.
Let S1= sum 1 to n.
Let S2= sum the sequence
S2-S1=b-a
Let T1= sum 1^2 to n^2
Let T2= sum the sqt of the sequence
T2-T1=b^2-a^2=(b-a)*(b+a)
So you now know the value of b-a and b+a. It's a simple linear equation.
In the test case:
b-a=2
b^2-a^2=12
=> b+a=6
so b=4 and a=2
Scan the sequence again to get the position index. |
r*c
发帖数: 167 | 19 眼花， 把个 sqt 看成是 sqrt.
【在 s****g 的大作中提到】
: =======To Lonelybug:
: About the mathematical solution:
: Let b be the missing number, a be the duplicate number.
: Let S1= sum 1 to n.
: Let S2= sum the sequence
: S2-S1=b-a
: Let T1= sum 1^2 to n^2
: Let T2= sum the sqt of the sequence
: T2-T1=b^2-a^2=(b-a)*(b+a)
: So you now know the value of b-a and b+a. It's a simple linear equation.
|
x*****0
发帖数: 452 | |
|
|
e*****i
发帖数: 182 | 21 弱问epi是什么啊！多谢！
【在 A*********c 的大作中提到】
: 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
: negative words当成pattern。
: 空格是pattern的一部分，无所吧。
: 第二题就是多了一个数字少了一个数字。
: 抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
: 找出2XOR4的一个非0位，就是2和4不一样的bit位置
: 再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
: 第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
: 对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。
|
s**x
发帖数: 7506 | 22
Co ask.
【在 e*****i 的大作中提到】
: 弱问epi是什么啊！多谢！
|
x*****a
发帖数: 9 | 23 第一题: ACAutomation
第二题: 就是扫一遍, swap直到 A[i] == i+1 为止, 然后再扫一遍看哪个不对, XOR
也行, 写起来蛋疼
第三道: quick select O(N) |
w****3
发帖数: 110 | |
w****y
发帖数: 56 | 25 a book. elements of programming interview.
【在 s**x 的大作中提到】
:
: Co ask.
|
q****m
发帖数: 177 | 26 第一题用 AC 自动机
【在 r********7 的大作中提到】
: 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
: 1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
: String>）.
: description 是一个非常长的String， 例如一段话。 要求其中不能有negative
: words。如果有 则输出哪里negative word。 没有则输出good。
: 回答 把description分成每一个word，然后比对 negative words
: followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
: 做。
: 2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
: 例如 531226.
|
x*****0
发帖数: 452 | 27 有一些不理解第二题的意思：
请问你：
输入：[5, 4, 3, 2, 2, 1]
输出是：６吗？
【在 r********7 的大作中提到】
: 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
: 1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
: String>）.
: description 是一个非常长的String， 例如一段话。 要求其中不能有negative
: words。如果有 则输出哪里negative word。 没有则输出good。
: 回答 把description分成每一个word，然后比对 negative words
: followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
: 做。
: 2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
: 例如 531226.
|
r********7
发帖数: 102 | 28 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
String>）.
description 是一个非常长的String， 例如一段话。 要求其中不能有negative
words。如果有 则输出哪里negative word。 没有则输出good。
回答 把description分成每一个word，然后比对 negative words
followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
做。
2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
例如 531226.
O(1)空间。 回答了用 bit运算 （XOR方法）。 followup 有没有其他方法，就想不
出来了。
3.给一个很大的数组，取前k个最小的数。
我回答 建一个priority queue， 长度为k， 然后遍历整个数组，每次都维护priority
queue。 但是每有一个元素，worst case就要比较k次才能发现哪个是最大的。 复杂
度是O(k*n)。
面试官 不满意。
感觉这1,3两道题比较类似，都是有一个是大数据， 然后进行比较。 遇到这样的就歇
菜，完全没啥思路。
顺便问一下 第一题能用 suffix树吗？ 个人感觉那样是不是更复杂了呢？ |
m******e
发帖数: 82 | 29 2. O(n)时间O(1)空间复原数组
3. 用优先队列不应该是O(nlogk)吗 |
f*****e
发帖数: 2992 | 30 第二题怎么用xor做？O(N)时间复杂度倒是可以。
【在 r********7 的大作中提到】
: 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
: 1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
: String>）.
: description 是一个非常长的String， 例如一段话。 要求其中不能有negative
: words。如果有 则输出哪里negative word。 没有则输出good。
: 回答 把description分成每一个word，然后比对 negative words
: followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
: 做。
: 2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
: 例如 531226.
|
|
|
A*********c
发帖数: 430 | 31 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
negative words当成pattern。
空格是pattern的一部分，无所吧。
第二题就是多了一个数字少了一个数字。
抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
找出2XOR4的一个非0位，就是2和4不一样的bit位置
再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。
【在 r********7 的大作中提到】
: 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
: 1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
: String>）.
: description 是一个非常长的String， 例如一段话。 要求其中不能有negative
: words。如果有 则输出哪里negative word。 没有则输出good。
: 回答 把description分成每一个word，然后比对 negative words
: followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
: 做。
: 2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
: 例如 531226.
|
r********7
发帖数: 102 | 32 谢了，第二题有没有 其他方法啊。 我跟面试官说的用xor运算，但是他说一个integer
最多32位，要是有32位以上的长度就不行了。 问有没有其他方法。
【在 A*********c 的大作中提到】
: 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
: negative words当成pattern。
: 空格是pattern的一部分，无所吧。
: 第二题就是多了一个数字少了一个数字。
: 抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
: 找出2XOR4的一个非0位，就是2和4不一样的bit位置
: 再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
: 第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
: 对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。
|
r********7
发帖数: 102 | 33 还有就是EPI那书好多啊，要怎么看呢？有没有着重看的地方？
【在 A*********c 的大作中提到】
: 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
: negative words当成pattern。
: 空格是pattern的一部分，无所吧。
: 第二题就是多了一个数字少了一个数字。
: 抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
: 找出2XOR4的一个非0位，就是2和4不一样的bit位置
: 再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
: 第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
: 对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。
|
A*********c
发帖数: 430 | 34 不太明白。为什么不行呢？int64_t XOR也可以呀。
有一些求和的算法会溢出吧。更危险了。
EPI我也刚开始看，随便翻的。碰到有意思的题目就做一道耍耍呗。题太多了。
integer
【在 r********7 的大作中提到】
: 谢了，第二题有没有 其他方法啊。 我跟面试官说的用xor运算，但是他说一个integer
: 最多32位，要是有32位以上的长度就不行了。 问有没有其他方法。
|
h*********o
发帖数: 230 | 35 找到 2OR4 后，后面怎么找。。。
【在 A*********c 的大作中提到】
: 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
: negative words当成pattern。
: 空格是pattern的一部分，无所吧。
: 第二题就是多了一个数字少了一个数字。
: 抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
: 找出2XOR4的一个非0位，就是2和4不一样的bit位置
: 再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
: 第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
: 对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。
|
A*********c
发帖数: 430 | 36 这个数字不是2就是4，那么把原来数组linear scan一遍，和这个元素比较。找到了就
是重复的，没找到就是缺的那个。
【在 h*********o 的大作中提到】
: 找到 2OR4 后，后面怎么找。。。
|
h****g
发帖数: 105 | 37 第二题： O(n)遍历数组求和，假设多的数字是a，miss的数字数b，那么求的和是sum(
Zn)+a-b. 第二遍就平方之和，结果是sqr(Zn)+a^2-b^2. 然后可以得到a+b. a和b也
可以求出来了，这题偏向数学吧。
第三题应该是对的，用一个长度为k的heap来读入streaming当中的数，只是复杂度应该
是O（nlogk） |
h*********o
发帖数: 230 | 38 比如 数组 5,3,2,2,4,6
全部xor一遍 应该是 1^2 对吗？
从右边第一位不相同。 按照第一位是否相同得到，3^5 跟2^2^4^6. 这里怎么知道1 跟
2？
【在 A*********c 的大作中提到】
: 这个数字不是2就是4，那么把原来数组linear scan一遍，和这个元素比较。找到了就
: 是重复的，没找到就是缺的那个。
|
A*********c
发帖数: 430 | 39 第一遍是1^2。最低位不同。就是奇偶数。比如说选奇数。
现在说第二步。
XOR A[i]中所有的奇数，以及全集中所有的奇数。
就是1^3^5^3^5得到1.
所以这个1是1OR2.
同样的，如果你遍历所有的偶数，就是2^4^6 ^ 2^2^4^6就会得到2.
总之你会得到重复的或者丢失的数字。
【在 h*********o 的大作中提到】
: 比如 数组 5,3,2,2,4,6
: 全部xor一遍 应该是 1^2 对吗？
: 从右边第一位不相同。 按照第一位是否相同得到，3^5 跟2^2^4^6. 这里怎么知道1 跟
: 2？
|
w*******e
发帖数: 285 | 40
第三题如果k很大，接近于n的话，复杂度就变成nlgn了，你可以用nth_element先找到
第k大的数，然后再用这个数partition，小于它的数就都在前面了，复杂度都是o(n).
【在 r********7 的大作中提到】
: 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
: 1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
: String>）.
: description 是一个非常长的String， 例如一段话。 要求其中不能有negative
: words。如果有 则输出哪里negative word。 没有则输出good。
: 回答 把description分成每一个word，然后比对 negative words
: followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
: 做。
: 2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
: 例如 531226.
|
|
|
h*********o
发帖数: 230 | 41 哦 要全集。。。这边 lost了
多谢 哈哈
【在 A*********c 的大作中提到】
: 第一遍是1^2。最低位不同。就是奇偶数。比如说选奇数。
: 现在说第二步。
: XOR A[i]中所有的奇数，以及全集中所有的奇数。
: 就是1^3^5^3^5得到1.
: 所以这个1是1OR2.
: 同样的，如果你遍历所有的偶数，就是2^4^6 ^ 2^2^4^6就会得到2.
: 总之你会得到重复的或者丢失的数字。
|
l*******g
发帖数: 82 | 42 第一题，suffixtree的话要看如何分词了。而且，suffixtree主要是搜索和搜索的精确
度有帮助，如果已经有neg词典的话就map就好了，然后先确定nag词，然后左右察看临
近词，比如is, not, yet, but之类的。这个感觉更像是machine learning sentiment
analysis。
第二题，那个数学的做法，那位再受累解释一下。没太明白。
第三题我觉得可以用conqure merge的做法，一般题目说有一个大数组，大文件，潜台
词就是最好提供一个可以parallel的处理方式，而且不要试图用用memory来存储太多东
西。
前些天面的EBay， onsite。
【在 r********7 的大作中提到】
: 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
: 1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
: String>）.
: description 是一个非常长的String， 例如一段话。 要求其中不能有negative
: words。如果有 则输出哪里negative word。 没有则输出good。
: 回答 把description分成每一个word，然后比对 negative words
: followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
: 做。
: 2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
: 例如 531226.
|
c********p
发帖数: 1969 | |
y*****g
发帖数: 10 | 44 不可以用hash吗
integer
【在 r********7 的大作中提到】
: 谢了，第二题有没有 其他方法啊。 我跟面试官说的用xor运算，但是他说一个integer
: 最多32位，要是有32位以上的长度就不行了。 问有没有其他方法。
|
s****g
发帖数: 43 | 45 =======To Lonelybug:
About the mathematical solution:
Let b be the missing number, a be the duplicate number.
Let S1= sum 1 to n.
Let S2= sum the sequence
S2-S1=b-a
Let T1= sum 1^2 to n^2
Let T2= sum the sqt of the sequence
T2-T1=b^2-a^2=(b-a)*(b+a)
So you now know the value of b-a and b+a. It's a simple linear equation.
In the test case:
b-a=2
b^2-a^2=12
=> b+a=6
so b=4 and a=2
Scan the sequence again to get the position index. |
r*c
发帖数: 167 | 46 眼花， 把个 sqt 看成是 sqrt.
【在 s****g 的大作中提到】
: =======To Lonelybug:
: About the mathematical solution:
: Let b be the missing number, a be the duplicate number.
: Let S1= sum 1 to n.
: Let S2= sum the sequence
: S2-S1=b-a
: Let T1= sum 1^2 to n^2
: Let T2= sum the sqt of the sequence
: T2-T1=b^2-a^2=(b-a)*(b+a)
: So you now know the value of b-a and b+a. It's a simple linear equation.
|
x*****0
发帖数: 452 | |
e*****i
发帖数: 182 | 48 弱问epi是什么啊！多谢！
【在 A*********c 的大作中提到】
: 第一题用string matching algorithm 算法解是不是不错？推荐robin karp。把
: negative words当成pattern。
: 空格是pattern的一部分，无所吧。
: 第二题就是多了一个数字少了一个数字。
: 抑或A[i]和i,即用531226和123456 XOR，得到 2XOR4
: 找出2XOR4的一个非0位，就是2和4不一样的bit位置
: 再过一遍，仅仅XOR 那些在这个bit位上为0（或者为1）的元素。得到2OR4
: 第三遍扫描看2OR4在不在A[i]里，在就是2，不在就是4.
: 对应的那个的元素就是 2OR4 XOR 2XOR4.参见EPI。
|
s**x
发帖数: 7506 | 49
Co ask.
【在 e*****i 的大作中提到】
: 弱问epi是什么啊！多谢！
|
x*****a
发帖数: 9 | 50 第一题: ACAutomation
第二题: 就是扫一遍, swap直到 A[i] == i+1 为止, 然后再扫一遍看哪个不对, XOR
也行, 写起来蛋疼
第三道: quick select O(N) |
|
|
w****3
发帖数: 110 | |
w****y
发帖数: 56 | 52 a book. elements of programming interview.
【在 s**x 的大作中提到】
:
: Co ask.
|
q****m
发帖数: 177 | 53 第一题用 AC 自动机
【在 r********7 的大作中提到】
: 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
: 1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
: String>）.
: description 是一个非常长的String， 例如一段话。 要求其中不能有negative
: words。如果有 则输出哪里negative word。 没有则输出good。
: 回答 把description分成每一个word，然后比对 negative words
: followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
: 做。
: 2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
: 例如 531226.
|
x*****0
发帖数: 452 | 54 有一些不理解第二题的意思：
请问你：
输入：[5, 4, 3, 2, 2, 1]
输出是：６吗？
【在 r********7 的大作中提到】
: 前些天面的EBay， onsite。 有几个问题感觉回答的不是很好，在这求教：
: 1. 两个输入，一个是description（String）， 另一个是Negative Words（List<
: String>）.
: description 是一个非常长的String， 例如一段话。 要求其中不能有negative
: words。如果有 则输出哪里negative word。 没有则输出good。
: 回答 把description分成每一个word，然后比对 negative words
: followup： 如果 negative words 不是一个单词 而是例如“is bad”。这种 要怎么
: 做。
: 2. 给一个数组，从1到n， 打乱顺序。 其中有个一元素是错的，求那个元素的index。
: 例如 531226.
|
x*******z
发帖数: 31 | 55 请问一下什么是acautomation啊，我刚在网上没有找着。。。或者能不能给一个链接什
么的。。。谢啦
【在 x*****a 的大作中提到】
: 第一题: ACAutomation
: 第二题: 就是扫一遍, swap直到 A[i] == i+1 为止, 然后再扫一遍看哪个不对, XOR
: 也行, 写起来蛋疼
: 第三道: quick select O(N)
|
