Rearrange String such that similar characters are placed at least 'K' distance apart So I was asked this in an interview, and I had to write this code on a white board. Sadly I couldn't complete the code :( . 

I've realized that writing code on white board is completely different from typing it on an editor. Firstly because, I type way faster than I write and secondly I can't keep adding lines in between, so the first line has to be my best line of code. 

What are some of the things I should keep in mind before I write my code, so that I make sure I make minimal changes once I write? 

// The idea is to calculate frequencies of characters, and create the 
// string by putting highest frequency characters one after another into it
// for 'K' times, and repeat the process.
/* Example:
* S = AAABBBCC, K = 3
* Result : ABCABCAB (all 'A's are 3 distance apart, similarly with B's and C's)
*/
class Node implements Comparable&lt;Node&gt;{
    char c;
    int frequency;

    public Node(char c, int f) {
        this.c = c;
        this.frequency = f;
    }

    public int compareTo(Node other) {
        if (this.frequency &gt; other.frequency)
            return -1;
        if (this.frequency &lt; other.frequency)
            return 1;
        if (this.c &lt; other.c)
            return -1;
        if (this.c &gt; other.c)
            return 1;
        return 0;
    }
}

public String rearrange(String s, int k) {
    StringBuilder sb = new StringBuilder();
    // calculate frequency
    Map&lt;Character, Integer&gt; map = new HashMap&lt;Character, Integer&gt;();
    for (Character c : s.toCharArray()) {
        if (map.containsKey(c)) {
            map.put(c, map.get(c) + 1);
        } else {
            map.put(c, 1);
        }
    }
    // create frequency based heap, if duplicate frequency, order alphabetical
    PriorityQueue&lt;Node&gt; heap = new PriorityQueue&lt;Node&gt;();

    for (Character c : map.keySet()) {
        heap.add(new Node(c, map.get(c)));
    }

    int len = 0;
    // keep removing k elements from heap
    // add them to result string
    // decrease frequency and add back to heap
    while (len &lt; s.length()) { // (n/k) * k log(n) == n log(n)

        int tempK = 0;
        Deque&lt;Node&gt; tempList = new LinkedList&lt;Node&gt;();

        while (tempK &lt; k &amp;&amp; !heap.isEmpty()) { // k log(n)
            Node node = heap.remove();
            sb.append(node.c);
            node.frequency--;
            if (node.frequency != 0) {
                tempList.add(node);
            }
            tempK++;
        }
        while (!tempList.isEmpty()) { //k log(n)
            heap.add(tempList.remove());
        }
        len = len + k;
    }
    return sb.toString();
}
I think it's unlikely that interviewers are expecting you to write perfect code up on the white board.  The main goals of these tasks is to get an insight into how you go about solving problems, knowledge of the language features and attention to detail.  You can demonstrate attention to detail by writing 100% correct code, however you can also demonstrate it in other ways.  My starting point is usually to clarify the requirements with the interviewers.  You can do this in the context of unit testing to help identify some test cases that you are considering and getting them to clarify what the expected outcomes from those cases would be.  These can be added to the board so that you have a reference.  So, for example:


What happens if you are passed an empty string
What happens if there is only 1 characters
What happens if you've got "aa" as suggested by @coderodde
What happens with "AAABBBCC", which is your example.  You've said it should be "ABCABCABC", which has introduced an extra C.  Is this really right?


Clarifying the problem not only demonstrates attention to detail and helps you to understand the problem, it also buys you some time to think about how best to solve the problem.

Next you need to think about the algorithm you're going to implement.  Consider jotting it down on paper or the whiteboard so that you've got a reference design, that way you can worry about the order/steps required without having to worry about the language constructs/syntax at the same time.

Have some kind of checklist in mind for what you need to consider in your solution. For example:


Public interface
Parameter checking
Error handling
Exceptions
etc


This will help you to at least consider these things.  You can then talk about them if appropriate, even if you choose not to write them up on the board.  So "I'd check 'k' to ensure it's a positive integer at the start of this method and throw IllegalArgumentException if it wasn't, however I'm not going to write it on the board so that I can concentrate on the main algorithm".

As far as your actual code you've posted goes, the spec isn't entirely clear (as demonstrated by some of questions above).  You're missing error checking on your rearrange method.  For example you don't check if k&lt;=0, what's going to happen if this is passed?

Try to be more expressive with variable names.  It's tempting when you have to write them down to shortcut names (heap,tempK,k,tempList etc), however if you do this in much the same way it causes problems for future maintainers, it makes it harder for you to remember what the variables represent and for the interviewers to follow your algorithm.

This line also looks a bit odd to me:

Deque&lt;Node&gt; tempList = new LinkedList&lt;Node&gt;();