Interview Question
Country: United States
Another option for sparse polynomials is store a list of tuples ordered by the exponent of x.
def sum_poly(poly1, poly2):
def sum(i1, i2):
if (i1 >= len(poly1)):
return poly2[i2:]
if (i2 >= len(poly2)):
return poly1[i1:]
p1, c1 = poly1[i1]
p2, c2 = poly2[i2]
if p1 == p2:
return [(p1, c1+c2)] + sum(i1+1, i2+1)
elif p1 < p2:
return [(p1, c1)] + sum(i1+1, i2)
else:
return [(p2, c2)] + sum(i1, i2+1)
return sum(0, 0)
poly1 = [(0, 5), (4, 3)] # 3x**4 + 5
poly2 = [(0, 2), (2, 7)] # 7x**2 + 2
assert [(0, 7), (2, 7), (4, 3)] == sum_poly(poly1, poly2)
Going with hashes for this one. which are represented as a list {<exponent,constant>}
def sum(polynomial1,polynomial2):
ans = polynomial1
for exponent,constant in polynomial2.iteritems():
if exponent in ans:
ans[exponent] += constant
else:
ans[exponent] = constant
return ans
polynomial1 = {0:5,5:12}
polynomial2 = {3:7,5:23}
assert {0:5, 3:7, 5:35} == sum(polynomial1, polynomial2)
For addition of two polynomials, the best data structure is a linked list sorted on the exponent.
In a linked list, space would not be wasted for sparse polynomials.
Adding two polynomials just involves tranversing the two lists and adding the values from matching exponents, and adding nodes non-matching exponents.
This can even be done in-place in linear time.
I thought of linked lists too, but in the context of this question, I'm not sure I could justify them over normal lists, even for the sparsed exponent assumption. The advantage of linked lists over contiguous lists is that you can insert into the middle of a linked list in O(1) time, but you don't need that for adding polynomials. Am I missing something?
O(1) insertion into the middle of a linked list? how is that possible?
the tradeoff here is O(1) insertion/access for an array vs O(n) insertion/access for linked list. it is a classic memory/performance problem
Once you have traversed to the 5th element in a linked list inserting an element requires constant time. Inserting an element into an array is O(N) time, since all elements to the right of the insertion point need to be shifted.
Just to be clear I would not use a linked list; I am trying to speculate on why the other person thinks they make sense.
If you can have an arbitrary set of variables, then represent monomials like this:
(((a,4),(x, 3), (y,2)), 5) # 5a**4x**3y**2
Represent polynomials as an array of monomials, sorted lexographically.
To add polynomials, merge the two lists starting from the front. You can easily determine if two monomials have the same combination of variables, and, if so, you combine them, adding the coefficients.
A list (vector or arraylist), the positions represent the power.
- bunnybare February 25, 201324x^4 + x^2 + 3 --> { 3, 1, 0, 24} etc.
Just add the respective positions.
To improve have a map where key is power and value is the number (good for sparse list).