Amazon Interview Question
Software Engineer / DevelopersCountry: India
this can be solved by intersection of two sorted linekd list sorted according to power of x;
aclear16 :-
Dude interviewer is mentioning that n is very large so its better to go with the Link list only because u can utilize memory which is scattered .
1. Intersection should read as union (with eliminating the 0s if it is stored as a linked list)
2. List or array depends on what is the expected number of non-zero tags, for large polynomials it is usual that there are only a few, so linked list is usually a better option.
I think the best way to store sparse polynomials is by using a map (exponent vector)
Thus for addition one has go through all nonzero coeffs of both polynomials
the point is we need to associate the coefficients at equal powers of 'x' of both polynomials. Suppose the input polynomials are given as maps:
'coeffs_f' and 'coeffs_g' of the form:
monomial_degree -> coefficient
then polynomial addition can be done as follows:
// loop through all non-zero monomials of 'f'
foreach idx from coeffs_f do
res[idx] = coeffs[idx]
if coeffs_g.find(idx) then
res[idx] += coeffs_g[idx];
*mark* coeffs_g[idx]
end if
end do
// loop through the remaining non-zero monomials of 'g'
foreach idx from coeffs_g do
// skip if coeffs_g[idx] is already there
if *marked* coeffs_g[idx] then continue
res[idx] += coeffs_g[idx];
end do
Additionally, using a map is more convenient because with a linked list you do not have direct access to polynomial coefficients (need to scan the whole list first)
We can make hash of polynomials where index is used as key.
In that case for addition, we just need to update hash which can be done in constant time.
how to go about the collisions because of different powers of x mapped into the slot. How will you add those different powers of x ? I assume you will be storing the coefficient only in hash table Right ??
I think the question said we need to store polynomial after the sum.
Initial polynomial can be given as string /array of objects etc.
This is very open ended
Hello Buddie,
Thanks for highlighting this and indicating about Amazon Interview Question for Software Engineer / Developers where more study and thought is necessary.
I would like to post an announcement for anyone who needs server resources at AWS. Basically, I have 600$ worth of AWS Credit and I am looking for people who would like to use these credits since I don't need them. The only issue here is that they expire at April 30th. I am ready to negotiate and maybe exchange for 150$ amazon gift card or something more tangible for me. Also, I am open to any kind of negotiation.
Awesome! Thanks for putting this all in one place. Very useful!
Obrigado,
Ajeeth
Link-List
- Ali_BABA January 29, 2012