Reversing k-sized sequences in a linked-list

Question

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

Given this linked list: 1->2->3->4->5

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 cursor = head; 
     ListNode current = null;
     ListNode remainingHalf = null;
     Queue linkQueue = new LinkedList();

     if(head==null){
         return null;
     }

     if(k<=1){
         return head;
     }
     if(k>findSize(head)){
         return head;
     }
     if(k==2){
         return reverse(head);
     }

     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;

             ListNode partial = reverse(head);
             linkQueue.add(partial);

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

     }
     boolean headFlag=false;
     ListNode toRet=null;
     while(!linkQueue.isEmpty()){
         ListNode first = (ListNode)linkQueue.poll();
         ListNode end=null;
         if(first!=null){
            end =  findEnd(first);
            if(headFlag==false){
                toRet = first;
                headFlag=true;
            }
         }
         else{
             break;
         }
         ListNode second = (ListNode)linkQueue.poll();
         if(second==null){
             ListNode temp = findEnd(toRet);
             temp.next=first;
             break;
         }
         end.next=second;


         if(linkQueue.size()==1 || linkQueue.size()==0){
             ListNode last = findEnd(toRet);
             last.next = (ListNode)linkQueue.poll();

         }
     }
     return toRet;

    }

    public int findSize(ListNode head){
        int count=0;
        while(head!=null){
            count++; head=head.next;
        }
        return count;
    }

    public ListNode findEnd(ListNode head){
        while(head.next!=null){
            head = head.next;
        }
        return head;
    }

    public ListNode reverse(ListNode head){
        if(head==null){
            return null;
        }
        if(head.next==null){
            return head;
        }
        ListNode remaining = head.next;
        head.next = null;
        ListNode temp = reverse(remaining);
        remaining.next = head;
        return temp;
    }
}

Answer 1

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.
    }

    public void add(int v) {
        ListNode node = head;
        while (node.next != null) {
            node = node.next;
        }
        node.next = new ListNode(v);
    }

    public void addAll(SolutionList toadd) {
        ListNode tail = head;
        while (tail.next != null) {
            tail = tail.next;
        }
        ListNode their = toadd.head.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;
        ListNode node = head.next;
        ListNode mark = head;
        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 [");
        ListNode node = head.next;
        while (node != null) {
            sb.append(node.val).append(", ");
            node = node.next;
        }
        if (head.next != null) {
            sb.setLength(sb.length() - 2);
        }
        sb.append("]");
        return sb.toString();
    }

    public SolutionList reverseK(final int k) {
        SolutionList copy = new SolutionList();
        copy.addAll(this);
        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) {
            soln.add(v);
        }
        System.out.println(soln);
        System.out.println("Reverse 2 " + soln.reverseK(2));
        System.out.println("Reverse 3 " + soln.reverseK(3));
    }

}

Answer 2

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 static com.google.common.collect.Lists.newLinkedList;
import java.util.LinkedList;
import java.util.List;
import com.google.common.collect.Iterables;
import com.google.common.collect.Lists;

...

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));

    final List<T> result = newLinkedList();
    Iterables.addAll(result, reversedFirstPart);
    Iterables.addAll(result, secondPart);
    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.

Two notes about the implementation:

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)

Answer 3

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.¹ 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.

   Your code compiles with warnings about Generics.

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 class LinkedListNode<T> {
    public final T value;
    private LinkedListNode<T> next;

    public LinkedListNode(T value, LinkedListNode<T> next) {
        this.value = value;
        this.next = next;
    }

    public static <T> LinkedListNode<T> makeList(List<T> list) {
        LinkedListNode<T> head = null;
        for (int i = list.size() - 1; i >= 0; i--) {
            head = new LinkedListNode<T>(list.get(i), head);
        }
        return head;
    }

    /**
     * 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();
    }

    public static <T> LinkedListNode<T> kReverse(LinkedListNode<T> head, int k) {
        if (k < 1) throw new IllegalArgumentException("k = " + k);
        return kReverse(head, k, head, null, 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
     *               k-group, including head
     *
     * @return The new leading node of the current k-group (which could be null
     *         if the current k-group is empty)
     */
    private static <T> LinkedListNode<T> kReverse(LinkedListNode<T> head, int k,
                                                  LinkedListNode<T> group,
                                                  LinkedListNode<T> prev,
                                                  int remain) {
        assert remain > 0;
        if (null == head) {
            // 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).
            LinkedListNode<T> n = kReverse(head.next, k, head.next, null, k);

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

            return head;

        } 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.
            LinkedListNode<T> n = kReverse(head.next, k, group, head, remain - 1);

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

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

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.

---

¹ 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().