Log-structured File System Notes

Assumption

Log-structured file systems are based on the assumption that files are cached in main memory and that increasing memory sizes will make the caches more and more effective at satisfying read requests. As a result, disk traffic will become dominated by writes.

Problems of existing file systems

• 1. Spread information around the disk (separate inode from file content).

• 2. File systems tend to write synchronously: the application must wail for the write rather than continuing while the write is handled in the background.

Log-structured file system

The goal is to improve write performance by buffering a sequence of file system changes in the file cache and then writing all the changes to disk sequentially in a single disk write operation.

Two key design issues:

• 1. How to retrieve information from the log.

• 2. How to manage the free space on disk.

Reference

http://www.cs.berkeley.edu/~brewer/cs262/LFS.pdf

Paxos Algorithm

The Paxos algorithm is a consensus algorithm for a fault-tolerant distributed system. A consensus algorithm ensures that a single one among the proposed valued is selected. In Paxos, there are three types of agent: proposers, accepters, learners.

The algorithm runs as follows:

1. A proposer selects a proposal number (integer) n and sends to a majority of acceptors. This is called a 'prepare' request. Here majority means greater than half of the acceptors. If an acceptor receives a 'prepare' request with number n greater than that of any 'prepare' request to which it has already responded, then it responds to the request with a promise not to accept any more proposals numbered less than n and with the highest-numbered proposal (if any) that it has accepted.

2. If the proposer receives a response to its prepare requests from a majority of acceptors, it send an 'accept' request to each of those acceptors for a proposal for a proposal numbered n with a value v. The v is the value of the highest-numbered proposal among the responses, or is any value if the responses reported no proposals. If an acceptor receives an 'accept' request numbered n, it must accept it if and only if it has not already promised to only consider proposals having an identifier greater than N.

3. Each acceptor responds to all learners whenever it accept a proposal.

C++ next_permutation implementation

template<typename Iter>
bool next_permutation(Iter first, Iter last) {
    // Empty
    if (first == last) return false;
    Iter i = first;
    ++i;
    // Only one element
    if (i == last) return false;
    i = last;
    --i;
       
    for(;;) {
        Iter ii = i;
        --i;
        // Check if there are two adjacent elements
        // such that the first one is smaller than the second one
        if (*i < *ii) {
            Iter j = last;
            // Find the first element that are bigger than i
            while (!(*i < *--j)) {}
            std::iter_swap(i, j);
            // Reverse the decreasing sequence
            std::reverse(ii, last);
            return true;
        }
        // No, this is the last permutation
        if (i == first) {
            std::reverse(first, last);
            return false;
        }
    }
}

Codeforces 216A

Here is the link: http://www.codeforces.com/problemset/problem/216/A

Basically you can think of the hexagon as a cuboid which you can see the top, front, and right side. So given a, b and c, the number of tiles is a * b * c - (a - 1) * (b - 1) * (c - 1). Pretty tricky, right?

Java Annotation

It's a great technology that helps your class focuses on what should be done, reduces the complexity of your class and makes your code clean. Here let's go through our own JUnit example to see how annotations work.

Here we create our own annotation:

import java.lang.annotation.*;

@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
public @interface Test {

}

Of course, the annotations don't do anything by themselves. We need a tool to process these annotations:

import java.lang.reflect.*;

public class TestRunner {

    public static void runTests(Object obj) {
        try {
            Class cl = obj.getClass();
            for (Method m : cl.getDeclaredMethods()) {
                Test t = m.getAnnotation(Test.class);
                if (t != null) {
                    m.invoke(obj, null);
                }
            }
        } catch (Exception e) {
            e.printStackTrace();
        }
    }
}

Now we can write our own test cases:

public class UnitTest {

    public UnitTest() {
        TestRunner.runTests(this);
    }
 
    @Test
    public void testCase1() {
        System.out.println("Test Case 1");
    }
 
    @Test
    public void testCase2() {
        System.out.println("Test Case 2");
    }
 
    public static void main(String[] args) {
        new UnitTest();
    }
}

Storing Passwords Securely

Storing Passwords Securely

Replace Inheritance with Delegation

The following article introduces replace inheritance with delegation
see: Replace Inheritance with Delegation

DP in Prolog

% My friend asked me to post this code. Take a look!

%

% Write a predicate buy(Stores,Links,MinCustomers) that determines the
% minimum number of customers required to buy all the items on sale in
% an outlet with a given list of Stores and Links connecting them. The
% customers will buy all sales in the Stores one by one, and travel 
% between stores along the available Links. A Store is a term 
% store(Name,Capacity,Bankrupt,Waiting), where: Name is a unique name, 
% Capacity is the number of customers required to buy all the sales in
% the store, Bankrupt is the number of customers bankrupt after buying 
% all sales in the store, and Waiting are the number of customers that
% remain in the store to wait for more sales. Any remaining customers 
% after a store sale that are not Waiting or Bankrupt, can move on to 
% shop in the next store. A link connects two stores, and is represented 
% by a term link(Namel,Name2) (you can assume that the Stores and Links 
% form a connected graph). In your plan, you are free to start at any 
% store, but you should travel at most once in either direction along a 
% link.
% 
% Example:
% buy([store(a,5,5,5),store(b,5,1,1),store(c,10,5,5)],
%     [link(a,b),link(b,c)],
%     MinCustomers).
%
% expecting MinCustomers=17
%
% Implementation: XSB
% Solution:
% Find min-cost hamilton path by dynamic programming (state compressing)
% Total number of states: 2^n * n, n denotes the number of vertice in the
% graph Val[s][j] denotes the min-cost of state s which ends at vertice j.
% The ith bit of s is set if the path has visited vertice i.

:- [basics].
:- [listutil].

buy(Stores, Links, MinCustomers):- 
  length(Stores, N),
  get_directed_links(Links, Lk),
  append(Links, Lk, Mp),
  End is (1 << N),
  dp(1, End, [[0]], Stores, Mp, MinCustomers).

get_directed_links([], []).
get_directed_links([H | T], [L | R]):-
  link(U, V) = H, L = link(V, U), get_directed_links(T, R).

get_min_element(End, End, Col, Stores, Best, Best).
get_min_element(Itr, End, Col, Stores, Cur, Best):-
  Itr1 is Itr + 1,
  ith(Itr1, Stores, Store),
  store(S, C, B, W) = Store,
  ith(Itr1, Col, V),
  P is V,
  (
    (
      P < Cur,
      get_min_element(Itr1, End, Col, Stores, P, Best)
    );
    (
      get_min_element(Itr1, End, Col, Stores, Cur, Best)
    )
  ).

% dynamic programming
dp(End, End, Val, Stores, Map, MinCustomers):-
  ith(End, Val, Col),
  length(Stores, L),
  get_min_element(0, L, Col, Stores, 10000000000, MinCustomers).

dp(Itr, End, Val, Stores, Map, MinCustomers):-
  length(Stores, L),
  search(Itr, 0, L, Val, [], New, Stores, Map),
  append(Val, [New], NewVal),
  Itr1 is Itr + 1,
  dp(Itr1, End, NewVal, Stores, Map, MinCustomers).

search(Level, End, End, Val, New, New, Stores, Map).
search(Level, Itr, End, Val, Cur, New, Stores, Map):-
  Itr1 is Itr + 1,
  X is Level /\ (1 << Itr),
  (
    (
      X is 0,
      append(Cur, [1000000000], Cur1),
      search(Level, Itr1, End, Val, Cur1, New, Stores, Map)
    );
    (
      Level1 is Level - X,
      (
        (
          Level1 is 0,
   I is Itr + 1,
   ith(I, Stores, Store),
   store(S, C, B, R) = Store,
   append(Cur, [C], Cur1),
   search(Level, Itr1, End, Val, Cur1, New, Stores, Map)
 );
 (
   J is Level1 + 1,
   ith(J, Val, Col),
   search1(Itr, 0, End, Col, 1000000000, Best, Stores, Map),
   K is Itr + 1,
   ith(K, Stores, Store),
   store(S, C, B, R) = Store,
   append(Cur, [Best], Cur1),
   search(Level, Itr1, End, Val, Cur1, New, Stores, Map)
 )
      )
    )
  ).

search1(I, End, End, Col, Best, Best, Stores, Map).
search1(I, J, End, Col, Cur, Best, Stores, Map):-
  K is I + 1,
  L is J + 1,
  ith(K, Stores, Store),
  store(S, C, B, W) = Store,
  (
    /* I and J is connected */
    (
      is_connect(J, I, Stores, Map),
      X is J + 1,
      ith(X, Col, V),
      VV is V + B + W,
      (
 (
   VV >= C,
   (
     (
       VV >= Cur,
       search1(I, L, End, Col, Cur, Best, Stores, Map)
     );
     (
       search1(I, L, End, Col, VV, Best, Stores, Map)
     )
   )
 );
 (
   (
     C >= Cur,
     search1(I, L, End, Col, Cur, Best, Stores, Map)
   );
   (
     search1(I, L, End, Col, C, Best, Stores, Map)
   )
 )
      )
    );
    /* I and J is not connected */
    (
      search1(I, L, End, Col, Cur, Best, Stores, Map)
    )
  ).

is_connect(I, J, Stores, Map):-
  X is I + 1,
  Y is J + 1,
  ith(X, Stores, Store1),
  store(N1, C1, B1, W1) = Store1,
  ith(Y, Stores, Store2),
  store(N2, C2, B2, W2) = Store2,
  member(link(N1, N2), Map).

B+ Tree operations

References: http://www.cs.jhu.edu/~hager/Teaching/cs226/Notes/B+Tree.pdf

Linux Command Line Tips

Linux command line tips that every linux user should know:
http://www.linuxstall.com/linux-command-line-tips-that-every-linux-user-should-know/

Parallelism For Prefix Sum

Recently I am studying parallel algorithm. Many algorithms taught in class use prefix sum. Given an array of n elements { a1, a2, a3, ... , an }, we are to calculate n partial sum { s1, s2, ... , sn }, where si = a1 + a2 + ... + ai. It is pretty straight forward that prefix sum is solved by O(n). Can we do better using parallelism?

The answer is yes. We can solve it using classical divide and conquer. Following is the pseudo-code:

This picture better illustrates the idea of above algorithm:

Here is a simple implementation of this algorithm using cilk concurrency platform:

void prefix_sum(LL *a, LL *s, unsigned int len){
    if (len == 1){ 
        s[1] = a[1];
        return ;
    }   
    int itr;
    cilk_for(unsigned int i = 1; i <= len; i++){
        s[i] = a[i];
    }   
    for (itr = 1; (1 << itr) <= len; itr++){
        // cout << itr << endl;
        cilk_for(unsigned int i = (1 << itr); i <= len; i += (1 << itr)){
            s[i] = s[i] + s[i - (1 << (itr - 1))];
        }
    }   
    itr--;
    while (itr >= 0){ 
        cilk_for(unsigned int i = (1 << itr); i <= len; i += (1 << itr)){
            if ((i >> itr) == 1){ 
                s[i] = s[i];
            } else if ((i >> itr) % 2 == 1){ 
                s[i] = s[i] + s[i - (1 << itr)];
            }
        }
        itr--;
    }   
}

Linux Directory Structure

This article illustrates Linux filesystem structure and the meaning of higher-level directories.
See:
http://www.thegeekstuff.com/2010/09/linux-file-system-structure/

Random Selection

Today when I coded ads recommendation for my db project, it reminds me some classical problems about random selection.

Q1. How to randomly select an element from a linked list whose size is unknown.

Node *ret = NULL;
int cnt = 0;

for (Node *p = head; p != NULL; p = p->next){
    if (rand() % ++cnt == 0)
        ret = p;
}

Q2. How to randomly select K elements from a huge linked list whose size is unknown.

Since the linked list is huge, we can assign a random number in [0, 1] to each element as its weight, then we can pick first K maximum-weighted elements.

Another solutions is to select the ith element with probability 1/i. We can prove that each element is selected with probability 1/N.

Ruby methods

Ruby provides way to call and define methods dynamically.

When you invoke a method, you actually send a message to an object. To illustrate this idea, let’s look at the following example.

class MyClass
  def greeting
    "Hello"
  end
end
obj = MyClass.new obj.greeting # => "hello"
obj.send :greeting # => "hello"

We can see that when you call greeting(), it actually goes through send() by sending the name of the method. This technique is called Dynamic Dispatch which means you can decide which method to call at runtime.

In Ruby, you also can define method dynamically with Module#define_method(). All you need to do is to pass a method name and a block.

class MyClass
  define_method :hello do
    "hello"
  end
end

obj = MyClass.new
puts obj.send :hello

With define_method(), we can define general-purpose method template to avoid duplicated code.

Another powerful thing in Ruby is method_missing(). With Ruby, there’s no compiler to check the method calls. So when you call a method that doesn’t existed, Ruby will finally call method_missing which raises NoMethodError. We can override method_missing() to handle no corresponding method. This is called Ghost Method since actually there is no corresponding method that exists.

class MyClass
  def method_missing(name, *args)
    puts "You tried to call #{name}, but this method is undefined"
  end
end

obj = MyClass.new
obj.hello   # => "You tried to call hello, but this method is undefined"

Ruby object model

If you pick up Ruby, you will love it! Currently I am reading the book Metaprogramming Ruby to dive into the depth in Ruby world.

1. Open Classes

You can easily add new methods to classes that has already existed, like the following:

class String
 def to_alphanumeric
  gsub /[^\w\s]/, ''
 end
end 

Now the String class has a new method ‘to_alphanumeric’. In fact, when you define a class, if it is predefined(like String), Ruby will open the existing class and add your methods. Otherwise, Ruby will create a class for you. This technique is simply called Open Class. So, you can overwrite the existing methods.

2. Object and Class Relationship

In Ruby, unlike Java, there is no connection between an object’s class and its instance variables. When you assign values, they just spring into existence in object. Ruby objects hold instance variables and reference to their classes which carry a list of methods. Here is an example:

class A
 def hey
  @v = "hey"
 end
end

obj = A.new
obj.instance_variables # => []
obj.hey
obj.instance_variables # => ["@v"]

Here is the relationship between class and object:

You can see that MyClass is just an object. But what MyClass has is instance methods that objects can call. Be careful with this jargon ‘instance method‘. It actually took me some time to understand this. And you can verify by running following code:

Array.instance_methods == [].methods # => true
Array.methods == [].methods          #=> false

3. Method

When you call a method, Ruby actually does two things:

• Method lookup
• Execute the method

In method lookup, there are concepts receiver and ancestor chain. Receiver is simply the object you call a method on. The ancestor chain is the path from class to its superclass, superclass to superclass’ superclass and so on. Ruby will look at each class’ instance methods along the chain until find the right method. One thing to notice that when you include a module in your class, Ruby creates an anonymous class that wraps the module and add it in the chain. In fact, Object includes module Kernel, that’s why you can call methods like puts, print in your class.

Manacher's algorithm

Longest palindromic substring is the problem of finding a maximum-length substring of a given string that is also a palindrome. Usually this can be done by dynamic programming or suffix array. However, Manacher's algorithm is a more efficient algorithm that takes only O(n) time.

The main idea is to turn odd/even palindromic substring into odd palindromic string. We add special characters among original characters. For example, we convert 'abba' to '#a#b#b#a#', 'aba' to '#a#b#a#'. And add '$' at the front of the string for handling edge cases.

Let's assume S = '1221' as to illustrate our algorithm. S' = '$#1#2#2#1#'. And we let array P to store the extension to the left(or right) in S'. So here,

S  #  1  #  2  #  2  #  1  #

P  1  2  1  2  5  2  1  2  1

P.S. P[i] - 1 is the length of the original palindrome.

Next question is how to calculate array P. Let id be the max palindromic substring's center, and mx = id + P[id], i.e., the right end of the substring. Then we have the following property:

    If mx > i, the P[i] >= min(P[2 * id - i], mx - i)

int mancher(){
    int mx = 0, id, i, ans = 0;
    memset(p, 0, sizeof(p));

    for (i = 1; i < m; i++){
        if (mx > i){
            p[i] = min(p[2 * id - i], mx - i);
        } else {
            p[i] = 1;
        }
        for ( ; str2[i - p[i]] == str2[i + p[i]]; p[i]++);
        if (i + p[i] > mx){
            mx = i + p[i];
            id = i;
        }
    }
    for (i = 0; i < m; i++){
        ans = max(ans, p[i]);
    }
    ans--;
    return ans;
}

Minimum Editing Distance

Minimum editing distance is to compute the minimum number of operations that transform a string X to another string Y by inserting, deleting and changing characters. This problem is solved by dynamic programming.

int m, n, dp[2][N];
char str1[N], str2[N];

int min_edit_dist(){
    int i, j, pre, cur, u, v;

    pre = 0, cur = 1;
    m = strlen(str1+1);
    n = strlen(str2+1);

    for (i = 0; i <= n; i++) dp[0][i] = i;
    for (i = 1; i <= m; i++){
        dp[cur][0] = i;
        for (j = 1; j <= n; j++){
            u = dp[pre][j]+1;
            v = dp[cur][j-1]+1;
            if (str1[i] == str2[j])
               dp[cur][j] = MIN(dp[pre][j-1], MIN(u, v));
            else
               dp[cur][j] = MIN(dp[pre][j-1] + 2, MIN(u, v));
        }
        pre ^= 1; cur ^= 1;
    }
    return dp[pre][n];
}

RB-Tree Implementation

Red-Black tree has the following properties:

• Root color is black
• If a node is red, then both its children are black
• For each node, all simple paths from the node to descendant leaves contain the same number of black nodes

#define RED 1
#define BLACK 0
struct Node {
 Node *lc, *rc, *pa;
 int color;
 int key;
 Node(){ }
 Node(int val){
  lc = rc = pa = NULL;
  key = val;
  color = RED;
 }
};

class RBTree {
 public:
 Node *root;

 RBTree(){
  root = NULL;
 }

 void print(){
  _print(root, 0);
  cout << endl <rc != NULL){
   u = u->rc;
  }
  return u;
 }

 void remove(Node *z){
  Node *y = z, *x;
  int color;
  if (z == NULL){
   return ;
  }
  color = y->color;
  if (z->lc == NULL && z->rc == NULL){
   if (z->pa == NULL){
    root = NULL;
   } else if (z == z->pa->lc){
    z->pa->lc = NULL;
   } else {
    z->pa->rc = NULL;
   }
   x = NULL;
  } else if (z->lc == NULL){
   x = z->rc;
   transplant(z, z->rc);
  } else if (z->rc == NULL){
   x = z->lc;
   transplant(z, z->lc);
  } else {
   y = minimum(z->rc);
   color = y->color;
   x = y->rc;
   if (y->pa == z){
    if (x){
     x->pa = y;
    }
   } else {
    transplant(y, y->rc);
    y->rc = z->rc;
    y->rc->pa = y;
   }
   transplant(z, y);
   y->lc = z->lc;
   y->lc->pa = y;
   y->color = z->color;
  }
  if (color == BLACK && root != NULL){
   puts("Fixup");
   remove_fixup(x);
  }
  delete z;
 }

 private:

 void left_rotate(Node *x){
  Node *y = x->rc;
  x->rc = y->lc;
  if (y->lc != NULL){
   y->lc->pa = x;
  }
  y->pa = x->pa;
  if (x->pa == NULL){
   root = y;
  } else if (x == x->pa->lc) {
   x->pa->lc = y;
  } else {
   x->pa->rc = y;
  }
  y->lc = x;
  x->pa = y;
 }

 void right_rotate(Node *x){
  Node *y = x->lc;
  x->lc = y->rc;
  if (y->rc != NULL){
   y->rc->pa = x;
  }
  y->pa = x->pa;
  if (x->pa == NULL){
   root = y;
  } else if (x == x->pa->lc){
   x->pa->lc = y;
  } else {
   x->pa->rc = y;
  }
  y->rc = x;
  x->pa = y;
 }

 void transplant(Node *u, Node *v){
  if (u->pa == NULL){
   root = v;
  } else if (u == u->pa->lc){
   u->pa->lc = v;
  } else {
   u->pa->rc = v;
  }
  v->pa = u->pa;
 }

 void _print(Node *node, int dep){
  if (node == NULL) return ;
  if (node->lc) _print(node->lc, dep + 1);
  printf("%d: col %d -- dep %d\n", node->key, node->color, dep);
  if (node->rc) _print(node->rc, dep + 1);
 }

 void _insert(Node *z){
  Node *y = NULL, *x = root;
  while (x != NULL){
   y = x;
   if (z->key key){
    x = x->lc;
   } else {
    x = x->rc;
   }
  }
  z->pa = y;
  if (y == NULL){
   root = z;
  } else if (z->key key){
   y->lc = z;
  } else {
   y->rc = z;
  }
  z->lc = z->rc = NULL;
  z->color = RED;
  insert_fixup(z);
  // puts("**** _insert done");
 }

 void insert_fixup(Node *z){
  Node *y;
  if (z == root){
   z->color = BLACK;
   return ;
  }
  // printf("insert_fixup %d\n", z->pa->color);
  while (z != root && z->pa->color == RED){
   if (z->pa == z->pa->pa->lc){
    y = z->pa->pa->rc;
    if (y != NULL && y->color == RED){
     z->pa->color = BLACK;
     y->color = BLACK;
     z->pa->pa->color = RED;
     z = z->pa->pa;
    } else if (z == z->pa->rc){
     z = z->pa;
     left_rotate(z);
    } else {
     z->pa->color = BLACK;
     z->pa->pa->color = RED;
     right_rotate(z->pa->pa);
    }
   } else {
    y = z->pa->pa->lc;
    if (y != NULL && y->color == RED){
     z->pa->color = BLACK;
     y->color = BLACK;
     z->pa->pa->color = RED;
     z = z->pa->pa;
    } else if (z == z->pa->lc){
     z = z->pa;
     right_rotate(z);
    } else {
     z->pa->color = BLACK;
     z->pa->pa->color = RED;
     left_rotate(z->pa->pa);
    }
   }
  }
  root->color = BLACK;
 }

 Node *_search(Node *rt, int key){
  if (rt == NULL || rt->key == key){
   return rt;
  }
  if (key key){
   return _search(rt->lc, key);
  } else {
   return _search(rt->rc, key);
  }
 }

 void remove_fixup(Node *x){
  Node *w;
  if (x == NULL) return ;
  printf("--- %d\n", x->key);
  while (x != root && x->color == BLACK){
   if (x == x->pa->lc){
    w = x->pa->rc;
    if (w->color == RED){
     w->color = BLACK;
     x->pa->color = RED;
     left_rotate(x->pa);
     w = x->pa->rc;
    }
    if (w->lc->color == BLACK && w->rc->color == BLACK){
     w->color = RED;
     x = x->pa;
    } else if (w->rc->color == BLACK){
     w->lc->color = BLACK;
     w->color = RED;
     right_rotate(w);
     w = x->pa->rc;
    } else {
     w->color = x->pa->color;
     x->pa->color = BLACK;
     w->rc->color = BLACK;
     left_rotate(x->pa);
     x = root;
    }
   } else {
    w = x->pa->lc;
    if (w->color == RED){
     w->color = BLACK;
     x->pa->color = RED;
     right_rotate(x->pa);
     w = x->pa->lc;
    }
    if (w->rc->color == BLACK && w->lc->color == BLACK){
     w->color = RED;
     x = x->pa;
    } else if (w->lc->color == BLACK){
     w->rc->color = BLACK;
     w->color = RED;
     left_rotate(w);
     w = x->pa->lc;
    } else {
     w->color = x->pa->color;
     x->pa->color = BLACK;
     w->lc->color = BLACK;
     right_rotate(x->pa);
     x = root;
    }
   }
  }
  x->color = BLACK;
 }
};

int main(){
 int cmd, v;
 RBTree rb;
 srand(time(NULL));
 for (int i = 0; i > cmd){
  if (cmd == 0){
   // insert
   cin >> v;
   rb.insert(v);
   puts("Insert done");
  } else if (cmd == 1){
   // search
   cin >> v;
   Node *p = rb.search(v);
   if (p) printf("Found %d\n", v);
   else printf("Not Found\n");
  } else if (cmd == 2){
   // remove
   cin >> v;
   Node *p = rb.search(v);
   puts("Removing");
   if (p) rb.remove(p);
   puts("Remove done");
  } else {
   rb.print();
   puts("");
  }
 }
}

Caching Tutorial

Caching Tutorial for Web Authors and Webmasters

http://www.mnot.net/cache_docs/

Unix as IDE

This article illustrates common tools for the unix/linux programming environment

http://blog.sanctum.geek.nz/series/unix-as-ide/

Technical Interview Questions - Data Structure

1. Given a dynamic stream of integral numbers, write a function that returns its median. The numbers may arrive in bursts at any time.

    min/max heap

2. There are two integer arrays ,each in very large files (size of each is larger than RAM). How would you find the common elements in the arrays in linear time.

    bitmap?

3. For an array of integers, find if there are 3 numbers that add up to zero. An algorithm of complexity O(n^2) was required.

    hash table

4. What is the complexity of an algorithm to check whether a binary tree is symetric or not. No need to check the data only the structure needs to be verified.

bool IsSymmetric(Node* r) {

    if ( r == NULL ) return true;

    return IsSymmetric(r->left, r->right);

}



bool IsSymmetric(Node* L, Node* R) {

    if ( !L && !R ) return true;

    if ( !L && R || L && !R ) return false;

    return IsSymmetric(L->left, R->right) && IsSymmetric(L->right, R->left);

}

5. Implement stack class, algorithm for returning minimum number

6. Implement Trie

Technical Interview Questions - Linked List

1. Implement enqueue and dequeue operations using stack(s).

2. Sort a link list using merge sort.

3. You are given two numbers in the form of linked list.Add them without reversing the linked lists. linked lists can be of any length.

4. Randomly select an element from a linked list. The length of linked list is unknown.

5. Reverse a linked list, recursion or non-recursion.

6. Given a circular linked list where the length of the stem can be arbitrary (the shape of the list can be like number 6). What is the size of the list? Or determine if a linked list has a loop.

7. How would you find the nth to last element in a linked list?

Use two pointers. Initalize both pointers to the front of the list then use a loop to traverse one pointer Nth times. Then moves both pointers until one reaches the end of the list. The second pointer is Nth to last element.