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$$

Equation

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$$

Robot's move

Problem : Robot's move

A robot is programmed to move forward F meters and backwards again, say B meters, in a straight line. The Robot covers 1 meter in T units of time. On Robot's path there is an obstacle after distance D from initial position in forward direction. This forward and backward movement is performed repeatedly by the Robot.

Your task is to calculate amount of time taken before the Robot hits the obstacle.

Input Format:
First line contains total number of test cases, denoted by N
Next N lines, contain a tuple containing 4 values delimited by space
F B T D, where

1. F denotes forward displacement in meters
2. B denotes backward displacement in meters
3. T denotes time taken to cover 1 meter
4. D denotes distance from Robot's starting position and the obstacle in forward direction

Output Format:

For each test case print time taken by the Robot to hit the obstacle

Constraints:

First move will always in forward direction

1 <= N <= 100

backward displacement < forward displacement i.e. (B < F)

forward displacement (F) > 0

backward displacement (B) > 0

time (T) > 0

distance (D) > 0

All input values must be positive integers only

Sample Input and Output

SNo.	Input	Output
1	2 5 4 8 10 8 2 3 15	400 69

Solution:
Find the distance to the point just before the last forward cycle starts. Find the time taken to reach this point. Beyond this point just add the time taken to take the forward steps.

C++ Program:

#include <iostream>
using namespace std;

int main(void) 
{
 int F,B,T,D;
 int N;
 cin>>N;
 while(N--)
 {
  cin>>F>>B>>T>>D;
  int forward = F-B; //The distance moved by robot in one forward and backward cycle
  int timeInOneCycle = (F+B)*T; //The time taken by robot to complete one forward and backward cycle
  int secondLastDistance = D-F; //The distance that the robot has to move before it can hit the obstacle
  int timeToSecondLastDistance = 0;
  int quotient = secondLastDistance/forward; //The number of forward and backward cycles needed to reach the secondLastDistance
  int remainder = secondLastDistance%forward;
  timeToSecondLastDistance = timeInOneCycle*quotient; //The time taken to reach the secondLastDistance
  int currentDistance = quotient*forward; //The distance covered by robot after completing quotient number of cycles
  int remainingTime = 0;
  int remainingDistance = D-currentDistance; //The distance remaining from the secondLastDistance point
  if(secondLastDistance <= 0) //If the total distance needed to be covered is less than or equal to the distance F covered by robot in forward direction
  {
   timeToSecondLastDistance = D*T;
  }
  else if(remainingDistance <= F) //If the remaining distance needed to be covered is less than or equal to the distance F covered by robot in forward direction
  {
   remainingTime = remainingDistance*T;
  }
  else //If the quotient calculated above is less than the number of cycles needed to reach the secondLastDistance point
  {
   currentDistance = currentDistance + forward;
   remainingTime = remainingTime + timeInOneCycle;
   remainingDistance = remainingDistance - forward;
   remainingTime = remainingTime + remainingDistance*T;
  }
  cout<<timeToSecondLastDistance + remainingTime<<endl;
 }
 return 0;
}