File APIs for Java Developers
Manipulate DOC, XLS, PPT, PDF and many others from your application.
http://aspose.com/file-tools
The moose likes Java in General and the fly likes An interview Question. Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Soft Skills this week in the Jobs Discussion forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "An interview Question." Watch "An interview Question." New topic
Author

An interview Question.

Komal Arora
Ranch Hand

Joined: Sep 30, 2010
Posts: 91

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


OCPJP
Campbell Ritchie
Sheriff

Joined: Oct 13, 2005
Posts: 40034
    
  28
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.
Joanne Neal
Rancher

Joined: Aug 05, 2005
Posts: 3742
    
  16
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

Joanne
Komal Arora
Ranch Hand

Joined: Sep 30, 2010
Posts: 91

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
Sheriff

Joined: Oct 13, 2005
Posts: 40034
    
  28
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.
Sresh Rangi
Ranch Hand

Joined: Nov 28, 2012
Posts: 48
    
    2
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

Joined: Aug 05, 2005
Posts: 3742
    
  16
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
Sheriff

Joined: Oct 13, 2005
Posts: 40034
    
  28
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?
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: An interview Question.