some_interesting_facts.txt

Bucket sort is mainly useful when input is uniformly distributed over a range. For example, consider the following problem. Sort a large set of floating point numbers which are in range from 0.0 to 1.0 and are uniformly distributed across the range.  http://www.geeksforgeeks.org/bucket-sort-2/

In sharding you can have logical and physical shards: user_id % 8 = logical shard
logical shards -> physical shard map
{
 0: A, 1: A,
 2: A, 3: A,
 4: B, 5: B,
 6: B, 7: B
}

64^5 us ~1B

Rule of thumb for caches is 20% of total data in cache will hit for 80% of traffic

CAP Theorem
Consistency: A read after a write always results in the data resulted from the write
Available: A request to DB always returns an answer - this is kinda non negotiable.
Partition Tolerance: If one part of the system i.e. one or many nodes goes down, we still continue to function based on quorum

To check if number is odd or even use bitwise operator to find what's the LSB
n&1 = 101 & 001 = 001 = 1; n&1 = 10 & 01 = 0

To detect cycle in undirected graph use union find algorithm. http://www.geeksforgeeks.org/union-find/
To detect cycles in directed graph use DFS and keep two sets of visited and recursion_stack_visited. cycle when rec_stack_v collision

Companies interview about 21-22 people(including phone screen) to make one hire. Conversion rate of referrals is 25%

ACID - Atomicity - transaction either succeeds or fails- ie. no inbetween state, 
Consistency - changes by one transaction are immediately available to see to another transaction, 
Isolation - multiple transactions can run simultaneously and wont affect each other, 
Durability - in case of failure data is persisted to disk and is durable

For lookup-intensive applications, AVL trees are faster than red–black trees because they are more strictly balanced.[
For an insert intensive tasks, use a Red-Black tree.

Uses of XOR :
1. is used to toggle bits
int i = 123;
i ^= (1 << 4); // toggle bit 5
2. for weak encryption
int b = 235321;
int key = 24552;
int encrypted = b ^ key;
int decrypted = encrypted ^ key; // equals 235321
3. Create hashcode
int i = 123;
for (int k = 0; k < 100; k++)
{
   i = i ^ (i << k) + i;
   System.out.println(i);
}

Also 0 ^ N = N
1 ^ N = N with bits flipped
N ^ N = 0
 

Modern processors run gigahertz thats 1B operations/sec. Anything interesting takes hundereds of operations. So you are looking at millions of operations / sec for one iteration of an array say.

R-B offers slightly faster insertion than AVL, at the cost of slightly slower lookup.

For a graph to be a valid tree it should have no cycles and one root and be connected.
For each edge use union find algorithm https://leetcode.com/problems/graph-valid-tree/#/solutions to detect cycle 
Also, the number of edges should be n-1: return edges.length == n - 1

DFS are more likely to get a stack overflow error than BFS

BFS uses a queue.

In a grid where some areas are unreachable think about starting from destination to all other squares vs other way round. e.g. https://leetcode.com/problems/walls-and-gates/#/solutions

You can use DNS SRV records for service discovery

A lock allows only one thread to enter the part that's locked and the lock is not shared with any other processes.

A mutex is the same as a lock but it can be system wide (shared by multiple processes).

A semaphore does the same as a mutex but allows x number of threads to enter.

You also have read/write locks that allows either unlimited number of readers or 1 writer at any given time.