Amazon Interview Question for Software Engineer / Developers


Country: India




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

Link-List

- Ali_BABA January 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

this can be solved by intersection of two sorted linekd list sorted according to power of x;

- AAYUSH KUMAR January 29, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

Why not an array where the index is the power?

- aclear16 January 29, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 .

- Nitin January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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.

- Selmeczy, Péter January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- 111 January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

ASM :- can you give a idea how will you do it through map ?

- Nitin January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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)

- 111 January 31, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

I agree... linklist :)

- Hector January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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.

- loveCoding January 30, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 votes

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 ??

- deepak January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

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

- loveCoding January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 votes

hey manan we have to store initial ds also its coming in form of stream .

- Nitin January 30, 2012 | Flag
Comment hidden because of low score. Click to expand.
0
of 0 vote

A linked list can be used. Each term looks like this

class Term{
  private float coeff;
  private int exp;
  private Term next;

  public Term(float coeff, int exp, Term next){
    this.coeff = coeff;
    this.exp = exp;
    this.next = next;
  }
}

- Anony February 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A linked list can be used. Each term looks like this

class Term{
  private float coeff;
  private int exp;
  private Term next;

  public Term(float coeff, int exp, Term next){
    this.coeff = coeff;
    this.exp = exp;
    this.next = next;
  }
}

(nobrainer .co .cc)

- Anony February 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

A linked list can be used. Each term looks like this

class Term{
  private float coeff;
  private int exp;
  private Term next;

  public Term(float coeff, int exp, Term next){
    this.coeff = coeff;
    this.exp = exp;
    this.next = next;
  }
}

(nobrainer .co .cc)

- Anony February 08, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

the same as given two sorted array/linkedlist and find their union

- shawn March 05, 2012 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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

- Ajeeth June 09, 2018 | Flag Reply


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