Classify the Hashing Functions based on the various methods by which the key value is found

Common multiple

Q: Given two numbers m and n, write a method to return the first number r that is
divisible by both (e.g., the least common multiple).

A:
The Approach:
What does it mean for r to be divisible by m and n? It means that all the primes in m must go into r, and all primes in n must be in r. What if m and n have primes in common?

For example, if m is divisible by 3^5 and n is divisible by 3^7, what does this mean about r? It means r must be divisible by 3^7.

The Rule: For each prime p such that p^a \ m (e.g., m is divisible by p^a) and p^b \ n, r must be divisible by p^max(a, b)

The Algorithm:
Define q to be 1.
for each prime number p less than m and n:
find the largest a and b such that p^a \ m and p^b \ n
let q = q * p^max(a, b)
return q

Array of size

Given an array of size n+1 which contains all the numbers from 1 to n. Find the number which is repeated in O(n) time. How do you proceed with the same with floating numbers from 0 to 1 instead of 1 to n?

Ans

The number appearing 2 times is (sum of all the numbers in the array) - (sum of the numbers from 1 to n). For floating numbers multiply it with 100 and proceed.

Missing number

Given an array of size n. It contains numbers in the range 1 to n. Each number is present at least once except for 1 number. Find the missing number.

Denominations of coins

You are given some denominations of coins in an array (int denom[])and infinite supply of all of them. Given an amount (int amount), find the minimum number of coins required to get the exact amount. What is the method called?

Maximum sum

Given an array all of whose elements are positive numbers, find the maximum sum of a subsequent elements with the constraint that no 2 numbers in the sequence should be adjacent in the array. So, 3 2 7 10 should return 13 (sum of 3 and 10) or 3 2 5 10 7 should return 15 (sum of 3, 5 and 7)

Convert a decimal number

How do you convert a decimal number to its hexa-decimal equivalent. Give a C code to do so.

Array of size n

Given an array of size n, containing every element from 1 to n+1, except one. Find the missing element.

Merge Sort

What is the time and space complexities of merge sort and when is it preferred over quick sort?