• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

An interview Question.

 
Ranch Hand
Posts: 91
Eclipse IDE Oracle Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi Guys,

I came accross an interview question which goes like this:

"You have two number represented by a linked list, where each node contains a single digit. The digits are stored in reverse order, such that the 1's digit is at the head of the list. Write a function that adds the two numbers and returns the sum as a linked list"
example:
Linked list 1: 7 -> 1 -> 6
Linked list 2: 5 -> 9 -> 2
The numbers would be: 617 and 295

output: 617+295 = 912

------------------------------------------------------------

Now i have written the following function to implement the above problem. The code works fine and i am getting the output.
I want to know from you guys whether the way i have programmed is nice or not? I keep getting feedbacks that my code is not "clean". can you please give me honest comments on the coding style.



The Node class is as follows: I am pasting it because the previous method uses the getNext() method.




Thanks,
Komal
 
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Your lines are too long. Or at least the first line with the long comment in is too long.
Why are you using Strings to put the numbers together? If it says single digits, why are they not numbers already?
Why are you using reverse? Why did you not put the numbers in the correct order first time?
If you had stopped for 5 minutes to think what the data structures are before writing anything down, you would have got much better code. If you had asked what format the numbers were stored in the linked list, you might have been able to dispense with the Strings.
 
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
The first fix I'd make to your code would be instead of appending each digit to the StringBuffer and then reversing it at the end, I would insert each digit at position 0 of the StringBuffer.

Having said that I wouldn't actually use a StringBuffer (or StringBuilder or String). The Nodes hold the data as ints therefore your code should always treat them as ints. As you retrieve the data from each node, multiply it by a power of ten and then add it to the current value.
i.e.
start with a current value of 0
get the first Node's data and multiply it by 10 to the power 0 and add it to current value
get the second Node's data and multiply it by 10 to the power 1 and add it to current value
get the third Node's data and multiply it by 10 to the power 2 and add it to current value
etc
 
Komal Arora
Ranch Hand
Posts: 91
Eclipse IDE Oracle Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Campell Ritchie:

Thanks for the honest comments.
I had 10 mins to solve the problem so the first thing that came into my mind was to traverse the list and store the values as string so that they can be reversed later and then converted to numbers and added. But i do understand that i am using strings when the question tells me to use int values. Will work on that.

Joanee Neal:

Thanks for the suggestion. I will try to code it like you said.


 
Campbell Ritchie
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
What Joanne suggested was what I would have expected.
In an interview, you are probably better off spending some of the time asking pertinent questions, eg “do those nodes always contain a one‑digit int?” and thinking of the solution than going straight in with the coding.
 
Ranch Hand
Posts: 59
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

Write a function that adds the two numbers and returns the sum as a linked list


You missed this part. The result should be a LinkedList.

The question doesn't give a limit to how large the lists are - so they could represent numbers larger than an int. The fact that they're in reverse order could be a clue to the intended solution. If we add two large numbers together by hand, we add the digits to the right first, and move to the left with a carry digit - so we're traversing the number in reverse order. So you can create the result list digit by digit, in reverse order without any conversion to multi-digit ints or strings.
 
Joanne Neal
Rancher
Posts: 3742
16
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Good points Sresh. I missed the part about the result being a LinkedList and also didn't consider large numbers. Must remember to read the spec carefully in future.
 
Campbell Ritchie
Marshal
Posts: 79178
377
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
I missed that bit, too. So did OP, by the looks of it.
If you have those stack‑like linked lists, it is simple to add the numbers together and put them onto a new stack. You would have to replace a null opposite a real value by 0.
Is the resultant list supposed to have the units value on top and the thousands on the bottom? And what are you doing about carries?
 
Consider Paul's rocket mass heater.
reply
    Bookmark Topic Watch Topic
  • New Topic