Get the Intersection Points of Two Link List

Problem:  There are two link lists that have an intersection point (they have the same end), which makes them forms a "Y" shape. Find the intersection point.

Solution:  Definitely we can traverse one list and hash all the nodes. Then traverse the other list. But if we want a O(1) space complexity, we can try the following two methods:

1. Traverse both lists to get the their length. Then move the pointer from the head of the longer list by len(long_list) - len(short_list) steps. Then move both pointers in parallel and compare.
2. Traverse one list, make the last node point to the head to form a circle and remember the length l. Move one pointer l steps, starting from the head of the second list. Then also start to move a second pointer, still from the head of the second list. Two pointers move in parallel. The node they meet each other is the intersection point.

Segment Tree and Interval Tree

To build a Segment Tree, first sort all the end points of the segments, than adding -infinity and +infinity. For n segments, we then partition (-infinity, +infinity) into 2n+1 segments. These 2n+1 segments serve as elementary intervals. From them (considering them as leafs),  we can build a balanced binary tree. Then we add the n segments into the tree. Each node represents an interval. Non-leaf nodes represent the interval which is the union of their children. When adding a segment, we store the information of that segment in all nodes where the nodes' intervals are within the segment's interval. Besides, the nodes' parents' interval are not within the segment's interval.

• building cost is O(nlogn), space cost is O(nlogn), the cost to find all segments that contain a point (stabbing query) is O(k+logn)
• can also solve box overlap problem, Klee's measure problem.
• For multi-level segment tree, first build a base segment tree on one axis. Then build small segment tree on each node of the base tree, only for the segments stored on that node.
• For more details, please check http://www.cnblogs.com/TenosDoIt/p/3453089.html (in Chinese).

To build an Interval Tree, it is a little bit similar. First sort all the end points of the intervals and find the median points. Every node in the interval tree is associated with a point. And the node contains all the intervals that cover the point. The left child (sub-tree) of the node contains all the intervals whose upper bounds are smaller than the node's point. Similarly, we can define the right child.

• building cost is O(nlogn), space cost is O(n), the cost to find all intervals that overlap with an interval   (range query) is O(k+logn). 
• The result is a ternary tree with each node storing:
  • A center point
  • A pointer to another node containing all intervals completely to the left of the center point
  • A pointer to another node containing all intervals completely to the right of the center point
  • All intervals overlapping the center point sorted by their beginning point
  • All intervals overlapping the center point sorted by their ending point
• If we need to do a range query with interval tree, see we want to find the set of r that overlap with interval q. We first to sort all the start/end points of intervals, then find those have either start/end inside q. Second, we need select one point in q, do the query on the interval tree to find all the intervals that have the point. At the end, we need to merge results and do the dedup.

See Also: Klee's measure problem

KMP algorithm

KMP algorithm stands for Knuth–Morris–Pratt algorithm. The problem it wants to solve is to search for a word W in a text string S efficiently. The followings only give the main idea of this algorithm:

1. The essence of the algorithm is to try to avoid comparing a character more than once. Assume we have two cursors m and i. m points to the start matching position for W within S. n points to the current location within W where we fail (we only had a partial match). To search for W in the rest of S, we don't need to start the next match check beginning at m+1, we can choose the position in a smart way.
2. To be smart, we need the help from an auxiliary table T . T has the same length as W. T[i] means if the match fails at the position i, how much we need to look back (reset the start cursor). Thus, m will be reset as m+i-T[i]. Moreover, we don't need to start matching process from the new start position, instead, we can just start from the new i that equals toT[i].
3. This table is mainly for those patterns which contain some non-prefix substring that are also some prefix of the patterns. For example,  in "ABCDABD", substring starting at position 4, "AB", is also the prefix "AB". On the contrary, for "ABC", there are no need to fall back.
4. The time complexity is O(n+k), where n and k are the length of S and W, respectively.

The following gives the table building algorithm:

table[0] = 0;
    table[1] = 0;

    int cnd = 0;

    for(int n =2; n<p.size();)
    {
       if(p[n-1] == p[cnd])
       {
          cnd++;
          table[n] = cnd;
          n++;
       }
       else if(cnd>0)
       {
         // This is the complicated part, if we can't find 
         // a match,  we need to gradually fall back, 
         // to look at shorter string to see if we can 
         // find a match.
         cnd = table[cnd];
       }
       else
       {
          cnd = 0;
          table[n] = cnd;
          n++;
       }

    }

Reservoir Sampling

Reservoir sampling is a sampling algorithm that randomly pick k elements out of a set of n elements. It is adapted from Knuth Shuffling. The key idea is to maintain a buffer with size k, then replace the elements in buffer with a descending probability. The application of this algorithm is when sampling a finite subset from streaming data. Reservoir sampling is very useful for online sampling on streaming data.

int buf[k];
//initialize the buffer
for(int i=0; i<k; i++)
   buf[i] = a[i];

for(int i=k; i<n; i++)
{
   int idx = random(0, i);
   if(idx<k) swap(buf[idx], a[i]);
   
}

The Myth of memset()

memset() according to its specification:

                     void * memset ( void * ptr, int value, size_t num );

However, the value will be converted to unsigned char before calling the actual memset().

"Mutable" Key Word

mutable allows a class data member to be modified in a const function.

Example:

Class A{
   private:
      mutable int x;

   public:
      void foo(int a) const
      {
         x = a;
      }   
}

Lights and Switches

Problem: Four lights in a room and four switches outside the room that control the light. You can only enter the room to check if the lights are on. If you are outside, you don't know. How to know the mapping from switches to lights by just entering the room once?

Solution: The key is to find two binary classifier, then we can encode 4 lights. One classifier is On/Off. The other is Cold/Hot. So we can turn on two switches for a while, let the lights become hot. Then turn off one of them. Then turn on one of the the rest two switches.Then rush into the room to check. There must be four different statuses: On and Hot, Off and Hot, On and Cold, Off and Cold.