Reversing k-sized sequences in a linked-list

Here is my solution to this problem; please be brutally honest/strict, if I would have written this code, in a 45 minute interview, what would you think? (I am aiming for Google,Facebook).

Here is the problem I solved:

*Given a linked list, reverse the nodes of a linked list k at a time and return its modified list. If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is. You may not alter the values in the nodes, only nodes itself may be changed.

For example

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

Thanks.

  public class ListNode {
int val;
ListNode next;
ListNode(int x) {
val = x;
next = null;
}
}

public class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
int count=1;
ListNode current = null;
ListNode remainingHalf = null;

return null;
}

if(k<=1){
}
}
if(k==2){
}

while(cursor!=null || cursor.next!=null){

while(count!=k){
if(cursor!=null){
cursor = cursor.next;
}
count++;
}
if(cursor!=null){
remainingHalf = cursor.next;
cursor.next=null;

cursor = remainingHalf;
}
else{
break;
}
count=1;
if(cursor==null || cursor.next==null){
break;
}

}
ListNode toRet=null;
ListNode end=null;
if(first!=null){
end =  findEnd(first);
toRet = first;
}
}
else{
break;
}
if(second==null){
ListNode temp = findEnd(toRet);
temp.next=first;
break;
}
end.next=second;

ListNode last = findEnd(toRet);

}
}

}

int count=0;
}
return count;
}

}
}

return null;
}
}
ListNode temp = reverse(remaining);
return temp;
}
}

-

Brutally honest?

If this is an interview, and you provide this line of code:

Queue linkQueue = new LinkedList();


Your resume gets put in the pile of 'ignore this person if they apply again'... ;-)

Genercis have been around for a decade now (introduced in 2004). You should know them, and use them.

Class Model

The ListNode should not be a public class. The information should be encapsulated within a single class, and not exposed. There should be no need for a user to have to supply a 'head' node to the public ListNode reverseKGroup(ListNode head, int k). This should be a class, say ReversingList which has a method reverseK(int k), and then provides a way to retrieve the re-ordered data (which may be in the format of a new ReversingList instance.

Algorithm

Your algorithm looks really complicated. There should be no need to scan the list before processing it. That indicates some serious inefficiencies.

Additionally, relying on the LinkedList class is a bit of a cheat... but, if you are going to use it, then you may as well go the whole hog, and use its reverse function... (descendingIterator())

How would I do it?

This was the original title of the question... well, how about:

public class SolutionList {

private static final class ListNode {
private final int val;
private ListNode next;

ListNode(int x) {
val = x;
next = null;
}

@Override
public String toString() {
return "ListNode " + val;
}
}

// use relatively common trick of having a dummy head node.
private final ListNode head = new ListNode(0);

public SolutionList() {
// default constructor does nothing.
}

while (node.next != null) {
node = node.next;
}
node.next = new ListNode(v);
}

while (tail.next != null) {
tail = tail.next;
}
while (their != null) {
tail.next = new ListNode(their.val);
tail = tail.next;
their = their.next;
}
}

public void reverseKInPlace(final int k) {
if (k <= 1 || head.next == null) {
return;
}
ListNode[] stack = new ListNode[k];
int depth = 0;
while (node != null) {
ListNode nxt = node.next;
stack[depth++] = node;
if (depth == k) {
while (--depth >= 0) {
mark.next = stack[depth];
mark = mark.next;
}
depth = 0;
}
node = nxt;
}
if (depth > 0) {
mark.next = stack[0];
}

}

@Override
public String toString() {
StringBuilder sb = new StringBuilder("SolutionList [");
while (node != null) {
sb.append(node.val).append(", ");
node = node.next;
}
sb.setLength(sb.length() - 2);
}
sb.append("]");
return sb.toString();
}

public SolutionList reverseK(final int k) {
SolutionList copy = new SolutionList();
copy.reverseKInPlace(k);
return copy;
}

public static void main(String[] args) {
int[] vals = { 1, 2, 3, 4, 5 };
SolutionList soln = new SolutionList();
for (int v : vals) {
}
System.out.println(soln);
System.out.println("Reverse 2 " + soln.reverseK(2));
System.out.println("Reverse 3 " + soln.reverseK(3));
}

}

-
I appreciate your honesty, as it helps improve my code-writing ability. Now what do you mean by use generics, like use an ArrayList<ListNode> instead? I don't see what's wrong with using a Queue interface? Pardon my ignorance, as I have 0 industry experience. –  bazang Mar 5 '14 at 0:04
@bazang - should be Queue<ListNode> linkQueue = new LinkedList<>();. This has a lot of benefits for creating bug-reduced code, and it eliminates a lot of compiler warnings, etc. It is important to study up on this. –  rolfl Mar 5 '14 at 0:06
+1 for ... wait for it, kid's bath time... ;-) this is the most important part of the review –  Marc-Andre Mar 5 '14 at 0:06
@bazang - Official Generics Tutorial - not necessarily the best. Google around –  rolfl Mar 5 '14 at 0:07
@bazang - updated with a code example. –  rolfl Mar 5 '14 at 0:23

I couldn't resist to disagree with @rolfl's following sentence:

Your resume gets put in the pile of 'ignore this person if they apply again'... ;-)

As an occasional interviewer I would appreciate a solution which shows that the candidate does not reinvent the wheel and can use (and know) the existing libraries.

Here is a solution with Guava:

import static com.google.common.collect.Lists.newArrayList;
import java.util.List;

...

public <T> List<T> reverseFirstPart(final LinkedList<T> input,
final int reversedElementsNumber) {
final Iterable<T> firstPart = Iterables.limit(input, reversedElementsNumber);
final Iterable<T> secondPart = Iterables.skip(input, reversedElementsNumber);
final List<T> reversedFirstPart = Lists.reverse(newArrayList(firstPart));

return result;
}


Related: Effective Java, 2nd edition, Item 47: Know and use the libraries The author mentions only the JDK's built-in libraries but I think the reasoning could be true for other libraries too.

1. I'd use consistent indentation.

2. Short variable names (like x) are not too readable:

ListNode(int x) {
val = x;
...


I suppose you have autocomplete, so using longer names does not mean more typing but it would help readers and maintainers a lot since they don't have to remember the purpose of each variable - the name should express the programmers intent. val also could be value. (Clean Code by Robert C. Martin, Avoid Mental Mapping, p25)

-
so if you were interviewing me, and I produced that working code in 45 minutes(I didn't create that ListNode class, it was a given, I only wrote the functions); you'd think I'm not Google quality? Please be honest here, and offer a bit of critique on what I'm doing wrong. I can generally solve questions quickly, but have a hard time producing the beautiful solution that you produced. –  bazang Mar 5 '14 at 1:29
@bazang: Oh dear :) What's Google quality at all? I guess the expected code quality depends on the position you applied for and code quality might not be the most important (!) factor for them. (I expect better code from a senior than a junior, therefore the junior's code could be worse.) So do your homework because code quality might not be that you should optimize for, maybe there are more important things you could learn. Anyway, you can find some good resources here: codereview.stackexchange.com/q/31/7076 workplace.stackexchange.com also a good place. –  palacsint Mar 5 '14 at 20:45
From the question statement: "You may not alter the values in the nodes, only nodes itself may be changed." It seems they wanted you to work with actual nodes. They would probably be annoyed if you used guava in this case. –  toto2 Nov 2 '14 at 16:49

Thank you for posing this delightfully tricky interview question. Before writing this review, I felt compelled to try coding it myself — on paper. It took me about an hour, and I made three mistakes.1 I've posted my solution below, with comments added after the fact. (In an interview, commentary would probably have been presented verbally.)

Evaluation criteria

If I were asking this question as an interviewer, here's what I would look for in a candidate's response. Of course, these criteria reflect my own abilities and preferences.

1. Reasonable syntax. If writing the solution on a computer, the code must compile with no warnings and no suppressed warnings. If writing the solution on a whiteboard, it should "visually compile" with only minor syntax errors.

2. One-pass O(n) solution. The solution, whether correct or not, must attempt to complete the task by traversing the list just once. If the candidate fails to produce code that accomplishes the task in one pass, I would be lenient if he/she spontaneously apologized for using a suboptimal algorithm. (In that case, I might ask the candidate to try again at the end of the interview, schedule permitting.)

For an interview, I would value a slightly buggy one-pass O(n) algorithm over a bug-free but inefficient algorithm. I believe that the candidate should quickly recognize that a one-pass solution is possible. Minor bugs are inevitable, but picking an inefficient strategy would just be going off in the wrong direction altogether.

In my opinion, a candidate who produces an inefficient algorithm should not be hired to develop production code: his/her work would probably require subsequent intervention by other developers to fix performance problems. However, such a programmer could still be useful for maintenance work or writing code for internal use (such as QA tests).

Your findSize() and findEnd() helper methods both walk the list to the end. Since your findEnd() is called from within a loop, your algorithm must not be O(n), much less a one-pass O(n).

3. Intelligent interaction. I would like to see that the candidate asks questions to seek clarification before and during the coding process. Some of the questions I would ask are listed below.

4. General cluefulness. A solution should be reasonably concise, and each chunk of code should be purposeful. By purposeful, I mean that I should be able to point to a chunk of code, and the candidate should be able to explain, preferably using diagrams, what the data structure looks like before executing that chunk, and the result after executing that chunk.

To be honest, your solution is too complex for me to follow in my head. If presented with your solution, I'd just challenge you with some questions instead:

• Is this an iterative or recursive solution? Why did you pick that over the alternative?
• What kind of running time would you expect?
• You have a cursor and a current. Isn't current a kind of cursor as well? Could you come up with more purposeful names?
• What is the Queue for?
• Before entering the first while-loop, there appear to be four base cases. Is that reasonable number of base cases? Could you get away with fewer base cases?
• Can you explain the loop condition while (cursor != null || cursor.next != null)? Would there ever be a situation where cursor is null but cursor.next is not?

Hopefully, those questions would trigger some "Aha!" or "Oops!" moments and result in some improvements. To be frank, though, your code is way too complex and confusing to be salvageable through a Socratic dialogue.

Interviewee strategy

1. For this question, I would prefer recursion to iteration. Recursive solutions are often more succinct and involve fewer variables. Recursion enforces some rigour in your thinking process, by making you think about preconditions, postconditions, and invariants. Recursion works well for this linked-list question precisely because invariants exist: walk k nodes down the list, and the situation looks similar.

Production Java code often avoids recursion due to practicalities such as the function-call overhead and worries about stack overflow. However, interview questions are naturally an academic exercise. Just in case the interviewer is prejudiced against recursion, ask two questions:

• "Will the input be small enough such that the stack overflow is not a concern?"
• "How about a recursive solution? I can rewrite it as an iterative solution afterwards, if you prefer."
2. Keep it simple. There are other things you can get away when coding in an interview, especially if coding on a whiteboard. Just keep talking.

• import java.util.*; "Of course, in production code, I would list individual classes."
• Naked linked list nodes. "Normally, I'd hide the nodes within the linked list. To save time, we'll just say that a node is a list. OK?"
• Public fields. "Normally, there would be getters and setters. I'll take a shortcut and expose .value and .next. However, to enforce your rule that nodes should have their pointers and not values manipulated, I'll make .value final. OK?"
3. Think out loud. Draw diagrams. Ask questions, especially questions that clarify the requirements. Score some points before writing a single line of code.

My ideal

Here's my solution, for comparison. The heart of the implementation, the kReverse() helper, is only about a dozen lines, if you strip out assertions and comments.

// Import * not advisable in production code, but good enough for interview code
import java.util.*;
import static java.lang.System.out;

public final T value;

this.value = value;
this.next = next;
}

public static <T> LinkedListNode<T> makeList(List<T> list) {
for (int i = list.size() - 1; i >= 0; i--) {
}
}

/**
* Stringifies entire list for diagnostics.
*/
public String toString() {
StringBuilder sb = new StringBuilder(this.value.toString());
for (LinkedListNode<T> n = next; n != null; n = n.next) {
sb.append(" -> ").append(n.value.toString());
}
return sb.toString();
}

if (k < 1) throw new IllegalArgumentException("k = " + k);
}

/**
* Sets the <tt>.next</tt> pointer of the <tt>head</tt> node and all
* of its successors to perform k-group reversal of a list.
*
* @param head   The current node being processed
* @param k      Chunk size, as specified in the problem
* @param group  The original head of this k-group
* @param prev   The original predecessor of head
* @param remain The number of nodes remaining to be processed in this
*
* @return The new leading node of the current k-group (which could be null
*         if the current k-group is empty)
*/
int remain) {
assert remain > 0;
// Incomplete or empty group.
return group;

} else if (1 == remain) {
// head is the last node of the k-group, and will become the
// leading node of the reversed k-group.

// Reverse the next k-group (and by recursion, all subsequent
// k-groups).  n is the leading node of the next k-group after
// its reversal is complete (possibly null).

// The next two statements must be in this order, because if
// k == 1, head and group are the same.
group.next = n;

} else {
// head not the last node of the k-group.  n is the leading node of
// this k-group after reversal: the same as the old leading node if
// this k-group is incomplete, or the same as the old trailing node
// of this k-group if reversal succeeds.

// group != n means this k-group has k members and is being reversed.
if (group != n && head != group) {
// i.e., the new trailing node, since it was already set in
// the (1 == remain) case above.
}
return n;
}
}

/**
* Tests
*/
public static void main(String[] args) {
List<Integer> oneFive = Arrays.asList(new Integer[] {1, 2, 3, 4, 5});
// No-op expected...
// IllegalArgumentException expected...
}
}


As stated above, comments and JavaDoc were added just before posting the code; I wouldn't have produced such nice comments in a time-limited situation.

This is, of course, not the only good solution possible. However, as you can see, your implementation is quite far off.

1 The three mistakes I made were:

• Wrote static LinkedListNode<T> function(…) instead of static <T> LinkedListNode<T> function(…)
• Forgot the head != group condition near the end of kReverse()
• Silly mistake when writing main().
-
I know it took you a while to write that comment; and I want to mention/emphasize, that I appreciate your time. I'll be posting more of my responses to questions that I will try to answering, and will appreciate it if you may continue to be brutally honest with me about my code. I will also start posting how long it took me to solve it. I agree, that in the case of that problem, I still feel like I did a TERRIBLE job, and honestly lost sleep over the fact that I couldn't solve it in a better manner. –  bazang Mar 5 '14 at 19:28
Please remember to upvote all answers that you find useful. I don't usually mention how much time it took me, but did so in this case only because you mentioned it too. This was not an easy challenge! Take your time to think through it. Hope to see more of your posts on Code Review! @JavaDeveloper is in a similar situation as you, and is up to 91 posts now. –  200_success Mar 5 '14 at 19:51
@JavaDeveloper, I think that trying to answer some questions tagged as interview-questions would give you some insight to help improve your interviewing skills. –  200_success Mar 5 '14 at 20:10