Bigger impact, newer/better technology, more responsbilities, work with smart people.
Software Engineering is an industry of continous learning, and so should I, also I noticed that you have a learning culture here, a place of learning.
Rather than many financial companies that keep technology as a back office, I'm looking for something that is tech-driven. I always
believe that technology is the key on the road to successful strategy.
life is about making decisions, it is like investments.
We're downtown, but we're not Wall Street.
- How it works:
look for meaningful patterns in the world’s data. Then we use these insights to create investment strategies.
Pattern. Meaning. Relationships.
Power of data and technology.
Predict the movement of the market (retirement investment).
- Why Two Sigma?
As a new grad, I’m looking for a place to grow and expand myself.
每轮都有自我介绍的时间和面试官介绍自己的时间
围绕围绕，扯回去扯回去！
Questions to ask
Could you briefly introduce Two Sigma? What do you guys do? And what does your team do?
What’s your typical day? I mean, as an engineer, how usually do you spend your day?
Halite the AI challenge, last time the 2016 TS cup, why do you guys so focus on AI and Robot?
Things that engineers build, are them only being used internally? And Also are you using any products of software from other companies?
About the trading and all related operations, are they human involved? In other words, how much do you guys trust decisions made by machines?
Phone
What's your most challenging project? Hash Table
What is a hash table? When to use? Why use it?
Given a (key, value) pair, hash table is data structure which converts the key to an index and then store the value somewhere using that index.
Generally, we can think of it a as a mapping from key to value.
Hash function generates index of buckets or slots using key.
Ideally, it maps key to a unique bucket. The best situation is it provides a uniform distribution of hash values.
Operations cost:
- Constant, amortized O(1)
- worst case O(n) for search & deletion (add flag to fix it)
Size:
- power of 2
- prime number, good for even poorly designed hash function
Resizing (resize + insert again O(n) in average (n/2)
- Load factor = (# of entries) / (# of buckets)
- keep size within a good range (not too many collision, not too large wasted memory)
Open Addressing (close hashing) is method of collision resolution in hash tables. It’s resolved by probing. Probing includes linear probing, quadratic probing and double hashing.
Linear probing:
Search: Find next available slot.
Insert:
Delete (Trouble):
- Iterate through the following slots until find an empty slot or move one back to this slot (recursively)
- Or use flag
Problems happen when there’s primary clustering. It means two records are mapped to the same index which causes one of them to move. And afterwards collisions increases during inserting more key value pair into hash table. A tendency that a collision will cause more nearby collisions.
With poorly designed hash function, i.e., hash function that would not make inputs uniformly distributed, linear probing could be slower than quadratic probing and double hashing.
Someone implement hash table and it is slow, why?
- poor hash function
- bad open addressing strategy
Use hash table to store data, but there is much more data than the machine's RAM, how to deal with that? add one more machine, rehash and reconstruct the hash table
Process vs Threads
In computing, a process is an instance of a computer program that is being executed. It contains the program code and its current activity. Depending on the operating system (OS), a process may be made up of multiple threads of execution that execute instructions concurrently.
In computer science, a thread of execution is the smallest sequence of programmed instructions that can be managed independently by a scheduler, which is typically a part of the operating system.
Each process provides the resources needed to execute a program. A process has a virtual address space, executable code, open handles to system objects, a security context, a unique process identifier, environment variables, a priority class, minimum and maximum working set sizes, and at least one thread of execution. Each process is started with a single thread, often called the primary thread, but can create additional threads from any of its threads.
A thread is the entity within a process that can be scheduled for execution. All threads of a process share its virtual address space and system resources. In addition, each thread maintains exception handlers, a scheduling priority, thread local storage, a unique thread identifier, and a set of structures the system will use to save the thread context until it is scheduled.
Typical difference is, processes run in separated memory while threads run in shared memory.
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.
How to communicate? IPC vs ITC (Inter-Process Communication vs Inter-Thread Communications)
IPC:
- File
A record stored on disk, or a record synthesized on demand by a file server, which can be accessed by multiple processes.
- Socket
A data stream sent over a network interface, either to a different process on the same computer or to another computer on the network. Typically byte-oriented, sockets rarely preserve message boundaries. Data written through a socket requires formatting to preserve message boundaries.
- Message Queue
A data stream similar to a socket, but which usually preserves message boundaries. Typically implemented by the operating system, they allow multiple processes to read and write to the message queue without being directly connected to each other.
Publish/Subscribe, Observer
- 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.
Like when we are using arrow symbol in command line.
- Shared memory
Multiple processes are given access to the same block of memory which creates a shared buffer for the processes to communicate with each other.
- Semaphore
A simple structure that synchronizes multiple processes acting on shared resources.
ITC:
- Synchronization primitives, like locks and semaphores
- Through Events: wait, notify
- Shared memory, cause typically they all live in the same process
Each thread has a private stack, which it can quickly add and remove items from. This makes stack based memory fast, but if you use too much stack memory, as occurs in infinite recursion, you will get a stack overflow.
All threads share a common heap. Since all threads share the same heap, access to the allocator/deallocator must be synchronized. There are various methods and libraries for avoiding allocator contention.
Some languages allow you to create private pools of memory, or individual heaps, which you can assign to a single thread.
every thread would be allocated its own memory space in stack while typically there is only one heap within one process. This means heap space is shared among all threads. Since it is global, it is faster in speed. But also, this causes synchronization issues, which could possibly slow the whole system down.
Some languages or OS my support allocating heaps for each thread.
Latency vs Throughput
Latency is the amount of time to finish an operation. Latency is the delay from input into a system to desired outcome.
Unit would be second granule.
Throughput is the amount of work we finished in a unit time.
Throughput is a measure of how many units of information a system can process in a given amount of time.
Bandwidth commonly measured in bits/second is the maximum rate that information can be transferred
Throughput is the actual rate that information is transferred
Latency the delay between the sender and the receiver decoding it, this is mainly a function of the signals travel time, and processing time at any nodes the information traverses
Throughput impacted by latency?
throughput = bandwith / rtt
rtt = latency * 2
latency up, throughput down
latency down, throughput up
Quicksort vs Merge sort
Quick sort
- in place
- average O(nlgn), worst O(n^2)
Merge sort
- average and worst O(nlgn)
- extra space O(n)
External sorting is a term for a class of sorting algorithms that can handle massive amounts of data. External sorting is required when the data being sorted do not fit into the main memory of a computing device (usually RAM) and instead they must reside in the slower external memory (usually a hard drive). External sorting typically uses a hybrid sort-merge strategy. In the sorting phase, chunks of data small enough to fit in main memory are read, sorted, and written out to a temporary file. In the merge phase, the sorted subfiles are combined into a single larger file.
The core idea, is that in the sorting phrase, the chunk of data that we need to sort could be loaded to RAM and thus apply sorting to them. Then we can write them back to the temporary file.
Both merge sort and quick sort could be used for external sorting.
Median of streaming data
Given a stream of numbers, how to calculate average, standard deviation, median?
Median: Max heap + min heap
Average: Keep track of sum & size
Standard deviation: Not other way, O(n) best?
Followup:
- what about largest (smallest) K% elements？
e.g., (n/10)th element
Design Pattern
A design pattern is a general reusable solution to a commonly occurring problem.
Each template is useful for solve a particular set of problems with some feature.
MVC Design Pattern
MVC is a design pattern for implementing user interface. It consists of three parts, Model, View and Controller, where each one of them is called components and has their own functionality.
Model manages all the data and logic of a software. It is the core component.
View is an interface responsible for taking all information from model and representing them to user.
Controller takes all commands from users sends them to model.
In this way, a software is loosely coupled and well organized into modules. We can very easily add new functions and features to it. And it is also very easy to maintain.
What other design patterns have you used?
(Creational)
Singleton -> Object Pool
Singleton is a design pattern where you allow only one instance of a class. In some cases, like its private variables don’t change, singleton is useful.
Later, to extend this we could use object pool where we allow multiple instances of a class. This could be useful when we need a couple of object at the same time while it’s expensive to create them. A good example would be service connections. We can use two hash tables to implement this. One for available objects and one for unavailable objects.
Factory -> Abstract Factory
Factory is a design pattern that allows us to dynamically specify an object’s class without calling constructor.
Prototype, Builder
(Structural)
Adapter, Facade
Adapter is a wrapper of old interface. We add it because the current function needs a new interface which is incompatible with the old one.
Facade is just a wrapper that aggregates some functionalities required by clients. By doing this, the whole system is easier to understand, to use and to test.
Composite
Composite is a design pattern that allows tree structure. It contains either variables we need, or a list objects of itself.
Proxy
(Behavioral)
Iterator
It’s just a pattern for iterating a data structure. By doing this, we can encapsulate the implementation of our own data structure and just provide the iterator interface.
State, Strategy
They both keep data as their member variables which can be changed in runtime.
Onsite First set
First round: Reverse Polish Notation
Make sure to know what the requirement is.
Operator (base class)
- operate(int val1, int val2)
Add,Subtract, Multiply, Divide四个class继承这个Operator base class的写法
- pay attention to Divide
Don’t over-design!
follow ups:
- token, operand and operator inherit from token
- unary and ternary operators, add a variable of NumOperands
- factory design pattern
Factory design pattern is a class where you can hide the creation logic of all sub-classes. Typically it would require a type and generate an object of sub-class. Essentially it’s a mapping from types sub-classes.
struct node
{
int parent;
int val;
bool valid;
bool visited;
};
要实现的函数大概长这样：
void DeleteSubTree(node* head, int index, int n){
// n代表数组里面一共有n个元素
(head+index)->visited = true; // Set up
(head+index)->valid = false; // this first!!
for(int i=0; i < n; i++){
if ((head+i)->visited) continue; // Memorization
if(NeedDelete(head, i)){
label(head, i);
}
}
}
bool NeedDelete(node* head, int index){
while(index != -1 && !(head+index)->visited ){
(head+index)->visited = true;
index = (head+index)->parent;
}
Meanwhile, two threads are modifying the same data structure — q1 and q2, so we need lock.
- lock = threading.Lock()
- modify calculate_pair to “with lock:”
- finally start the threads, and run
try:
thread.start_new_thread(thread1, (s1, ))
thread.start_new_thread(thread2, (s2, ))
except:
print "Couldn't start threads."
各种切入点啊，看题目要求吧！
Followups:
- 如果有多个queue，比如10个queue怎么办，lock ds (like semaphore), then do the same thing
process() {
while (true) {
LOCK L1
x = s1.get()
list1.add(x)
UNLOCK L1
LOCK L2
for y in list2
if (abs(x - y) < 1)
print
UNLOCK L2
}
}
Slow Web Accessing
- client-server-database model
- draw diagram/model
(Start from browser)
DNS (back to front)
- cache
- test: check response time
CDN (ip address of a data center)
- cache
- test: try different ip of the host
Load balancer / Router (inside a data center)
- different kinds of request
- download, long connection, web browsing, short connection
- different protocol
- balance request numbers to different servers
- test: monitor server load and request type
Back end
- asynchronous vs synchronous response
- reduce I/O waiting time
Message queue
- distributed system
Database
- same request -> cache
- too many connections at the same time -> batch
- Database itself is slow -> in-memory database
- bad formatted, low efficient queries
- bad table design
(Back to browser)
Front end
- bad javascript
- call library, which doesn’t do well in CDN
Browser
- hardware acceleration
General / QoS
- bandwidth, low speed for transferring data
- throughput, low speed for processing data
(- error rate)
Wildcard matching
Firstly, think this through. All corner cases, test cases.
According to this, write a naive recursion implementation. Walk them through. Make sure to illustrate the idea clearly!!!
def is_match_recursion(s, p):
if not s: # Corner case.
return p.count('*') == len(p)
if not p: # Corner case.
return not s
if p[-1] == '?' or s[-1] == p[-1]: # Recursive call.
return is_match(s[:-1], p[:-1])
if p[-1] == '*’: # Recursive call.
return is_match(s, p[:-1]) or is_match(s[:-1], p)
return False
Two optimizations:
Change passing str to passing list + indices, save memory in recursive calls.
Avoid duplicated computation by importing memorization {(si, pi): True/False}
Extend the idea above to Dynamic Programming. Make sure to be clear about the tabular fill-up (relationship), and corner cases.
def is_match(s, p):
m = len(s)
n = len(p)
matched = [[False] * (n+1) for _ in xrange(m+1)]
matched[-1][-1] = True # Corner Case.
for i in xrange(n): # Corner Case.
if p != '*':
break
matched[-1][i] = True
for si in xrange(m):
for pi in xrange(n):
if s[si] == p[pi] or p[pi] == '?’: # Relationship.
matched[si][pi] = matched[si-1][pi-1]
elif p[pi] == '*’: # Relationship.
matched[si][pi] = matched[si][pi-1] or matched[si-1][pi]
else:
matched[si][pi] = False
return matched[m-1][n-1]
Followup, Backtracking!
si, pi = 0, 0
last_si, last_pi = None, None
while si < len(s):
if pi < len(p) and (s[si] == p[pi] or p[pi] == '?'):
si += 1
pi += 1
elif pi < len(p) and p[pi] == '*':
last_si = si + 1
last_pi = pi + 1
pi += 1
elif last_pi:
pi = last_pi
si = last_si
last_si += 1
else:
return False
return p[pi:].count('*') == len(p) - pi
Second set
First round: Power of 4 Of course it could be solved by brute force= =
while abs(num) > 1:
if num % 4 != 0: return False
num /= 4
return num == 1
It reminds me of power of 2:
num & (num-1) == 0 # power of 2
This means there’s only one bit in binary representation.
All we need to do is to add another condition.
- num > 0 and num | 0x55555555 == 0x55555555 # explain 0x55555555
def hasNext(self):
while self.x < len(self.nums) and \
self.y >= len(self.nums[self.x]):
self.x += 1
self.y = 0
return self.x < len(self.nums) and self.y < len(self.nums[self.x])
def next(self):
if self.hasNext():
val = self.nums[self.x][self.y]
self.last_return = (self.x, self.y)
self.y += 1
return val
else:
raise Exception('No more values')
def remove(self):
if self.last_return:
x, y = self.last_return
self.last_return = None
self.nums[x].pop(y)
self.x, self.y = x, y
else:
raise Exception('None couldn\'t be removed')
Mod 5 iterator.
bool hasNext() {
# Either way is okay, hasNext() or next() while (self.n % 5 != 0 and Iterator::hasNext()) { self.n = Iterator::hasNext(); }
return self.n % == 0;
}
int next() {
if (!hasNext())
throw runtime_error("no more elements!");
val = self.n
self.n = INIT_VAL # not equal to n * 5
return val;
}
Some theory
- 理论。给两个set，如果取他们的交集，问了各个方法的优缺点（时间复杂度+空间复杂度）
- brute force
- sort one, binary search the other one
- sort, then two pointers
- hashmap - merge，归并排序duplicates???
- add field ‘font’ in the internal nodes, split when necessary
- Undo/redo?
- Use two stacks, one for each, and make operations into objects
Third round Debug guava
At least 4 functions need to rewrite, debug:
- put
- size
- clear
- clearall
// put
public boolean put(@Nullable K key, @Nullable V value) {
Collection<V> collection = map.get(key);
if (collection == null) {
collection = createCollection(key);
if (collection.add(value)) {
totalSize++;
map.put(key, collection);
return true;
} else {
throw new AssertionError("New Collection violated the Collection spec");
}
} else if (collection.add(value)) {
totalSize++;
return true;
} else {
return false;
}
}
/**
* Removes all values for the provided key.
*/
private void removeValuesForKey(Object key) {
Collection<V> collection = Maps.safeRemove(map, key);
if (collection != null) {
int count = collection.size();
collection.clear();
totalSize -= count;
}
}
// get
public Collection<V> get(@Nullable K key) {
Collection<V> collection = map.get(key);
if (collection == null) {
collection = createCollection(key);
}
return wrapCollection(key, collection);
}
Third Set
First round LRU
Get
- illegal input
- update (key, value)
Set
- key existed — update
- new key
— enough space
— not enough space
Size
Fast
- in get, hash table to get value and move it to head
- in set, double linked list for quick modification
— move to head
— add to head
— delete from tail
Second round Best Time to Buy and Sell Stock III
One dimension
- max_profit = array(n)
- max_profit[i] = max(max_profit[i], # day i is not involved in transaction, we’re using stat from previous day, or
prices[i] - min_prices from [0 .. i-1] # stock sold on day i, buy on j from [0 .. i-1], max_minus_prices from [0 .. i-1])
K dimension (k transactions)
- max_profit = matrix[k * n], max profit till day i using UP to k transactions.
- max_profit[kk][i] = max(max_profit[kk][i-1], # same, not involved with day i
max(prices[i] - prices[j] + max_profit[kk-1][j]) # One transaction bought on day j, sold on day i
# plus max_profit[kk-1][j], on day j using k - 1 transactions
- where the underline part is computed multiple times, each time we can just use max_diff = max(max_diff, - prices[j] + max_profit[kk-1][j]) to save time.
Algorithm:
def find_kth_smallest(self, nums1, nums2, k):
m, n = len(nums1), len(nums2)
if m > n:
return self.find_kth_smallest(nums2, nums1, k)
if not nums1:
return nums2[k - 1]
if k == 1:
return min(nums1[0], nums2[0])
i = min(k / 2, m)
j = min(k / 2, n)
if nums1[i - 1] > nums2[j - 1]:
return self.find_kth_smallest(nums1, nums2[j:], k - j)
else:
return self.find_kth_smallest(nums1[i:], nums2, k - i)
def findMedianSortedArrays_v2(self, A, B):
m, n = len(A), len(B)
if m > n:
A, B, m, n = B, A, n, m
if n == 0:
raise ValueError
imin, imax, half_len = 0, m, (m + n + 1) / 2
while imin <= imax:
i = (imin + imax) / 2
j = half_len - i
if i < m and B[j - 1] > A[i]:
# i is too small, must increase it
imin = i + 1
elif i > 0 and A[i - 1] > B[j]:
# i is too big, must decrease it
imax = i - 1
else:
# i is perfect
狗仔卡
收藏
淘帖
好苗
杂草
提升卡
置顶卡
关贴卡
开贴卡
变色卡
千斤顶
楼主
