Difference between Binary Semaphore and Mutex





A Java example of bounded buffer

public class BoundedBuffer{

final Lock lock = new ReentrantLock();

final Condition notFull = lock.newCondition();

final Condition notEmpty = lock.newCondition();


final Object [] items = new Object[100];

int putptr, takeptr, count;

public void put(Object x) throws InterruptedException{



while(count == items.length)  notFull.await();

items[putptr] = x ;

if( ++putptr == items.length)  putptr=  0 ;



} finally{




public Object take() throws InterruptedException{



while ( count == 0 )   notEmpty.await();

Object x = items[takeptr];

if( ++takeptr == items.length)  takeptr=  0;

— count ;


return x ;






public class BlockingQueue{
private List queue = new LinkedList();
private int limit = 10 ;
public BlockingQueue(int limit){
this.limit = limit ;

public synchronized void enqueue(Object item) throws InterruptedException{
while(this.queue.size() == this.limit){
if(this.queue.size() == 0){
this.queue.add(item) ;

public synchronized void deque() throws InterruptedException {
while(this.queue.size() == 0 ) {
if( this.queue.size() == this.limit) {
return this.queue.remove(0);




google linkedin facebook面经集锦


Given API:
int Read4096(char* buf);
It reads data from a file and records the position so that the next time when it is called it read the next 4k chars (or the rest of the file, whichever is smaller) from the file.
The return is the number of chars read.

Todo: Use above API to Implement API
“int Read(char* buf, int n)” which reads any number of chars from the file.






f design question 总结

Web Cache and HTTP

Caching Tutorial for Web Authors and Webmasters

HTTP Made Really Easy
A Practical Guide to Writing Clients and Servers

In an extremely rough and simplified sketch, assuming the simplest possible HTTP request, no proxies and IPv4 (this would work similarly for IPv6-only client, but I have yet to see such workstation):

  1. browser checks cache; if requested object is in cache and is fresh, skip to #9
  2. browser asks OS for server’s IP address
  3. OS makes a DNS lookup and replies the IP address to the browser
  4. browser opens a TCP connection to server (this step is much more complex with HTTPS)
  5. browser sends the HTTP request through TCP connection
  6. browser receives HTTP response and may close the TCP connection, or reuse it for another request
  7. browser checks if the response is a redirect (3xx result status codes), authorization request (401), error (4xx and 5xx), etc.; these are handled differently from normal responses (2xx)
  8. if cacheable, response is stored in cache
  9. browser decodes response (e.g. if it’s gzipped)
  10. browser determines what to do with response (e.g. is it a HTML page, is it an image, is it a sound clip?)
  11. browser renders response, or offers a download dialog for unrecognized types

Again, discussion of each of these points have filled countless pages; take this as a starting point. Also, there are many other things happening in parallel to this (processing typed-in address, adding page to browser history, displaying progress to user, notifying plugins and extensions, rendering the page while it’s downloading, pipelining, connection tracking for keep-alive, etc.).


TCP 3-Way Handshake

TCP 3-Way Handshake
TCP 3-Way Handshake
TCP 3-Way Handshake

Flacky Test

Eradicating Non-Determinism in Tests

An automated regression suite can play a vital role on a software project, valuable both for reducing defects in production and essential for evolutionary design. In talking with development teams I’ve often heard about the problem of non-deterministic tests – tests that sometimes pass and sometimes fail. Left uncontrolled, non-deterministic tests can completely destroy the value of an automated regression suite. In this article I outline how to deal with non-deterministic tests. Initially quarantine helps to reduce their damage to other tests, but you still have to fix them soon. Therefore I discuss treatments for the common causes for non-determinism: lack of isolation, asynchronous behavior, remote services, time, and resource leaks.

B-Tree and B+Tree


B-tree and B+tree are the most commonly used data structure for building index in database/file system. The reason is it has a higher branching factors over balanced BST(like red black tree) thus it has a lower height. The reason is nodes need to be accessed for BST and B-Tree(B+tree) are both logm(n) where m is the number of branches on each node. lower height means fewer access to the disk to retrieve the nodes, which is what matters for database performance. Database usually stores huge amounts of data and the index can be too large to fit into memory as well and instead stored on the disk. Access to the disk is much slower than memory access. Although higher branching factor means more time in finding the key in the node itself performed in memory, it’s almost ignorable comparing to the time in disk I/O.

Usuallly the database created a node with a size exactly equal to the size of one page so it can be read using one read I/O.
B+TREE’s advantages over B tree:

1. since its internal nodes don’t store data but only store keys, it can have more keys than B-tree within same size of space (one page normally). It means higher branching factor and lower height.
2. Faster full-scan of data using the linked list of all data items at the bottom: fewer cache misses comparing a full-tree traversal of B-tree.

Advantages of B-tree over B+tree: data is closer to the root. thus if some node is much more frequently accessed and we can gain some performance if it’s closer to the root.