c**y
发帖数: 73 | 1 1. 大数乘法
给定两个非常大的数，写出一个函数返回它们的乘积。可以自己定义需要用到的数据结
构来表示每个数。我用了vector。
2. 系统设计的问题。
给定一个数据中心，如何收集statistics在给定的时间范围（t0，t1）。
这是系统设计题，没啥代表性。
3. 给定一个点，找出一百万个点中距离这个点最近的k个点。
用heap来存当前最近的k个点，然后scan这一百万个点一遍。
4. 给定一个函数fetch10k()，要求实现另外一个函数fetch()。这个题的说明比较复杂
，最后没有写完。具体说明如下。
fetch10k()是给定的，signature如下。
int fetch10k(char *buffer)
这个函数干的事情是从底层读出数据，写到传入的buffer中。这个buffer是一个默认
10k bytes大小的空buffer。返回类型int，返回写入后buffer中数据的size。
注意返回的数据大小和底层的数据大小有关。如果底层数据size是0，那么返回也是0，
因为buffer里什么也没有写。
如果底层数据是小于10k，例如5k，那么返回值是5k，因为只有5k的数据，并且全部写
到10k的空buffer中去了。
如果底层数据是大于或者等于10k，那么返回值是10k。因为10k的数据被写入到buffer
中。注意每次在call这个函数的时候，底层数据的指针也被移动，使得连续的fetch10k
的call读出连续的底层数据。
要求用fetch10k实现的函数fetch()，signature如下。
int fetch(int size, char *buffer)
这里size是指定希望读出的数据大小，buffer是用来存放读出的数据的（假设足够大）
。返回值int是实际从底层数据读出的数据大小。
给几个例子说明可能返回的情况。
（1）size = 8k，但是底层数据只有2k，那么返回值是2k。
（2）size = 8k，底层数据有20k，那么返回值是8k。
（3）size = 8k，底层数据是0，那么返回值是0。
另外一个很重要的要求是能够用这个函数连续从地底读出一段数据。下面是个例子。
底层数据一共有24k，要求能够用三个fetch(8k,buffer)把这个24k的数据读出来。在这
三次fetch的call中，每次读出8k的数据，放到指定的位置（通过buffer）。对于这个
要求，需要特别考虑在一次fetch10k的call中，如何把剩余的2k的数据保留下来，并且
提供给下一次的fetch的call。
好吧，刚开始没有考虑到最后的那个要求，给了一个解法。后他指出我的解法不满足最
后的那个条件。我就改了code，没改完时间就到了。
这个题模糊的地方太多了。 |
h*****a
发帖数: 1718 | 2 多谢。能详细说说2么？是说只处理timestamp在一定范围内的数据？
3直接这样做应该没错，但现实中的优化可能是要对空间进行一下划分。这个看面试人
的要求了。
【在 c**y 的大作中提到】
: 1. 大数乘法
: 给定两个非常大的数，写出一个函数返回它们的乘积。可以自己定义需要用到的数据结
: 构来表示每个数。我用了vector。
: 2. 系统设计的问题。
: 给定一个数据中心，如何收集statistics在给定的时间范围（t0，t1）。
: 这是系统设计题，没啥代表性。
: 3. 给定一个点，找出一百万个点中距离这个点最近的k个点。
: 用heap来存当前最近的k个点，然后scan这一百万个点一遍。
: 4. 给定一个函数fetch10k()，要求实现另外一个函数fetch()。这个题的说明比较复杂
: ，最后没有写完。具体说明如下。
|
r*****e
发帖数: 792 | 3 第三题我昨天也被问了，总体感觉比我的要难啊。
第一题为了以防万一做了好几遍，onsite的前一天还又看了一遍，就差背code了，
因为听说他们家爱问这个。不过没遇上。
【在 c**y 的大作中提到】
: 1. 大数乘法
: 给定两个非常大的数，写出一个函数返回它们的乘积。可以自己定义需要用到的数据结
: 构来表示每个数。我用了vector。
: 2. 系统设计的问题。
: 给定一个数据中心，如何收集statistics在给定的时间范围（t0，t1）。
: 这是系统设计题，没啥代表性。
: 3. 给定一个点，找出一百万个点中距离这个点最近的k个点。
: 用heap来存当前最近的k个点，然后scan这一百万个点一遍。
: 4. 给定一个函数fetch10k()，要求实现另外一个函数fetch()。这个题的说明比较复杂
: ，最后没有写完。具体说明如下。
|
c**y
发帖数: 73 | 4 因为是系统设计题，不要求写code，谈谈思路就行了。
我的proposal是不同时间段的data，用不同的gradunality存。比如过去24小时的data
，每分钟存一次。过去一个星期的data，每天存一次。过去每个月的data，每个星期存
一次。。。。
如果要的t0和t1是过去24小时内的，可以给出。如果超过，只能给出更粗线条的data了
。比如可以给出当日上午10点和11点间的data，但是没法给出去年同一日期上午10点和
11点间的data。
【在 h*****a 的大作中提到】
: 多谢。能详细说说2么？是说只处理timestamp在一定范围内的数据？
: 3直接这样做应该没错，但现实中的优化可能是要对空间进行一下划分。这个看面试人
: 的要求了。
|
c**y
发帖数: 73 | 5 最后一题是我目前经历过最难的题。遗憾面试的人不是老中。如果是的话，估计就不会
有最后的那个要求了。
也可能因为水平有限。觉得就会挂着这个题上面。
【在 r*****e 的大作中提到】
: 第三题我昨天也被问了，总体感觉比我的要难啊。
: 第一题为了以防万一做了好几遍，onsite的前一天还又看了一遍，就差背code了，
: 因为听说他们家爱问这个。不过没遇上。
|
h*****a
发帖数: 1718 | 6 其实这个题也算是个中频题，以前G常问。
【在 c**y 的大作中提到】
: 最后一题是我目前经历过最难的题。遗憾面试的人不是老中。如果是的话，估计就不会
: 有最后的那个要求了。
: 也可能因为水平有限。觉得就会挂着这个题上面。
|
r*****e
发帖数: 792 | 7 看你的题目描述就快累死了，这种题可能其实不难，但是理解起来就要花
好长时间，其实挺无聊的。碰上了也只能说运气不好了。
【在 c**y 的大作中提到】
: 最后一题是我目前经历过最难的题。遗憾面试的人不是老中。如果是的话，估计就不会
: 有最后的那个要求了。
: 也可能因为水平有限。觉得就会挂着这个题上面。
|
r*******e
发帖数: 7583 | 8 夫家是F？
最后一题就是著名的read1024()啊，G以前经常问，版上讨论过多次
这题很完整写出来没有错的都很不容易
buffer
fetch10k
【在 c**y 的大作中提到】
: 1. 大数乘法
: 给定两个非常大的数，写出一个函数返回它们的乘积。可以自己定义需要用到的数据结
: 构来表示每个数。我用了vector。
: 2. 系统设计的问题。
: 给定一个数据中心，如何收集statistics在给定的时间范围（t0，t1）。
: 这是系统设计题，没啥代表性。
: 3. 给定一个点，找出一百万个点中距离这个点最近的k个点。
: 用heap来存当前最近的k个点，然后scan这一百万个点一遍。
: 4. 给定一个函数fetch10k()，要求实现另外一个函数fetch()。这个题的说明比较复杂
: ，最后没有写完。具体说明如下。
|
s*********s
发帖数: 318 | 9 有read1024()的source code学习一下吗？
【在 r*******e 的大作中提到】
: 夫家是F？
: 最后一题就是著名的read1024()啊，G以前经常问，版上讨论过多次
: 这题很完整写出来没有错的都很不容易
:
: buffer
: fetch10k
|
t*q
发帖数: 104 | 10 Am I missing anything?
直接写不就好了，没觉得有啥tricky的地方啊
【在 r*******e 的大作中提到】
: 夫家是F？
: 最后一题就是著名的read1024()啊，G以前经常问，版上讨论过多次
: 这题很完整写出来没有错的都很不容易
:
: buffer
: fetch10k
|
|
|
r*******e
发帖数: 7583 | 11 这题有两种问法，给定read1024()
一个是让实现readline()，在这里有过讨论：
http://www.mitbbs.com/article_t/JobHunting/32101029.html
另一个是实现read(int size)读任意大小，好像更麻烦一些
【在 s*********s 的大作中提到】
: 有read1024()的source code学习一下吗？
|
g*******s
发帖数: 2963 | 12 第三题这种要用heap的一般可以直接调用priority_queue么？
还是要自己写个queue的实现？ |
r*******e
发帖数: 7583 | 13 的确不难，不过按照另外一个贴里说标准是每小时做三道
你可以写一下，看15分钟能不能做到bug free
【在 t*q 的大作中提到】
: Am I missing anything?
: 直接写不就好了，没觉得有啥tricky的地方啊
|
c**y
发帖数: 73 | |
a***n
发帖数: 538 | 15 这么难啊。比我2个月前面的时候感觉难了一个数量级。我有一道很简单的设计题没有
答出来。 |
h*****a
发帖数: 1718 | 16 呵呵，看来我随口一说又是躺着中枪了，怎么每小时3道成标准了？
说实话，面G的话，还真是做得快就多给你一道题，做的越多最后就越impressive，就
越容易拿offer. 有时候你虽然做出来了正确solution，但同一个面试官在面试别人的
时候另外的人用的时间更少，这当然会让人觉得你水平不够啊。
【在 r*******e 的大作中提到】
: 的确不难，不过按照另外一个贴里说标准是每小时做三道
: 你可以写一下，看15分钟能不能做到bug free
|
a*****n
发帖数: 158 | 17 最后一题,,用一个静态变量存当前的指针不就行料吗 ??? 第2题有现成的实现,,看一下
ＯＰＥＮＴＳＤＢ．． |
r**h
发帖数: 1288 | 18 最后一题我的想法是，根据fetch10k的返回值是否是10k，以及当前size是否大于
fetch10k的返回值分四种情况讨论。每次用fetch10k取出数据放到临时buf里，然后再
根据情况从临时buf拷贝相应的长度到总buf里，并记录从开始读取为止已经读的总size。
不过那个额外条件我不是很理解怎么做：按理说静态的文件指针应该是包含在fetch10k
里面不能被访问到，也就是说不能通过seek或者回退指针的方法来暂存已经被读出的数
据。这时候应该是需要另外一个buf来hold住被读出但是没有被使用过的部分，或者当
前buf完全存下10k数据，但是要有一个额外的变量来指明当前buf的实际大小这样下次
call的时候可以先检查当前buf可用的部分。
不过根据函数的signature不知道如何把这些额外的信息返回来供下次使用，难道是要
用全局变量或者静态变量吗？ |
r*******e
发帖数: 7583 | 19 嗯，需要一个全局或者静态变量
size。
fetch10k
【在 r**h 的大作中提到】
: 最后一题我的想法是，根据fetch10k的返回值是否是10k，以及当前size是否大于
: fetch10k的返回值分四种情况讨论。每次用fetch10k取出数据放到临时buf里，然后再
: 根据情况从临时buf拷贝相应的长度到总buf里，并记录从开始读取为止已经读的总size。
: 不过那个额外条件我不是很理解怎么做：按理说静态的文件指针应该是包含在fetch10k
: 里面不能被访问到，也就是说不能通过seek或者回退指针的方法来暂存已经被读出的数
: 据。这时候应该是需要另外一个buf来hold住被读出但是没有被使用过的部分，或者当
: 前buf完全存下10k数据，但是要有一个额外的变量来指明当前buf的实际大小这样下次
: call的时候可以先检查当前buf可用的部分。
: 不过根据函数的signature不知道如何把这些额外的信息返回来供下次使用，难道是要
: 用全局变量或者静态变量吗？
|
g**G
发帖数: 767 | 20 同问，如果用Priority queue的话，是不是得写个wrapper，把超出大小的就边扫边丢
掉了
【在 g*******s 的大作中提到】
: 第三题这种要用heap的一般可以直接调用priority_queue么？
: 还是要自己写个queue的实现？
|
|
|
s**x
发帖数: 7506 | |
m*****e
发帖数: 7 | 22 knn is my most favorite interview question to interviewee. But if you do it
in such a brute-force way, you are dead. :)
【在 c**y 的大作中提到】
: 看来还是复习的不够。。。
|
c*********m
发帖数: 43 | 23 最后一题写了个，大家看看有啥bug没
#define MAX_BUFFER_SIZE 10 * 1024
extern int fetch10k(char *buffer);
char temp[MAX_BUFFER_SIZE + 1];
int fetch(int size, char *buffer)
{
assert(size > 0 && buffer != NULL);
static int currentPos = 0;
string s;
int currSize = 0;
static int len = 0;
while (1)
{
if (currentPos != len)
{
int i;
for (i = currentPos; i < len; i++)
{
s += temp[i];
if (++currSize == size)
{
currentPos = i + 1;
break;
}
}
if (currSize == size)
break;
else
currentPos = len;
}
else
{
len = fetch10k(temp);
currentPos = 0;
if (len == 0)
break;
}
}
if (s.size() == 0)
return 0;
else
{
strcpy(buffer, s.c_str());
return s.size();
}
} |
w******j
发帖数: 185 | 24 请问楼主可以透露一下是在哪里面的吗？另外是general hire，还是一个组？
谢谢.... |
