## Flipkart Interview Question for Software Engineer / Developers

Country: India
Interview Type: Phone Interview

Comment hidden because of low score. Click to expand.
2
of 2 vote

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

Comment hidden because of low score. Click to expand.
0

Can the 31 be replaced by 2?

Comment hidden because of low score. Click to expand.
0

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!

Comment hidden because of low score. Click to expand.
1
of 1 vote

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;
}``````

Comment hidden because of low score. Click to expand.
2
of 2 vote

The polynomial function will work. I guess other variation could be using unique prime numbers to each of the alphabets. Hash would be multiplication of each character in the string.

Comment hidden because of low score. Click to expand.
1
of 1 vote

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

Comment hidden because of low score. Click to expand.
0

good yaar men.....
u might be good AT g.d

Comment hidden because of low score. Click to expand.
0
of 0 vote

its xn(h^n)
sorry...

Comment hidden because of low score. Click to expand.
0
of 0 vote

index hash(const char *key, int tablesize)
{

Comment hidden because of low score. Click to expand.
0
of 0 vote

index hash(const char *key, int tablesize)
{ int hashval =0;
while(*key != '\0') {
hashval += (hashval<<5)+ *key++;
}
return hashval%tabesize ;}

Comment hidden because of low score. Click to expand.
0
of 0 vote

``````int HashFunc1 (const char* s, int size)
{
unsigned int h = (unsigned int)strlen(s);
int step = (int)((h>>5)+1);

for (int i=h; i>=step; i-=step)
h = h ^ ((h<<5)+(h>>2)+(unsigned char)(s[i-1]));

return h%(size-1);
}``````

Comment hidden because of low score. Click to expand.
-1
of 1 vote

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)

Comment hidden because of low score. Click to expand.
0

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.

Comment hidden because of low score. Click to expand.
0

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.

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.