|
|
g*****i
发帖数: 2162 | 3 bless
第一题多线程为啥2好?感觉list被其他thread修改的话两种方法都受影响啊
第二题value初始值都是0吗?如果是的话似乎3行code就出来了啊.
int k=in1.known & in2.known;
int v=in1.value | in2.value;
return k & v; |
|
r*******g
发帖数: 1335 | 4 第二题merge sort的话岂不是很耗费硬盘空间
第三题我很好奇的是如何每次取最小的数，你说的dijkstra不是最短路径算法么，貌似
你说的是一次explor很多数，然后选最小一个，这样平坦下来开销小？explor的数还可
以放到heap里面。 |
|
f*******t
发帖数: 7549 | 5 第一题可以看作6个位置里选3个，因为摆了3个某种颜色的球后剩下的位置肯定是填3个
另一种颜色的球。所以是C63。
第二题先选3个位置，剩下的6个位置里再选3个。应该是C93*C63 |
|
|
r*******g
发帖数: 1335 | 7 找到第三题了，thanks
第二题貌似还要两个版本，一个版本是说位置不同就不count，一个版本说位置不同只
要重复出现了就count。 |
|
d********t
发帖数: 9628 | 8 第一题简单，有帝国大厦那么高的一叠硬币能不能放进一个房间，肯定能放进的。
第二题我就挂了，问为啥一个男人把汽车推进一个旅馆然后就输掉全部身家。答案是he
's playing monopoly。是玩大富翁吗？ |
|
|
p*****2
发帖数: 21240 | 10 第一题each product stores a customer list who registered notification
第二题each product has a hashtable to store customers who purchased already
行不行呀。 |
|
p*****2
发帖数: 21240 | 11 我就做了第二题，第一题做了一半，没时间了。这次要对两个能进前100. |
|
i**********e
发帖数: 1145 | 12 第一题我也想知道有没有 O(N) 解和 O（1） space 那么神奇的方法。
第二题是 reservoir sampling. |
|
g*********e
发帖数: 14401 | 13 第一题他的意思应该是用一个256长的int array来记录，第二题没看懂 |
|
h**k
发帖数: 3368 | 14 第二题是老题，题目是从一个不知到总长度的int stream中采集k个样本，怎么做才能
使stream中的每个int被采的概率相同？ |
|
|
p*****2
发帖数: 21240 | 16 第二题我就不懂base64这些东西。L家考的也太specific了。第三题我理解主要是考虑
安全性，如果state放在 client还能安全。 |
|
t*********7
发帖数: 255 | 17 来自主题: JobHunting版 - 请问两道题 第一题应该没有O(n)的搞法吧...第二题倒是有O(n)的搞法,好像是一篇高端论文...
nlgn的搞法应该是median of medians algo...同求熟悉这个算法的大神指点. |
|
h*****3
发帖数: 1391 | 18 第二题有啥好算法啊？我能想到的就是从1开始好好算，算到n。
第一题也没啥好算法吧？就是不停的求combine（n-1,k-1)? |
|
i*********7
发帖数: 348 | 19 第一题是求一个循环链表的最大和的子链表。
譬如说 1 -> -1 -> 2。然后又回到1，最大和是3，子链表是 2 -> 1。
第二题如下。
There are n gas stations positioned along a circular road. Each has a
limited supply of gas. You can only drive clockwise around the road. You
start with zero gas. Knowing how much gas you need to get from each gas
station to the next and how much gas you can get at each station, design an
algorithm to find the gas station you need to start at to get all the way
around the circle.
跪求各位大神，求思路求解答。 |
|
i*********7
发帖数: 348 | 20 你的意思是，第一题最多只需要简单的转两轮即可？
第二题怎么看都不像是O(N)的吧？它在不停的尝试出发点啊。 |
|
p*****2
发帖数: 21240 | 21 第一题
encrypt(hash(long url))
第二题，类似count sort |
|
t****a
发帖数: 1212 | 22 数论太烂。第一题怎么做呢？
第二题感觉是先从小到大排序以后顺着merge过来，这样最大的数字被merge最少，损失
最小。你觉得呢？ |
|
D**********d
发帖数: 849 | 23 需要说明的是 题目要求结合运算满足结合律（环表），不满足交换律, 不然干脆是两
个 sets,
为什么叫 lists?
所以 Greedy 不能解第二题，见以下反例
按 Greedy 算法
( (2 3) 4 ) ( 6 (5 4) ) ) = 62
但是有一解法 （把 2 3 4 移到末位）
（（6 5） （（4 2）（3 4） ）） = 61
可用二维 DP 解, O(N^2)
对于第一题， 可对 B 用 二进制表示(所以 log(B) ), 利用
(a mod c)^n mod c = a^n mod c
求解 |
|
h****n
发帖数: 1093 | 24 第一题吧
s1 aaaab s2 zzzzb
应该有两个结果 一个就是aaaab和zzzzb，还有一个就是aaaa和zzzz
第二题应该题意很清楚吧。？ |
|
b***m
发帖数: 5987 | 25 第一题还是比较简单的，大家来讨论一下第二题的思路。 |
|
b*****u
发帖数: 648 | 26 第一题能否这么弄
建一个大根堆，
和一个hash_map > map用于存储比key小，又出
现得比key早的value
对每一个新数x，首先放入堆，整理，然后对所有在x下面的值y， map[x].push_back(y)
最后对map[y]里的每一个值，
将(x, y, map[y][i])存入result
//===============================
第二题遍历一次signature，I 加一 D 减一， 然后把最低值记下来，设为1，推出其余 |
|
g*******r
发帖数: 44 | 27 第一题是应该找到一个i,j,k就可。
你第二题说贪心是咋做的呢？说详细点行吗，谢谢了。 |
|
P******r
发帖数: 842 | 28 是，给一道没做过的就完了。
那就不问就不说。问了就毫不犹豫说做了。可是要在问啥时候做的咋办，要是昨天刚练
过的。
如果第一次做得好，结果人家问做没做，说做了。然后第二题人家上来就问做没做过，
之后每题都上来就问做没做过，那咋办？
或者偶尔主动说一次做过了？ |
|
c********t
发帖数: 5706 | 29 多谢！
第一题最后发现用 char array 比 StringBuilder还快
第二题又超时了，再求帮助！
用的是双queue解法，感觉比你和wwwyhs说的hashmap>用空间
更少，时间也应该更少，为啥又超呢？（唉，我为什么又说又）
public ArrayList> findLadders(String start, String end,
HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> ret = new ArrayList>(
);
int curr=1, next=0, count=1, n=start.length(), length=Integer.MAX_
VALUE... 阅读全帖 |
|
c********t
发帖数: 5706 | 30 多谢！
第一题最后发现用 char array 比 StringBuilder还快
第二题又超时了，再求帮助！
用的是双queue解法，感觉比你和wwwyhs说的hashmap>用空间
更少，时间也应该更少，为啥又超呢？（唉，我为什么又说又）
public ArrayList> findLadders(String start, String end,
HashSet dict) {
// Start typing your Java solution below
// DO NOT write main() function
ArrayList> ret = new ArrayList>(
);
int curr=1, next=0, count=1, n=start.length(), length=Integer.MAX_
VALUE... 阅读全帖 |
|
p*****p
发帖数: 379 | 31 第一题你怎么答的？最简单的解法O(n^2)吧
或者类似bit，用个mask，需要4个int
第二题用个二维数组就行了吧 |
|
j******s
发帖数: 48 | 32 Q1. Bin-String Distance
You are only given strings made of by '1's and '0's (no empty strings),
such as "1", "101", "0000". Let's call them bin-strings.
The term "strange-distance" of two bin-strings is defined as follows:
Rip off their common prefix, the "strange-distance" is therefore sum
of length of remaining strings. E.g., "111001001" and "1110101001"
after taking off common prefix "1110", the remains are "01001" and
"101001". So their strange distance is 11.
Your program input will... 阅读全帖 |
|
j******s
发帖数: 48 | 33 好吧，自己回答一下思路，虚心求各路大神拍，给点意见
第一题应该是建立一个binary tree,然后recursive求每一个节点的左右子树的最高高
度,他们和就是在这一位上的largest distance，可以online做，但是需要在每个节点
保存左右子树的高度并且动态更新。
o(n) time + O(n) space
第二题,
Assumption:
1 Log file is typically very small, operations are append, delete and read.
2 Cluster is built on Hadoop, which has a chunk size of 64MB, roughly, and
it might be too large and inefficient if we use this chunk size for the log
file.
3 Log information is typically not very important, less effort is needed for
redundan... 阅读全帖 |
|
x*********w
发帖数: 533 | 34 第一题有伪DP解法，不是很容易看出来啊
第二题和increasing sub sequence 差不多 |
|
p*****2
发帖数: 21240 | 35
第二题怎么感觉那么别扭。就是mapreduce吧？
第一题要写代码吗？上个星期刚做了这个练习，不过做的太粗了，现在差不多都忘记了
。 |
|
c******a
发帖数: 789 | 36 来自主题: JobHunting版 - 两道F的题 第一题如果没理解错，就是一个很specific的parser。主要考coding bug free？
第二题我只能想到O(n^2)解，唉 |
|
r**h
发帖数: 1288 | 37 来自主题: JobHunting版 - 两道F的题 第一题转成后序直接计算就可以了吧，不过没练熟要写出来不容易
第二题。。。求n log n的解法 |
|
f******p
发帖数: 173 | 38 第一题counting，url长度不会太大，分配一个Bundle[400]的数组，
class Bundle {
int count;
int avgLen;
}
存每个长度的url的个数和均值。然后还有
total_url_count, total_url_avg_length
95%url的平均长度就是： (total_url_count * total_url_avg_length-sum_{i in top
5% url set}{count_i*avgLen_i}) divided by (total_url_count - sum_{i in top
5% url set}{count_i})
第二题不会。。可以退化成二维或者一维的。怎么感觉和closest pair of points的解
法有些类似。
5% |
|
b********g
发帖数: 28 | 39 依上面的讨论，第一题可以用两个堆：minHeap (right, 5%) & maxHeap (left, 95%).
堆中节点为：
class Node{
int length;
int count;
}
另外用两个HASHMAP，用来记录各个堆中某个长度在堆中对应的节点；对每个堆，用两
个变量分别记录其总URL个数和平均长度。插入新的URL长度时，只要维护两个堆的平衡
和相关变量既可。空间复杂度为O(n)，n为最长的URL长度，可以理解为常数
第二题可以先算出空间的边界，然后将整个空间分割成边长为１的立方体，并给每个立
方体分配ID。用一个HASHMAP记录与每个立方体相交的球体链表。如果某个立方体不与
任何球体相交，则不用记录。然后是处理每个点，计算出其所在的立方体ID，然后检查
其对应的球体链表，并将包含它的球体计数加１.
如果球体均匀分布的话，时间复杂度为O(m + n)。 |
|
n****a
发帖数: 174 | 40 一小时两道题
我记得当时我的第二题是矩阵迷宫找出口 |
|
A*********c
发帖数: 430 | 41 第一题用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。 |
|
x*****a
发帖数: 9 | 42 第一题: ACAutomation
第二题: 就是扫一遍, swap直到 A[i] == i+1 为止, 然后再扫一遍看哪个不对, XOR
也行, 写起来蛋疼
第三道: quick select O(N) |
|
A*********c
发帖数: 430 | 43 第一题用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。 |
|
x*****a
发帖数: 9 | 44 第一题: ACAutomation
第二题: 就是扫一遍, swap直到 A[i] == i+1 为止, 然后再扫一遍看哪个不对, XOR
也行, 写起来蛋疼
第三道: quick select O(N) |
|
w*****e
发帖数: 931 | 45 关于第二题我是这么想的：
1. 因为单独一个字母也要count，可能使得输出串甚至比输入更长，所以需要明确保证
数组有足够的空间。
2. 可以先从做往右扫一遍，遇上单独一个字母不用管，否则计数update。比如
abbbccddeefgh最后变成ab3c2d2e2fgh.记住数目为1的字母总数，这道题里面是4.
3. 已经能知道输出字符串的总长，从右往左scan。 |
|
f*****e
发帖数: 2992 | 46 第一题排序，然后从小到大确定位置。
第二题DP。 |
|
p*****2
发帖数: 21240 | 47 感觉第一题没什么太大chanllenge呀？查双方friends的合集不久行了吗？这个应该很
快快呀。
第二题是放内存里吗？4G内存还是disk？ |
|
l*****7
发帖数: 55 | 48 我觉得还是坦诚告诉他比较好。另外，也建议不换题，先讨论一下。
1. 先说说自己当时开始的想法，然后讲自己怎么想到最优解的。
2. 用最快的方式给出最优解，及复杂度
3. 讲点有意思的扩展谈论一下。
最后一条，比如有一次我写完链表找环的问题，就讲了个故事。话说小明有一阵子无聊
，在计算器上乱按了一个数，然后平方，接着再平方。很快就溢出了，计算器比较弱，
只保留最低9位。小明也不管高位，接着把当前有效数平方。最后发生一个有趣的现象
，有个神奇的数，请问…
面试官瞪大眼睛，看着我，到这里忽然哈哈大笑，说：哈哈，那个数…。
我赶紧打住，让他再出第二题。
亏？ |
|
P****2
发帖数: 197 | 49 第一题，P(X) = 扔到6结束游戏概率 P(X) = 1/6 * 1 + 5/6 * (1-P(X))
第二题关键是分解，分解成X1,...X5随机变量，Xi表示i-1样东西出现后，看到ith的次数
Xi明显是Geometric Dist，并且相互独立,E(Xi) = 1/Pi |
|
l**********1
发帖数: 415 | 50 第一题不会
感觉第二题只能dfs不能dp，因为1）要一个路径作为答案而不是只要一个数字。2）因
为可以四个方向走，所以解的树有环
等待大牛解答 |
|
