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.

Just add the respective positions.

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

- bunnybare February 25, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- showell30@yahoo.com February 26, 2013 | Flag
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)

- Anonymous February 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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}

- showell30@yahoo.com February 27, 2013 | Flag
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.

- gen-y-s February 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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?

- showell30@yahoo.com February 27, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- Anonymous March 03, 2013 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Anonymous March 03, 2013 | Flag
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

- Anon February 26, 2013 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- showell30@yahoo.com February 26, 2013 | Flag


Add a Comment
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.

Learn More

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.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More