Recently I came across an interview question - "Given a statement in char[], reverse the order of words in that statement without using any extra temporary char[] or String functions". Here is my solution for this question.
There will be N - 1 Runs for reversing a statement which has N words in it.
1st Run will move the First word in statement to make it as Last Word and move the remaining space from first position before the word just moved.
2nd Run will move the now First word in statement to make it as 2nd last word and the remaining space from first position before the word just moved.
So, (N-1)th Run will move the now First word in statement to make it as Nth last word (i.e., Second Word) and the space before it from first position.
There will be N - 1 Runs for reversing a statement which has N words in it.
1st Run will move the First word in statement to make it as Last Word and move the remaining space from first position before the word just moved.
2nd Run will move the now First word in statement to make it as 2nd last word and the remaining space from first position before the word just moved.
So, (N-1)th Run will move the now First word in statement to make it as Nth last word (i.e., Second Word) and the space before it from first position.
public class ReverseStatement {
private static final char WORD_DELIMITER = ' ';
public static void main(String[] args) {
char[] input = "One Two Three Four".toCharArray();
System.out.println(input);
new ReverseStatement().reverse(input);
System.out.println(input);
}
int wordsLength[];
public synchronized void reverse(char[] input) {
if (input == null) {
throw new NullPointerException("input");
}
if (input.length == 0) {
throw new IllegalArgumentException("input is empty");
}
if (input[0] == WORD_DELIMITER || input[input.length - 1] == WORD_DELIMITER) {
throw new IllegalArgumentException(
"input must not start or end with SPACE");
}
countAndUpdateWordsLength(input);
int newPosition = input.length;
for (int run = 1; run < (wordsLength.length); run++) {
newPosition = newPosition - wordsLength[run - 1];
shiftFirstNCharsTo(input, wordsLength[run - 1], newPosition);
shiftFirstNCharsTo(input, 1, --newPosition);
}
}
private void countAndUpdateWordsLength(final char[] input) {
int wordCount = 0;
// Loop to identify the total number of words.
int lastSpaceAt = 0;
for (int i = 0; i < input.length; i++) {
if (input[i] == WORD_DELIMITER) {
wordCount++;
if (lastSpaceAt == (i - 1)) {
throw new IllegalArgumentException(
"Continuous Spaces Detected " + i + ", " + lastSpaceAt);
}
lastSpaceAt = i;
}
}
// Incrementing by 1 for last word in input
wordCount++;
wordsLength = new int[wordCount];
int wordNumber = 0;
int eachWordLength = 0;
// Loop to count each word's length
for (int i = 0; i < input.length; i++) {
if (input[i] == WORD_DELIMITER) {
wordsLength[wordNumber] = eachWordLength;
eachWordLength = 0;
wordNumber++;
continue;
}
eachWordLength++;
}
wordsLength[wordNumber] = eachWordLength; // For the last word
}
private static void shiftFirstNCharsTo(char[] input, int n, int newPosition) {
if (newPosition + n > input.length) {
throw new RuntimeException("Cannot move to " + newPosition);
}
for (int x = n - 1; x >= 0; x--) {
int targetPosition = newPosition + n - 1;
for (int y = x; y < targetPosition; y++) {
char t = input[y];
input[y] = input[y + 1];
input[y + 1] = t;
}
newPosition--;
}
}
}
Output:
One Two Three Four
Four Three Two One
If you find any bug or improvement area, please comment.
