一亩三分地论坛

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

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

Two sigma 电面附solution

[复制链接] |试试Instant~ |关注本帖
cytmike 发表于 2016-10-28 20:55:20 | 显示全部楼层 |阅读模式

2016(10-12月) 码农类 硕士 全职@TwoSigma - 猎头 - 技术电面 |Pass在职跳槽

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

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

x
他们家问问题的次序都跟面经一模一样
我都打印了出来,不用翻页,就顺序读出来

大米求大米

Q1 What     is a hash table? What do you do to handle hash table collision?
Q2
Medianin a     stream of integers
Q3
Whatis merge     sort? What is quick sort? What are theirrelative advantages and     disadvantages?
Q4 examples of design pattern
Q5 Differences    between threads and processes and how to communicate? IPC ITC
Q6
What     is throughput? What is     latency? What are their     relationships?. 1point3acres.com/bbs
. 鍥磋鎴戜滑@1point 3 acres

solution
  • What     is a hash table? What do you do to handle hash table collision? 我答了最基本的hash     function, hash into a slot, linear probing, chaining method, etc.
2 parts:array and hash function; a data structure that can map keys to values.
  
           Average
  
  
                 Worst case
  
  
Space
  
  
O(n)[1]
  
  
O(n)
  
  
Search
  
  
O(1)
  
  
O(n)
  
  
Insert
  
  
O(1)
  
  
O(n)
  
  
Delete
  
  
O(1)
  
  
O(n)
  
A hash function is any function that can be used to map dataof arbitrary size to data of fixed size.
Separate chaining with linked lists
open addressing,all entry records are stored in the bucket array itself. When a new entry hasto be inserted, the buckets are examined, starting with the hashed-to slot andproceeding in some probe sequence, until an unoccupied slot is found.Quadratic:H+1,H+4,H+9,H+16,H+25,…linear probing searches the table for the closest following free locationand inserts the new key there.
  • Median     in a     stream of integers - 我答了two     heapsolution,然后补充说如果内存不够存stream可以用reservoir     sampling     sample一个subset来估算。
For thefirst two elements add smaller one to the maxHeap on the left, and bigger oneto the minHeap on the right. Then process stream data one by one,
Step1: Add next item to one of the heaps
   if next item is smaller than maxHeap rootadd it to maxHeap,
   else add it to minHeap
Step2: Balance the heaps (after this step heaps will be either balanced or one ofthem will contain 1 more item)
   if number of elements in one of the heaps isgreater than the other by
   more than 1, remove the root element fromthe one containing more elements and  add to the other one
Then at anygiven time you can calculate median like this:
   If the heaps contain equal elements;
     median = (root of maxHeap + root of minHeap)/2
   Else
     median = root of the heap with moreelements
  • What     is merge     sort? What is quick sort? What are their     relative advantages and     disadvantages? 我主要说了merge     sortstable sort而且可以比较方便的去sort     linked list或者是用k-way merge sortsort     external     files, quick sortin     place sort,比较快。. Waral 鍗氬鏈夋洿澶氭枃绔,
Merge sort: divide and conquer,stable (preserves the input order of equal elements in the sortedoutput) , external merge sort (tape drives),n log n worst, O(n)space, good for multithreading
Quick sort: divide and conquer,pivot, not stable, n^2 worst, in place, faster with good pivot
  • Design     patterns?     What is your definition of design     pattern? Give me some examples? 我答了singleton,     factory     pattern以及MVC,并且补充说MVC应该是high-levelarchitecture         design pattern
software design pattern is ageneral reusable solution to a commonly occurring problem within a givencontext in software design. It is a description or templatefor how to solve a problem that can be used in many different situations.Design patterns are formalized bestpractices that the programmer can use to solve common problems whendesigning an application or system. softwarearchitectural pattern for implementing userinterfaces on computers
Components
A typical collaboration of the MVC components.
file:///C:\Users\BIGBRO~1\AppData\Local\Temp\msohtmlclip1\01\clip_image002.pngThe central component of MVC, the model,captures the behavior of the application in terms of its problemdomain, independent of the user interface.[5]
  • The model     directly manages the data, logic and rules of the application.
  • A view     can be any output representation of information, such as a chart or a     diagram. Multiple views of the same information are possible, such as a     bar chart for management and a tabular view for accountants.
  • The third     part, the controller, accepts input and converts it to commands for     the model or view.[6]
InteractionsIn addition to dividing the application into three kinds of components, themodel–view–controller design defines the interactions between them.[7]. visit 1point3acres.com for more.
  • A model     stores data that is retrieved according to commands from the controller     and displayed in the view.
  • A view     generates new output to the user based on changes in the model.
  • A controller     can send commands to the model to update the model's state (e.g. editing a     document). It can also send commands to its associated view to change the     view's presentation of the model (e.g. by scrolling through a document).. 1point 3acres 璁哄潧
Advantage: Displayand Processing are separated. Being able to tease these components apart makesthe code easier to re-use and independently test.
the singleton pattern is a design pattern that restricts theinstantiation of a class to one object.
Disadvantage: anti-patternin that it is frequently used in scenarios where it is not beneficial,introduces unnecessary restrictions in situations where a sole instance of aclass is not actually required, and introduces global variable into anapplication
  • Differences         between threads and processes and how to communicate? 我主要说了threadshared     same     process and same memory space, low overhead;     processseparate memory         spaces, high overhead. Process通信可以用file,     socket, pipe等等, thread通信就用shared     memory     variable.. 鍥磋鎴戜滑@1point 3 acres
a process is an instance of a computerprogram that is being executed. It contains the program code and itscurrent activity. A process contains one ormore threads. https://en.wikipedia.org/wiki/Inter-process_communication
thread of execution is the smallestsequence of programmed instructions that can be managed independently by cpu
Threads differ from traditional multitasking operating system processes in that:
  • processes are typically independent, while threads     exist as subsets of a process
  • processes carry considerably more state information than threads, whereas multiple threads     within a process share process state as well as memory and other resources
  • processes have separate address spaces,     whereas threads share their address space
  • processes interact only through system-provided inter-process     communication mechanisms
  • context switching     between threads in the same process is typically faster than context     switching between processes.
IPC:
      
A record stored on disk, or a record synthesized on demand  by a file server, which can be accessed by multiple processes.
  
      
A data stream sent over a network interface, either to a  different process on the same computer or to another computer on the network.
  
      
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.
  
ITC: · Shared memory, like a variable or some other data structure
· Synchronization primitives, like locks and sempahores
·  Events: wait, notify
  • What     is throughput? What is     latency? What are their     relationships?
Latencyis the time involved to complete any sort of process. Throughput is the amountof information a system canprocess within a given time period (actual rate that the information istransferred). Latency and throughput are not necessarily correlated, because ofdata density. A system that has high latency but can transfer a huge amount ofdata can still have higher throughput than a low-latency system.
Throughtput is affected by latencyif protocol requires synchronous acknowledges of received data.


评分

3

查看全部评分

elizabethxiazhi 发表于 2016-11-1 10:30:53 | 显示全部楼层
LZ店面完多久通知onsite的啊
回复 支持 反对

使用道具 举报

syjohnson 发表于 2016-11-7 04:41:09 | 显示全部楼层
lz太给力了!预祝onsite好运
回复 支持 反对

使用道具 举报

 楼主| cytmike 发表于 2016-11-13 11:50:24 | 显示全部楼层
elizabethxiazhi 发表于 2016-11-1 10:30
LZ店面完多久通知onsite的啊

about 10 days
回复 支持 反对

使用道具 举报

xyao01 发表于 2016-11-15 05:22:37 | 显示全部楼层
感谢楼主的分享!请问median of the data stream需要写code吗 还是口述就行了?
回复 支持 反对

使用道具 举报

tqi222 发表于 2016-11-15 05:32:25 | 显示全部楼层
太棒了 楼主有之前online code challange的信息吗?
回复 支持 反对

使用道具 举报

小飞飞一起飞 发表于 7 天前 | 显示全部楼层
好顶赞 强烈看好楼主
回复 支持 反对

使用道具 举报

本版积分规则

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

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

关闭

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

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

custom counter

GMT+8, 2016-12-3 22:35

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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