Two Sigma Phone Screen Summary

How does Hash Table work

Hash Table stores key, value pairs into an array of buckets/slots. Given an input key, it uses a hash function to compute the index of this array, to compute where to put the key, value pair. The key of hash function is to key keys as uniformly disturbed, and as spread out as possible. For example, java hash function (magic number 31):

int hushfunc(string key){
   int sum = 0;
   for(int i=0; i<key.length(); i++){
       sum = sum * 31 + (int)key[i];
       sum %= hash_table_size;
    }
    return sum;
}

Closed Hashing vs Open Hashing

Open Hashing: use linked list, add linked list to the same bucket.
Closed Hashing (Open addressing): Use different probing technique, or double hashing, to calculate the interval between probes. Also, hash table needs rehashing, when size reaches around 1/10 of capacity.
Closed hashing has better performance when load size is small.

Thread vs Process

Both are independent sequences of code execution. Thread lives within process, and the threads within same process sharing same memory space. They have the same heap, data, code. Yet each thread has their own stack/program counter. When process dies, all threads within it dies.
One process can have its own virtual memory space, and threads lives within it.

Inter-thread communication:

passing references to objects, and changing shared objects,

Inter-process communication:

passing copied reference to processes.

Difference between Quicksort and Mergesort

Quicksort the space complexity is O(logn), for the stack space, Mergesort the space complexity is O(n).
Mergesort guarantees the time complexity will be O(logn); Quicksort time performance depends on the selection of pivot. Worst case can be O(n2). Yet, quicksort stands out in the following three places.

It's in place, and doesn't requires extra memory.
Has a small hidden time factor.
Since it's in place, and no extra memory, it has better cache performance.

Throughput vs Latency

Definition wise:
Latency is the time required to perform some action or to produce some result. Latency is measured in units of time: hours, minutes, seconds, nanoseconds or clock periods.
Throughput is the number of such actions executed or results produced per unit of time.

Compare Floating Points:

#include <stdbool.h>
bool Equality(double a, double b, double  margin){
  if (fabs(a-b) < margin) return true;
  return false;
}
margin can be DBL_EPSILON(minimum meaningful double)

How to store floating point:

Float:
1-bit Sign, 8-bit Exponent, 23-bit Mantissa (尾数),
Double 1-bit Sign, 11-bit Exponent, 52-bit Mantissa.

Paste_Image.png

Question, I know the company is using algorithms, and scientific ways to approach the trading strategy. Could you please explain me a little more details on the Role I am applying, and what is your expectation from a candidate like me, to fit the job.

Two Sigma Phone Screen Summary