Hash Table Simplified

A very basic explanation of a Hash Table Data Structure

Let us consider the problem of storing a large number of words so that insertion and search operations can be performed in O (1) time complexity

If the words are stored in a simple array, then the operation will have time complexity of O (n) where n is the number of words.

We can solve the above problem by using a Hash Table data structure

What is a hash table?

A hash table is a set of key-value pairs where key is unique and a particular key cab hold a certain value.

A key is generated by a hash function.

For our example, let us consider that the hashing function works in the following manner:

1. The letters of the word are assigned a particular integer value. For example: a -> 1, b -> 2, c -> 3 and so on.

2. The integers corresponding to the letters present in a particular word are added.

3. This sum is taken as a key

4. Let us assume the number of keys formed in this way is k (which is constant). There is a catch* here which is discussed later. For now assume that the maximum number of possible keys is a constant k.

5. Let us also assume that the number of words corresponding to a single key is constant which equals to w on an average.

Now let us consider the following words and the corresponding sums which will be the keys.

Word	Sum which will be used as key
abc	6
ae	6
abcd	10
ade	10

  

Sample Hash Table storage:

Now to search for a word ade:

1. First the sum is determined which is O (1). Please note that the complexity of finding the sum for a given word having m letters is negligible compared to the complexity of finding a word in an array containing n such words.

2. Now this key can be searched in the key linked list in O(k) which in Big O notation boils down to O(1).

3. Once the key is determined, the word can be searched in O(w) which in Big O notation again boils down to O(1).

So the Search operation can be performed on such a data structure with time complexity of O (n).

Similarly for inserting a word acf:

1. First the sum is determined which is O (1). Please note that the complexity of finding the sum for a given word having m letters is negligible compared to the complexity of finding a word in an array containing n such words.

2. Now this key can be searched in the key linked list in O(k) which in Big O notation boils down to O(1).

3. Once the key is determined, the word can be inserted in O(w) which in Big O notation again boils down to O(1).

So the Insertion operation can be performed on such a data structure with time complexity of O (n).

*Catch: The choice of the hashing function needs to be made very carefully so as to maintain the following two criteria:

1. The number of unique keys generated by the hashing function should not become too high.

2. The number of words or entities needed to be stored in one linked list should not become too large.

Note: This is an attempt to explain the hash table data structure in a very simple terms. Actual implementations are much more complex and use details of the available memory storage.

References:
https://en.wikipedia.org/wiki/Hash_table

Milk Man and His Bottles

Problem : Milk Man and His Bottles

A Milkman serves milk in packaged bottles of varied sizes. The possible size of the bottles are {1, 5, 7 and 10} litres. He wants to supply desired quantity using as less bottles as possible irrespective of the size. Your objective is to help him find the minimum number of bottles required to supply the given demand of milk.

Input Format:First line contains number of test cases N
Next N lines, each contain a positive integer Li which corresponds to the demand of milk.

Output Format:
For each input Li, print the minimum number of bottles required to fulfill the demand

Constraints:
1 <= N <= 1000
Li > 0
1 <= i <= N

Sample Input and Output

SNo.	Input	Output
1	2 17 65	2 7

C++ Program:

#include <iostream>
 using namespace std;

 int main() {
  int N,a,A[4]={1, 5, 7, 10};
  cin>>N;
  while(N--)
  {
   cin>>a;
   int sum = 0;
   for(int i=3;i>=0;i--)
   {
    sum+=a/A[i];
    a=a%A[i];
   }
   cout<<sum<<endl;
  }
  return 0;
 }

 

Optimum Cost Calculator

Problem : Optimum Cost Calculator

A town A is located on a river. We have to send cargo to town B which is located 'a' kilometers downstream and 'd' kilometers from the river. Government wants to construct a sea link between B and the river such that the cost of transportation of goods from A to B is the cheapest. The transport cost of a unit of cargo per kilometer by waterway is half the cost incurred by taking the highway.

Your task is to help the government find a point in the river from which to construct a highway to town B so that the government's objective of reducing transportation cost is achieved. More specifically, calculate the distance from town A where the highway has to be constructed and the length of the highway to be constructed.

Input Format:
First line contains the distance between A and C along the river denoted 'a'
Second line contains the distance between C and B along the road denoted by 'd'

Output Format:
Print the distance of the point in the river denoted by D from Town A.
Print the length of the highway that needs to be built from D to B.

OR

Print "Invalid Input", if any constraint is violated

Constraints:
0 < a <= (57 * d)
0 < d <= (1.7 * a)
Calculations and printing of output should be done upto 11­digit precision

Sample Input and Output

SNo. 1	Input 50 10	Output X= 44.22649730810 Y= 11.54700538379
2	40 10	X= 34.22649730810 Y= 11.54700538379
3	172 3	Invalid Input

Mathematical logic:
Cost = $$c = c_1 x + c_2y$$ where \(c_1\) is cost of travelling on water and \(c_2\) is cost of travelling on land. As per the given condition, $$c_1 = \frac{c_2}{2}$$ Hence the equation becomes: $$c = \frac{cx}{2} + cy$$
$$ => c = c(x/2 + y)$$
Also, as per the given figure, the relation between \(x\) and \(y\) can be represented as follows: $$y^2 = (a-x)^2 + d^2$$
$$=> y = \sqrt{(a-x)^2 + d^2}                               \cdots 1 $$                                                  
The objective is to minimize the cost function c. So $$ \frac{d}{dx}c[\frac{x}{2}+ \sqrt{(a-x)^2 + d^2}] = 0$$ Solving the above differential equation: $$\frac{1}{2} - \frac{2(a - x)}{2\sqrt{(a-x)^2 + d^2}} = 0$$ $$=> \frac{1}{2} = \frac{(a - x)}{\sqrt{(a-x)^2 + d^2}} $$ Squaring both sides, we get: $$=> \frac{1}{4} = \frac{(a - x)^2}{(a-x)^2 + d^2} $$ $$=> 4(a-x)^2 = (a-x)^2 + d^2$$ $$ => 3(a-x)^2 = d^2$$$$ => x = a - \frac{d}{\sqrt{3}}$$ From equation 1 above, $$y = \frac{2}{\sqrt3}d$$