Interview Puzzlers: Sentence Reverse & Palindrome

Java interview puzzlers

Java interview puzzlers

 

Given a sentence such as “The fox jumps over the lazy dog”, implement in Java how you would reverse this to output “dog lazy the over jumps the fox”.

This is a relatively simple piece of code that has a few gotchas. Watch the code along video below or head straight past for the explanation.

public class StringReverserTest {
    @Test
    public void wordsOfTheStringWillBeInReverseOrder() throws Exception {
        StringReverser stringReverser = new StringReverser();
        String result = stringReverser.reverse("fox jumps over the lazy dog");
        assertThat(result, is("dog lazy the over jumps fox"));
    }
}
public class StringReverser {

    public String reverse(String stringToReverse) {
        String[] split = stringToReverse.split(" ");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = split.length ; i > 0; i--) {
            stringBuilder.append(split[i - 1] + " ");
        }
        return stringBuilder.substring(0, stringBuilder.length() - 1);
    }
}

First of all we need to split the string into its constituent words, which we can do using the .split() function on String.  It’s surprising how many people don’t realise functions like this exist which mean they are instantly flumoxed.

We then iterate in reverse through the array.  We take the length of the array (e.g. the number of words) and count down.  This can be tricky due to zero indexing so be careful.

We then append each word to a StringBuilder and add a space.  Why StringBuilder? If in theory we were to pass a huge sentence of thousands of words into this method then it would create a ton of objects, which would also make it slower.  Take this code sample I’ve just run on my machine:

//Version 1
long l = System.currentTimeMillis();
       StringBuilder sb = new StringBuilder();
       for(int i=0; i<10000; i++){
           sb.append("Core Java Interview Questions");
       }
       System.out.println(System.currentTimeMillis() - l);
//Version 2
       l = System.currentTimeMillis();
       String hi = "";
       for(int i=0; i<10000; i++){
           hi = hi + "Core Java Interview Questions";
       }
       System.out.println(System.currentTimeMillis() - l);

The StringBuilder version takes 7ms. Incredibly the second version takes 4112ms.  That’s almost 600 times slower!

We then have the final gotcha; when returning the String we need to cut off the last space (every time we add a word we add a space to the end).  Substring can be tricky for getting the indexing

Write a program to detect if a String is a Palindrome
Watch the code-along video below or head straight past for the explanation.

public class PallindromDetectorTest {
    @Test
    public void detectsThatRacecarIsRacecarBackwards() throws Exception {
        PallindromDetector pallindromDetector = new PallindromDetector();
        boolean result = pallindromDetector.check("racecar");
        assertThat(result, is(true));
    }

    @Test
    public void emptyStringIsAPallindrome() throws Exception {
        PallindromDetector pallindromDetector = new PallindromDetector();
        boolean result = pallindromDetector.check("");
        assertThat(result, is(true));
    }

    @Test
    public void oneLetterIsAPallindrome() throws Exception {
        PallindromDetector pallindromDetector = new PallindromDetector();
        boolean result = pallindromDetector.check("a");
        assertThat(result, is(true));
    }

    @Test
    public void returnsFalseForAWordThatIsNotAPallindrome() throws Exception {
        PallindromDetector pallindromDetector = new PallindromDetector();
        boolean result = pallindromDetector.check("Core Java Interview Questions");
        assertThat(result, is(false));
    }
}


public class PallindromDetector {
 public boolean check(String toCheck) {
 for (int i = 0; i < toCheck.length(); i++) {
 int length = toCheck.length();
 if(!(toCheck.charAt(i) == (toCheck.charAt(length -1-i)))){
 return false;
 }
 if(i + 1 >= length/2)break;
 }
 return true;
 }
}

In this example there are a few requirements considerations. What happens if the String is empty? What happens if there is only one letter?  You should ensure you ask this question. I’ve assumed that both are in fact palindromes.

There are multiple approaches to this, but I have gone with this simple solution that involves no extra data structures and only half a run through of the data.  We use a loop to iterate through the data; at 0, we check the first character to see if it matches the last character.  If it does not, we instantly return false.  We then increment i by 1, and check the next letter along, then the next furthest back.  This continues until we get halfway, or one less than halfway if it’s an uneven number of letters.

 

Be the first to leave a comment. Don’t be shy.

Join the Discussion

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <s> <strike> <strong>