|
|
|
|
m**a
发帖数: 139 | 5 这个n是单词数,扫描一遍文件是O(n).
这是哪个公司的题？ |
|
h********w
发帖数: 221 | 6 这题没读明白，啥叫“最小的包含所有搜索单词的段落”，完整1个段落同时size最小
？ |
|
d*****y
发帖数: 205 | 7 这是Introduction to Algorithms书上的课后题。
是Point of Most intersection( POM)问题。
用sweep line algorithm，要点是将每个区间的左右端点分开并排序，
得到2n个end point数组，简单的做法可以将2N个端点augment +1 和-1计数，
也可以在扫描过程中维持一个当前仍然被交叉的区间的集合（用二叉树），插入和删除
都是log n
这样的算法不仅可以计数还可以输出哪些区间有交叉。
另外还可以变形为求和其他区间交叉最多的segment，
这时需要再保持额外的数据结构，比如当前端点处已经扫描过的左端点数量。 |
|
C***U
发帖数: 2406 | 8 这题问了好多次了
可以把他们转化成()的算法
a_i=(, b_i=)
然后把它们根据大小排成一列。 这里用nlogn的时间。
然后你从第一位开始走，
遇到(就+1 遇到)就-1
把所有的数 记录下来 最大的数就是你要的答案了。 |
|
d*****y
发帖数: 205 | 9 这是Introduction to Algorithms书上的课后题。
是Point of Most intersection( POM)问题。
用sweep line algorithm，要点是将每个区间的左右端点分开并排序，
得到2n个end point数组，简单的做法可以将2N个端点augment +1 和-1计数，
也可以在扫描过程中维持一个当前仍然被交叉的区间的集合（用二叉树），插入和删除
都是log n
这样的算法不仅可以计数还可以输出哪些区间有交叉。
另外还可以变形为求和其他区间交叉最多的segment，
这时需要再保持额外的数据结构，比如当前端点处已经扫描过的左端点数量。 |
|
C***U
发帖数: 2406 | 10 这题问了好多次了
可以把他们转化成()的算法
a_i=(, b_i=)
然后把它们根据大小排成一列。 这里用nlogn的时间。
然后你从第一位开始走，
遇到(就+1 遇到)就-1
把所有的数 记录下来 最大的数就是你要的答案了。 |
|
q********c
发帖数: 1774 | 11 BFS, DFS 都可以，这题关键是考怎么copy links. |
|
k*******r
发帖数: 355 | 12 BTW, 这是facebook 给俺的电面题，让俺非常郁闷 |
|
s*******f
发帖数: 1114 | 13 来自主题: JobHunting版 - G家电面题 G逐渐开始找有经验的笨蛋了，不像以前出耗脑力的题了。 |
|
p*******m
发帖数: 47 | 14 BT树结构, 中间节点是算数运算符(只有+ - * / 4种操作), 叶节点是数字, 要求给出
算数表达式 (要求没有冗余括号)
比如
*
/ \
+ *
/ \ / \
1 2 4 5
表达式 = (1 + 2) * 4 * 5, 不能是 (1+2)*(4*5)
+
/ \
* +
/ \ / \
1 2 4 5
表达式 = 1 * 2 + 4 + 5, 不能是 1 * 2 + (4 + 5)
总之, 这题的难点是 算数表达式不能有冗余括号
我当时的思路: in-order 递归遍历, 遇到 + - 给出左右括号 (但这样就有冗余括号).
面试官指出后, 我说我可以再扫描遍得到的表达式，去除冗余括号 (这也是我情急下
蒙的).
他说不行, 只能在遍历BT时一次完成. 他提示考虑运算符的优先级, 但后来时间到了,
也就草草收场
真心请教思路, 多谢
=========================================
class No... 阅读全帖 |
|
s*********5
发帖数: 514 | 15 上午刚面的题，感觉有点意思：
一个大数组，在1到25000之间，只有4K memory, 打印出其中正好只出现过一次的数。
没出现过，出现过2次，3次，或更多，都不打印。
分享给大家，千万别翻成英文。
晚上回来跟大家讨论。
马上去另一家Onsite了， bless 我吧 |
|
y****n
发帖数: 743 | 16 4K Bytes = 32K Bits，每个bit对应一个整数，足够应对1-25000的范围。
原题说能拿到一个数组，而不是文件，把数组里的数字置为负数arr[n]=-arr[n]
通过数字的符号和相应的bit值组合成三种可能：未出现，出现一次，出现多次 |
|
p*****2
发帖数: 21240 | 17 yishan的这个思路很有趣。好像上次解一道题也是这种思路。不知道是学来的，还是自
己想出来的。 |
|
J*****u
发帖数: 30 | 18 为什么不能在第二次出现直接标为false呢？谢
4K Bytes = 32K Bits，每个bit对应一个整数，足够应对1-25000的范围。原题说能拿
到一个数组，而不是文件，把数组里的数字置为负数arr[n]=-arr[n........
★ Sent from iPhone App: iReader Mitbbs Lite 7.52 |
|
s*********5
发帖数: 514 | 19 上午刚面的题，感觉有点意思：
一个大数组，在1到25000之间，只有4K memory, 打印出其中正好只出现过一次的数。
没出现过，出现过2次，3次，或更多，都不打印。
分享给大家，千万别翻成英文。
晚上回来跟大家讨论。
马上去另一家Onsite了， bless 我吧 |
|
y****n
发帖数: 743 | 20 4K Bytes = 32K Bits，每个bit对应一个整数，足够应对1-25000的范围。
原题说能拿到一个数组，而不是文件，把数组里的数字置为负数arr[n]=-arr[n]
通过数字的符号和相应的bit值组合成三种可能：未出现，出现一次，出现多次 |
|
p*****2
发帖数: 21240 | 21 yishan的这个思路很有趣。好像上次解一道题也是这种思路。不知道是学来的，还是自
己想出来的。 |
|
J*****u
发帖数: 30 | 22 为什么不能在第二次出现直接标为false呢？谢
4K Bytes = 32K Bits，每个bit对应一个整数，足够应对1-25000的范围。原题说能拿
到一个数组，而不是文件，把数组里的数字置为负数arr[n]=-arr[n........
★ Sent from iPhone App: iReader Mitbbs Lite 7.52 |
|
|
a********r
发帖数: 218 | 24 来自主题: JobHunting版 - M家电面题 总共两道题，全不会，
1. If we don't run an executable file, how do you tell it is a malware or a
normal executable file? What kind of information can you use to find whether
it is a potential malware?
2. How do you write a program to compare the difference between two
executable files? what kind of components will you compare? |
|
p*****2
发帖数: 21240 | 25 来自主题: JobHunting版 - M家电面题 第一问不就是病毒扫描吗？有一些比较基本的技术。
第二题要问清楚想找什么difference |
|
t**********h
发帖数: 2273 | 26 来自主题: JobHunting版 - M家电面题 我擦，我题都没看懂。膜拜北京 |
|
a********r
发帖数: 218 | 27 来自主题: JobHunting版 - M家电面题 我也膜拜北京
第一问如何扫描？面试官是个hiring manager.面试的是码工。只是在电话里谈，不需
真的写代码。他的意思是不能运行这个executable文件，不然你的PC就感染了。
第二题面试官要我告诉他找什么difference. 一个是正常的executable文件，一个怀疑
是malware |
|
s****n
发帖数: 70 | 28 给了这么长一道题，光读就读了半天
Write a Java function, printTree(), which prints a given tree in depth first
format to stdout. Details:
The argument of printTree is a stream of pairs of string values.
Each string found anywhere in the input represents a unique node.
Each item in the stream is a pair indicating a parent/child relationship
in the tree. The first element in the pair is the parent. The second
element in the pair is the child.
Each parent can have many children.
The input list may con... 阅读全帖 |
|
l*********8
发帖数: 4642 | 29 谢谢分享
先建树，然后输出。 其实是两道小题
first
|
|
j*****o
发帖数: 394 | 30 这是电面题还是ONSITE啊。。。？
complete
approximation |
|
i****y
发帖数: 58 | 31 来自主题: JobHunting版 - A家电面题 谢谢分享。。想问问第三题的思路。。。很怕这类问题诶。。 |
|
C***U
发帖数: 2406 | 32 来自主题: JobHunting版 - A家电面题 觉得第三题完全不会啊。没学过网络。遇到就挂了。
join |
|
q****m
发帖数: 177 | 33 来自主题: JobHunting版 - A家电面题 第一题是用类似于 quick sort的思路吗 |
|
t********e
发帖数: 344 | 34 来自主题: JobHunting版 - A家电面题 第一题用XOR吗 |
|
h****n
发帖数: 1093 | 35 Leetcode 上的原题
class Solution {
public:
vector plusOne(vector &digits) {
// Start typing your C/C++ solution below
// DO NOT write int main() function
int size = digits.size();
vector res;
if(size<1) return res;
//加1操作，只需要把初始值置为1即可
int carry = 1;
int i;
for(i=size-1;i>=0;i--)
{
//这里注意先push后更新carry的值，否则会有错误
res.push_back((digits[i]+carry)%10);
if(digits[i]+carry>9)... 阅读全帖 |
|
p*****2
发帖数: 21240 | 36
这题要求的是自定义数据结构，leetcode上数据结构给定死了，未必是最优。 |
|
p*****2
发帖数: 21240 | 37
可能面试官在leetcode上看的题，上边用的int[] |
|
j*****y
发帖数: 1071 | 38 cactus graph那道题是要写 code 吗？
You
with |
|
|
|
l**b
发帖数: 457 | 41 二爷不用DP，奇怪啊！第3题用Trie的话memory吃不消吧？用DP是不是好点？
贴个简单的代码，helper是recursive的，helper2是DP的，2爷帮忙看看，是不是又出
错了：
public boolean isSubSequence(String s, String t) {
assert(s != null && t != null);
if (t.length() == 0) return true;
//return helper(s, t, 0, 0);
return helper2(s, t);
}
private boolean helper(String s, String t, int si, int ti) {
if (ti == t.length()) return true;
if (si >= s.length()) return false;
if (s.charAt(si) == t... 阅读全帖 |
|
|
j********g
发帖数: 80 | 43 第二题 是不是把s按顺序扫一遍就行了， 我没理解错吧
bool find_substr(string si, string t){
int s_len=si.size();
int t_len=t.size();
int j=0;
for(int i=0; i
while(si[i]!=t[j] && j
j++;
if(j==t_len)
return false;
j++;
}
return true;
} |
|
H****s
发帖数: 247 | 44 原题要看是否subsequence 不是 substr |
|
t****a
发帖数: 1212 | 45 第三题很有趣，偶来给个clojure的解
基本思路是
1. 对T做预处理，构建graph，同时，记录每个字符a-z所出现的位置
2. 由于S长度<100，数量却很大(100M)，意味着有很多重复，使用memoize function会
大大减少计算量
下面的程序在1/1000大小的S数据集上运行需要1.7秒。观察了一下时间和数据集大小趋
势，在完整数据集上几分钟内也可以产生结果
(def alphabet (map char (range (int \a) (inc (int \z)))))
(def T (vec (take 10000000 (repeatedly #(rand-nth alphabet)))))
(def S (take 100000 (repeatedly (fn [] (take (inc (int (* (rand) 100))) (
repeatedly #(rand-nth alphabet)))))))
(def T-ix (group-by #(T %) (range (count T))))
(def T-map (let [pairs (dist... 阅读全帖 |
|
|
j*****y
发帖数: 1071 | 47 cactus graph那道题是要写 code 吗？
You
with |
|
|
|
l**b
发帖数: 457 | 50 二爷不用DP，奇怪啊！第3题用Trie的话memory吃不消吧？用DP是不是好点？
贴个简单的代码，helper是recursive的，helper2是DP的，2爷帮忙看看，是不是又出
错了：
public boolean isSubSequence(String s, String t) {
assert(s != null && t != null);
if (t.length() == 0) return true;
//return helper(s, t, 0, 0);
return helper2(s, t);
}
private boolean helper(String s, String t, int si, int ti) {
if (ti == t.length()) return true;
if (si >= s.length()) return false;
if (s.charAt(si) == t... 阅读全帖 |
|
