This week's book giveaway is in the OO, Patterns, UML and Refactoring forum. We're giving away four copies of Refactoring for Software Design Smells: Managing Technical Debt and have Girish Suryanarayana, Ganesh Samarthyam & Tushar Sharma on-line! See this thread for details.
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"
Linked list 1: 7 -> 1 -> 6
Linked list 2: 5 -> 9 -> 2
The numbers would be: 617 and 295
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.
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.
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.
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
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.
Thanks for the suggestion. I will try to code it like you said.
Joined: Oct 13, 2005
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.
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.
Joined: Aug 05, 2005
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.
Joined: Oct 13, 2005
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?