## Interview Question

Country: United States

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

A list (vector or arraylist), the positions represent the power.

24x^4 + x^2 + 3 --> { 3, 1, 0, 24} etc.

To improve have a map where key is power and value is the number (good for sparse list).

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

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)``````

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

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)``````

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

This code is a bit dangerous, because it mutates polynomial1. Here's your failing test:

``````assert {0:5, 3:7, 5:35} == sum(polynomial1, polynomial2)
assert polynomial1 == {0:5,5:12}``````

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

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.

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

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?

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

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

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

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.

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

how about if first poly is x^2y + xy^3 and second polynomial is x^2+x

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

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.

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.