求推荐100-150左右的显卡 - 未名空间MITBBS历史存档

国际科技财经博客移民网络热点娱乐民生时事公众号

Redian新闻

>未名空间

>Hardware - 计算机硬件

求推荐100-150左右的显卡

求推荐100-150左右的显卡# Hardware - 计算机硬件

m*u2012-10-18 07:10

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

i*e2012-10-18 07:10

2 楼

http://changba.com/s/HBqRtIOfXBh5Om8YSwJLEA?code=Gt1bjDM0qnF-9Z

s*h2012-10-18 07:10

3 楼

显卡型号太多了，实在不太清楚哪一款比较好
要求安静，节能，稳定，性能的话能流畅Dota2，D3,LOL就可以了，对FPS没有爱
打算从现在到Thanks Giving期间开始留意

f*g2012-10-18 07:10

4 楼

第一个人：
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*o2012-10-18 07:10

5 楼

您起码能唱上去啊
有多少人根本唱不上去，那个心像海的心。。
不错啦

i*a2012-10-18 07:10

6 楼

ATI 68x0

【在 s*******h 的大作中提到】

: 显卡型号太多了，实在不太清楚哪一款比较好
: 要求安静，节能，稳定，性能的话能流畅Dota2，D3,LOL就可以了，对FPS没有爱
: 打算从现在到Thanks Giving期间开始留意

h*k2012-10-18 07:10

7 楼

你代码有个常见bug，自己找找吧。

【在 f****g 的大作中提到】

: 第一个人：
: 1 写一个返回所有n比特格雷码的函数
: 函数形式 vector getGrayCode(n)
: 比如 getGrayCode(2)，应该返回{0,1,3,2}
: 2 如果一个lookup table很大，并且你有足够的内存装入这个table，但是为什么不把
: 这个
: lookup table整个放到内存里？而是只把一部分放进去
: 说实话不是很明白，他的意思是cache的问题，如果把整个table放进去，可能产生更
: 多的cache
: miss。。。

i*e2012-10-18 07:10

8 楼

可是太难听了。。

b*22012-10-18 07:10

9 楼

150可以买到7850

f*g2012-10-18 07:10

10 楼

谢谢，　是　＆　而非　bit operation &&,haha

【在 h**k 的大作中提到】

: 你代码有个常见bug，自己找找吧。

z*n2012-10-18 07:10

11 楼

难听吗？我咋觉得唱功不错，唱得也挺棒呢，看来我是无可救药了，求指点我一下唱成
这么难听就好了，哈哈。。。

【在 i*****e 的大作中提到】

: 可是太难听了。。

a*t2012-10-18 07:10

12 楼

前几天142的7850不知道还在不在

【在 s*******h 的大作中提到】

h*k2012-10-18 07:10

13 楼

? bit operator 是 &，逻辑与是 &&，这个你没错啊
循环终止条件错了。

【在 f****g 的大作中提到】

: 谢谢，　是　＆　而非　bit operation &&,haha

q*x2012-10-18 07:10

14 楼

呵呵，我被骗了。。。
mm明明声音非常棒，味道也很足，听着好专业。
mm对自己要求太高啦。
呼唤完整版~

s*h2012-10-18 07:10

15 楼

刚看了一下，那个已经过期了
对了，这种东西是在感恩节当天买好，还是那个什么Cyber Monday好？

f*g2012-10-18 07:10

16 楼

Got it :-) Thanks! should be hi >0, what a stupid mistake

【在 h**k 的大作中提到】

: ? bit operator 是 &，逻辑与是 &&，这个你没错啊
: 循环终止条件错了。

i*e2012-10-18 07:10

17 楼

我现在就是看各种比赛有好听的就录一下，可惜没有一首能唱道完全让自己满意，所以
就唱一半玩玩了。。
而且好多本来也不熟懒得学后半段了

j*o2012-10-18 07:10

18 楼

搭车关注~~

p*n2012-10-18 07:10

19 楼

第二个人第3题
既然严格大于n/2，那么只要用selection sort找第n/2个元素，这个元素就是要找的
元素。
time complexity O(n)

d*o2012-10-18 07:10

20 楼

我可以教你，不过这个是要花时间练的哦。。。你人在哪？

【在 i*****e 的大作中提到】

: http://changba.com/s/HBqRtIOfXBh5Om8YSwJLEA?code=Gt1bjDM0qnF-9Z

n*y2012-10-18 07:10

21 楼

2nd

【在 b*****2 的大作中提到】

: 150可以买到7850

m*u2012-10-18 07:10

22 楼

这个怎么会是O(n)

【在 p******n 的大作中提到】

: 第二个人第3题
: 既然严格大于n/2，那么只要用selection sort找第n/2个元素，这个元素就是要找的
: 元素。
: time complexity O(n)

i*e2012-10-18 07:10

23 楼

波士顿，能用微信教吗。。

m*u2012-10-18 07:10

24 楼

第一个人第二题你有什么想法？

【在 f****g 的大作中提到】

d*o2012-10-18 07:10

25 楼

可以试试。。。不过微信的音质有点差，不知道效果怎样。。。你把你微信号发给我吧
～

x*32012-10-18 07:10

26 楼

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*u2012-10-18 07:10

27 楼

我说的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*y2012-10-18 07:10

28 楼

第一个人第二题目，我觉得主要不是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*u2012-10-18 07:10

29 楼

我提了这个问题
他说你可以假设内存是无限大的，也就是不会影响其他程序。。。
所以他给的答案让我非常confused

swap

【在 l*******y 的大作中提到】

: 第一个人第二题目，我觉得主要不是cache miss吧，整个放进内存和部分放进内存的
: cache miss是一样的吧？都是访问的entry在cache里没有就会产生miss。
: 我觉得是把整个table放进内存，会影响别的程序，产生更多的page fault，page swap
: in/out 的 overhead更大。

p*72012-10-18 07:10

30 楼

我觉得题目难度和fulltime没什么区别啊

l*y2012-10-18 07:10

31 楼

内存无限大的话应该是全放内存比较好吧？

【在 m****u 的大作中提到】

: 我提了这个问题
: 他说你可以假设内存是无限大的，也就是不会影响其他程序。。。
: 所以他给的答案让我非常confused
:
: swap

s*n2012-10-18 07:10

32 楼

p*72012-10-18 07:10

33 楼

这个算法确实是对的。证明应该和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*72012-10-18 07:10

34 楼

第三个题，考官要求的复杂度是多少？想了半天觉得还是N^3

【在 m****u 的大作中提到】

m*u2012-10-18 07:10

35 楼

是啊，NND 一个intern考这么难得题

【在 p********7 的大作中提到】

: 我觉得题目难度和fulltime没什么区别啊

m*u2012-10-18 07:10

36 楼

有N^2的解法，用hashtable

【在 p********7 的大作中提到】

: 第三个题，考官要求的复杂度是多少？想了半天觉得还是N^3

f*g2012-10-18 07:10

37 楼

我觉得这题可能是那种完全开放的题目。
比如我面试的他们问我：
什么时候有Ｏ（ｎｌｏｇｎ）的算法不用，反而用n^2的呢？
给出越多的答案越好

【在 m****u 的大作中提到】

: 我提了这个问题
: 他说你可以假设内存是无限大的，也就是不会影响其他程序。。。
: 所以他给的答案让我非常confused
:
: swap

s*n2012-10-18 07:10

38 楼

什么叫young table？搜了一下搜不出来，给个提示？

【在 p********7 的大作中提到】

: 这个算法确实是对的。证明应该和young table查找一个数的证明类似，没看过怎么证
: 明的。

f*g2012-10-18 07:10

39 楼

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*g2012-10-18 07:10

40 楼

What's the point for this question?
2 有list of strings，要求首先encode到一个string，然后再decode，恢复这些
strings，如何encode和decode

f*g2012-10-18 07:10

41 楼

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*72012-10-18 07:10

42 楼

我知道算法了，用斜率以及与x轴的交点位置为关键词，代表了不同的直线
struct line
{
float slope;
float length;
};
用一个
map mp;
map::iterator it;
for(i=0;ifor(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*k2012-10-18 07:10

43 楼

用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*k2012-10-18 07:10

44 楼

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*k2012-10-18 07:10

45 楼

证明的简单思路是：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*g2012-10-18 07:10

46 楼

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*72012-10-18 07:10

47 楼

young tableau

【在 s***n 的大作中提到】

: 什么叫young table？搜了一下搜不出来，给个提示？

p*72012-10-18 07:10

48 楼

MAP 是nLogN，但是hash_map需要你提供hash function，很难提供一个没有collision的
这个题应该有个地方需要注意到是，我觉得应该使用分数去算slope，以及于x轴相交的点横坐标。
因为用float很难保证2个float是相同的，他们永远只是近似相同。
需要写个函数去判断2个分数是否相同。

【在 h**k 的大作中提到】

: C++中的map使用BST来实现的，所以查询、插入都是O(logn)。你需要使用hash_map。

A*H2012-10-18 07:10

49 楼

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; iif (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*u2012-10-18 07:10

50 楼

不考虑float精度问题

collision的
的点横坐标。

【在 p********7 的大作中提到】

: MAP 是nLogN，但是hash_map需要你提供hash function，很难提供一个没有collision的
: 这个题应该有个地方需要注意到是，我觉得应该使用分数去算slope，以及于x轴相交的点横坐标。
: 因为用float很难保证2个float是相同的，他们永远只是近似相同。
: 需要写个函数去判断2个分数是否相同。

k*n2012-10-18 07:10

51 楼

m*u2012-10-18 07:10

52 楼

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*g2012-10-18 07:10

53 楼

谢谢！　我能想到的办法就是直接一个一个的算，想知道的思路阿。

【在 m****u 的大作中提到】

: getGrayCode(2)就是返回2bit的格雷码
: 也就是：{00, 01, 11, 10}
: getGrayCode(3)就是
: {000， 001， 011， 010, 110, 111, 101, 100}

p*72012-10-18 07:10

54 楼

这道题根本就是在考grey码，和stl的用法。不懂grey怎么办？

【在 m****u 的大作中提到】

: getGrayCode(2)就是返回2bit的格雷码
: 也就是：{00, 01, 11, 10}
: getGrayCode(3)就是
: {000， 001， 011， 010, 110, 111, 101, 100}

p*72012-10-18 07:10

55 楼

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*62012-10-18 07:10

56 楼

很多年前，我大一学格雷码的时候，就发现这个规律了。

b*n2012-10-18 07:10

57 楼

这题听起来不难.string之间加个dummy seperator就行了.

【在 f****g 的大作中提到】

: What's the point for this question?
: 2 有list of strings，要求首先encode到一个string，然后再decode，恢复这些
: strings，如何encode和decode

b*n2012-10-18 07:10

58 楼

能给个很简洁的代码吗?

【在 p********7 的大作中提到】

: 000
: 001
: 011
: 010
: 110
: 111
: 101
: 100
: 其实就是找变化规律，用2进制列出来就看出来规律了吧。
: bit[0] 除了开头是1个数就变，其他都是2个数变化1次

g*72012-10-18 07:10

59 楼

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*k2012-10-18 07:10

60 楼

嗯，你这么做可以。

【在 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*e2012-10-18 07:10

61 楼

第一个人：
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