n****e
发帖数: 678 | 1 Exactly
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。 |
|
n****e
发帖数: 678 | 2 Exactly
Skyline 的解法貌似是（没记错的话）：
把所有的turning points 放在一起，根据coordination从小到大sort 。
struct turnpoint {
int ptr; //coordinate;
bool startOrEnd;
int volume
}
再用max-heap, 把所有的turning points扫一遍，遇到start turning point, 把
volume放入max-heap. 遇到end turning point，把对应的volume从max-heap中取出。
max-heap的max 值就是对应区间的最大volume
complexity是O(nlogn)
max-heap可以用multiset实现。 |
|
|
s*w
发帖数: 729 | 4 无脑 rolling hash，对付这种定长的字串专用
从头扫到尾，对当前长度10的子串算一个 hash code, 结果查询以前(set, 或者 unor
dered_set)存起来的 hash code，重复的话，就输出当前的子串
比直接存所有的unique子串要省时间省空间 |
|
J****3
发帖数: 427 | 5 攒人品
From MITBBS:
1. 给一个二叉树 返回镜像 (Binary Tree Mirror)
2. Implement a thread-safe blocking queue.
3. 一个嵌套Map， 就是一个HashMap, 它的value可以是一个element也可以是另外一个
嵌套map或是空的map. 实现一个iterator来遍历这个map里面的所有element。 就是类
似树遍历一样的方法
4. 给你一个数组，其中一个数出现了大于N／３次，N是数组长度。怎么找？我先说
HASHTABLE，他问我还有没有什么办法。想来想去只能SORT. 他就问下一题了。不知道
还有没有什么最优解。我觉得那种针对一个数字出现过大于N／２的VOTING ALGORITHM
好象不是很合适吧。
5.后缀波兰表达式STRING转换为中缀表达式的STRING。
这题本来很简单，但我可能算错了。纠结的地方是a,b,+,c,/
到底是 (c/(a+b)) 还是 ((a+b)/c)
6. Implement pow(double a, int b)
7. 接着给Amazon的favori... 阅读全帖 |
|
d********e
发帖数: 239 | 6 第一个程序有个小错误，return ret?
第二个程序 ret = maxOccur;？or ret = i?
如果不知道出现最多的数是哪个，怎么也得扫两遍吧，要不ret可能记录的是别的数的
index吧 |
|
h******6
发帖数: 2697 | 7
就是假设我们现在在a1[i] 然后我遍历a2到a2[j]==a1[i]的话 我swap(a2, i, zero);
zero=j;swap(a2, i, j);其中zero负责记录值为0的位置的index
他让改进 然后我就先扫一遍a2用hashmap记录每个数值的index 这样后面就不用遍历来
找某个数值的index了 |
|
|
c******0
发帖数: 260 | 9 从前往后扫，然后再从后往前。版上最近也有人面过这题，你搜搜。挺简单的 |
|
b*********s
发帖数: 115 | 10
谢bless
这个题当时我答的并不好，我就说说后来面试官跟我解释的那个做法吧。
对input从左往右扫，维持一个hashtable记录前面所出现过所有三位数和它们最后一次
出现的位置，举个例子说明
input：2 3 4 5 2 3 4 5 1...
用 digit 代表正在扫描的数字，record表示hashtable：
digit record
2 {}
3 {}
4 {234: 0}
5 {234: 0, 345: 1}
2 {234: 0, 345: 1, 452: 2}
3 {234: 0, 345: 1, 452: 2, 523: 3}
4 {234: 4, 345: 1, 452: 2, 523: 3}
.
.
.
此外，在扫描一个数字的时候，如果发现有重复出现的三位数，那么就开始对比下去，
尝试找到最长的match。继续用回上面的例子：
在扫描到第二个4的时候，会发现234重复出现，所以就继续比较input[3] 和 input[7]
, 两个都是5，match，所以继续比较inpu... 阅读全帖 |
|
c*****m
发帖数: 271 | 11 没看出来这里所说的方法能把题目所述的 3, 5, 6, 5, 6, 5, 6, 5, 8...压缩成#3,
#5, #6, 2 5, #8...啊，如果hashtable中只记三位数的话。有哪位大牛能解释一下么？
谢bless
这个题当时我答的并不好，我就说说后来面试官跟我解释的那个做法吧。
对input从左往右扫，维持一个hashtable记录前面所出现过所有三位数和它们最后一次
出现的位置，举个例子说明
input：2 3 4 5 2 3 4 5 1...
用 digit 代表正在扫描的数字，record表示hashtable：
digit record
2 {}
3 {}
4 {234: 0}
5 {234: 0, 345: 1}
2 {234: 0, 345: 1, 452: 2}
3 {234: 0, 345: 1, 452: 2, 523: 3}
4 {234: 4, 345: 1, 452: 2, 523: 3}
.
.
.
此外，在扫描一个数字的时候，如果发现有重复出现的三位数，那么... 阅读全帖 |
|
l*****7
发帖数: 55 | 12 6.b 难道不是前后开始各扫一遍完事？当前积(和)先累积到result[i]，后更新。 |
|
J******u
发帖数: 42 | 13 这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。 |
|
J******u
发帖数: 42 | 14 这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。 |
|
J******u
发帖数: 42 | 15 这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。 |
|
J******u
发帖数: 42 | 16 这个如果不是暴力地解，基本上只能greedy了吧。想不出不greedy的算法了。访问到每
个字母的时候，如果该字母和目标字母不同，就往左和往右扫，找最近的目标字母，然
后switch一下。但是这样的做法就是greedy了。 |
|
z******h
发帖数: 22 | 17 直接扫一遍就可以了吧，维护一个pattern的字符串，发现匹配不上的时候就把pattern
更新为从第一个字符到当前字符的字符串，并且从当前字符开始重新匹配。因为原来字
符串的开头必然是pattern的开头，并没有必要KMP。
★ 发自iPhone App: ChineseWeb 7.8
★ 发自iPhone App: ChineseWeb 7.8 |
|
|
|
H*********a
发帖数: 34 | 20 我也发一个想法，从string的第2位开始扫（为了保证那个子string的长度为2），当前
位的char和string首char一样的时候，就以首位到当前位的子string为模型，匹配后面
的相隔同等位置，同等长度的子string。这个方法不能处理"aaaaaaaaaa"，因为认为这
是"aaaaa"乘以2。
bool check(int l, int n, string s) {
if (n % l != 0)
return false;
for (int j = 1; j < n/l; j++) {
if (s.substr(0, l) != s.substr(j*l, l))
return false;
}
return true;
}
bool isMultiple(string s) {
int n = s.size();
if (n <= 3)
return false;
for (int i = 2; i <= n/2; i++) {
... 阅读全帖 |
|
m*********1
发帖数: 204 | 21 昨天晚上睡不着，上来发的，没想到一天有那么多回复了。看了大家的回复，我觉得我
这个题目不简单啊。呵呵。。。
不过这个题目我后来仔细思考过，我的做法是这样的：
1.两头同时开始扫，找到base case: 当substring(0,i) == substring(j,n)的时候，
我假设substring(0,i)为这个重复的base case. 这里n是原String的length
这里可以优化的是，如前面同学所说，i不能被length整除的话，就不用比较，直接跳
过去
2.从1找到base case以后，两头切掉，留下中间部分substring(i,j)，先看一下长度，
能不能整除i，不能就直接false，可以的话，写个循环，每次切i长度下来，和base
case对比一下是不是相等，直到结束。
因为很多不能整除的数可以跳过去，这个做法的worse case 是长度正好是2^n的String
，并且base case正好是2^k的长度的情况。
比如 ababababababacab 这样找到base case = ab，然后要切到最后才发现ac，但是
感觉还是能满足O(n)
我贴... 阅读全帖 |
|
p******d
发帖数: 63 | 22 先用O(n)的Z algorithm算Z[i]=从i开始最长的prefix长度，i=1...n-1
例如
abcabcabc对应的Z={null, 0, 0, 3, 0, 0, 3, 0, 0}
aaabaaaaba对应的Z={null, 2, 1, 0, 3, 5, 2, 1, 0, 1}
aaaaaaaaaa对应的Z={null, 9, 8, 7, 6, 5, 4, 3, 2, 1}
之后扫一遍Z数组返回满足Z[i]==i的i值，到i-1的prefix就是答案
Z algorithm看这里http://codeforces.com/blog/entry/3107 |
|
c****p
发帖数: 6474 | 23 两个指针，head, tail,记循环节长度len为1
head初始都为0，tail为1。tail一直自增。
如果str[head] == str[tail], head自增。如果head>= len则归零
如果str[head] != str[tail]，则len = tail。
扫完一遍查len和str.size()的关系就得了。 |
|
z******h
发帖数: 22 | 24 直接扫一遍就可以了吧，维护一个pattern的字符串，发现匹配不上的时候就把pattern
更新为从第一个字符到当前字符的字符串，并且从当前字符开始重新匹配。因为原来字
符串的开头必然是pattern的开头，并没有必要KMP。
★ 发自iPhone App: ChineseWeb 7.8
★ 发自iPhone App: ChineseWeb 7.8 |
|
|
|
H*********a
发帖数: 34 | 27 我也发一个想法，从string的第2位开始扫（为了保证那个子string的长度为2），当前
位的char和string首char一样的时候，就以首位到当前位的子string为模型，匹配后面
的相隔同等位置，同等长度的子string。这个方法不能处理"aaaaaaaaaa"，因为认为这
是"aaaaa"乘以2。
bool check(int l, int n, string s) {
if (n % l != 0)
return false;
for (int j = 1; j < n/l; j++) {
if (s.substr(0, l) != s.substr(j*l, l))
return false;
}
return true;
}
bool isMultiple(string s) {
int n = s.size();
if (n <= 3)
return false;
for (int i = 2; i <= n/2; i++) {
... 阅读全帖 |
|
m*********1
发帖数: 204 | 28 昨天晚上睡不着，上来发的，没想到一天有那么多回复了。看了大家的回复，我觉得我
这个题目不简单啊。呵呵。。。
不过这个题目我后来仔细思考过，我的做法是这样的：
1.两头同时开始扫，找到base case: 当substring(0,i) == substring(j,n)的时候，
我假设substring(0,i)为这个重复的base case. 这里n是原String的length
这里可以优化的是，如前面同学所说，i不能被length整除的话，就不用比较，直接跳
过去
2.从1找到base case以后，两头切掉，留下中间部分substring(i,j)，先看一下长度，
能不能整除i，不能就直接false，可以的话，写个循环，每次切i长度下来，和base
case对比一下是不是相等，直到结束。
因为很多不能整除的数可以跳过去，这个做法的worse case 是长度正好是2^n的String
，并且base case正好是2^k的长度的情况。
比如 ababababababacab 这样找到base case = ab，然后要切到最后才发现ac，但是
感觉还是能满足O(n)
我贴... 阅读全帖 |
|
p******d
发帖数: 63 | 29 先用O(n)的Z algorithm算Z[i]=从i开始最长的prefix长度，i=1...n-1
例如
abcabcabc对应的Z={null, 0, 0, 3, 0, 0, 3, 0, 0}
aaabaaaaba对应的Z={null, 2, 1, 0, 3, 5, 2, 1, 0, 1}
aaaaaaaaaa对应的Z={null, 9, 8, 7, 6, 5, 4, 3, 2, 1}
之后扫一遍Z数组返回满足Z[i]==i的i值，到i-1的prefix就是答案
Z algorithm看这里http://codeforces.com/blog/entry/3107 |
|
c****p
发帖数: 6474 | 30 两个指针，head, tail,记循环节长度len为1
head初始都为0，tail为1。tail一直自增。
如果str[head] == str[tail], head自增。如果head>= len则归零
如果str[head] != str[tail]，则len = tail。
扫完一遍查len和str.size()的关系就得了。 |
|
l*****i
发帖数: 13 | 31 abaaabaa False
想不出来只扫一遍的做法啊 |
|
l*****i
发帖数: 13 | 32 abaaabaa False
想不出来只扫一遍的做法啊 |
|
l*****f
发帖数: 2198 | 33 想了一个晚上想出一个简便的解法：
1. 扫一遍string，统计每个字符出现的个数。
2. 如果是true,那每个字符出现的个数必定相等。所以如有任何字符出现次数与其他的
次数不符，返回false
3. 假设每个字符出现个数都为n,则“可能”会有符合条件的pattern. 此种pattern的
长度为
(string length/n)*i, i = 1,2,3，假设这个数为k
4. 写一个loop，依次验证
string(0) = string (k) = string (2k).....
string(1) = string(k+1) = string(2k + 1)...
...
直到string(k-1) = string(2k - 1) ...
任何时候遇到false，则返回结果false,否则返回true
复杂度没估计过，应该不会很大 |
|
w********s
发帖数: 1570 | 34 积分图像
扫一遍可以获得积分图像
S(i,j)=从(0,0)到(i,j)的点的个数
之后，对于任意的矩形(i,j),(k,l)，都可以一步求得其中包含的点的个数
S2 = S(k,l) - S(k,j) - S(i,l) + S(i,j)
O(n^2)肯定可以搞定。
点. |
|
t*****a
发帖数: 106 | 35 Struct Card
{
int ID;
int up;
int bottom;
}
card上下颠倒了，ID不变，然后Hashmap扫一遍就行了，用ID判断是不是self-comp |
|
w********s
发帖数: 1570 | 36 第二题，不是扫一遍之后记录所有的字母的位置
比如str=abcdbacebd, set=abcd
a:0,5
b:1,4,8
c:2,6
d:3,9
pos = 0:
abcd={0,1,2,4}, length = 4, pop 0
pos = 1:
abcd={5,1,2,4}, length = 5, pop 1
pos = 2:
abcd={5,4,2,4}, length = 4, pop 2
... |
|
J***o
发帖数: 553 | 37 其实关键在于确定第i个人的位置的时候，因为剩下的都是比他高的，而已经确定位置
的都是比他矮的，只要保证他前面有和原排序前面比他高的人数量相等的空位即可。如
果直接扫空位的话是O(N^2)。快一点的方法是把剩下的空位段保存在interval tree里
，这样每次找第k个空位只要O(logN)，总体的复杂度是O(NlogN) |
|
t**********0
发帖数: 1700 | 38 来自主题: JobHunting版 - 谈G家面经 这方法要扫两遍的。 |
|
Z**********4
发帖数: 528 | 39 来自主题: JobHunting版 - 谈G家面经 可以这么做：
先必须用一个maxValue记录最大数的值，用作比对。
然后还需要记录maxIndex就是最大值所在的index.
还需要一个occur记录最大值出现的个数。
每次如果遇到一个没有当前maxValue大的数字，无视之。
如果遇到一个比当前maxValue大的数字，当然要更新maxValue. 而且也可以放心地更新
maxIndex，因为目前最大值是第一次出现。 occur也reset到1.
问题关键在于出现跟maxValue一样大的数字如何操作。就需要random地替换一个。先更
新orrcur让orrcur++
然后出个随机数使得当前的这个index有1/occur的概率被采用即可。
随机数可以就用C里面的 (rand()%occur + 1)这个范围就是[1, occur]而且可以
assume是等概率。
如果这个随机数==1， 那么就把当前的maxIndex更新，不然就do nothing.
数学证明应该可以用数学归纳法，这里只推前三个。
假设最大值出现的index是i1, i2, i3
P(maxIndex == i1) = 1 * (1-1/2) *(1-1/... 阅读全帖 |
|
b***S
发帖数: 29 | 40 来自主题: JobHunting版 - 谈G家面经 我也觉得扫一次足矣 |
|
f***s
发帖数: 112 | 41 有从1开始的连续整数乱序数组，例如1到100，其中有k个缺失了，k已知。
如何用最快最少占用内存找到这k个整数。
提示，考虑二进制 1到100数字可以用 2的7次方表示。
时间复杂度很好证明需要全扫0(n),空间复杂度如何能到0(1)？ |
|
f***s
发帖数: 112 | 42 我能想到的就是因为每一个数字都至少有一个1，所以可以统计每一位1的缺失情况
譬如如果0000000 这七个位末尾（表示十进制0-1）缺少 m个1， 那么就是说有这k个缺
失的数字有m个mod 2 等于 1
极端简单情况是每个却是数字都只有一个 1， 那么扫一遍就知道是什么数字了，如果
有些数字不止一个1，那么看看能不能建立一些方程？ |
|
m*****n
发帖数: 2152 | 43 很简单啊，
第一遍算每个区间的连续0或者1的长度，
比如[1 0 1]，就是[1 1 1]
[1 1 0 1 0 0] 就是[2 1 1 2]
然后，第二遍扫看看[x 1 y]这个pattern的最大的和x+1+y是多少。
对不符合这种pattern的情况，就是最大的串的长度+1 或者是 最大的串的长度（这儿
有个问
题，如果全0或者全1，必须改吗？）。
其实实际编程，只要一遍就行了，用个 3 elements的moving window，有点DP的意思。
0 |
|
r*******k
发帖数: 1423 | 44 嗯
看来应该就是从头扫到尾
记录当前是奇数引号还是偶数引号
如果是奇数，就不care comma
否则遇到comma输出|
记录第一个引号的位置和上一个引号的位置，
遇到comma时，不要输出这两个引号
然后也没啥了
不过代码能不能写出来，而且一次过，还是很不好说的 |
|
m******3
发帖数: 346 | 45 应该不用这么麻烦吧，两个变量，记录word1 和 word 2最近出现的位置，然后每次计
算当前的距离，如果这个距离小于当前已知的最小距离，就更新最小距离，O(n)扫一遍
就行 |
|
m******3
发帖数: 346 | 46 应该不用这么麻烦吧，两个变量，记录word1 和 word 2最近出现的位置，然后每次计
算当前的距离，如果这个距离小于当前已知的最小距离，就更新最小距离，O(n)扫一遍
就行 |
|
l*********u
发帖数: 19053 | 47 来自主题: JobHunting版 - T面经一题 先搞成ax+b=cx+d，再扫一遍，算a,b,c,d。先括号，再*/，再+- |
|
l*********u
发帖数: 19053 | 48 来自主题: JobHunting版 - T面经一题 先搞成ax+b=cx+d，再扫一遍，算a,b,c,d。先括号，再*/，再+- |
|
h**********w
发帖数: 39 | 49 第一个是 match 0 - n个*前的字符 所以应该是regex
第二个brute force 扫就行，考点是offline build index 支持快速search |
|
m****v
发帖数: 780 | 50 用hadoop，map到小的interval，count, 找出哪个interval
再来一边，重复，直到最后足够小，单机扫 |
|
