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

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

Suggest a cryptographic hash function, SHA1 or MD5. They are expensive but very good hash function.

How to store passwords in database? How to use them? How to store SSN in database? Is there difference? Hint: Do you really want to see the actual pas

How to store passwords in database? How to use them? How to store SSN in database? Is there difference? Hint: Do you really want to see the actual password when they are retrieved? Do you want to see SSN when they are retrieved?

You cannot see the password, so you should hash the password and store the hashed password in the database associated with user id, when you login, input the user id and password, get the hashed password based on the user id, and hash the new input password, then compare the hashed password from database to the hashed input password, if equal, perform a successful login. Why not use encryption on the password

What is consistent hashing?

What is consistent hashing?

Consistent hashing is a scheme that provides hash table functionality in a way that the addition or removal of one slot does not significantly change the mapping of keys to slots. In contrast, in most traditional hash tables, a change in the number of array slots causes nearly all keys to be remapped. By using consistent hashing, only K/n keys need to be remapped on average, where K is the number of keys, and n is the number of slots.
http://www.spiteful.com/2008/03/17/programmers-toolbox-part-3-consistent-hashing/

having a string say, "foobarfoo", in which "fo" and "oo" are repeated twice. You have to find all such repeated pairs whose length is tow in O(n) time

having a string say, "foobarfoo", in which "fo" and "oo" are repeated twice. You have to find all such repeated pairs whose length is tow in O(n) time. The string can only have alphanumeric elements in it and code it in C.

Use suffix tree O(n) which is not easy to code
Use dp which is O(n^2)
Use hash table, it can be done in O(n).
Traverse the string, each time take two consecutive characters, hash them in the hashtable, the hash function is just base 36 number system

void foo(char* str)
{
 int i=0;
 int j=1;
 int hashtable[1296]={0};//36*36
 while(str[j])
 {
  int idx=(str[i]-'a')*36+(str[j]-'a');//base 36
  if(!hashtable[idx])
   hashtable[idx]=1;
  else cout<<str[i]<<str[j]<<endl;
  i++;
  j++;
 }
}

Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without ex

Given two arrays of numbers, find if each of the two arrays have the same set of integers ? Suggest an algo which can run faster than NlogN without extra space?

use a hash function,
sum up all hash values in first array
sum up all hash values in second array
compare

like checksum problem...