背景

capfs是实验室自主研发，隶属于国家863重大项目“海量存储系统整体研究”的分布式对象存储系统，设计采用类似于PNFS的三方架构，具有高聚合带宽，并且具备高可扩展性、支持大目录等。系统能够达到60GB/s聚合带宽，支持10PB级存储，IOPS达到10^4至10^5，系统能够支持10亿个文件的访问（这些不需要强调）。

任务

主要任务是为capfs提供分布式锁服务，为系统中的共享资源提供协同访问和一致性视图，保证数据并发访问的安全性。主要涉及flock文件锁系统调用功能及多客户端访问同一文件的元数据或数据一致性，满足读写一致性要求。

设计

首先是带领小组分析学习成熟系统NFS及Lustre文件系统的一致性保证机制，为设计作为参考。NFS在v3版本之前都仅采用时间戳判断元数据是否失效，并每次更新同步并重新请求元数据，在多客户端访问下可能存在短暂的读写不一致情况。NFSv4在此基础上引入租约及回调机制，但只在open操作时申请，并且在remove类似操作时释放并回调，导致在多客户端情况下可能出现ping-pong效应且客户端缓存利用不足。Lustre设计多种锁类型进行一致性保护，修改了Linux内核以支持意图锁模式，并利用多种回调机制使得客户端尽可能持有锁，在服务器实现方面利用namespace及资源两个概念描述被保护的共享资源，并为每个资源设计三种锁队列。

编写分布式锁主体框架以及与分布式系统耦合相关的代码。主要是提供文件级租约锁服务以保障客户端元数据缓存的一致性，该设计充分吸取了NFS的设计经验，这样就可以避免复杂的锁请求恢复及死锁检测（租约会在一段时间后自动失效，目前设置为30s，优化可以使用自适应算法），但是在lookup时即申请并在对应操作进行锁升级以加大并发度。服务器与回调接口设计参考Lustre，服务器架设在mds端，这样锁请求与元数据请求同时发送；同时在客户端架设锁客户端以类似plugin的形式嵌合（模块），接口传入资源字符串以保证通用性，以不同的命名规则区分文件锁及租约锁申请。

优化、难点

性能优化方面实现锁客户端的锁缓存方便回调查找，以及所谓子树锁优化，前者保证回调查找的高效，后者保证同一目录下多文件不用多次进行租约授予。继续可以利用冲突判断（目前为5次，超过后即放弃元数据缓存）降低ping-pong效应，特别是子树锁可能导致的冲突加剧。容易忽略的地方是客户端的时间同步。高可用性方面，需要加强mds的高可用性，锁相关的mds事务处理尚未实现。（关键设计难点在删除操作的一致性保证，目前尚未解决）。

支持5000并发访问

关键点：Linux内核开发，租约机制，回调，子树锁优化

13.1 Write a method to print the last K lines of an input file using C++.

int tail(const string &fname, int lines, list &res)
{
    ifstream fs(fname.c_str());
    if(!fs)
        return -1;
    int status = 0;
    int bytes_perline = 100;
    fs.seekg(0, fs.end);//fs.end
    streamoff end_pos = fs.tellg();
    streamoff start_pos = end_pos - bytes_perline*lines;
    if(start_pos < 0) start_pos = 0;
    fs.seekg(start_pos, fs.beg);

    string line;
    list::iterator it = res.begin();
    while(res.size() < lines){         
       getline(fs, line);         
       it = res.insert(it, line);         
       ++it;         
       if(status == 0){ //find last lines             
         if(fs.eof()){                 
                if(res.size() > lines)
                    break;
                end_pos = start_pos;
                start_pos>>=1;
                fs.clear();
                fs.seekg(start_pos, fs.beg);
                res.erase(--it);
                it=res.begin();
                status = 1;
            }
        }else if(status > 0){ // look up in the front
            if(fs.tellg() >= end_pos){
                if(res.size() > lines)
                    break;
                end_pos = start_pos;
                start_pos>>=1;
                fs.clear();
                fs.seekg(start_pos, fs.beg);
                res.erase(--it);
                it=res.begin();
                 if(start_pos <= 0) // reach the top                     
                    break;             
             }                  
        }    
   }         
   if(res.size()> lines ){
       int i = res.size()-lines;
       for(;i>0;--i)
          res.erase(res.begin());
   }

   return res.size();
}

int main(int argc, char const *argv[])
{
    int ret;
    list res;
    ret = tail(argv[1], atoi(argv[2]), res);
    if(ret>0)
        copy(res.begin(), res.end(), ostream_iterator(cout, "\n"));
    return 0;
}

**13.2 Compare and contrast a hash table vs an STL map. How is a hash table implemented? If the number of inputs is small, what data structure options can be used instead of a hash table.** STL map's pairs are in sorted order but hash table don't and STL map takes O(nlgn) to find a elm yet hash table takes O(1) time. When implement a hash table you should find a hash function, deal with collision and size of table. If inputs is small then RB tree would be a a alternative way for hash table. **13.3 How do virtual functions work in C++?** A virtual function depends on a "virtual table". If any function or class is declared as virtual, a v-table is constructed which stores addresses of the virtual functions of this class. The compiler also adds a hidden vptr in all such classes which points to the vtable. If a virtual function is not overriden in the derived class, the vtable of the derived class stores the adress of the function in his parent class. The vtable is used to resolve the address of the function. Dynamic binding in C++ is therefore performed though the vtable mechanism. **13.4 What is the difference between deep copy and shallow copy? Explain how you would use each.** Shallow copy just copy the address of the object's ptr field yet deep copy also copy the values of that ptr points to which need dynamic allocated space. The default copy constructor and assignment operator make shallow copies. Deep copy usually are used to deal with the string or buffer. **13.5 What is the significance of the keyword “volatile” in C** Volatile informs the compiler that the value of the variable can change from the outside, without any update done by the code, thus just don't optimize the variable related code and fetch the variable value from memory instead of the register. **13.6 What is name hiding in C++? ** "Name hiding is particularly tricky if the derived class's method has a different signature than the base class's method of the same name." Base class's method would be hidden if the derived class overrides that method (no-virtual function) and overloaded in the same time. (see Effective C++ rule 33) **13.7 Why does a destructor in base class need to be declared virtual?** If we delete on the base ptr which points to the derived class object, the base class destructor called first (for no-virtual function) which would lead to a memory leak for the derived part. We should declare base class's destructor in virtual so that derived destructor would be called first and destroy all parts of the object as we expected. **13.8 Write a method that takes a pointer to a Node structure as a parameter and returns a complete copy of the passed-in data structure.The Node structure contains two pointers to other Node structures.** It's mush alike deep copy a binary tree.

typedef struct Node Node_t;
struct Node{
   struct Node* ptr1;
   struct Node* ptr2; 
};
typedef set<Node_t*> NodeMap;

Node_t* copy_recursive(Node_t* cur, NodeMap &map){
    if(cur == NULL) return NULL;
    NodeMap::iterator it = map.find(cur);
    if(it != map.end())
       return *it;
    Node_t* node = new Node_t;
    map.insert(node);
    node->ptr1 = copy_recursive(cur->ptr1, map);
    node->ptr2 = copy_recursive(cur->ptr2, map);
    return node;
} 

Node_t* copy_node(Node_t* root){
     NodeMap map;
     return copy_recursive(root, map);
}

**13.9 Write a smart pointer (smart_ptr) class. ** Check Effective C++ rule 14.

template <class T>
class smart_ptr {
public:
    smart_ptr(T *ptr){
        //cout<<"default"<<endl;
        ref = ptr;
        ref_count = new unsigned int();
        *ref_count = 1;
    }

    smart_ptr(smart_ptr &sptr){
        //cout<<"copy assign"<<endl;
        ref = sptr.ref;
        ref_count = sptr.ref_count;
        ++*ref_count;
    }

    smart_ptr& operator=(smart_ptr &sptr){
        //cout<<"= assign"<<endl;
        if(this != &sptr && ref != sptr.ref) {
            if (--*ref_count == 0){ // this may already got a ptr
                clear();
                //cout<<"= clear"<<endl;
            }

            ref = sptr.ref;
            ref_count = sptr.ref_count;
            ++*ref_count;
        }
        return *this;
    }

        T operator*() { return *ref; }

    ~smart_ptr(){
        //cout<<*ref_count<<endl;
        if(--*ref_count == 0){
            clear();
            //cout<<"clear"<<endl;
        }
    }
private:
    void clear(){
        delete ref;
        delete ref_count;
        ref = NULL;
        ref_count = NULL;
    }
protected:
    T *ref;
    unsigned int *ref_count;
};

int main(int argc, char const *argv[])
{
    int *p1 = new int();
    *p1 = 100;
    smart_ptr sp1(p1), sp2(p1);
    smart_ptr spa = sp1; // copy assign not = assign
    sp2 = sp1; // = assign
    cout<<*spa<<endl; // spa is the same of sp1
    return 0;
}

**15.1 Write a method to find the number of employees in each department**

SELECT Departments.name, count(Employees.id) FROM Departments, Employees WHERE Employees.depid = Departments.id(+) GROUP BY Departments.id

SELECT Departments.name, count(Employees.id) FROM Departments LEFT JOIN Employees ON Employees.depid = Departments.id GROUP BY Departments.id

**15.2 What are the different types of joins? Please explain how they differ and why certain types are better in certain situations.** ** ** There are innerjoin, left outer join, right outer join, full outer join and cross join. INNER JOIN result set will only contain datas where the criteria match.

SELECT * FROM Employees, Departments WHERE Employees.dpid = Departments.id;

CROSS JOIN returns the Cartesian product of rows from tables in the join. It will produce rows which combine each row from the first table with each row from the second table.

SELECT * FROM Employees, Departments;

LEFT OUTER JOIN returns all the values from an inner join plus all values in the left table that do not match to the right table(NULL in the case of no matching join predicate).

SELECT * FROM Employees, Departments WHERE Employees.dpid = Departments.id(+);

RIGHT OUTER JOIN returns all the values from the right table and matched values from the left table (NULL in the case of no matching join predicate). Right and left outer joins are functionally equivalent. FULL OUTER JOIN combines the effect of applying both left and right outer joins. Some database systems do not support the full outer join functionality directly.

SELECT * FROM Employees INNER JOIN Departments ON Employees.dpid = Departments.id UNION ALL;

**15.3 What is denormalization? Explain the pros and cons.** denormalization is the process of attempting to optimize the read performance of a database by adding redundant data or by grouping data, like storing the count of the "many" objects in a one-to-many relationship as an attribute of the "one" relation or adding attributes to a relation from another relation with which it will be joined. It's do good in performance yet more redundant data. **15.5 Imagine a simple database storing information for students’ grades. Design what this database might look like, and provide a SQL query to return a list of the honor roll students (top 10%), sorted by their grade point average.**

CREATE TABLE Students(
    'sid' INT NOT NULL AUTO_INCREMENT,
    'name' varchar(20) NOT NULL,
    'sex' enum(f,m),
    PRIMARY KEY('sid')
);

CREATE TABLE Courses(
    'cid' INT NOT NULL AUTO_INCREMENT,
    'name' varchar(20) NOT NULL,
    'description' text,
    PRIMARY KEY('cid')
);

CREATE TABLE Enrollment(
     'eid' INT NOT NULL AUTO_INCREMENT,
     'cid' INT NOT NULL,
     'sid' INT NOT NULL,
     'grade' INT NOT NULL,
     PRIMARY KEY('eid')
);

SELECT Students.name, GPA 
FROM (
     SELECT TOP 10 percent Avg(Enrollment.grade) AS GPA, Enrollment.sid 
     FROM Enrollment 
     GROUP BY Enrollment.sid 
     ORDER BY Avg(Enrollment.grade)
) Honors, Students 
WHERE Students.sid = Honors.sid;

**16.1 Explain the following terms: virtual memory, page fault, thrashing.** _Virtual memory_ maps memory addresses used by programs to physical addresses in memory hardware, thus Main storage as seen by a process or task appears as a contiguous address space. _Page fault_ is a trap raised by the hardware when a program accesses a page that is mapped in the virtual address space, but not loaded in physical memory. _Thrashing_ occurs when a computer's virtual memory subsystem is in a constant state of paging, rapidly exchanging data in memory for data on disk, to the exclusion of most application-level processing, which causes the performance of the computer to degrade or collapse. **16.2 What is a Branch Target buffer? Explain how it can be used in reducing bubble cycles in cases of branch misprediction** The _branch target buffer_ is a true cache, the full PC value must be conpared to validate that this is a branch instruction before taking any action which reduces the penalty by predicting the path of the branch, computing the target of the branch and caching the information used by the branch. There will be no stalls if the branch entry found on BTB and the prediction is correct, otherwise the penalty will be at least two cycles. **16.3 Describe direct memory access (DMA). Can a user level buffer/pointer be used by kernel or drivers? ** _DMA_ is a feature that allows certain hardware subsystems within the computer to access system memory independently of the CPU. By using DMA, drivers can access the memory allocated to the user level buffer/pointer. **16.5 Write a program to find whether a machine is big endian or little endian.**

bool check_little_endian()
{
   union{
       int a;
       char b;
   }c;
   c.a = 1;
   return c.b ? true : false;
}

bool check_little_endian()
{
    short int a = 0x0001;
    char* b = (char*)&a;
    return b[0] ? true : false;
}

**16.6 Discuss how would you make sure that a process doesn’t access an unauthorized part of the stack ** For native code there is the possiblility of stack overflow and remember in a multi-threaded environment, there can be multiple stacks in a process and nothing can fully prevent process access memory addresses. We can build a sandbox for the program and vm is a good example. **16.8 A device boots with an empty FIFO queue. In the first 400ns period after startup, and in each subsequent 400ns period, a maximum of 80 words will be written to the queue. Each write takes 4ns. A worker thread requires 3ns to read a word, and 2ns to process it before reading the next word. What is the shortest depth of the FIFO such that no data is lost?**   **16.9 Write an aligned malloc & free function that takes number of bytes and aligned byte (which is always power of 2) EXAMPLE align_malloc(1000,128) will return a memory address that is a multiple of 128 and that points to memory of size 1000 bytes aligned_free() will free memory allocated by align_malloc **

void* align_malloc(size_t bytes, size_t aligned){
    void* p1; // original block
    void** p2; // aligend block
    // extra space for storing p1 and alignment
    int offset = aligend - 1 + sizeof(void*); 
    if ((p1 = (void*)malloc(bytes + offset)) == NULL)
        return NULL;
    // make sure p2 minus the extra space address and the result is aligned
    p2 = (void**)(((size_t)(p1) + offset) & ~(aligend - 1)); 
    p2[-1] = p1; //store p1 for free operation
    return p2;
}

void align_free(void* p){
    free(((void**)p)[-1]);
}

**16.10 Write a function called my2DAlloc which allocates a two dimensional array. Minimize the number of calls to malloc and make sure that the memory is accessible by the notation arr[i][j] **

int** my2DAlloc(int r, int c){
    int header = r * sizeof(int*);
    int data = r * c * sizeof(int);
    int** arr = (int**)malloc(header + data);
    int* buf = (int*)(arr + r); // save space for r ptrs
    for(int i =0; i< r; ++i)
        arr[i] = buf + i * c; //every ptr points to the right place which works for arr[i][j]
    return arr;
}

**17.1 Explain what happens, step by step, after you type a URL into a browser. Use as much detail as possible.** 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): 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.). **17.5 What are the differences between TCP and UDP?** TCP is a connection-oriented protocol and it's reliable, ordered and heavyweight. UDP is connectionless protocol and it's unreliable, not ordered and lightweight. **18.1 What’s the difference between a thread and a process?** A process can be thought of as an instance of a program in execution. Each process is an independent entity to which system resources (CPU time, memory, etc ) are allocated and each process is executed in a separate address space. A thread uses the same heap space of a process. A process can have multiple threads. Each thread still has its own registers and its own stack, but other threads can read and write the heap memory. **18.2 How can you measure the time spent in a context switch?** If the total timeof execution of all the processes was T, then the context switch time = T – (SUM for all processes (waiting time + execution time)). Overall, we can say that this is mostly an approximate calculation which depends on the underlying OS. **18.3 Implement a singleton design pattern as a template such that, for any given class Foo, you can call Singleton::instance() and get a pointer to an instance of a singleton of type Foo. Assume the existence of a class Lock which has acquire() and release() methods How could you make your implementation thread safe and exception safe?**

class Lock {
public:
    Lock();
    ~Lock();
    void AcquireLock(){};
    void RelaseLock(){};
};

template  class Singleton{
public:
    Singleton();
    ~Singleton(){
        if (object != 0)
            delete object;
    }
    static T* instance();
private:
    static Lock lock;
    static T* object;
};

template 
Lock Singleton::lock;

template 
T* Singleton::object;

template 
T* Singleton::instance(){
    if(object == 0){
        lock.AcquireLock();
        if (object == 0) {
            object = new T;
        }
        lock.RelaseLock();
    }
    return object;
}

int main(int argc, char const *argv[])
{
    int* stest = Singleton::instance();
    return 0;
}

**18.5 i) Can you design a mechanism to make sure that B is executed after A, and C is ex - ecuted after B? ii) Suppose we have the following code to use class Foo We do not know how the threads will be scheduled in the OS Foo f; f.A(.....); f.B(.....); f.C(.....); f.A(.....); f.B(.....); f.C(.....); Can you design a mechanism to make sure that all the methods will be executed in sequence?** i)

Semaphore a(0),b(0);
A {
   ...
   a.Release(1);
}
B {
   a.Acquire(1);
   ....
   b.Release(1);
}
C {
   b.Acquire(1);
   ...
}

ii)

Semaphore a(0),b(0),c(1);
A {
   c.Acquire(1);
   ...
   a.Release(1);
}
B {
   a.Acquire(1);
   ....
   b.Release(1);
}
C {
   b.Acquire(1);
   ...
   c.Release(1);
}

7.7 Explain how you would design a chat server In particular, provide details about the various backend components, classes, and methods. What would be the hardest problems to solve?

We can learn from twitter and QQ server design. The main concepts of the chat server would be user(status), chat group and messages.

enum Status{offline, online, away}
struct Message{ User from_user; User to_user; String post_message;}
class User {Status type; Message posts[]; sendMessage(); addGroup(); updateStatus(); createGroup(); }
struct Group { Message posts[]; User list[];}

Information sync with memory cache and database; Server scale; User session management;

7.9 Explain the data structures and algorithms that you would use to design an in-memory file system. Illustrate with an example in code where possible

File system must inlude dir and file structure. The key points are design of super block, directory and inodes. Super block mainly deal with namespace and organize inodes, which we could use hash table for fast fetching. Inodes contains meta data and organize datas, which we could use B tree (memory efficient) or radix tree(linux, fast fetching) or log structure (journaling tech for availability). Directory mainly deal with file lookup operations which convert string path to the rightful inode.

7.10 Describe the data structures and algorithms that you would use to implement a garbage collector in C++

Organize object with Smart ptr using reference counting tech(bad with dead lock). Will java’s mark-sweep tech work?

8.1 Write a method to generate the nth Fibonacci number

def fibonacci(n):
    a,b=0,1
    while(n>0):
        a,b,n=b,a+b,n-1
    return a

8.2 Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot? FOLLOW UP Imagine certain squares are “off limits”, such that the robot can not step on them. Design an algorithm to get all possible paths for the robot.

Using DFS and traceback to print all paths.

8.3 Write a method that returns all subsets of a set.

It’s easy to solve this problem using 2^n bitmap for all subsets status and go thourgh to print corresponding subset.

def subsets(a, idx, len):
    sbs = []
    if idx == len:
        sb = []
        sbs.append(sb) #empty set
        print(sb)
    else:
        rsb = subsets(a, idx+1, len)
        e = a[idx]

    #print(idx,rsb)
    for i in rsb:
        t1 = i[:]
        sbs.append(t1) #keep origin
        t2 = i[:]
        t2.append(e) #add new elm
        sbs.append(t2)
        print(t2)
return sbs</pre>

8.4 Write a method to compute all permutations of a string.

void permutations(const string &s, vector &v){
    if (s == “”){
        v.push_back(s);
    }else{
        string c = s.substr(0, 1); // substr(offset, len)
        vector vt;

    permutations(s.substr(1), vt); // get rest permutations
    for (std::vector::iterator i = vt.begin(); i != vt.end(); ++i)
    {
        v.push_back(*i);
        //insert in any space between the character to get permutation
        for (int j = 0; j <= i->length(); ++j)
        {
            string st = *i; //copy one
            st.insert(j, c);
            v.push_back(st);
        }

    }
}

}
if duplicate character is allowed which may result in duplicate answers then

void unique_permutations(const string &s, set &v){
    if (s == “”){
        v.insert(s);
    }else{
        for (int i = 0; i < s.length(); ++i){
            string c = s.substr(i, 1); // substr(offset, len)
            string t = s; //copy one for erase
            set vt;
            unique_permutations(t.erase(i, 1), vt); // get rest permutations
            for (std::set::const_iterator i = vt.begin(); i != vt.end(); ++i)
            {
                v.insert(i);
                v.insert(c + i);
            }
        }
    }
}

8.5 Implement an algorithm to print all valid (e g , properly opened and closed) combi -nations of n-pairs of parentheses EXAMPLE: input: 3 (e g , 3 pairs of parentheses) output: ()()(), ()(()), (())(), ((()))

void paretheses(int n, int idx, int len, string res){
    int i, j;
    int remain = idx + 1;
    if(n == len){
        res += “(“;
        for(j = remain; j > 0; –j){
            res += “)”;
        }
        cout<<res<<”,”;
        }else{
                 res += “(“;
                 for(i = remain; i >= 0; –i){
            string tmp = res;

        for(j = i; j > 0; --j){
            tmp += ")";
        }

        paretheses(n + 1, remain - i, len, tmp);

    }
}

}
8.6 Implement the “paint fill” function that one might see on many image editing programs. That is, given a screen (represented by a 2 dimensional array of Colors), a point, and a new color, fill in the surrounding area until you hit a border of that color’.

Using recursive DFS or better using BFS way to search, no need to traceback so pretty easy.

8.7 Given an infinite number of quarters (25 cents), dimes (10 cents), nickels (5 cents) and pennies (1 cent), write code to calculate the number of ways of representing n cents

It could be solved by generating function, but a little bit complicate:

int cents[] = {1, 5, 10, 25};
int caculate(int n){
    int i, j, k, res;
    int c1 = new int[n+1];
    int c2 = new int[n+1];
    for(i=0; i<=n; ++i){
        c1[i] = 1;  //firstly one cent
        c2[i] = 0;
    }

//then 5, 10, 25 cents
for(i=1; i<=3; ++i){

    for(j=0; j<=n; ++j){
        for(k=0; k+j<=n; k+=cents[i]){
            c2[j+k] += c1[j];
        }
    }

    for(j=0; j<=n; ++j){
        c1[j] = c2[j];
        c2[j] = 0;
    }
}

res = c1[n];

delete[] c1;
delete[] c2;

return res;

}
or using a recursive method:

int caculate2(int sum, int c, int n){
    int ways = 0;
    int i;
    if(sum <= n){
           if(sum == n) return 1;
                for(i=3; i>=0; –i){
                if(c >= cents[i])
            ways += caculate2(sum+cents[i], cents[i], n);
        }
    }
    return ways;
}

9.2 Write a method to sort an array of strings so that all the anagrams are next to each other

Simply sort every string alphabetically first and then compare with other strings (c++ string could use “>” op to compare).

9.3 Given a sorted array of n integers that has been rotated an unknown number of times, give an O(log n) algorithm that finds an element in the array.You may assume that the array was originally sorted in increasing order EXAMPLE: Input: find 5 in array (10 14 15 16 19 20 25 1 3 4 5 7) Output: 10 (the index of 5 in the array)

int search(int n, int a[], int len){
    int low, high, mid;
    low = 0, high = len-1;
    while(low<=high){
       mid = (low + high)/2;
       if(a[mid] == n){
          return mid;
       }else if (a[mid] < n){ //25 1 3 4 5 7 10 14 15 16 19 20
           if(a[mid] < a[low]){
               if(a[low] < n) high = mid -1;
               else low = mid + 1;
           }else
               low = mid + 1;
       }else if (a[mid] > n){
           if(a[mid] < a[low]) high = mid -1;
           else{
              if(a[low] < n) high = mid - 1;
              else low = mid + 1;
           }
       }
    }
}

9.4 If you have a 2 GB file with one string per line, which sorting algorithm would you use to sort the file and why?

 

9.5 Given a sorted array of strings which is interspersed with empty strings, write a method to find the location of a given string
Example: find “ball” in [“at”, “”, “”, “”, “ball”, “”, “”, “car”, “”, “”, “dad”, “”, “”] will return 4
Example: find “ballcar” in [“at”, “”, “”, “”, “”, “ball”, “car”, “”, “”, “dad”, “”, “”] will return -1

Using binary search method just moving right to neglect empty strings.

9.6 Given a matrix in which each row and each column is sorted, write a method to find an element in it.
Just search line by line in O(m+n) time:

int search_matrix(int mat[][], int m, int n, int x){
    int row = 0, col = n-1;
    while(row<=m && col >=0){
        if(mat[row][col] == x) return row * n + col;
        else if(mat[row][col] > x) –col;
        else  ++row;
    }
}

Binary search method also works:

int search_matrix(int mat[][], int m, int n, int x){
    int r1 = 0, c1 = 0;
    int r2 = m-1, c2 = n-1;
    int i = (r1+r2)/2, j = (c1+c2)/2;
    while((i!=r1||i!=r2) && (j!=c1||j!=c2)){ //may have some problems
        if(mat[i][j] == x)
           return in+j;
        else if(mat[i][j] < x){
            r2 = i, c2 = j;
        }else {
            r1 = i, c1 = j;
        }
        i = (r1+r2)/2, j = (c1+c2)/2;
    }
}

*9.7 A circus is designing a tower routine consisting of people standing atop one another’s shoulders. For practical and aesthetic reasons, each person must be both shorter and lighter than the person below him or her. Given the heights and weights of each person in the circus, write a method to compute the largest possible number of people in such a tower.
EXAMPLE:
Input (ht, wt): (65, 100) (70, 150) (56, 90) (75, 190) (60, 95) (68, 110)
Output:The longest tower is length 6 and includes from top to bottom: (56,90) (60,95) (65,100) (68,110) (70,150) (75,190)

It’s a LIS problem which can be solved in O(nlgn) by mento and binary search. (hdu1025)

10.2 There are three ants on different vertices of a triangle. What is the probability of collision (between any two or all of them) if they start walking on the sides of the triangle? Similarly find the probability of collision with ‘n’ ants on an ‘n’ vertex polygon.

Q1:For three ants and triangle, every ant has two directions and vertices to crawl, so there will be 2^3 conditions and only when all ants choose the same direction(clockwise or anticlockwise) will lead them not to collision. So probability of collision is 1 - 2/2^3

Q2: Similarly, probability of collision is 1 - 2/2^n

10.3 Given two lines on a Cartesian plane, determine whether the two lines would intersect.

line is different from segment, but the latter is more difficlut to judge if intersect with each other which could be solved by vector multiply.

10.4 Write a method to implement *, - , / operations You should use only the + operator

For multiply operation:

for i in range (1,n):
         res+=m

For minus operation:

for i in range(0,n):
     if (i + m == n):
         return i

For division operation:

res=0
for i in range(1,m):
    res+=n
    if(res==m):
       return i
    if(res>m):
       return i-1

10.5 Given two squares on a two dimensional plane, find a line that would cut these two squares in half

Any line go though the center of square would cut it in half, so a line go though both squares’ center would be the answer. Just be careful with the case that both sqaures’ center are the same point.

10.6 Given a two dimensional graph with points on it, find a line which passes the most number of points

Rather than using two points pair methond to represent the segment(we could also go though and check every pair in O(n^3) time), we could use slope and y-intercept thus this problem is no different than finding most common number in a list of numbers.

10.7 Design an algorithm to find the kth number such that the only prime factors are 3, 5, and 7

Using O(n^2) time to caculate one by one, which can be accelerated by hash list to reduce repeated aculation(hdu1058)

11.2 You are given the source to an application which crashes when it is run. After running it ten times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one?

Memory leak causes out of memory and leads to crash or variable is not initialized with proper value. Unproper system configuration could also leads to crash (eg. max fd or max thread numbers) and sometimes interacting with hardware may also cause such problems.

11.3 We have the following method used in a chess game: boolean canMoveTo(int x, int y) x and y are the coordinates of the chess board and it returns whether or not the piece can move to that position. Explain how you would test this method

Invalid conditions for four corners and all possible move in board.
Valid conditions for all direction and all pieces.

11.4 How would you load test a webpage without using any test tools?

Load test usaually includes thoughput, response time, resource utilization and pressure tests.

11.5 How would you test an ATM in a distributed banking system?

Test should include UI test (accessiblity test) and functional test (single machine test and ditributed system test).

12.1 If you were integrating a feed of end of day stock price information (open, high, low, and closing price) for 5,000 companies, how would you do it? You are responsible for the development, rollout and ongoing monitoring and maintenance of the feed. Describe the different methods you considered and why you would recommend your approach.The feed is delivered once per trading day in a comma separated format via an FTP site. The feed will be used by 1000 daily users in a web application.

This problem actually ask you how to store this feed. SQL Database would be a good choice. NoSQL storage engine like mogodb would also do the job. Format could be XML or JSON.

12.2 How would you design the data structures for a very large social network (Facebook, LinkedIn, etc)? Describe how you would design an algorithm to show the connection, or path, between two people (eg, Me->Bob->Susan->Jason->You)

Using array to store friends’ id so a graph in general. We could use other information to seperate people’s information cleverly.

12.3 Given an input file with four billion integers, provide an algorithm to generate an integer which is not contained in the file. Assume you have 1 GB of memory. FOLLOW UP What if you have only 10 MB of memory?

If 1 GB memory we could simply use bitmap approach. For 10 MB memory we have to deal with blocks of numbers firstly using counting method and then deal with proper blocks using bitmap.

12.4 You have an array with all the numbers from 1 to N, where N is at most 32,000. The array may have duplicate entries and you do not know what N is. With only 4KB of memory available, how would you print all duplicate elements in the array?

Just use bitmap method as we have space for 0 ~ 42^108 which is exactly bigger than 32,000.

12.5 If you were designing a web crawler, how would you avoid getting into infinite loops?

Simply try DFS or BFS approach to go through the whole gragh which means you have got a map to store the all urls as points.

12.6 You have a billion urls, where each is a huge page. How do you detect the duplicate documents?

You have to check the content of huge web page for url rather than url it self. To content comparing we could use hash finger method(or other similar method), then we’ve got a billion finger prints which is still a large number. We could hash those finger prints to different files and deal with every file in memory one by one or hash those to different machine.

12.7 You have to design a database that can store terabytes of data. It should support efficient range queries. How would you do it?

Using B+ tree to build the database.

Python可以很简单实现C语言中for(i = len; i>=0; –i)的逆序循环，而且有不止一种写法：

第一种，for i in range(len, -1, -1) ，简单易懂

第二种，for i in range(0, len+1)[::-1]，利用list的[start:end:step]排序功能，当然在大数组下性能堪忧

1. 1 Implement an algorithm to determine if a string has all unique characters. What if you can not use additional data structures?

It’s means to check if a string has repeated character or not. It can be solved by using a bitmap and Assic table(128 for normal and 256 with special). key: using n=(int)string[i] to get Assic number and (bitmap[n/32] & 1<<(n%32)) to check if repeated.

1.2 Write code to reverse a C-Style String (C-String means that “abcd” is represented as five characters, including the null character )?

Exchange characters between start index 0 and end index string length - 1, stop when two pointers meet.

1.3 Design an algorithm and write code to remove the duplicate characters in a string without using any additional buffer. NOTE: One or two additional variables are fine. An extra copy of the array is not. FOLLOW UP Write the test cases for this method ?

Not allowed to apply for new arrays. Compare each characters in the string and if duplicated just remove in place, key: using null character to replace duplicated character. Test cases should include unique characters string, null string, string with only one character, common string with sequence duplicate characters or with not.

1.4 Write a method to decide if two strings are anagrams or not ?

If new array is allowed to apply for, it can be solved by counting table in O(n) time. Actually sort two strings and compare each characters is enough to get the answer in O(nlgn) time.

1.5 Write a method to replace all spaces in a string with ‘%20’ .

Firstly count the ectra space needed by replacing, two chars’ space for each character. If space is enough then just fill and move, otherwise you should realloc space and copy whole string, don’t forget the null character.

1.6 Given an image represented by an NxN matrix, where each pixel in the image is 4 bytes, write a method to rotate the image by 90 degrees Can you do this in place ?

To rotate 90 degrees in clockwise just exange M[i][j] with M[j][N-i], implementation could firstly exange elms between diagonal and then exange columns i with N-i

1.7 Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column is set to 0.

Go through the matrix only to register which column or row has zero and then go through the matrix again to set those rows or columns to zero which takes O(mn) time, key: only need array row[m] nd column[n]

1.8 Assume you have a method isSubstring which checks if one word is a substring of another. Given two strings, s1 and s2, write code to check if s2 is a rotation of s1 using only one call to isSubstring (i e , “waterbottle” is a rotation of “erbottlewat”)

To use isSubstring function we need string s1 is longer than s2, so just duplicate s1 by s1’ = s1 + s1 (s1’ contains all rotations of s1) then check if s2 is substring of s1’ to judge rotaion.

2.1 Write code to remove duplicates from an unsorted linked list FOLLOW UP How would you solve this problem if a temporary buffer is not allowed?

Using hash table could be the best way. If temporay buffer is not allowed then just using algorithm in 1.3 taking O(n^2) time.

2.2 Implement an algorithm to find the nth to last element of a singly linked list.

Using two pointers at a distance of n to solve. Another way is using recursion as stack.

2.3 Implement an algorithm to delete a node in the middle of a single linked list, given only access to that node

EXAMPLE
Input: the node ‘c’ from the linked list a->b->c->d->e
Result: nothing is returned, but the new linked list looks like a->b->d->e

Just copy the data from next node and delete next node by pointing the next pointer field to the node after next node. Note that there would be a problem if the node is the last node in the list.

2.4 You have two numbers represented by a linked list, where each node contains a single digit The digits are stored in reverse order, such that the 1’s digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list

EXAMPLE
Input: (3 -> 1 -> 5) + (5 -> 9 -> 2)
Output: 8 -> 0 -> 8

Just pay attention to null list and list in different length.

3.1 Describe how you could use a single array to implement three stacks

It’s easy to implement with three stack top pointers to seperate space.

3.2 How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time

It’s hard to deal with the pop when min element was on the top of the stack. So extra space are needed to store those bigger elms. An extra stack could be used to store min elms. Every time you push a new elem, compare it with the top of extra stack and smaller one has to be pushed into extra stack. The same, when pop out a elem you should check if it equal to the top of extra stack and if so you have to pop it out from the extra stack.

3.3 Imagine a (literal) stack of plates. If the stack gets too high, it might topple. Therefore, in real life, we would likely start a new stack when the previous stack exceeds some threshold. Implement a data structure SetOfStacks that mimics this. SetOfStacks should be composed of several stacks, and should create a new stack once the previous one exceeds capacity. SetOfStacks push() and SetOfStacks pop() should behave identically to a single stack (that is, pop() should return the same values as it would if there were just a single stack) FOLLOW UP Implement a function popAt(int index) which performs a pop operation on a specific sub-stack

It’s worth implementing in C++

3.4 In the classic problem of the Towers of Hanoi, you have 3 rods and N disks of different sizes which can slide onto any tower The puzzle starts with disks sorted in ascending order of size from top to bottom (e g , each disk sits on top of an even larger one) You have the following constraints:
(A) Only one disk can be moved at a time
(B) A disk is slid off the top of one rod onto the next rod
(C) A disk can only be placed on top of a larger disk
Write a program to move the disks from the first rod to the last using Stacks

void hanoi(int n, char src, char bri, char dst){
    if(n==1){
        cout<<"Move disk "<<n<<" from "<<src<<" to "<<dst<<endl;
    }
    else{
        hanoi(n-1, src, dst, bri);
        cout<<"Move disk "<<n<<" from "<<src<<" to "<<dst<<endl;
        hanoi(n-1, bri, src, dst);
    }
}
`</pre>
You should change it with using stack

**3.5 Write a program to sort a stack in ascending order. You should not make any assumptions about how the stack is implemented. The following are the only functions that should be used to write this program: push | pop | peek | isEmpty.**

If only stack could be used then an extra stack is needed to simulate insert sort

**4.1 Implement a function to check if a tree is balanced. For the purposes of this question, a balanced tree is defined to be a tree such that no two leaf nodes differ in distance from the root by more than one**

Just get every leaf node's depth by tree walk(time O(n)) and store them (space O(n/2)) then go through the array to judge if the tree is unbalanced or check the tree in a postorder that is recursively down and then judge.

**4.2 Given a directed graph, design an algorithm to find out whether there is a route between two nodes**

Using BFS to find.

**4.3 Given a sorted (increasing order) array, write an algorithm to create a binary tree with minimal height **

It's easy to use recursion way to build the tree with limited length. You can use binary search way to build binary search tree.

**4.4 Given a binary search tree, design an algorithm which creates a linked list of all the nodes at each depth (ie , if you have a tree with depth D, you’ll have D linked lists) **

Just walk though the tree and link those nodes to the linked lists based on the depth of the nodes. A better solution is using BFS way to walk though the tree.
<pre>`void tree_level_walk(struct bt_tree* root, vector&lt;list&gt; &amp;res){
    list ltmp;
    list::iterator it;
    struct bt_tree* tmp;
    int depth = 1;

    ltmp.push_back(root);
    res[depth].push_back(ltmp);

    while(!res[depth].empty()){ // check every level
        ltmp.clear();
        for(it=res[depth].begin(); it!=res[depth].end(); ++it){ // using list as queue to store all next level nodes
            tmp = *it;
            if(tmp-&gt;left) ltmp.push_back(tmp-&gt;left);
            if(tmp-&gt;right) ltmp.push_back(tmp-&gt;right);
        }
        ++depth;
        res[depth].push_back(ltmp);
    }
}
`</pre>
**4.5 Write an algorithm to find the ‘next’ node (ie , in-order successor) of a given node in a binary search tree where each node has a link to its parent**
<pre>`def tree_successor(self, node):
     if node.right != None:
          return tree_min(node.right)
     tmp = node.parent
     while tmp != None and node == tmp.right:
          node = tmp
          tmp = node.parent
     return tmp
`</pre>
**4.6 Design an algorithm and write code to find the first common ancestor of two nodes in a binary tree. Avoid storing additional nodes in a data structure. NOTE: This is not necessarily a binary search tree **

If you want store all ancestor of one node to check then using hash table instead of simple array. But it requires every node has a link to its parent and additional space. Else you can start from root and using recursive way to find result and take over very time you find a closer one.
<pre>`bool father(struct bt_tree* n1, struct bt_tree* n2){
    if(n1 == NULL) return false;
    else if(n1 == n2) return true;
    else return father(n1-&gt;lchild, n2) || father(n1-&gt;rchild, n2);
}

void find_ancestor(struct bt_tree* head, struct bt_tree* n1, struct bt_tree* n2, struct bt_tree** res){
    if(head == NULL) return;
    if(head &amp;&amp; father(head, n1) &amp;&amp; father(head, n2)){
        res = head; 
        find_ancestor(head-&gt;left, n1, n2, res);
        find_ancestor(head-&gt;right, n1, n2, res);
    }
}`</pre>
Here is a better solution to check less node
<pre>`struct bt_tree* find_ancestor(struct bt_tree* head, struct bt_tree* n1, struct bt_tree *n2){
     if(head == NULL) return NULL;
     if(head == n1 || head == n2) return head; //check if ancestor
     struct bt_tree* left = find_ancestor(head-&gt;left, n1, n2);
     struct bt_tree* right = find_ancestor(head-&gt;right, n1, n2);
     if(left &amp;&amp; right) return head;
     return left?left:right;
}`</pre>
**4.7 You have two very large binary trees: T1, with millions of nodes, and T2, with hundreds of nodes. Create an algorithm to decide if T2 is a subtree of T1**

Using BFS way to go though T1 and compare with T2 if the node is equal with T2's root. Using string comparing technique is a better way for it's easier to store in disk file so just compare inorder and preoder sequence. It's a really hard to deal with such big data.

**4.8 You are given a binary tree in which each node contains a value. Design an algorithm to print all paths which sum up to that value. Note that it can be any path in the tree it does not have to start at the root. **

You can walk though the tree and backtrace every node if it has a link to parent to calculate the sum and judge.

**5.1 You are given two 32-bit numbers, N and M, and two bit positions, i and j. Write a method to set all bits between i and j in N equal to M (eg, M becomes a substring of N located at i and starting at j)
EXAMPLE:
Input: N = 10000000000, M = 10101, i = 2, j = 6
Output: N = 10001010100**

(N ^ ~(1&lt;&lt;(j-i+1)-1)&lt;&lt;i) | (M&lt;&lt;i)

**5.2 Given a (decimal - eg 3.72) number that is passed in as a string, print the binary representation. If the number can not be represented accurately in binary, print “ERROR”**

Using '%' op to deal with integer part and  multiply op to deal with decimal part which should be finished the same time s as its length, for example  decimal part of 3.72  should be finished in two times of multiply or should print "ERROR"

**5.3 Given an integer, print the next smallest and next largest number that have the same number of 1 bits in their binary representation**

To make a larger number just find the 1st zero bit after 1 bits and change that bit into 1 and set all lower bit into 0, in the mean time of going though the number remember to count the number of 1 bit (not including the last 1 bit before the changed bit) and then set the same number of 1 bit from the lowest bit place. A better way to count 1 bit is using following method:
<pre>`
int count_one(int x){
    x = (x &amp; (0x55555555)) + ((x &gt;&gt; 1) &amp; (0x55555555));
    x = (x &amp; (0x33333333)) + ((x &gt;&gt; 2) &amp; (0x33333333));
    x = (x &amp; (0x0f0f0f0f)) + ((x &gt;&gt; 4) &amp; (0x0f0f0f0f));
    x = (x &amp; (0x00ff00ff)) + ((x &gt;&gt; 8) &amp; (0x00ff00ff));
    x = (x &amp; (0x0000ffff)) + ((x &gt;&gt; 16) &amp; (0x0000ffff));
    return x;
}

To make a lower number is the same just find the 1st 1 bit after zero bits and count 1 bits(including the changed bit) and then set.
Yet you should be careful with the negative numbers.

5.4 Explain what the following code does: ((n & (n-1)) == 0)

To check if n is power of 2.

5.5 Write a function to determine the number of bits required to convert integer A to integer B
Input: 31, 14
Output: 2

Using (1<<i) and operation and to go though two number and count how many bit are different. A better way is to count the 1 in result of A ^ B.

5.6 Write a program to swap odd and even bits in an integer with as few instructions as possible (eg, bit 0 and bit 1 are swapped, bit 2 and bit 3 are swapped, etc)

((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1)

5.7 An array A[1…n] contains all the integers from 0 to n except for one number which is missing. In this problem, we cannot access an entire integer in A with a single operation. The elements of A are represented in binary, and the only operation we can use to access them is “fetch the jth bit of A[i]”, which takes constant time. Write code to find the missing integer. Can you do it in O(n) time?

Testing number of every bit in the array to select the minimal part and make the missing element.

def find_missing(a[], n):
     len = n-1
     column = lg(n)
     res = 0
     for j in range(column-1, 0, -1):
          count0=count1=0
          a1=a2=[]
          for i in a:
              if (getBit(i, j)):
                  a1[count1++]=i
              else:
                  a0[count0++]=ai
          if count1 >= count0: #may have problem when count eqs to zero
              a=a0, len = count0
          else:
              a=a1, len = count1
              res+=(1<<j)
     return res

Remember missing one number problem can always be solved by sumup(1,n)-sumup(a[1],a[n])

6.1 Add arithmetic operators (plus, minus, times, divide) to make the following expression true: 3 1 3 6 = 8 You can use any parentheses you’d like

(3+1)/3*6=8

6.2 There is an 8x8 chess board in which two diagonally opposite corners have been cut off You are given 31 dominos(多米诺骨牌), and a single domino can cover exactly two squares Can you use the 31 dominos to cover the entire board? Prove your answer (by providing an example, or showing why it’s impossible)

As two corners painted in the same color are cut off. It’s imporssible to cover with uncoupled numbers of squares.

6.3 You have a five quart jug and a three quart jug, and an unlimited supply of water (but no measuring cups) How would you come up with exactly four quarts of water? NOTE: The jugs are oddly shaped, such that filling up exactly ‘half’ of the jug would be impossible

Firstly using full five quart jug minus three quart jug(5-3=2), then put the rest in three quart jug(3-2=1) and then use full five quart jug to fill three quart jug(5-1=4).

6.4 A bunch of men are on an island A genie comes down and gathers everyone together and places a magical hat on some people’s heads (ie , at least one person has a hat) The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat.

All men on the island knowns there exists at least one hat. So one hat takes one day, two hats take two days and c hats take c days to remove.

6.5 There is a building of 100 floors If an egg drops from the Nth floor or above it will break If it’s dropped from any floor below, it will not break You’re given 2 eggs Find N, while minimizing the number of drops for the worst case.

Using section to reduce number of drops, x + (x-1) + (x-2) + ... + 1 >= 100 and x eqs to 14 then sections will be 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99, 100 and then first egg to test the section and second egg to test level sequencely.

6.6 There are one hundred closed lockers in a hallway. A man begins by opening all one hundred lockers. Next, he closes every second locker. Then he goes to every third locker and closes it if it is open or opens it if it is closed (eg , he toggles every third locker). After his one hundredth pass in the hallway, in which he toggles only locker number one hundred, how many lockers are open?

Except 1 and the number itself, if the number i can be divided exactly by factor a then it can be diveded exactly by factor i/a meaning that number of factors would be even. Only when i=i/a the number of factors will become odd and the number i must be the full square so from 1 to 100 will be 10 lockers remain open.