|
|---|
|
|
|
|
|
|
a********9
发帖数: 129 | 1 L:
问答题
Write-through cache vs write-back cache
what's memory mapped file
算法题，都是老题
1) 给一个nested的int array， 返回sum of int weight by its depth
2) 写一个支持removeRandom的hashtable
3) 一串字符串，返回有多少个substring符合某些pattern，这些pattern都是10char的
长度，所以逐个比较就可以了
4) tree lowest ancestor( tree node have parent pointer)
RF:
基本全是老印，一个比一个吊炸天
1) 给一个数字，可以删除k个digit，返回最小的结果
example num=42139,k=1 == > 2139
answers: 首先从左到右，如果左边的digit比右边的大，就删除左边的digit，如果删
除不够k个digit则把最后的几位删掉，不大好实现，最好把输入变成array再做，或者
java的string
2) 写一个数据结构支持,put,get,getRandom
BST postorder to a linkedlist
convert sorted arry to BST
3) hadoop任务进行到一半时候DFS name node挂了，如果记录state保证之后能继续任
务而不是重新开始(这题其实没大懂）
4) clone directed graph
5) design a log system to record structure/object，有点serialize + key-value
store filesystem 的感觉
leetcode Interleaving String
google面的是TSE, technical solution engineer
network trouble shooting，场景是客户说无法上网，让你如何一步步isolate
problem，很坑爹的题目
还有就是给一堆http的报文，问你发生了什么
考几个linux cmd，cat file | awk '{print $5}' | uniq | c*****e
发帖数: 67 | | b*********s
发帖数: 115 | 3 谢面经!
RF 第一题答的不对
比如说 num = 42319, k = 4, 按你的删法会得到2, 但最小应该是1
应该是扫描前k个digit，找到最小的一个，假设为第i个，那么就把前i- 1个digit删掉
，然后对从第i+1个digit开始到字符串末尾的substring递归，新的递归里面k要减掉i
- 1
下面是python实现：
def solve(s, k):
return deleteDigit(s, 0, len(s), k)
def deleteDigit(s, start, end, k):
if end - start <= k or k <= 0:
return ''
minDigit = 10
minPosition = -1
for i in range(start, start + k + 1):
d = ord(s[i]) - ord('0')
if 0 <= d <= 9:
if d < minDigit:
minDigit = d
minPosition = i
else:
raise Exception('illegal char: ' + s[i])
return s[minPosition] + deleteDigit(
s,
minPosition + 1,
end,
k - (minPosition - start)
)
| c*****e
发帖数: 67 | 4 +1. 我想的也是前i个找最小，然后递归。
i
【在 b*********s 的大作中提到】
: 谢面经!
: RF 第一题答的不对
: 比如说 num = 42319, k = 4, 按你的删法会得到2, 但最小应该是1
: 应该是扫描前k个digit，找到最小的一个，假设为第i个，那么就把前i- 1个digit删掉
: ，然后对从第i+1个digit开始到字符串末尾的substring递归，新的递归里面k要减掉i
: - 1
: 下面是python实现：
: def solve(s, k):
: return deleteDigit(s, 0, len(s), k)
: def deleteDigit(s, start, end, k):
| l****1
发帖数: 33 | 5 >1) 给一个数字，可以删除k个digit，返回最小的结果
>example num=42139,k=1 == > 2139
这个可以处理k次，每次删除1个digit吧
我用C语言string实现，删除的digit用特殊字符标记，不难实现，
尽量用递归，一次成功，:-) | l*********d
发帖数: 78 | 6 好像没有问题啊？
k = 4
42319 -> 2319 -> 219 -> 19 -> 1
i
【在 b*********s 的大作中提到】
: 谢面经!
: RF 第一题答的不对
: 比如说 num = 42319, k = 4, 按你的删法会得到2, 但最小应该是1
: 应该是扫描前k个digit，找到最小的一个，假设为第i个，那么就把前i- 1个digit删掉
: ，然后对从第i+1个digit开始到字符串末尾的substring递归，新的递归里面k要减掉i
: - 1
: 下面是python实现：
: def solve(s, k):
: return deleteDigit(s, 0, len(s), k)
: def deleteDigit(s, start, end, k):
| s**x
发帖数: 7506 | 7 1234567, k=1, should delete 7.
222223, k=1, should delete 3.
seems these cases not covered
i
【在 b*********s 的大作中提到】
: 谢面经!
: RF 第一题答的不对
: 比如说 num = 42319, k = 4, 按你的删法会得到2, 但最小应该是1
: 应该是扫描前k个digit，找到最小的一个，假设为第i个，那么就把前i- 1个digit删掉
: ，然后对从第i+1个digit开始到字符串末尾的substring递归，新的递归里面k要减掉i
: - 1
: 下面是python实现：
: def solve(s, k):
: return deleteDigit(s, 0, len(s), k)
: def deleteDigit(s, start, end, k):
| g*****g
发帖数: 212 | 8 RF1:
从左到右扫描：
记录当前最大，
1）如果当前值小于最大， 删除最大
2）如果便利到最后，删除最大
int deleteOne(char[] str, int n)
{
if (n == 0)
return 0;
int j= 0;
for(int i=1; i
{
if (str[i]
{
break;
}
else if (str[i] > str[j])
{
i = j;
}
}
for(int k=j; k
{
str[k] = str[k+1]
}
return n-1;
} | b*********s
发帖数: 115 | 9
第一个就是最大的情况下是不删的，直接往后递归。这两个case我的程序跑出来分别得
出123456和22222，是对的。
【在 s**x 的大作中提到】
: 1234567, k=1, should delete 7.
: 222223, k=1, should delete 3.
: seems these cases not covered
:
: i
| b*********s
发帖数: 115 | 10
按我理解的楼主的算法 ("如果删除不够k个digit则把最后的几位删掉") 是42319 ->
2319, 然后还差三个，就把最后三个删掉，得到2
【在 l*********d 的大作中提到】
: 好像没有问题啊？
: k = 4
: 42319 -> 2319 -> 219 -> 19 -> 1
:
: i
| | | r***e
发帖数: 29 | 11 应该是从左向右找第一个逆序，如42，31，去除逆序数。 如果无逆序，去最后一个数。
string removal(string value)
{
if(value.length()<2)
{
return value;
}
string vt;
unsigned int pos = 0;
for(; pos
{
if(value[pos]>value[pos+1])
{
break;
}
}
if(pos < value.length()-1)
{
vt = value.substr(0, pos)+value.substr(pos+1);
} else
{
vt = value.substr(0, pos);
}
return vt;
} | e*****i
发帖数: 182 | 12 3)就是修改使namenode和datanode id一致么？ | r***e
发帖数: 29 | | b***e
发帖数: 1419 | 14 你这个复杂性太高。O(n*k). This is actually a majia for classic sliding
window max/min in stream. Use de-que to get O(n).
i
【在 b*********s 的大作中提到】
: 谢面经!
: RF 第一题答的不对
: 比如说 num = 42319, k = 4, 按你的删法会得到2, 但最小应该是1
: 应该是扫描前k个digit，找到最小的一个，假设为第i个，那么就把前i- 1个digit删掉
: ，然后对从第i+1个digit开始到字符串末尾的substring递归，新的递归里面k要减掉i
: - 1
: 下面是python实现：
: def solve(s, k):
: return deleteDigit(s, 0, len(s), k)
: def deleteDigit(s, start, end, k):
| b*********s
发帖数: 115 | 15
You are right. deque is much better. Below is the implementation using deque
def solve2(s, k):
from collections import deque
d = deque(maxlen=k + 1)
n = len(s)
if n <= k:
return ''
for i in xrange(k + 1):
while d and ord(d[-1][1]) > ord(s[i]):
if s[i] == '0':
break
d.pop()
d.append((i, s[i]))
res = []
for i in xrange(k + 1, n):
res.append(d.popleft()[1])
while d and d[0][0] < i - k:
d.popleft()
while d and ord(d[-1][1]) > ord(s[i]):
d.pop()
d.append((i, s[i]))
res.append(d.popleft()[1])
return ''.join(res)
【在 b***e 的大作中提到】
: 你这个复杂性太高。O(n*k). This is actually a majia for classic sliding
: window max/min in stream. Use de-que to get O(n).
:
: i
| l***p
发帖数: 358 | 16 中间有0的情况，比如
10042319
#include
int main(int argc, char * argv[])
{
int num = atoi(argv[1]);
char s[] = "45002319";
printf("source: %s and num:%d", s, num);
size_t size;
while (num > 0 && (s && (size = strlen(s)) > 0))
{
if (size > 1)
{
if (s[0] > s[1])
{// 4[<4, 0]
size_t cz = 1;
char * n = s + 1;
while (*n != '\0' && *n++ == '0')
{ // 40
cz += 1;
}
strcpy(s, s+cz);
}
else
{ //34
strcpy(s+1, s+2);
}
}
else
{ // only one character, move forward
*s = '\0';
}
num--;
}
printf(", result:%s\n", s);
return 0;
}
你们考虑过如果这个数是negative情况,比如
-42319 | A*****o
发帖数: 284 | 17 中间含0的情况, 我觉得应该尽量删除0前面的元素...
发个自己写的:
void remove(vector & v, int i) {
vector::iterator it = v.begin() + i;
v.erase(it);
}
int delk(int a, int K) {
if (a <= 0 || K <= 0) return a;
vector v;
int t = a;
while (t) {
v.push_back(t%10);
t /= 10;
}
reverse(v.begin(), v.end());
int i;
int cnt = 0;
while (cnt < K) {
i = 0;
while (i+1 < v.size() && v[i] <= v[i+1]) i++;
remove(v, i);
cnt++;
}
int r = 0;
for (i = 0; i < v.size(); i++) {
r *= 10;
r += v[i];
}
return r;
}
void run() {
//int a = 42139;
//int k = 4;
int a = 10042319;
int k = 4;
cout << delk(a, k) << endl;
} | a********9
发帖数: 129 | 18 data infursture，至于第一题，答案是面试官很nice的告诉的我
国人大哥我对不起你，因为RF貌似没让我签那个什么ND
【在 c*****e 的大作中提到】
: 楼主RF面的是什么职位？
| J*****a
发帖数: 4262 | 19 楼主第一题的思路是对的，即“左向右扫描，若左边一位比右边一位大，则删除左边，
以此循环，如果最后还有删除名额，则删最后几位”。只是复杂度不是最优而已
你上来就说人家“不对”，欠考虑吧，况且你一开始给出的解复杂度不比楼主的低
这题根本不用deque，用个stack即可
而且0为什么不能放第一位？1023，k=1删除第一位即可，得到23，为最小，用以下方法
根本无需特殊处理
public int getSmallest(String input, int k){
if(input == null || k > input.length()) return null;
Stack s = new Stack();
for(int i = 0; i < input.length(); i++){
while(!s.isEmpty() && s.peek() > input.charAt(i) && k-- > 0) s.pop();
s.push(input.charAt(i));
}
while(k-- > 0) s.pop();
String rl = "";
while(!s.isEmpty()) rl = s.pop() + rl;
return Integer.parseInt(rl.length() == 0 ? "0" : rl);
}
【在 b*********s 的大作中提到】
: 谢面经!
: RF 第一题答的不对
: 比如说 num = 42319, k = 4, 按你的删法会得到2, 但最小应该是1
: 应该是扫描前k个digit，找到最小的一个，假设为第i个，那么就把前i- 1个digit删掉
: ，然后对从第i+1个digit开始到字符串末尾的substring递归，新的递归里面k要减掉i
: - 1
: 下面是python实现：
: def solve(s, k):
: return deleteDigit(s, 0, len(s), k)
: def deleteDigit(s, start, end, k):
| k*****o
发帖数: 43 | | b********r
发帖数: 620 | 21 if we apply LZ's algorithm, what happens to 45389, k = 3? should it be 45 or
38?
basically my question is that do we have to remove digits from ends only, or
digits in the middle can be removed as well.
【在 J*****a 的大作中提到】
: 楼主第一题的思路是对的，即“左向右扫描，若左边一位比右边一位大，则删除左边，
: 以此循环，如果最后还有删除名额，则删最后几位”。只是复杂度不是最优而已
: 你上来就说人家“不对”，欠考虑吧，况且你一开始给出的解复杂度不比楼主的低
: 这题根本不用deque，用个stack即可
: 而且0为什么不能放第一位？1023，k=1删除第一位即可，得到23，为最小，用以下方法
: 根本无需特殊处理
: public int getSmallest(String input, int k){
: if(input == null || k > input.length()) return null;
: Stack s = new Stack();
: for(int i = 0; i < input.length(); i++){
| J*****a
发帖数: 4262 | 22 你没看懂吧
楼主的算法是：
45389
第一个去掉5，因为5比3大
得到4389
第二个去掉4，因为4比3大
得到389
此时，没有数位比它的直接右邻居大了，但还剩一个名额，从尾巴去
得到38
or
or
【在 b********r 的大作中提到】
: if we apply LZ's algorithm, what happens to 45389, k = 3? should it be 45 or
: 38?
: basically my question is that do we have to remove digits from ends only, or
: digits in the middle can be removed as well.
|
|
|
|
|
|
|
|
