O*******d
发帖数: 20343 | 1 问了两个问题。30分钟时间。都是写code
1。写一段code，检测一串数字是否是Fabonacci系列。
2。给两个ascend排序的integer array，找出他们的union，并且descend排序。
都给写出来了。当然code没有优化，显得比较乱。考官问了几个怎样改进的问题。 从
此没有下文了。 两个星期了，连据信都没有。 |
p*****2
发帖数: 21240 | 2
白板就两道题，一个人？
【在 O*******d 的大作中提到】
: 问了两个问题。30分钟时间。都是写code
: 1。写一段code，检测一串数字是否是Fabonacci系列。
: 2。给两个ascend排序的integer array，找出他们的union，并且descend排序。
: 都给写出来了。当然code没有优化，显得比较乱。考官问了几个怎样改进的问题。 从
: 此没有下文了。 两个星期了，连据信都没有。
|
O*******d
发帖数: 20343 | 3 就是，两道题，对方只有一个人。
【在 p*****2 的大作中提到】
:
: 白板就两道题，一个人？
|
O*******d
发帖数: 20343 | 4 第二道题，估计考官也没有准备充足。 我写到半截，突然发现如果array的数字如果有
重复的，例如一个array有两个2，code就比较复杂，需要处理重复的数字。 他好像也
才明白。就说假设数字没有同样值的。 |
p*****2
发帖数: 21240 | 5
有重复的怕啥？
【在 O*******d 的大作中提到】
: 第二道题，估计考官也没有准备充足。 我写到半截，突然发现如果array的数字如果有
: 重复的，例如一个array有两个2，code就比较复杂，需要处理重复的数字。 他好像也
: 才明白。就说假设数字没有同样值的。
|
l*****a
发帖数: 14598 | 6 没有重复的不就是两个数组本身?
【在 O*******d 的大作中提到】
: 第二道题，估计考官也没有准备充足。 我写到半截，突然发现如果array的数字如果有
: 重复的，例如一个array有两个2，code就比较复杂，需要处理重复的数字。 他好像也
: 才明白。就说假设数字没有同样值的。
|
b***m
发帖数: 5987 | 7 这是初面？
【在 O*******d 的大作中提到】
: 就是，两道题，对方只有一个人。
|
O*******d
发帖数: 20343 | 8 初面。一直没有下文。
【在 b***m 的大作中提到】
: 这是初面？
|
O*******d
发帖数: 20343 | 9 两个array的数值范围可以重复。 但每个array的数字不能有重复。 例如12345就没有
重复数字，但122345就有重复数字。 所以ascend排序的array必须要说明这点。
【在 l*****a 的大作中提到】
: 没有重复的不就是两个数组本身?
|
O*******d
发帖数: 20343 | 10 有重复的，只能把重复数字提取一次。 我写的code复杂度是O（N），所以必须要有循
环来检查提取的数字是否跟前一个一样，如果一样，就要跳过去，直到数字不一样。
如果假设没有重复数字，这些麻烦都没有了。
【在 p*****2 的大作中提到】
:
: 有重复的怕啥？
|
|
|
p*****2
发帖数: 21240 | 11
这题不难。有重复的也很好处理。O(N)复杂度够了。数组不是本身是排号序的吗？
【在 O*******d 的大作中提到】
: 有重复的，只能把重复数字提取一次。 我写的code复杂度是O（N），所以必须要有循
: 环来检查提取的数字是否跟前一个一样，如果一样，就要跳过去，直到数字不一样。
: 如果假设没有重复数字，这些麻烦都没有了。
|
O*******d
发帖数: 20343 | 12 处理不难，就是加一个小循环。 但时间很紧。
【在 p*****2 的大作中提到】
:
: 这题不难。有重复的也很好处理。O(N)复杂度够了。数组不是本身是排号序的吗？
|
p*****2
发帖数: 21240 | 13
为什么要加循环？
【在 O*******d 的大作中提到】
: 处理不难，就是加一个小循环。 但时间很紧。
|
b***m
发帖数: 5987 | 14 A家就这一点最讨厌了，初面不合格就经常没消息，recruiter发封邮件会死啊。
【在 O*******d 的大作中提到】
: 初面。一直没有下文。
|
O*******d
发帖数: 20343 | 15 如果你用两个指针，或者两个index来走过两个array，每次提取数字时，要检查当前数
字是否跟前一个数字一样，如果一样，就要跳到下一个位置，再重复检查，一直到不一
样，或者到了尾端。
【在 p*****2 的大作中提到】
:
: 为什么要加循环？
|
O*******d
发帖数: 20343 | 16 如果没有重复数字，两个index在提取数字后，就直接跳到下一个数字了。 |
O*******d
发帖数: 20343 | 17 就冲着这点，我对A家的印象大大降低。
【在 b***m 的大作中提到】
: A家就这一点最讨厌了，初面不合格就经常没消息，recruiter发封邮件会死啊。
|
h****n
发帖数: 1093 | 18 不用额外加一个小循环，这个都可以直接在大循环里判断的
【在 O*******d 的大作中提到】
: 如果你用两个指针，或者两个index来走过两个array，每次提取数字时，要检查当前数
: 字是否跟前一个数字一样，如果一样，就要跳到下一个位置，再重复检查，一直到不一
: 样，或者到了尾端。
|
f*****e
发帖数: 2992 | 19 有重复的话union取个数大的。STL是这么干的。
【在 O*******d 的大作中提到】
: 两个array的数值范围可以重复。 但每个array的数字不能有重复。 例如12345就没有
: 重复数字，但122345就有重复数字。 所以ascend排序的array必须要说明这点。
|
h****n
发帖数: 1093 | 20 写写
第一题：
bool CheckFab(vector input)
{
int size = input.size();
int first = 0; second = 1, third;
int i;
if(size<1) return false;
if(size==1) return input[0]==1?true:false;
if(size>=2&&(input[0]!=0||input[1]!=1))
return false;
for(i=2;i
{
third = first+second;
if(third!=input[i]) return false;
first = second;
second = thrid;
}
return true;
}
第二题：
vector GetUnion(vector input1, vector input2)
{
int size1 = input1.size();
int size2 = input2.size();
int i,j;
vector res;
for(i=size1-1,j=size2-1;i>=0||j>=0;)
{
if(i>=0&&j>=0)
{
if(input1[i]>input2[j])
{
if(input1[i]!=res.back())
res.push_back(input1[i]);
i--;
}
else if(input1[i]
{
if(input2[j]!=res.back())
res.push_back(input2[j]);
j--;
}
else
{
if(input1[i]!=res.back())
res.push_back(input1[i]);
i--;
j--;
}
}
else if(i>=0)
{
if(input1[i]!=res.back())
res.push_back(input1[i]);
i--;
}
else
{
if(input2[j]!=res.back())
res.push_back(input2[j]);
j--;
}
}
return res;
}
【在 O*******d 的大作中提到】
: 问了两个问题。30分钟时间。都是写code
: 1。写一段code，检测一串数字是否是Fabonacci系列。
: 2。给两个ascend排序的integer array，找出他们的union，并且descend排序。
: 都给写出来了。当然code没有优化，显得比较乱。考官问了几个怎样改进的问题。 从
: 此没有下文了。 两个星期了，连据信都没有。
|
|
|
p*****2
发帖数: 21240 | 21
没错。你给LZ写一个吧。
【在 h****n 的大作中提到】
: 不用额外加一个小循环，这个都可以直接在大循环里判断的
|
d******i
发帖数: 76 | 22 写了个c++的code。
vector unionTwoArray(vector &a, vector &b)
{
int i = a.size() -1;
int j = b.size() -1;
vectorres;
while (i>=0 || j >= 0)
{
while (i >0 && a[i -1] == a[i])
--i;
while (j > 0 && b[j -1] == b[j])
--j;
int aV = i >= 0 ? a[i] : INT_MIN;
int bV = j >=0 ? b[j] : INT_MIN;
if(aV < bV)
res.push_back(bV), --j;
else if(aV > bV)
res.push_back(aV), --i;
else
{
res.push_back(aV);
--i;
--j;
}
}
return res;
} |
h****n
发帖数: 1093 | 23 额，我写的没你写的简洁
【在 d******i 的大作中提到】
: 写了个c++的code。
: vector unionTwoArray(vector &a, vector &b)
: {
: int i = a.size() -1;
: int j = b.size() -1;
: vectorres;
: while (i>=0 || j >= 0)
: {
: while (i >0 && a[i -1] == a[i])
: --i;
|
p*****2
发帖数: 21240 | 24 感觉都有点长。有没有test case？如果有的话，我写一个。 |
d******i
发帖数: 76 | 25
赶紧写，好跟你学学啊，呵呵
test case
1. {},{}
2. {1}, {};
3. {1,1}, {1}
4. {1, 2, 3, 4}, {5}
5. {1, 2, 3, 4, 4, 4,}, {4}
6. {1, 2, 3, 4, 4, 4}, {4, 4}
7. {1, 1, 2, 2, 3, 3}, {1, 2, 3, 4}
差不多了
【在 p*****2 的大作中提到】
: 感觉都有点长。有没有test case？如果有的话，我写一个。
|
p*****2
发帖数: 21240 | 26 我写了一个，看看对不对？
//assume A and B not null and length!=0
ArrayList getUnion(int[] A, int[] B)
{
ArrayList al=new ArrayList();
int i=A.length-1;
int j=B.length-1;
while(i>=0 && j>=0)
{
al.add(Math.max(A[i], B[j]));
while(i>=0 && A[i]==al.get(al.size()-1))
i--;
while(j>=0 && B[j]==al.get(al.size()-1))
j--;
}
while(i>=0)
{
if(A[i]!=al.get(al.size()-1))
al.add(A[i]);
i--;
}
while(j>=0)
{
if(B[j]!=al.get(al.size()-1))
al.add(B[j--]);
j--;
}
return al;
} |
h****n
发帖数: 1093 | 27 后面两个if 改成 while吧
【在 p*****2 的大作中提到】
: 我写了一个，看看对不对？
: //assume A and B not null and length!=0
: ArrayList getUnion(int[] A, int[] B)
: {
: ArrayList al=new ArrayList();
: int i=A.length-1;
: int j=B.length-1;
:
: while(i>=0 && j>=0)
: {
|
p*****2
发帖数: 21240 | 28
对。
【在 h****n 的大作中提到】
: 后面两个if 改成 while吧
|
d******i
发帖数: 76 | 29
有bug吧，第一次while结束后，如果剩下的里面有重复呢？
【在 p*****2 的大作中提到】
:
: 对。
|
h****n
发帖数: 1093 | 30 我也刚想说这个问题。。。
后面两个while里面也需要做这个重复判断
【在 d******i 的大作中提到】
:
: 有bug吧，第一次while结束后，如果剩下的里面有重复呢？
|
|
|
p*****2
发帖数: 21240 | 31
对。这个fix了之后代码就不简洁了。我看看怎么搞更好一点。
【在 d******i 的大作中提到】
:
: 有bug吧，第一次while结束后，如果剩下的里面有重复呢？
|
p*****2
发帖数: 21240 | 32 这个对不对呀？
//assume A and B not null
ArrayList getUnion(int[] A, int[] B)
{
ArrayList al=new ArrayList();
int i=A.length-1;
int j=B.length-1;
while(i>=0 || j>=0)
{
int max=Integer.MIN_VALUE;
if(i>=0) max=Math.max(max, A[i]);
if(j>=0) max=Math.max(max, B[j]);
al.add(max);
while(i>=0 && A[i]==max)
i--;
while(j>=0 && B[j]==max)
j--;
}
return al;
} |
d******i
发帖数: 76 | 33
NB,学习了
【在 p*****2 的大作中提到】
: 这个对不对呀？
: //assume A and B not null
: ArrayList getUnion(int[] A, int[] B)
: {
: ArrayList al=new ArrayList();
: int i=A.length-1;
: int j=B.length-1;
:
: while(i>=0 || j>=0)
: {
|
p*****2
发帖数: 21240 | 34
不好意思。这要是面试就挂了。第一个程序有大bug。所以我还是喜欢OJ，不然对自己
写的code没啥信心。
【在 d******i 的大作中提到】
:
: NB,学习了
|
b***m
发帖数: 5987 | 35
其实面试的时候，那么老长的代码，面试官也看不出来太大问题。我今天随便写了一个
，就把那漂亮女烙印面试官给糊弄过去了（当然她挑出了两个小bug）。
【在 p*****2 的大作中提到】
:
: 不好意思。这要是面试就挂了。第一个程序有大bug。所以我还是喜欢OJ，不然对自己
: 写的code没啥信心。
|
p*****2
发帖数: 21240 | 36
大牛说说现在微软什么组比较值得加入呢？
【在 b***m 的大作中提到】
:
: 其实面试的时候，那么老长的代码，面试官也看不出来太大问题。我今天随便写了一个
: ，就把那漂亮女烙印面试官给糊弄过去了（当然她挑出了两个小bug）。
|
b***m
发帖数: 5987 | 37
说实话，在我个人看来，所有组都差不多，都是打工而已，还是要想办法自己做点儿事
情。
【在 p*****2 的大作中提到】
:
: 大牛说说现在微软什么组比较值得加入呢？
|
h****n
发帖数: 1093 | 38 难道你不是在M？我咋一直有个印象你在M工作
【在 p*****2 的大作中提到】
:
: 大牛说说现在微软什么组比较值得加入呢？
|
b***m
发帖数: 5987 | 39 与其说选择哪个组，不如说跟对一个老板（包括老板的老板）、工作开心最重要。 |
p*****2
发帖数: 21240 | 40
错觉吧。呵呵。
【在 h****n 的大作中提到】
: 难道你不是在M？我咋一直有个印象你在M工作
|
|
|
p*****2
发帖数: 21240 | 41
好老板可遇而不可求呀。
【在 b***m 的大作中提到】
: 与其说选择哪个组，不如说跟对一个老板（包括老板的老板）、工作开心最重要。
|
h****n
发帖数: 1093 | 42 那这位大牛是在M工作么。。。怎么又去面M。。
【在 b***m 的大作中提到】
: 与其说选择哪个组，不如说跟对一个老板（包括老板的老板）、工作开心最重要。
|
p*****2
发帖数: 21240 | 43
面试能碰到美女多爽？
【在 h****n 的大作中提到】
: 那这位大牛是在M工作么。。。怎么又去面M。。
|
w******0
发帖数: 4472 | 44 电话面试？ 网络白板？
我也电话面试+网络白板了一次，2天后悲剧了。 ：）
初面。一直没有下文。
【在 O*******d 的大作中提到】
: 初面。一直没有下文。
|
p*****2
发帖数: 21240 | 45
什么题？
【在 w******0 的大作中提到】
: 电话面试？ 网络白板？
: 我也电话面试+网络白板了一次，2天后悲剧了。 ：）
:
: 初面。一直没有下文。
|
b***m
发帖数: 5987 | 46 我说过好多遍我现在在家待业被政府养着啊。
【在 h****n 的大作中提到】
: 那这位大牛是在M工作么。。。怎么又去面M。。
|
w******0
发帖数: 4472 | 47 1，实现STACK：使得MIN, PUSH, POP，都是CONSTANT TIME
2，找出整数数组里唯一一个只出现ODD TIME的数。
用任何语言都可以。
什么题？
【在 p*****2 的大作中提到】
:
: 什么题？
|
d**********x
发帖数: 4083 | 48 这。。
他们的题已经简单成这样了么？
【在 w******0 的大作中提到】
: 1，实现STACK：使得MIN, PUSH, POP，都是CONSTANT TIME
: 2，找出整数数组里唯一一个只出现ODD TIME的数。
: 用任何语言都可以。
:
: 什么题？
|
h****n
发帖数: 1093 | 49 试试4 1 5 6 11 17 28...
intverify_fib1(int *arr, int len){
★ Sent from iPhone App: iReader Mitbbs Lite 7.56 |
p*****2
发帖数: 21240 | 50 第一题一定是排好序的吧？有没有可能是没有排序的？ |
|
|
p*****2
发帖数: 21240 | 51
其实这两题挺经典的。Leetcode应该加到OJ里边去。
【在 w******0 的大作中提到】
: 1，实现STACK：使得MIN, PUSH, POP，都是CONSTANT TIME
: 2，找出整数数组里唯一一个只出现ODD TIME的数。
: 用任何语言都可以。
:
: 什么题？
|
Q*******e
发帖数: 939 | 52 没有排序的先排序或者用哈稀吧
【在 p*****2 的大作中提到】
: 第一题一定是排好序的吧？有没有可能是没有排序的？
|
h****n
发帖数: 1093 | 53 其实我觉的fib是从0开始的
intverify_fib1(int *arr, int len){
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 Q*******e 的大作中提到】
: 没有排序的先排序或者用哈稀吧
|
p*****2
发帖数: 21240 | 54
我主要想知道面试的时候是怎么要求的。或者会不会扩展到没有排序的情况。
【在 Q*******e 的大作中提到】
: 没有排序的先排序或者用哈稀吧
|
h****n
发帖数: 1093 | 55 hash最多帮你去除重复 最后还得排序还不如一开始就排序
没有排序的先排序或者用哈稀吧
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 Q*******e 的大作中提到】
: 没有排序的先排序或者用哈稀吧
|
Q*******e
发帖数: 939 | 56 排序需要至少nlogn吧
hash一遍, 然后检查是否每个hash项为1
【在 h****n 的大作中提到】
: hash最多帮你去除重复 最后还得排序还不如一开始就排序
:
: 没有排序的先排序或者用哈稀吧
: ★ Sent from iPhone App: iReader Mitbbs Lite 7.56
|
h****n
发帖数: 1093 | 57 那题目要求的结果降序输出怎么搞 如果原数组无序 光用hash的话
排序需要至少nlogn吧hash一遍, 然后检查是否每个hash项为1
★ Sent from iPhone App: iReader Mitbbs Lite 7.56
【在 Q*******e 的大作中提到】
: 排序需要至少nlogn吧
: hash一遍, 然后检查是否每个hash项为1
|
d******i
发帖数: 76 | 58
找到唯一一个出现odd time的数，只需要异或所有的数就行了吧，
int findOdd(int * arr, int len)
{
if(len == 0) return INT_MAX;
int odd = 0;
for(int i = 0; i < len; ++i)
{
odd ^= arr[i];
}
return odd;
}
【在 Q*******e 的大作中提到】
: 排序需要至少nlogn吧
: hash一遍, 然后检查是否每个hash项为1
|
h****n
发帖数: 1093 | 59 没错
【在 d******i 的大作中提到】
:
: 找到唯一一个出现odd time的数，只需要异或所有的数就行了吧，
: int findOdd(int * arr, int len)
: {
: if(len == 0) return INT_MAX;
: int odd = 0;
: for(int i = 0; i < len; ++i)
: {
: odd ^= arr[i];
: }
|
Q*******e
发帖数: 939 | 60 How about sequenct
0 1 1 2 2 3 3
【在 h****n 的大作中提到】
: 没错
|
|
|
h****n
发帖数: 1093 | 61 然后返回0，呵呵，没错
【在 Q*******e 的大作中提到】
: How about sequenct
: 0 1 1 2 2 3 3
|
Q*******e
发帖数: 939 | 62 0 0 1 1 2 2 3 3
【在 h****n 的大作中提到】
: 然后返回0，呵呵，没错
|
h****n
发帖数: 1093 | 63 题目要求要有唯一一个出现ODD次数的数。。。。。
【在 Q*******e 的大作中提到】
: 0 0 1 1 2 2 3 3
|
l*********8
发帖数: 4642 | 64 我也写一个第二题，还没测呢。
void GetReversedSortedUnion(vector a, vector b, vector &
merged)
{
for (int i=a.size()-1, j=b.size()-1; i>=0 || j>=0; ) {
if (j < 0 || a[i] < b[j])
merged.push_back(a[i--]);
else
merged.push_back(b[j--]);
int n = merged.size();
if (n >= 2 && merged[n-1] == merged[n-2])
merged.pop_back();
}
}
【在 O*******d 的大作中提到】
: 问了两个问题。30分钟时间。都是写code
: 1。写一段code，检测一串数字是否是Fabonacci系列。
: 2。给两个ascend排序的integer array，找出他们的union，并且descend排序。
: 都给写出来了。当然code没有优化，显得比较乱。考官问了几个怎样改进的问题。 从
: 此没有下文了。 两个星期了，连据信都没有。
|
c******t
发帖数: 391 | 65 请教第一题检测Fibonacci数列，题目是要求数列都是从1开始么？比如3,5,8,13这个算
么？ |
O*******d
发帖数: 20343 | |
