Hash Table Size

How to choose size of hash table?

Suppose I have 200.000 of words.

A good rule of thumb is to keep the load factor at 75% or less (some will say 70%) to maintain (very close to) O(1) lookup. Assuming you have a good hash function.

Based on that, you would want a minimum of about 266,700 buckets (for 75%), or 285,700 buckets for 70%. That's assuming no collisions.

266,700 = 200000 x 100/75

285,700 = 200000 x 100/70

Hash table size

• By "size" of the hash table we mean how many slots or buckets it has
• Choice of hash table size depends in part on choice of hash function, and collision resolution strategy
• But a good general “rule of thumb” is:
• The hash table should be an array with length about 1.3 times the maximum number of keys that will actually be in the table, and
• Size of hash table array should be a prime number
• So, let M = the next prime larger than 1.3 times the number of keys you will want to store in the table, and create the table as an array of length M
• (If you underestimate the number of keys, you may have to create a larger table and rehash the entries when it gets too full; if you overestimate the number of keys, you will be wasting some space)

How to find whether a given number is prime or not?

A number is greater than 1 is called a prime number, if it has only two factors, namely 1 and the number itself.

Prime numbers up to 100 are:2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Procedure to find out the prime number

Suppose A is given number.

Step 1: Find a whole number nearly greater than the square root of A. K ¿ square root(A) Step 2: Test whether A is divisible by any prime number less than K. If yes A is not a prime number. If not, A is prime number.

Example:

Find out whether 337 is a prime number or not?

Step 1: 19 ¿ square root (337) Prime numbers less than 19 are 2, 3, 5, 7, 11, 13, 17 Step 2: 337 is not divisible by any of them

Therefore 337 is a prime number

int prime(int n) {
int i;
        // Corner cases
if(n<=1)
return 0;
if(n<= 3)
return 1;

if(n%2 == 0 || n%3 == 0 || n%5 == 0) {
return 0;
}

for(i=5;i*i <=n;i++) {
if(n%i == 0)
return 0;
}

return 1;
}

Hashing

• String hash function 

• Recall that the Java String function combines successive characters by multiplying the current hash by 31 and then adding on the new character. 

  int hash = 0; for (int i = 0; i < length(); i++) { hash = 31 * hash + charAt(i); } return hash;

•  Probably a pretty decent hash algorithm, as presented in K&R version 2 (verified by me on pg. 144 of the book); NB: be sure to remove % HASHSIZE from the return statement if you plan on doing the modulus sizing-to-your-array-length outside the hash algorithm. Also, I recommend you make the return and "hashval" type unsigned long instead of the simple unsigned (int).

  unsigned hash(char *s)
  {
      unsigned hashval;
  
      for (hashval = 0; *s != '\0'; s++)
          hashval = *s + 31*hashval;
      return hashval % HASHSIZE;
  }

• 


http://codeforces.com/blog/entry/13529
http://codersmaze.com/data-structure-explanations/graphs-data-structure/
http://www.dsalgo.com/2013/02/index.php.html
http://www.quora.com/Which-are-the-top-blogs-to-follow-to-explore-about-algorithms-and-data-structures
http://codersmaze.com/data-structure-explanations/graphs-data-structure/dijkstras-algorithm-for-shortest-path/
http://www.programminggeek.in/2013/08/java-implementation-of-dijkstra-shortest-path-algorithm-for-coursera-programming-assignment-5.html#.VYgv4JP6yb8
http://www.thecrazyprogrammer.com/2014/03/dijkstra-algorithm-for-finding-shortest-path-of-a-graph.html
http://www.sanfoundry.com/c-programming-examples-graph-problems-algorithms/

Dijkstra Algorithm for Finding Shortest Path of a Graph

Dijkstra algorithm is also called single source shortest path algorithm. It is based on “greedy” technique. The algorithm maintains a list ‘visited[ ]’ of vertices, whose shortest distance from the source is already known.

If visited[1], equals 1, then the shortest distance of vertex i is already known. Initially, visited[i] is marked as, for source vertex.

At each step, we mark visited[v] as 1. Vertex v is a vertex at shortest distance from the source vertex. At each step of the algorithm, shortest distance of each vertex is stored in an array ‘distance[ ]’.

Also Read: What is Quick Sort? Algorithm and C Program to Implement Quick Sort

Also Read: C Program and Algorithm for Conversion of an Expression from Infix to Postfix

Algorithm

1. Create cost matric C[ ][ ] from adjacency matrix adj[ ][ ]. C[i][j] is the cost of going from vertex i to vertex j. If there is no edge between vertices i and j then C[i][j] is infinity.

2. Array visited[ ] is initialized to zero.

               for(i=0;i<n;i++)

                              visited[1]=0;

3. If the vertex 0 is the source vertex then visited[0] is marked as 1.

4. Create the distance matrix, by storing the cost of vertices from vertex no. 0 to n-1 from the source vertex 0.

               for(i=1;i<n;i++)

                              distance[i]=cost[0][i];

Initial, distance of source vertex is taken as 0.

 i.e. distance[0]=0;

5. for(i=1;i<n;i++)

- Choose a vertex w, such that distance[w] is minimum and visited[w] is 0.

Mark visited[w] as 1.

- Recalculate the shortest distance of remaining vertices from the source.

- Only, the vertices not marked as 1 in array visited[ ] should be considered for recalculation of distance.

i.e. for each vertex v

               if(visited[v]==0)

                              distance[v]=min(distance[v],

                              distance[w]+cost[w][v])

Time Complexity

The program contains two nested loops each of which has a complexity of O(n). n is number of vertices. So the complexity of algorithm is O(n²).

C Program on Dijkstra Algorithm for Finding Minimum Distance of Vertices from a Given Source in a Graph

#include<stdio.h>

#include<conio.h>

#define INFINITY 9999

#define MAX 10

void dijkstra(int G[MAX][MAX],int n,int startnode);

void main()

{

    int G[MAX][MAX],i,j,n,u;

    printf("Enter no. of vertices:");

    scanf("%d",&n);

    printf("\nEnter the adjacency matrix:\n");

    for(i=0;i<n;i++)

        for(j=0;j<n;j++)

            scanf("%d",&G[i][j]);

    printf("\nEnter the starting node:");

    scanf("%d",&u);

    dijkstra(G,n,u);

}

void dijkstra(int G[MAX][MAX],int n,int startnode)

{

    int cost[MAX][MAX],distance[MAX],pred[MAX];

    int visited[MAX],count,mindistance,nextnode,i,j;

    //pred[] stores the predecessor of each node

    //count gives the number of nodes seen so far

    //create the cost matrix

    for(i=0;i<n;i++)

        for(j=0;j<n;j++)

            if(G[i][j]==0)

                cost[i][j]=INFINITY;

            else

                cost[i][j]=G[i][j];

    //initialize pred[],distance[] and visited[]

    for(i=0;i<n;i++)

    {

        distance[i]=cost[startnode][i];

        pred[i]=startnode;

        visited[i]=0;

    }

    distance[startnode]=0;

    visited[startnode]=1;

    count=1;

    while(count<n-1)

    {

        mindistance=INFINITY;

        //nextnode gives the node at minimum distance

        for(i=0;i<n;i++)

            if(distance[i]<mindistance&&!visited[i])

            {

                mindistance=distance[i];

                nextnode=i;

            }

        //check if a better path exists through nextnode

        visited[nextnode]=1;

        for(i=0;i<n;i++)

            if(!visited[i])

                if(mindistance+cost[nextnode][i]<distance[i])

                {

                    distance[i]=mindistance+cost[nextnode][i];

                    pred[i]=nextnode;

                }

        count++;

    }

    //print the path and distance of each node

    for(i=0;i<n;i++)

            if(i!=startnode)

            {

                printf("\nDistance of node %d=%d",i,distance[i]);

                printf("\n Path=%d",i);

                j=i;

                do

                {

                    j=pred[j];

                    printf("<-%d",j);

                }while(j!=startnode);

            }

}

Find the two repeating elements in a given array

You are given an array of n+2 elements. All elements of the array are in range 1 to n. And all elements occur once except two numbers which occur twice. Find the two repeating numbers.

For example, array = {4, 2, 4, 5, 2, 3, 1} and n = 5

The above array has n + 2 = 7 elements with all elements occurring once except 2 and 4 which occur twice. So the output should be 4 2.

Answers:

Method 1 (Basic)
Use two loops. In the outer loop, pick elements one by one and count the number of occurrences of the picked element in the inner loop.

This method doesn’t use the other useful data provided in questions like range of numbers is between 1 to n and there are only two repeating elements.


#include<stdio.h>
#include<stdlib.h>
void printRepeating(int arr[], int size)
{

int i, j;
printf(" Repeating elements are ");
for(i = 0; i < size; i++)
for(j = i+1; j < size; j++)
if(arr[i] == arr[j])
printf(" %d ", arr[i]);

}

int main()
{

int arr[] = {4, 2, 4, 5, 2, 3, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;

}

Time Complexity: O(n*n)
Auxiliary Space: O(1)

Method 2 (Use Count array)
Traverse the array once. While traversing, keep track of count of all elements in the array using a temp array count[] of size n, when you see an element whose count is already set, print it as duplicate.

This method uses the range given in the question to restrict the size of count[], but doesn’t use the data that there are only two repeating elements.


#include<stdio.h>
#include<stdlib.h>

void printRepeating(int arr[], int size)
{

int *count = (int *)calloc(sizeof(int), (size - 2));
int i;
printf(" Repeating elements are ");
for(i = 0; i < size; i++)
{

if(count[arr[i]] == 1)

printf(" %d ", arr[i]);

else

count[arr[i]]++;

}

}

int main()
{

int arr[] = {4, 2, 4, 5, 2, 3, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;

}

Time Complexity: O(n)
Auxiliary Space: O(n)

Method 3 (Make two equations)
Let the numbers which are being repeated are X and Y. We make two equations for X and Y and the simple task left is to solve the two equations.
We know the sum of integers from 1 to n is n(n+1)/2 and product is n!. We calculate the sum of input array, when this sum is subtracted from n(n+1)/2, we get X + Y because X and Y are the two numbers missing from set [1..n]. Similarly calculate product of input array, when this product is divided from n!, we get X*Y. Given sum and product of X and Y, we can find easily out X and Y.

Let summation of all numbers in array be S and product be P

X + Y = S – n(n+1)/2
XY = P/n!

Using above two equations, we can find out X and Y. For array = 4 2 4 5 2 3 1, we get S = 21 and P as 960.

X + Y = 21 – 15 = 6

XY = 960/5! = 8

X – Y = sqrt((X+Y)^2 – 4*XY) = sqrt(4) = 2

Using below two equations, we easily get X = (6 + 2)/2 and Y = (6-2)/2
X + Y = 6
X – Y = 2

Thanks to geek4u for suggesting this method. As pointed by Beginer , there can be addition and multiplication overflow problem with this approach.
The methods 3 and 4 use all useful information given in the question


#include<stdio.h>
#include<stdlib.h>
#include<math.h>

/* function to get factorial of n */
int fact(int n);

void printRepeating(int arr[], int size)
{

int S = 0; /* S is for sum of elements in arr[] */
int P = 1; /* P is for product of elements in arr[] */
int x, y; /* x and y are two repeating elements */
int D; /* D is for difference of x and y, i.e., x-y*/
int n = size - 2, i;
/* Calculate Sum and Product of all elements in arr[] */
for(i = 0; i < size; i++)
{

S = S + arr[i];
P = P*arr[i];

}

S = S - n*(n+1)/2; /* S is x + y now */
P = P/fact(n); /* P is x*y now */
D = sqrt(S*S - 4*P); /* D is x - y now */
x = (D + S)/2;
y = (S - D)/2;
printf("The two Repeating elements are %d & %d", x, y);

}

int fact(int n)
{

return (n == 0)? 1 : n*fact(n-1);

}

int main()
{

int arr[] = {4, 2, 4, 5, 2, 3, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;

}


Time Complexity: O(n)
Auxiliary Space: O(1)

Method 4 (Use XOR)
Thanks to neophyte for suggesting this method.
The approach used here is similar to method 2 of this post.
Let the repeating numbers be X and Y, if we xor all the elements in the array and all integers from 1 to n, then the result is X xor Y.
The 1’s in binary representation of X xor Y is corresponding to the different bits between X and Y. Suppose that the kth bit of X xor Y is 1, we can xor all the elements in the array and all integers from 1 to n, whose kth bits are 1. The result will be one of X and Y.


void printRepeating(int arr[], int size)
{

int xor = arr[0]; /* Will hold xor of all elements */
int set_bit_no; /* Will have only single set bit of xor */
int i;
int n = size - 2;
int x = 0, y = 0;
/* Get the xor of all elements in arr[] and {1, 2 .. n} */
for(i = 1; i < size; i++)

xor ^= arr[i];

for(i = 1; i <= n; i++)

xor ^= i;

/* Get the rightmost set bit in set_bit_no */
set_bit_no = xor & ~(xor-1);
/* Now divide elements in two sets by comparing rightmost set
bit of xor with bit at same position in each element. */
for(i = 0; i < size; i++)
{

if(arr[i] & set_bit_no)

x = x ^ arr[i]; /*XOR of first set in arr[] */

else

y = y ^ arr[i]; /*XOR of second set in arr[] */

}
for(i = 1; i <= n; i++)
{

if(i & set_bit_no)

x = x ^ i; /*XOR of first set in arr[] and {1, 2, ...n }*/

else

y = y ^ i; /*XOR of second set in arr[] and {1, 2, ...n } */

}
printf("\n The two repeating elements are %d & %d ", x, y);

}


int main()
{

int arr[] = {4, 2, 4, 5, 2, 3, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;

}

Method 5 (Use array elements as index)

Traverse the array. Do following for every index i of A[].
{
check for sign of A[abs(A[i])] ;
if positive then
   make it negative by   A[abs(A[i])]=-A[abs(A[i])];
else  // i.e., A[abs(A[i])] is negative
   this   element (ith element of list) is a repetition
}

Example: A[] =  {1, 1, 2, 3, 2}
i=0; 
Check sign of A[abs(A[0])] which is A[1].  A[1] is positive, so make it negative. 
Array now becomes {1, -1, 2, 3, 2}

i=1; 
Check sign of A[abs(A[1])] which is A[1].  A[1] is negative, so A[1] is a repetition.

i=2; 
Check sign of A[abs(A[2])] which is A[2].  A[2] is  positive, so make it negative. '
Array now becomes {1, -1, -2, 3, 2}

i=3; 
Check sign of A[abs(A[3])] which is A[3].  A[3] is  positive, so make it negative. 
Array now becomes {1, -1, -2, -3, 2}

i=4; 
Check sign of A[abs(A[4])] which is A[2].  A[2] is negative, so A[4] is a repetition.

Note that this method modifies the original array and may not be a recommended method if we are not allowed to modify the array.


#include <stdio.h>
#include <stdlib.h>

void printRepeating(int arr[], int size)
{

int i;

printf("\n The repeating elements are");
for(i = 0; i < size; i++)
{

if(arr[abs(arr[i])] > 0)

arr[abs(arr[i])] = -arr[abs(arr[i])];

else

printf(" %d ", abs(arr[i]));

}

}

int main()
{

int arr[] = {1, 3, 2, 2, 1};
int arr_size = sizeof(arr)/sizeof(arr[0]);
printRepeating(arr, arr_size);
getchar();
return 0;

}

Finding a duplicate number in an array of random numbers?

Suppose you have an array of 1001 integers. The integers are in random order, but you know each of the integers is between 1 and 1000 (inclusive). In addition, each number appears only once in the array, except for one number, which occurs twice. Assume that you can access each element of the array only once. Describe an algorithm to find the repeated number. If you used auxiliary storage in your algorithm, can you find an algorithm that does not require it?

Answer:


The solution here is straight forward. Sum all the numbers and subtract (1000*1001)/2 from that. The result is the no you are looking for.

Eg:
Input: 1,2,3,2,4 => 12
Expected: 1,2,3,4 => 10

Input - Expected => 2

Find 10 maximum integer out of 1 million integers.

You Have File of Containing 1 Million Integers You need To Find 10 Maximum Integer Out of Them. How You Will Do That. What is Time & space Complexity of Algorithm that you will use then optimize the solution.. 

Constraints- U can't Store Whole File in memory @ one time e.g. if u will do that gigabyte of memory may be required so that should be avoided.


Answer:
Using Min Heap:

Use a min-heap of 10 elements.Initialize the heap with first 10 elements in O(10) [constant] time.For each of the next element,check whether it is greater than root of min heap,if it is,replace that element by the next element and heapify the heap again in O(log10) [constant] time.At last extract all the 10 elements one by one in O(log10) constant time each.so space complexity O(1) time complexity O(N).

Using Max Heap:

A solution for this problem may be to divide the data in some sets of 1000 elements (let’s say 1000), make a heap of them, and take 10 elements from each heap one by one. Finally heap sort all the sets of 10 elements and take top 10 among those. But the problem in this approach is where to store 10 elements from each heap. That may require a large amount of memory as we have billions of numbers.

Reuse top 20 elements from earlier heap in subsequent elements can solve this problem. I meant to take first block of 1000 elements and subsequent blocks of 990 elements each. Initially heapsort first set of 1000 numbers, took max 10 elements and mix them with 990 elements of 2ndset. Again heapsort these 1000 numbers (10 from first set and 990 from 2nd set), take 10 max element and mix those with 980 elements of 3rd set. Repeat the same exercise till last set of 990 (or less) elements and take max 20 elements from final heap. Those 10 elements will be your answer.


Complexity: O(n) = n/1000*(complexity of heapsort 1000 elements)

Since complexity of heap sorting 1000 elements will be a constant so the O(n) = N i.e. linear complexity