一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 2088|回复: 26
收起左侧

[找工就业] [twosigma面经集合]收到了大魔王的onsite邀请 顺便发一波电面面经

[复制链接] |试试Instant~ |关注本帖
shiloh00 发表于 2016-11-5 01:05:14 | 显示全部楼层 |阅读模式

2016(4-6月)-[16]CS硕士+<3个月短暂实习/全职 - 校园招聘会| 码农类全职@TwoSigmafresh grad应届毕业生

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
讲真 面twosigma真的不是我的本意 对于一个转专业的学生来说 这种公司真的是去找虐 我把简历放到学校的link board上 hr来找我的我 电面还是那些题:. 鍥磋鎴戜滑@1point 3 acres
我把自己准备时候的面经打包发上来 有些东西是我自己的理解 可能不太对或者不准确
今天收到了onsite邀请 本着去纽约旅游一波的心态还是觉得去一趟吧
  • Hashmap 的 collision control?  How does Hashtable works  (follow up: how does open addressing works?   What's the problem of linear probing?
How does hash table works?
        1. A table of buckets (an array of buckets), using the array index to denote each bucket.
        2. For each entry <key, value>, it goes to one of the buckets, the bucket index is determined by a hash function applied on key and the size of array.

Key ———(hash func) —> hash ——-(get_index  hashcode % array.length())——->index——>bucket

hash map can only hash one null key, and it’s always mapped to bucket 0.
. Waral 鍗氬鏈夋洿澶氭枃绔,

collision control:
- (close addressing) Separate chaining: they will be assigned to the list
-  open addressing:starting with the hashed-to slot and proceeding in some probe sequence, until an unoccupied slot is found.

Linear probling(open addressing):
        1. Probe: To give a key x, and get its index h(x); and continue to the adjacent cells h(x) + 1, h(x) + 2 …if find a cell whose stored key is x, then returned the value from that cell. Otherwise, if an empty cell is found, then return the key is not present in the dictionary.
            2. Insertion: follow the same steps: find the an empty cell or a cell whose stored key is x:
if the insertion cell cause the load factor of the table to grow above the threshold, will cause rehashing:  the whole table will be replaced by a new table(bigger one). Normally, if the size is lager than 1/2, causing the load factor to stay between 1/4 to 1/2.
        3. Deletion:  
                Lazy deletion: key-value pairs is removed by replacing the value by a special flag value indicating a deleted key.  But there’s some shortcomings for this way.: will contribute  to the load factor of the hash table. With this strategy, it may become necessary to rehash all the remaining key-value pairs when too many cell are occupied by deleted keys.
                 

3. Process 与 thread的区别

不同process之间有不同的address space 但是thread是share memory的
线程的优点: 不需要额外分配内存 通信方便 但是会有线程安全问题 一个挂了另一个也会挂
process 有context switch have high overhead

Thread synchronization : Mutex, semaphore, conditional variable
Heap是在thread之间共享的 但是stack是每一个thread自己所有的

4. IPC(inter-process communication )有哪些:
  • Pipe(管道) : 管道可以用于具有亲缘关系(父子进程)进程间的通信
A unidirectional data channel. Data written to the write end of the pipe is buffered by the operating system until it is read from the read end of the pipe. Two-way data streams between processes can be achieved by creating two pipes utilizing standard input and output.

  • signal: 信号是比较复杂的通信方式,用于通知接受进程有某种事情发生, 除了用于进程间的通信之外,还可以发送信号给进程本身 signal 只能给本机的进程发送消息 本身不能传数据 但是职能告诉你发生了什么->A system message sent from one process to another, not usually used to transfer data but instead used to remotely command the partnered process. Waral 鍗氬鏈夋洿澶氭枃绔,

  • semaphore: 主要用于作为进程间通信机制        A simple structure that synchronizes multiple processes acting on shared resources.

  • Socket:1. Unix domain socket(只能在同一台机发 不会丢失信息 所以本机不需要 tcp header 不会丢包所以不用重传)
                      2. network socket(可以在不同的机发 可能会丢失信息 所以需要重传 TCP三次握手 over head)

5.File: A record stored on disk, or a record synthesized on demand by a file server, which can be accessed by multiple processes.
. more info on 1point3acres.com
ITC(inner thread communication) 线程通信方式:
1. 锁机制:互斥锁 + 条件变量 (conditional varaible)+ 读写锁(read lock, write lock)
互斥锁:提供了以排他的方式防止数据结构被并发修改的方法
读写锁允许了多个线程同时读共享数据, 对写操作是互斥的
条件变量可以进行原子的方式阻塞进程,知道某个特定条件为真为止, 对条件的测试是在互斥锁的额保护下进行的。条件变量始终与互斥锁一起使用
2. semaphore 包括了无名线程信号量和命名线程信号量

线程间的通信目的主要用于线程同步,所以线程没有像进程通信中的用于数据交换的通信机制

5. Latency and throughput:
Difference, example of throughput and latency
.1point3acres缃
latency: 延迟 throughput: 吞吐量 衡量软件系统的最常见的两个指标
low latency doesn't mean throughput:
低延迟不意味着高吞吐量

latency is the time required to perform some action or to produce some result
latency is measured in unit of time, -hours, minutes, nanoseconds or clock periods.
. Waral 鍗氬鏈夋洿澶氭枃绔,
Throughput is the number of such actions executed or results produced per unit of time. This is measured in units of whatever is being produced (cars, motorcycles, I/O samples, memory words, iterations) per unit of time.

example:
An assembly line is manufacturing cars. It takes eight hours to manufacture a car and that the
produces one hundred and twenty cars per day.

The latency is: 8 hours.
鏉ユ簮涓浜.涓夊垎鍦拌鍧.
The throughput is: 120 cars / day or 5 cars / hour.

7. median of data stream

可以用两个heap来做


class medium {
private:
        priority_queue<int, vector<int>, greater<int> > min_heap;
        priority_queue<int, vector<int>, less<int> > max_heap;
public:
        void push(int a) {
                if(min_heap.size() == max_heap.size()) {
                        min_heap.push(a);
                }
                else if(min_heap.size() > max_heap.size()) {
                        int top = min_heap.top();
                        if(top > a) {
                                max_heap.push(a);
                        }
                        else{
                                min_heap.pop();
                                min_heap.push(a);
                                max_heap.push(top);
                        }
                }
                else{
                        int top = max_heap.top();
                        if(top > a) {
                                max_heap.pop();
                                max_heap.push(a);
                                min_heap.push(top);
                        }
                        else{
                                min_heap.push(a);               
                        }
                }
        }
        int get_medium(){
                int len = max_heap.size() + min_heap.size();
                if(len % 2 == 0) {
                        return (max_heap.top() + min_heap.top()) / 2;
                }
                else if(max_heap.size() > min_heap.size()) {
                        return max_heap.top();
                }
                else
                        return min_heap.top();
        }
};

. 1point3acres.com/bbs
9.  How to evaluate infix notation with parenthesis? (basic caculator)
class Solution {
public:
    int calculate(string s) {
        stack<int> ss;
        char sign = '+';
        int tmp = 0, res = 0;
        for(int i = 0; i < s.size(); i++) {
            if(isdigit(s)) {
                tmp = tmp* 10 + s - '0';
            }
            if(!isdigit(s) && !isspace(s)|| i == s.size() - 1) {
                if(sign == '+') {
                    ss.push(tmp);
                }
                else if(sign == '-') {
                    ss.push(-tmp);
                }
                if(sign == '*') {
                    int t = ss.top();
                    ss.pop();
                    ss.push(t * tmp);
                }
                else if(sign == '/') {
                    int t = ss.top();
                    ss.pop();
                    ss.push(t / tmp);
                }
                tmp = 0;
                sign = s;
            }
        }
        while(!ss.empty()) {
            res = res + ss.top();
            ss.pop();
        }
        return res;
    }
};


评分

14

查看全部评分

listen8019 发表于 2016-11-7 08:48:37 | 显示全部楼层
忆梦前尘 发表于 2016-11-7 08:25
. Waral 鍗氬鏈夋洿澶氭枃绔,问个问题。。。two sigma是HR打电话过来就相当于电面了是么?还是像其他家HR一样随便聊聊
. more info on 1point3acres.com
和HR随便聊聊,不涉及面试,顺便发给你OA,再顺便谢鸭妈脏面经。

评分

1

查看全部评分

回复 支持 1 反对 0

使用道具 举报

zxyzzj 发表于 2016-11-5 01:38:42 | 显示全部楼层
感谢分享,好东西~
回复 支持 反对

使用道具 举报

leixiang5 发表于 2016-11-5 04:16:13 | 显示全部楼层
羡慕楼主~ 我往死里骚扰。就是不给我面试~
回复 支持 反对

使用道具 举报

oily 发表于 2016-11-6 22:19:51 | 显示全部楼层
mark,感谢楼主的信息
回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-11-7 02:47:41 | 显示全部楼层
感谢lz,祝lz onsite顺利! 下周正好要面,来看下面经
回复 支持 反对

使用道具 举报

jiamuxeuer 发表于 2016-11-7 03:11:14 | 显示全部楼层
楼主,可以说一下你的OA遇到什么题了么?地里搜不到最近的Two sigma OA~非常感谢楼主。 祝楼主onsite顺利!
回复 支持 反对

使用道具 举报

海盗包子 发表于 2016-11-7 06:36:28 | 显示全部楼层
祝楼主好运~先码上,和h r发了13封邮件还没确定下phone screen。。。不知道还能不能用得上
回复 支持 反对

使用道具 举报

忆梦前尘 发表于 2016-11-7 08:25:44 | 显示全部楼层
问个问题。。。two sigma是HR打电话过来就相当于电面了是么?还是像其他家HR一样随便聊聊
回复 支持 反对

使用道具 举报

finerve 发表于 2016-11-7 08:46:59 | 显示全部楼层
这些基础知识,即使不是转专业的,也要好好准备..会写程序和会回答概念问题真的是两回事..
回复 支持 反对

使用道具 举报

 楼主| shiloh00 发表于 2016-11-7 08:54:31 | 显示全部楼层
leixiang5 发表于 2016-11-5 04:16
羡慕楼主~ 我往死里骚扰。就是不给我面试~

羡慕什么 onsite那么难 反正也过不了
回复 支持 反对

使用道具 举报

 楼主| shiloh00 发表于 2016-11-7 08:54:45 | 显示全部楼层
jiamuxeuer 发表于 2016-11-7 03:11
楼主,可以说一下你的OA遇到什么题了么?地里搜不到最近的Two sigma OA~非常感谢楼主。 祝楼主onsite顺利!

不记得了 我在地里找的
回复 支持 反对

使用道具 举报

 楼主| shiloh00 发表于 2016-11-7 08:55:00 | 显示全部楼层
忆梦前尘 发表于 2016-11-7 08:25
问个问题。。。two sigma是HR打电话过来就相当于电面了是么?还是像其他家HR一样随便聊聊

随便聊。。。。。。
回复 支持 反对

使用道具 举报

 楼主| shiloh00 发表于 2016-11-7 08:55:51 | 显示全部楼层
finerve 发表于 2016-11-7 08:46
这些基础知识,即使不是转专业的,也要好好准备..会写程序和会回答概念问题真的是两回事..

我是说的他家onsite 7轮 。。还要在Linux环境下跑代码 考的非常之底层
回复 支持 反对

使用道具 举报

xiayuan0623 发表于 2016-11-7 08:57:03 | 显示全部楼层
谢谢楼主,请问楼主投的是software engineer 的 campus hire这个职位吗
回复 支持 反对

使用道具 举报

 楼主| shiloh00 发表于 2016-11-7 09:01:28 | 显示全部楼层
xiayuan0623 发表于 2016-11-7 08:57
谢谢楼主,请问楼主投的是software engineer 的 campus hire这个职位吗

我没投 hr联系的
回复 支持 反对

使用道具 举报

EuniceYLiu 发表于 2016-11-8 00:40:37 | 显示全部楼层
markmakrmarkmark,谢谢楼楼啦
回复 支持 反对

使用道具 举报

mrdanding 发表于 2016-11-10 08:58:47 | 显示全部楼层
LZ约的几号店面,我约的1号。。
回复 支持 反对

使用道具 举报

 楼主| shiloh00 发表于 2016-11-10 09:00:21 | 显示全部楼层
mrdanding 发表于 2016-11-10 08:58 鏉ユ簮涓浜.涓夊垎鍦拌鍧.
LZ约的几号店面,我约的1号。。

我去onsite
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-8 20:33

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表