# Finding the Mth to last Element

Challenge:

Write a program which determines the Mth to last element in a list.

Specifications:

The first argument is a path to a file.
The file contains series of space delimited characters followed by an integer.

The integer represents an index in the list (1-based), one per line.
Print out the Mth element from the end of the list, one per line.

If the index is larger than the number of elements in the list, ignore that input.

Solution:

import java.io.File;
import java.io.FileNotFoundException;
import java.util.Scanner;

public class MToLast {
public static void main(String[] args) throws FileNotFoundException {
Scanner input = new Scanner(new File(args[0]));

while (input.hasNextLine()) {
retrieveAndPrintMToLast(input.nextLine());
}
}

private static void retrieveAndPrintMToLast(String line) {
int targetIndex = Integer.parseInt(line.replaceAll("\\D", ""));
String sanitized = line.replaceAll("[^a-zA-Z]", "");
int limit = sanitized.length();

if (targetIndex <= limit) {
System.out.println(sanitized.charAt(limit - targetIndex));
}
}
}


This passes my tests, I tried to account for some edge cases, is there anything I missed or something I can improve?

For anyone interested, this challenge, and many others like it are available here.

• What happens when m is > 9? – lealand Mar 8 '15 at 22:55
• Doesn't occur, according to the specifications it is 1 based. – Legato Mar 8 '15 at 22:57
• 1-based means the array is 1-to-M, not 0-M or 0-(M-1) etc. Look up the split method. That's what you should be using. I'd also use \\s+ for your split regex so that you can support an arbitrary number of spaces between the entries. – lealand Mar 8 '15 at 23:00
• I'm aware of the split method, I misunderstood what '1 based' meant. – Legato Mar 8 '15 at 23:02
• Can you cite a source for the challenge? – 200_success Mar 9 '15 at 13:29

Your solution looks nice and compact, but it's not necessarily how I would go about it. I come from a background where you have to anticipate faulty input, and so I raise my eyebrows at the first two lines of your method where you blindly start replacing the input.

What happens if you read a line of characters like A B 3 D 5 1? Do you still get A as a result? Numeric characters are still characters. Also, \n is char. The class is much more than what is captured by your [^a-zA-Z] pattern.

The problem specification is straightforward, but you're trying to attack it with regexes instead of something more appropriate. As soon as you transform your input, you are working with data that is manipulated based on your assumptions. This will lead to strange bugs later on that are hard to track down.

I would also suggest changed the method from returning void to char, then let whatever calling method take care of the output.

Finally, make sure you're testing all the bases. What happens when there's an empty string? A string with just one character, or just one integer. What if the last integer is less than 0?

• This was a programming challenge and actually passed, but it was very helpful to see how vastly different mine was when account for the real world. For you to point out all the cases where this would simply cause an error/fail was immensely profound. Thank you. – Legato Mar 9 '15 at 2:30

If I'm interpreting the problem definition right, the input contains single letters, all delimited by precisely one space. At the end of the line is an integer. Since the text says "integer" rather than "digit", I would assume it can consist of multiple characters, for example "123" would be valid, not only the digits 1 to 9. I will assume this interpretation in my answer.

First, to make the solution testable, I'd extract the main logic to a function that takes a line and returns the mth-to-last character or 0 (that's different from '0', mind you) if m is out of range.

static char retrieveAndPrintMToLast0(String line) {
String sanitized = line.replaceAll("\\s", "");
if (!sanitized.isEmpty()) {
int limit = sanitized.length() - 1;
int targetIndex = Character.getNumericValue(sanitized.charAt(limit));
sanitized = sanitized.substring(0, limit);

if (targetIndex <= limit) {
return sanitized.charAt(limit - targetIndex);
}
}
return 0;
}


Now it's possible to add some unit tests to verify the behavior:

@Test
public void test_hello_1() {
assertEquals('o', getMthToLast("h e l l o 1"));
}

@Test
public void test_hello_5() {
assertEquals('h', getMthToLast("h e l l o 5"));
}

@Test
public void test_hello_9() {
assertEquals(0, getMthToLast("h e l l o 9"));
}

@Test
public void test_helloworld_10() {
assertEquals('h', getMthToLast("h e l l o w o r l d 10"));
}

@Test
public void test_helloworld_11() {
assertEquals(0, getMthToLast("h e l l o w o r l d 11"));
}

@Test
public void test_1_2_3_4_2() {
assertEquals('3', getMthToLast("1 2 3 4 2"));
}

@Test
public void test_empty_1() {
assertEquals(0, getMthToLast("1"));
}


Most of these tests pass, except the two cases where the last "integer" consists of more than 1 digit.

With these unit tests covering my back, now I can boldly go and refactor the original code:

• It should be possible to calculate the right position without removing the spaces
• Removing the spaces doesn't look great in general: it's an extra $O(N)$ operation (though I do realize we're talking about a N that's maximum 9, but still...)
• Removing the spaces would clearly not have a place in a little bit extended problem where there may be multiple character sequences, not just single letters, as removing the spaces in that case would destroy the input.
• The sanitized.isEmpty check seems a bit redundant: the text says that each line is followed by an integer, so if there's an integer, the line will never be empty

The modified implementation incorporating these ideas:

static char retrieveAndPrintMToLast(String line) {
int limit = (line.length() - 1) / 2;
int indexAfterLastSpace = line.lastIndexOf(' ') + 1;
int targetIndex = Integer.parseInt(line.substring(indexAfterLastSpace));

if (targetIndex <= limit) {
return line.charAt(indexAfterLastSpace - 2 * targetIndex);
}
return 0;
}