Duplicate documents

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

A quick easy way to find duplicates without going through all data is to use a hash table. The key will be the page, the value will be url. If one page already exists in the table, the next one cannot be added, so it can be discarded.

Since each page is huge, so the next thing to think about is to use a hash. Any hashing method you can think of, but since the hash value is an integer, then it will take 4 byte for each url, so in total we will have less than 1 GB required memory.

However, we cannot forget each page is associated with a url. The maximum characters a url can contain is around 2000 (Internet Explore is 2083, but let's just keep it simple), in Java, each character is 2 byte, so in total 4kb. On average a url may not exceed 100 characters, so around 200 bytes? However, we are having 1b of it, so 200 GB? Technically impossible to save all of them in one machine.

Now comes our distributed system. Assume we have n machines, with each can hold x hash values. So in total we will need nx > 1b, assuming no duplicates. So now if we have a hash value v, v / n will be the machine we need to look for the data and v % n is the position to store the data.
For example, if n = 10, and v = 13. Then we will go to the machine index = 1 (index starts from 0) and put it in the 3rd position.

Note that since we are using multiple machines, we will need to deal with network latency.

Sort String

You are given two strings. String T is a string where characters need to be reordered. String O contains characters (none of them repeated) which defines the order/precendence to be used while reordering the string T. Write an algorithm to do the reordering.
*** SPOILER ALERT ***
The question was pusposefully underspecified - upon questioning it was revealed that the string O might not necessarily include all characters used in string T - the characters not included in string O are supposed to be placed at the beginning of the resulting string (in no particular order).

At first, I thought it is a type of counting sort, so I was trying to use an array. The spoiler reminds me that not all characters in String T is included in String O, so it probably is not. I finalized with a map implementation, which may not be the most optimal one consider the extra space I used.

public class SortString {
 public static String sortString(String T, String O){
  if(T == null || O == null || T.length() == 0 || O.length() == 0)
   return T;
  Map count = new HashMap ();
  for(int i = 0; i < O.length(); i++)
   count.put(O.charAt(i), 0);
  StringBuilder rst = new StringBuilder();
  for(int i = 0; i < T.length(); i++){
   char c = T.charAt(i);
   if(!count.containsKey(c))
    rst.append(c);
   else
    count.put(c, count.get(c) + 1);
  }
  for(int i = 0; i < O.length(); i++){
   char c = O.charAt(i);
   int num = count.get(c);
   while(num-- > 0){
    rst.append(c);
   }
  }
  return rst.toString();
 }

 public static void main(String[] args) {
  String T = "dcdavgtealgbm";
  String O = "abcdefghijkl";
  System.out.println(sortString(T, O));

 }

}

Apply Function to multiple machines

Part 1: You are given a computer #1 with array Foo, a computer #2 with array Bar and a spare computer #3. You need to apply a function F to corresponding/matching elements of the two arrays. How would you do that?
Part 2: Once you scale up, how would you balance the number of machines sorting with the machines applying the function?
Part 3: What if the master (which is distributing the work) dies and never recovers?

I would try to use my limited knowledge to approach this problem. The answer may or may not be correct. For the original problem, see here.


Part1:
From Part2, we know that we need to sort the two arrays. However, the problem is not clear on "matching elements", so I would say, sort them separately in two machines and merge the result in computer #3. We can also assign some elements of both arrays to computer #3 and let it do some of the work, then merge all 3 partially sorted arrays. However, we need to think about the band width problem when we try to distribute some data to the third machine. Any O(nlogn) sorting algorithm would be good.

So the next step is to find all needed elements, distribute them evenly  (to all three) and let them apply the function F.


Part2:
I think the problem may be, while sorting the array, if we find some elements that we need to apply to F, we can just send another job for applying F. The answer provided by the interviewee is quite nice:

Either run a small subset first to get an idea if it is linear distribution and then divide statically according to that or try to adapt during processing depending on the load of the machines.

Part3:
I would say to always keep a copy of the data to the other two machines (assuming we only have 3), and keep communicating with each other for data update. When one fails, use another one as the master.

Least significant digit of Fibonacci

Assume we only take the least significant digit of each value in fibonacci sequence, and form the sequence of digits into pairs. In those pairs, the first value of one pair is the same as second value of its predecessor. 

As we know the fibonacci sequence is 1, 1, 2, 3, 5, 8, 13, 21... 

so the pair sequence is: 

[1, 1], [1, 2], [2, 3], [3, 5], [5, 8], [8, 3], [3, 1] ... 

Write a function to output the first n pairs of this sequence. 

void Outputpairs(int n)

public class FibonacciLeastDigit {
 public static void outPutPairs(int n){
  int prevprev = 1;
  int prev = 1;
  for(int i = 1; i <= n; i++){
   System.out.format("[%d , %d]\n", prevprev, prev);
   int curr = (prevprev + prev) % 10;
   prevprev = prev % 10;
   prev = curr;
  }
 }

 public static void main(String[] args) {
  outPutPairs(13);
 }
}

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 UPWhat if you have only 10 MB of memory?

This is a very interesting problem. The problem requires knowledge on both memory limits or bit operations, and consider I am not good at either, it becomes even more interesting.

So the first question, we have 1 GB memory
1GB memory is 2^30 bits, so if we use each bit to represent a number, we can put at most 2 ^ 30 numbers, which can fit 4 billion numbers. So the way we do it is to create a byte array with each element represent 1 byte, which can hold 8 numbers. We go through all the numbers and set the corresponding bit to 1. For example, 11 would be in the 2nd byte and the 3rd bit. Then we go through the byte array again, if a bit is not set to one, then that one is the missing one we are looking for.

public static void findMissing() throws FileNotFoundException{
  byte[] bitField = new byte[0xfffffff / 8];
  Scanner in = new Scanner(new FileReader("numbers"));
  while(in.hasNextInt()){
   int n = in.nextInt();
   bitField[n / 8] |= 1 << (n % 8);
  }
  boolean found = false;
  for(int i = 0; i < bitField.length && !found; i++){
   for(int j = 0; j < 8; j++){
    if((bitField[i] & (1 << j)) == 0){
     System.out.println(i * 8 + j);
     found = true;
     break;
    }
   }
  }
 }

Second, we have 10 MB memory
10 MB is around 2^23 + 2 bits, so we cannot put all numbers this time. Naturally we will think of separate the number so that we can fit each portion into the memory. So consider we have a bucket that can put 2^20 numbers, for 2^32 numbers, we will need 2^12 buckets (These numbers are from the solution provided by the book, I don't think the numbers are accurate here, but the idea is the same.  4 billion integers is around 2^30, so I think we only need 2 ^ 10 buckets, anyway).
We use two arrays, the bucket, which has the length of numBucket, and the bitField as the previous question. Now we go through all the numbers, if the number should be in the range of that bucket, we increase the count of that bucket. So if there is a bucket that has less numbers than it is supposed to have (2^20), we know there is at least one missing number in that bucket.
Now we go through the numbers again, and put all numbers in that range into the bitField, as we did in the last problem, and then we find the missing one.

public static void findMissing2() throws FileNotFoundException{
  int bitSize = 1048576; //2^20, number of numbers we need to put in one bucket
  int numBucket = 4096; // (2^32 / 2^20), number of buckets we need
  byte[] bitField = new byte[bitSize / 8];
  int[] blocks = new int[numBucket];
  Scanner in = new Scanner(new FileReader("numbers"));
  //count how many numbers are in each bucket
  while(in.hasNextInt()){
   int n = in.nextInt();
   blocks[n / bitSize]++;
  }
  int startNumber = 0;
  for(int i = 0; i < numBucket; i++){
   if(blocks[i] < bitSize){
    startNumber = i * bitSize;
    break;
   }
  }
  in = new Scanner(new FileReader("numbers"));
  while(in.hasNextInt()){
   int n = in.nextInt();
   if(n >= startNumber && n < startNumber + bitSize){
    bitField[(n - startNumber) / 8] |= (1 << (n - startNumber) % 8);
   }
  }
  boolean found = false;
  for(int i = 0; i < bitField.length && ! found; i++){
   for(int j = 0; j < 8; j++){
    if(((bitField[i] << j) & 1) == 0){
     System.out.println(startNumber + i * 8 + j);
     found = true;
     break;
    }
   }
  }
 }

Breadth first search using Distributed System

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 (e.g., Me -> Bob -> Susan -> Jason -> You).

This problem is from the Cracking code interview. However, I saw a video on YouTube about how to use distributed system (MapReduce) to do Breadth first search. So I guess that would be a good answer.

How to store the graph: The nodes a list of adjacent nodes (if all weights are 1).

At each iteration, we will start from the original node and grow the frontier by one level. The distance to the start node (DistanceTo(startNode) = 0). For all nodes n directly reachable from startNode, DistanceTo(n) = 1.

Using the above graph, if startNode = 1, then DistanceTo(2) = 1, DistanceTo(11) = 1, DistanceTo(5) = 1, ...etc....
For all nodes reachable from other set of nodes S, DistanceTo(n) = 1 + min(DistanceTo(m), m in S).
So if 4, and 7 is reachable by 2, DistanceTo(4) = 2, DistanceTo(7) = 2.

Not the entire adjacency matrix(sparse matrix, adjacent nodes) to the mapper. Each mapper receives a single row, describing who can be reached from some nodes that we've already known about.
Key: node n that is processing
Value: DistanceTo(n), a list of adjacency nodes (nodes n points to).

So for 1:
Key:1
Value: 0,  (2, 3, 5, 11)

Then from those nodes it can reach, we emit those nodes as keys, DistanceTo = D + 1 (shuffle & sort phrase).
So output from mapper:
Key 2, Value 1
Key 3, Value 1
Key 5, Value 1
Key 11, Value 1

The reducer then receive all these values and select the minimum as the new distance. So if 3 can be reached by:
1 -> 3 (1)
1 -> 11 -> 12 -> 3 (3)
The reducer will select 1.

Then we will pick those output keys and move to the next iteration: a non- MapReduce component then feeds the output of this step back into the MapReduce task for another iteration
Mapper emits the node itself and the points-to list as well. So 1 will be sent back to mapper again, so the shortest distanceTo will not be changed.

Eventually all DistanceTo will converge to their shortest distance, so the algorithm will stop if no shorter distance is found.

Add the edge weight to the adjacency nodes, DistanceTo(n) = DistanceTo(m) + weight(m, n).

Min Hash

My friend threw me a question "How to measure the similarity between two tweets" and asked me to take a look of MinHash. I didn't connect these two together until I started to go over MinHash today, it is kind of fun, and consider NLP is one of my interests, I couldn't say it's not helpful.

There are quite a few highly mathematical explanations about MinHash, if you want to dig deeper to the math, go through the following links:

http://infolab.stanford.edu/~ullman/mmds/ch3.pdf
http://www.cs.cmu.edu/~guyb/realworld/slidesS13/minhash.pdf
http://blog.cluster-text.com/tag/minhash/

However, I would highly recommend this blog, which uses rather plain language and really easy to understand.

Measuring the similarity
When my friend first threw me that question, I told him, well, consider the two tweets as two vector of words with dimension d in the vector space, and measure the distance between them. This is not a wrong approach, and works fine with tweets. However, here is the problem:

1. How to measure the distance? 
Definitely you can say any measuring method that is on top of your mind (Euclidean, Cosine, Edit, etc.). However, here we are talking about two text contents, how to pick a logical one?

2. d
Yeah, that is called the "curse of dimensionality". The maximum of tweets is 140 words, so the d wouldn't exceed 140 (Still high enough). However, now if we want to check if my paper is plagiarism or not, since the shortest paper I have heard is 3000 words (a letter, which I have never succeeded in writing one), we are dealing with d in the range of 3000 to 10000. Besides lots of calculations, it's is highly possible we cannot find any similarity.

Shingles
So here comes the first concept: Shingle. Each shingle contains a fixed number of words, and we will have n - shingle length + 1 shingles given n is the number of words in the text.

So the next question is, how long should a shingle be? In a thumb of rule,

k should be picked large enough that the probability of any given shingle appearing in any given document is low.

where k is the length of the shingles. In general, k = 5 would work well with a normal length e-mail while k = 9 is acceptable  for a research paper.

But what exactly is shingle? Use an example I learned from the above mentioned blog:

Given the text "Dora is a stupid lovely happy dog and Jesse is a smart ugly boring cat". The shingles given k = 5 would be:

Dora is a stupid lovely
is a stupid lovely happy
a stupid lovely happy dog
stupid lovely happy dog and
lovely happy dog and Jesse
happy dog and Jesse is
dog and Jesse is a
and Jesse is a smart
Jesse is a smart ugly
is a smart ugly boring
a smart ugly boring cat

As you can see, when we break down the text to shingles, the meanings of some contents deviate from the original text.  This is kind of interesting!

And this is the set of words we are going to use to measure the similarity.

But you still haven't answer those two questions?

Random shingle selections and MinHash
If I write a 10000 words paper, even if I break down my paper to shingles, I will still have ... 9996 shingles, not helping a lot here. Alternatively, we can randomly select 200 shingles from all shingles we have, and use that as our new set. That will shrink our set to only 2 % compared to the original one! That reduces lots of workload. And that's the reason when we choose the length of the shingle, we need to make it long enough: to assure randomness.

In Java, a string is considered an object, so storing 200 strings is still not a quite good idea. That's when the hash functions come and rescue the world. It's an integer, so it takes constant space. From the blog, the way they do it is like this:

1. Break down the text to shingles;
2. Calculate the hash value for each shingle;
3. Store the minimum hash value among all hash values;
4. Repeat step 2 and step 3 for desired number of hash values, e.g. 200.

Since hashing is another way of random selection (uniform probability for small and large numbers), so hashing 200 times (using two different hash functions) is the same as randomly select 200 shingles.

But I am not a cryptography expert, in fact I only know at most 2 hash functions, and if I steal one from Java, I still need... 197... 

Well, one way to do it is:

you XOR the value returned by String.hashCode() with 199 random numbers to generate the 199 other hash code values. 

See why it works, here is the answer.

Locality Sensitive Hashing (LSH)
If we only need to compare the similarity between two items, we are good now. However, consider a typical clustering algorithm that we need to measure similarities among lots of items, say Nearest Neighbor?
Here comes the MinHash using LSH. LST requires a hash function to divide input into large number of buckets. The similar items will be hashed into the same bucket. The idea of LSH based on MinHash is to divide the hash signatures into b bands. Hash the columns in each band with a basic hash function. If text a and text b have same values in a band, they will be hashed into the same bucket in that band. So if we have in total 200 hash signatures, and we divide them into 10 bands, so in each band, we need to calculate 20 hash codes for each document. If any documents in any band have the same hash values, they need to be considered in the same bucket, and need further comparison.

Source: http://matthewcasperson.blogspot.com/2013/11/minhash-for-dummies.html

I stole the above figure from the blog I mentioned. In this example, we need to compare document one and document three further since they have the same hash values. If in band two, for example, document one and document four have the same hash values, we need to compare document one and document four too.

Wait, how to measure the similarity???

Here comes the most important question. The similarity is measured by the so called Jaccard similarity: 

Using MinHash, it becomes the equal elements in hash(A) and hash(B) / total elements 

Code snippet

The following code is an example. For simplicity, this code only compares similarity between two set of strings, so I didn't write the singles part and the LSH part. 

import java.util.*;
public class MinHash {
 //numHash: number of hash functions needed 
 // in this small case, we set it size of text a + size of text b in the test case
 public double similarity(Set text1, Set text2, int numHash){
  
  long[][] minHashValues = new long[2][numHash];
  Arrays.fill(minHashValues[0], Long.MAX_VALUE);
  Arrays.fill(minHashValues[1], Long.MAX_VALUE);
  Random r = new Random(63689);
  int similarity = 0;
  for (int i = 0; i < numHash; i++){
   int a = r.nextInt() + 1;
   for(String s : text1)
    minHashValues[0][i] = Math.min(minHashValues[0][i], getHash(s.hashCode(), a, i));
   for(String s : text2)
    minHashValues[1][i] = Math.min(minHashValues[1][i], getHash(s.hashCode(), a, i)); 
   if(minHashValues[0][i] == minHashValues[1][i]){
    similarity++;
   }
  }
  return (double)similarity / numHash;
 }
 //using circular shifts: http://en.wikipedia.org/wiki/Circular_shift
 //http://stackoverflow.com/questions/5844084/java-circular-shift-using-bitwise-operations
 //circular shifts XOR random number
 private long getHash(int value, int random, int shift){
  //the first hash function comes from string.hashCode()
  //http://www.codatlas.com/github.com/openjdk-mirror/jdk7u-jdk/master/src/share/classes/java/lang/String.java?keyword=String&line=1494
  if(shift == 0)
   return value;
  int rst = (value >>> shift) | (value << (Integer.SIZE - shift));
  return rst ^ random;
 }
}
public class MinHashTester {

 public static void main(String[] args) {
  Set text1 = new HashSet ();
  text1.add("Dora");
  text1.add("is");
  text1.add("a");
  text1.add("stupid");
  text1.add("lovely");
  text1.add("happy");
  text1.add("puppy");
  Set text2 = new HashSet ();
  text2.add("Dora");
  text2.add("is");
  text2.add("a");
  text2.add("stupid");
  text2.add("lovely");
  text2.add("happy");
  text2.add("puppy");
  
  Set text3 = new HashSet ();
  text3.add("Dora");
  text3.add("the");
  text3.add("happy");
  text3.add("puppy");
  text3.add("loves");
  text3.add("Shirley");
  
  Set text4 = new HashSet ();
  text4.add("Dora");
  text4.add("stupid");
  text4.add("is");
  text4.add("lovely");
  text4.add("happy");
  text4.add("a");
  text4.add("puppy");
  MinHash mh = new MinHash();
  System.out.println(String.format("%.3f", mh.similarity(text1, text2, text1.size() + text2.size())));
  System.out.println(String.format("%.3f", mh.similarity(text1, text3, text1.size() + text3.size())));
  System.out.format("%.3f", mh.similarity(text1, text4, text1.size() + text4.size()));
  
  
 }

}

The output from 3 tests are here:

Apparently the order doesn't affect the total similarity, since we are only storing the minimum hash values among all strings. Note that in reality, we need to deal with singles, not bag of words as showing in the code, because order DOES matter. 

Moreover, I am always interested in hashing, even though I have never taken any classes on cryptography. Here is how Java implements hash in HashMap.hash() and String.hashCode().