## Flipkart Interview Question

Software Engineer / Developers**Country:**India

**Interview Type:**Phone Interview

Isn't 31 used because its a prime number?? Also some later solutions give shifting by 5 (<<5) which is same as multiplying by 32... which I think is wrong because it may generate the same index value!

That's horner's method. The challenge with this approach is, You would hit int limit with string of size 7 characters. This could be avoided using mod.

```
public static int calculate_hash(String input, int tableSize) {
int h = 0;
int len = input.length();
for (int i = 0; i < len; i++) {
h = ( 31 * h + input.charAt(i) ) % tableSize; //mod
}
return h;
}
```

Actually, what u guys are talk about are the same algo , they are both polynominal hash function , the code use Horner's rule , such as: h = k1 + 31*k2 + 31^2*k3 is computed by ((k3)*31 + k2)*31+k1

above answer might not be good because it will cause collisions. consider using strings

1. apple

2. aplpe

will create the same result

what they were probably looking for was the polynomial hashing algorithm

its like

x0+x1(h^1)+x2(h^2)+x3(h^3)+ .... + xn(h^3)

x_n is a character in a string

hash function outputs dont need to be positive numbers between 1 to M, there's a compressor function that is used after the hashing algorithm to make a hashtable

i used a book to answer this question (just for fyi! :P)

The answer posted by Sridhar Namballa is not a bad hash function.It is a popular hash fn called Bernstein hash. If you properly check, it doesnt create the same result. You were probably talking of a hash function as poor as 'sum of all ascii codes of a string'. But the hash function you had suggested is a good one too.

The answer posted by Sridhar Namballa is not a bad hash function.It is a popular hash fn called Bernstein hash. If you properly check, it doesnt create the same result. You were probably talking of a hash function as poor as 'sum of all ascii codes of a string'. But the hash function you had suggested is a good one too.

- Sridhar Namballa December 02, 2011