This week's giveaway is in the Android forum.
We're giving away four copies of Android Security Essentials Live Lessons and have Godfrey Nolan on-line!
See this thread for details.
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 Android Security Essentials Live Lessons this week in the Android 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: 38020
    
  22
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: 3429
    
  12
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: 38020
    
  22
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: 45
    
    1
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: 3429
    
  12
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: 38020
    
  22
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?
 
wood burning stoves
 
subject: An interview Question.
 
Similar Threads
Linked List Data Structure Implementation - No Java API
Swap function in java
Issues with Linked List Add methods
Sorting ArrayList
what is the code trying to say between inheritance and aggregation?