m****u
发帖数: 3915 | 1 两个phone interview, 各45分钟
第一个人：
1 写一个返回所有n比特格雷码的函数
函数形式 vector getGrayCode(n)
比如 getGrayCode(2)， 应该返回{0,1,3,2}
2 如果一个lookup table很大，并且你有足够的内存装入这个table，但是为什么不把
这个
lookup table整个放到内存里？而是只把一部分放进去
说实话不是很明白，他的意思是cache的问题，如果把整个table放进去，可能产生更
多的cache
miss。。。
请达人解释一下这道题
3 平面上有n个点，找一条直线，使它穿过最多的点
第二个人：
1 两个sorted array A，B， 问能否从A，B中各取且只取一个数，是他们的和为x
2 有list of strings， 要求首先encode到一个string，然后再decode，恢复这些
strings，如何encode和decode
3 寻找majority element， 既从一个长度为n的数组中找出一个数，这个数的出现次数
严格大于
n/2 |
f****g
发帖数: 313 | 2 第一个人：
1 写一个返回所有n比特格雷码的函数
函数形式 vector getGrayCode(n)
比如 getGrayCode(2)， 应该返回{0,1,3,2}
2 如果一个lookup table很大，并且你有足够的内存装入这个table，但是为什么不把
这个
lookup table整个放到内存里？而是只把一部分放进去
说实话不是很明白，他的意思是cache的问题，如果把整个table放进去，可能产生更
多的cache
miss。。。
请达人解释一下这道题
3 平面上有n个点，找一条直线，使它穿过最多的点
O(n^2logn)
第二个人： |
h**k
发帖数: 3368 | 3 你代码有个常见bug，自己找找吧。
【在 f****g 的大作中提到】
: 第一个人：
: 1 写一个返回所有n比特格雷码的函数
: 函数形式 vector getGrayCode(n)
: 比如 getGrayCode(2)， 应该返回{0,1,3,2}
: 2 如果一个lookup table很大，并且你有足够的内存装入这个table，但是为什么不把
: 这个
: lookup table整个放到内存里？而是只把一部分放进去
: 说实话不是很明白，他的意思是cache的问题，如果把整个table放进去，可能产生更
: 多的cache
: miss。。。
|
f****g
发帖数: 313 | 4 谢谢， 是 ＆ 而非 bit operation &&,haha
【在 h**k 的大作中提到】
: 你代码有个常见bug，自己找找吧。
|
h**k
发帖数: 3368 | 5 ? bit operator 是 &，逻辑与是 &&，这个你没错啊
循环终止条件错了。
【在 f****g 的大作中提到】
: 谢谢， 是 ＆ 而非 bit operation &&,haha
|
f****g
发帖数: 313 | 6 Got it :-) Thanks! should be hi >0, what a stupid mistake
【在 h**k 的大作中提到】
: ? bit operator 是 &，逻辑与是 &&，这个你没错啊
: 循环终止条件错了。
|
p******n
发帖数: 32 | 7 第二个人 第3题
既然严格大于n/2，那么只要用selection sort找第n/2个元素，这个元素就是要找的
元素。
time complexity O(n) |
m****u
发帖数: 3915 | 8
这个怎么会是O(n)
【在 p******n 的大作中提到】
: 第二个人 第3题
: 既然严格大于n/2，那么只要用selection sort找第n/2个元素，这个元素就是要找的
: 元素。
: time complexity O(n)
|
m****u
发帖数: 3915 | 9 第一个人第二题你有什么想法？
【在 f****g 的大作中提到】
: 第一个人：
: 1 写一个返回所有n比特格雷码的函数
: 函数形式 vector getGrayCode(n)
: 比如 getGrayCode(2)， 应该返回{0,1,3,2}
: 2 如果一个lookup table很大，并且你有足够的内存装入这个table，但是为什么不把
: 这个
: lookup table整个放到内存里？而是只把一部分放进去
: 说实话不是很明白，他的意思是cache的问题，如果把整个table放进去，可能产生更
: 多的cache
: miss。。。
|
x******3
发帖数: 245 | 10 count = 1;
major = nil;
for a in A[1:n]
if (a != majorl)
count--;
if (count == 0)
major = a;
count++;
return major
【在 m****u 的大作中提到】
: 第一个人第二题你有什么想法？
|
|
|
m****u
发帖数: 3915 | 11 我说的selection sort不是O(n)...
这个算法当然是O(n)
【在 x******3 的大作中提到】
: count = 1;
: major = nil;
: for a in A[1:n]
: if (a != majorl)
: count--;
: if (count == 0)
: major = a;
: count++;
:
: return major
|
l*******y
发帖数: 1498 | 12 第一个人第二题目，我觉得主要不是cache miss吧，整个放进内存和部分放进内存的
cache miss是一样的吧？ 都是访问的entry在cache里没有就会产生miss。
我觉得是把整个table放进内存，会影响别的程序，产生更多的page fault，page swap
in/out 的 overhead更大。
【在 m****u 的大作中提到】
: 两个phone interview, 各45分钟
: 第一个人：
: 1 写一个返回所有n比特格雷码的函数
: 函数形式 vector getGrayCode(n)
: 比如 getGrayCode(2)， 应该返回{0,1,3,2}
: 2 如果一个lookup table很大，并且你有足够的内存装入这个table，但是为什么不把
: 这个
: lookup table整个放到内存里？而是只把一部分放进去
: 说实话不是很明白，他的意思是cache的问题，如果把整个table放进去，可能产生更
: 多的cache
|
m****u
发帖数: 3915 | 13 我提了这个问题
他说你可以假设内存是无限大的，也就是不会影响其他程序。。。
所以他给的答案让我非常confused
swap
【在 l*******y 的大作中提到】
: 第一个人第二题目，我觉得主要不是cache miss吧，整个放进内存和部分放进内存的
: cache miss是一样的吧？ 都是访问的entry在cache里没有就会产生miss。
: 我觉得是把整个table放进内存，会影响别的程序，产生更多的page fault，page swap
: in/out 的 overhead更大。
|
p********7
发帖数: 549 | |
l*******y
发帖数: 1498 | 15 内存无限大的话应该是全放内存比较好吧？
【在 m****u 的大作中提到】
: 我提了这个问题
: 他说你可以假设内存是无限大的，也就是不会影响其他程序。。。
: 所以他给的答案让我非常confused
:
: swap
|
s***n
发帖数: 373 | 16
第一个人：
1 写一个返回所有n比特格雷码的函数
函数形式 vector getGrayCode(n)
比如 getGrayCode(2)， 应该返回{0,1,3,2}
2 如果一个lookup table很大，并且你有足够的内存装入这个table，但是为什么不把
这个
lookup table整个放到内存里？而是只把一部分放进去
说实话不是很明白，他的意思是cache的问题，如果把整个table放进去，可能产生更
多的cache
miss。。。
请达人解释一下这道题
3 平面上有n个点，找一条直线，使它穿过最多的点
O(n^2logn)
第二个人：
【在 f****g 的大作中提到】
: 第一个人：
: 1 写一个返回所有n比特格雷码的函数
: 函数形式 vector getGrayCode(n)
: 比如 getGrayCode(2)， 应该返回{0,1,3,2}
: 2 如果一个lookup table很大，并且你有足够的内存装入这个table，但是为什么不把
: 这个
: lookup table整个放到内存里？而是只把一部分放进去
: 说实话不是很明白，他的意思是cache的问题，如果把整个table放进去，可能产生更
: 多的cache
: miss。。。
|
p********7
发帖数: 549 | 17 这个算法确实是对的。证明应该和young table查找一个数的证明类似，没看过怎么证
明的。
【在 s***n 的大作中提到】
:
: 第一个人：
: 1 写一个返回所有n比特格雷码的函数
: 函数形式 vector getGrayCode(n)
: 比如 getGrayCode(2)， 应该返回{0,1,3,2}
: 2 如果一个lookup table很大，并且你有足够的内存装入这个table，但是为什么不把
: 这个
: lookup table整个放到内存里？而是只把一部分放进去
: 说实话不是很明白，他的意思是cache的问题，如果把整个table放进去，可能产生更
: 多的cache
|
p********7
发帖数: 549 | 18 第三个题，考官要求的复杂度是多少？想了半天觉得还是N^3
【在 m****u 的大作中提到】
: 两个phone interview, 各45分钟
: 第一个人：
: 1 写一个返回所有n比特格雷码的函数
: 函数形式 vector getGrayCode(n)
: 比如 getGrayCode(2)， 应该返回{0,1,3,2}
: 2 如果一个lookup table很大，并且你有足够的内存装入这个table，但是为什么不把
: 这个
: lookup table整个放到内存里？而是只把一部分放进去
: 说实话不是很明白，他的意思是cache的问题，如果把整个table放进去，可能产生更
: 多的cache
|
m****u
发帖数: 3915 | 19 是啊，NND 一个intern考这么难得题
【在 p********7 的大作中提到】
: 我觉得题目难度和fulltime没什么区别啊
|
m****u
发帖数: 3915 | 20 有N^2的解法，用hashtable
【在 p********7 的大作中提到】
: 第三个题，考官要求的复杂度是多少？想了半天觉得还是N^3
|
|
|
f****g
发帖数: 313 | 21 我觉得这题可能是那种完全开放的题目。
比如我面试的他们问我：
什么时候有Ｏ（ｎｌｏｇｎ）的算法不用，反而用n^2的呢？
给出越多的答案越好
【在 m****u 的大作中提到】
: 我提了这个问题
: 他说你可以假设内存是无限大的，也就是不会影响其他程序。。。
: 所以他给的答案让我非常confused
:
: swap
|
s***n
发帖数: 373 | 22 什么叫young table？ 搜了一下搜不出来，给个提示？
【在 p********7 的大作中提到】
: 这个算法确实是对的。证明应该和young table查找一个数的证明类似，没看过怎么证
: 明的。
|
f****g
发帖数: 313 | 23 My algorithm for this question is:
Assume there is a set of points on the plane S = {P0, P1,..., Pn-1}
maxNumOfPoint = 0
for(i = 0; i < n; i ++)
{
for( j = 0; j < n; j ++)
{
if(i == j)
{
slope Ki = 0;
}
else
{
Calculate the slope between Pi and Pj: Kj = (Yj-Yi)/Xj-Xi;
}
}
qSort(K0,...,Kn-1);
Find all the points with the same slope M;
if( M > maxNumOfPoint)
{
maxNumOfPoint = M;
【在 m****u 的大作中提到】
: 有N^2的解法，用hashtable
|
f****g
发帖数: 313 | 24 What's the point for this question?
2 有list of strings， 要求首先encode到一个string，然后再decode，恢复这些
strings，如何encode和decode |
f****g
发帖数: 313 | 25 I understand how to compute the Graycode, but don;t quite understand the
getGrayCode means? Could you show more examples, thanks!
1 写一个返回所有n比特格雷码的函数
函数形式 vector getGrayCode(n)
比如 getGrayCode(2)， 应该返回{0,1,3,2} |
p********7
发帖数: 549 | 26 我知道算法了，用斜率以及与x轴的交点位置为关键词，代表了不同的直线
struct line
{
float slope;
float length;
};
用一个
map mp;
map::iterator it;
for(i=0;i
for(j=0;j
{
line thisline;
calculate the slope and the x pos of the cross point;
if(it=mp.find(thisline))
{
int pointnum = it->second+1;
mp.erase(it)
mp.insert(pair(thisline,pointnum));
}
else
mp.insert(pair(thisline,2));
}
}
【在 m****u 的大作中提到】
: 有N^2的解法，用hashtable
|
h**k
发帖数: 3368 | 27 用hash table只记录斜率不行，在worst case下，可能有O(n)的直线斜率是一样的，你
需要至少O(n)来判断这些直线是不是一条之间。
直接用hash table记录直线方程的两个参数。
【在 f****g 的大作中提到】
: My algorithm for this question is:
: Assume there is a set of points on the plane S = {P0, P1,..., Pn-1}
: maxNumOfPoint = 0
: for(i = 0; i < n; i ++)
: {
: for( j = 0; j < n; j ++)
: {
: if(i == j)
: {
: slope Ki = 0;
|
h**k
发帖数: 3368 | 28 C++中的map使用BST来实现的，所以查询、插入都是O(logn)。你需要使用hash_map。
【在 p********7 的大作中提到】
: 我知道算法了，用斜率以及与x轴的交点位置为关键词，代表了不同的直线
: struct line
: {
: float slope;
: float length;
: };
: 用一个
: map mp;
: map::iterator it;
: for(i=0;i
|
h**k
发帖数: 3368 | 29 证明的简单思路是：Because a and b are sorted,
if a[lo] + b[hi] > SUM
then a[i] + b[hi] > SUM for all i > lo, i.e., there is no pair including b[
hi] with sum of SUM. So we can discard b[hi].
Similarly,
if a[lo] + b[hi] < SUM
then a[lo] + b[i] < SUM for all i < hi.
【在 s***n 的大作中提到】
: 什么叫young table？ 搜了一下搜不出来，给个提示？
|
f****g
发帖数: 313 | 30 Hey hock,
Assume we represent a line as y = ax + b; I compute the slope between one
point pi, and all other points in the rest. Since slope and a point Pi(xi,
yi)
can determine a line, only recording the slope should work.
I might miss something? Can I give me a more specific example?
Thanks!
【在 h**k 的大作中提到】
: 用hash table只记录斜率不行，在worst case下，可能有O(n)的直线斜率是一样的，你
: 需要至少O(n)来判断这些直线是不是一条之间。
: 直接用hash table记录直线方程的两个参数。
|
|
|
p********7
发帖数: 549 | 31 young tableau
【在 s***n 的大作中提到】
: 什么叫young table？ 搜了一下搜不出来，给个提示？
|
p********7
发帖数: 549 | 32 MAP 是nLogN，但是hash_map需要你提供hash function，很难提供一个没有collision的
这个题应该有个地方需要注意到是，我觉得应该使用分数去算slope，以及于x轴相交的点横坐标。
因为用float很难保证2个float是相同的，他们永远只是近似相同。
需要写个函数去判断2个分数是否相同。
【在 h**k 的大作中提到】
: C++中的map使用BST来实现的，所以查询、插入都是O(logn)。你需要使用hash_map。
|
A*H
发帖数: 127 | 33 two problems:
major should be initialized to a[0]
also count++ should not be applied to the first if
my code
int findMajority(int a[], int n) {
int m=a[0];
int count=1;
for (int i=1; i
if (a[i] == m)
count++;
else if (count == 0) {
m = a[i];
count = 1;
}
else
count--;
}
return m;
}
【在 x******3 的大作中提到】
: count = 1;
: major = nil;
: for a in A[1:n]
: if (a != majorl)
: count--;
: if (count == 0)
: major = a;
: count++;
:
: return major
|
m****u
发帖数: 3915 | 34 不考虑float精度问题
collision的
的点横坐标。
【在 p********7 的大作中提到】
: MAP 是nLogN，但是hash_map需要你提供hash function，很难提供一个没有collision的
: 这个题应该有个地方需要注意到是，我觉得应该使用分数去算slope，以及于x轴相交的点横坐标。
: 因为用float很难保证2个float是相同的，他们永远只是近似相同。
: 需要写个函数去判断2个分数是否相同。
|
k*******n
发帖数: 8891 | |
m****u
发帖数: 3915 | 36 getGrayCode(2)就是返回2bit的格雷码
也就是：{00, 01, 11, 10}
getGrayCode(3)就是
{000， 001， 011， 010, 110, 111, 101, 100}
【在 f****g 的大作中提到】
: I understand how to compute the Graycode, but don;t quite understand the
: getGrayCode means? Could you show more examples, thanks!
: 1 写一个返回所有n比特格雷码的函数
: 函数形式 vector getGrayCode(n)
: 比如 getGrayCode(2)， 应该返回{0,1,3,2}
|
f****g
发帖数: 313 | 37 谢谢！ 我能想到的办法就是直接一个一个的算，想知道的思路阿。
【在 m****u 的大作中提到】
: getGrayCode(2)就是返回2bit的格雷码
: 也就是：{00, 01, 11, 10}
: getGrayCode(3)就是
: {000， 001， 011， 010, 110, 111, 101, 100}
|
p********7
发帖数: 549 | 38 这道题根本就是在考grey码，和stl的用法。不懂grey怎么办？
【在 m****u 的大作中提到】
: getGrayCode(2)就是返回2bit的格雷码
: 也就是：{00, 01, 11, 10}
: getGrayCode(3)就是
: {000， 001， 011， 010, 110, 111, 101, 100}
|
p********7
发帖数: 549 | 39 000
001
011
010
110
111
101
100
其实就是找变化规律，用2进制列出来就看出来规律了吧。
bit[0] 除了开头是1个数就变，其他都是2个数变化1次
bit[1] 除了开头是2个数变，其他都是4个数变化1次
bit[i] 除了开头是2^i 个数变，其他都是2^(i+1)个数变一次
开头都是0
【在 f****g 的大作中提到】
: 谢谢！ 我能想到的办法就是直接一个一个的算，想知道的思路阿。
|
h**6
发帖数: 4160 | 40 很多年前，我大一学格雷码的时候，就发现这个规律了。 |
|
|
b*****n
发帖数: 221 | 41 这题听起来不难.string之间加个dummy seperator就行了.
【在 f****g 的大作中提到】
: What's the point for this question?
: 2 有list of strings， 要求首先encode到一个string，然后再decode，恢复这些
: strings，如何encode和decode
|
b*****n
发帖数: 221 | 42 能给个很简洁的代码吗?
【在 p********7 的大作中提到】
: 000
: 001
: 011
: 010
: 110
: 111
: 101
: 100
: 其实就是找变化规律，用2进制列出来就看出来规律了吧。
: bit[0] 除了开头是1个数就变，其他都是2个数变化1次
|
g*****7
发帖数: 111 | 43 1 写一个返回所有n比特格雷码的函数
函数形式 vector getGrayCode(n)
比如 getGrayCode(2)， 应该返回{0,1,3,2}
这题用recursive不就好了吗？
vector getGrayCode(int n)
{
if (n <= 0) return vector();
if (n == 1)
{
vector ret(2, 0);
ret[1] = 1;
return ret;
}
vector subcodes = getGrayCode(n-1);
size_t subsize = subcodes.size();
subcodes.resize(2*subsize);
for (size_t i = 0; i < subsize; ++i)
subcodes[i+subsize] = subcodes[subsize-1-i] | (1 << (n-1));
return subcodes;
} |
h**k
发帖数: 3368 | 44 嗯，你这么做可以。
【在 f****g 的大作中提到】
: Hey hock,
: Assume we represent a line as y = ax + b; I compute the slope between one
: point pi, and all other points in the rest. Since slope and a point Pi(xi,
: yi)
: can determine a line, only recording the slope should work.
: I might miss something? Can I give me a more specific example?
: Thanks!
|
y*********e
发帖数: 518 | 45 第一个人：
1 写一个返回所有n比特格雷码的函数
函数形式 vector getGrayCode(n)
比如 getGrayCode(2)， 应该返回{0,1,3,2}
===============================================
n bit 格雷码和 n bit 的 2 进制的整数是一样的，只是排列顺序不一样。所以，会有
2^n个格雷码。
格雷码同2进制数的转换关系是这样的：
二进制数 B = { b3 b2 b1 b0 }
格雷码数 G = { g3 g2 g1 g0 }
g3 = 0 XOR b3
g2 = b3 XOR b2
g1 = b2 XOR b1
g0 = b1 XOR b0
在2进制数前面补0，然后XOR每两个相邻的bit。举个例子，对于2进制数 11，前面补0
就成了011，然后 0 ^ 1 = 1, 1 ^ 1 = 0，转换成格雷码就是 10。
知道了这些，就可以开始写代码了。2进制转格雷码，C代码：
int binToGrayCode(int num, int n) {
int bitL = 0;
in |
