5
\$\begingroup\$

This is a problem in CodeEval, moderate level. The problem is very easy for this level. But I am not able to get more than 60 points for any solution I submit. (Moderate levels highest score is 65 and they take speed and memory into consideration.)

The problem statement is:

There are two strings: A and B. Print 1 if string B occurs at the end of string A. Otherwise, print 0.

Input

  1. Hello World,World
  2. Hello CodeEval,CodeEval
  3. San Francisco,San Jose

Output

  1. 1
  2. 1
  3. 0

import java.io.*;

public class Main {
    public static void main (String[] args) throws IOException {
        File file = new File(args[0]);
        BufferedReader buffer = new BufferedReader(new FileReader(file));
        String line;
        String[] words;
        while ((line = buffer.readLine()) != null) {
            System.out.println(trailingStrings(line));
        }
    }

    public static int trailingStrings(String line) {
        int indexOfComma = line.indexOf(",");

        int secondStringLength = line.length()-indexOfComma-1;

        int firstStringLength = indexOfComma;

        if(firstStringLength < secondStringLength) {
            return 0;
        }
        int i = indexOfComma+1;
        int j = indexOfComma - secondStringLength;
        while(j<indexOfComma) {
            if(line.charAt(j) != line.charAt(i)) {
                return 0;
            }
            j++; i++;
        }
        return 1;
    }
}
  • Memory Usage: 4784128 (bytes)
  • Speed: 644 ms

If I instead split the line with "," and get the words and use String.endsWith(), I am getting better memory usage. This surprises me because in my first solution I am not creating new String objects, I just use one String.

import java.io.*;
public class Main {
    public static void main (String[] args) throws IOException {
        File file = new File(args[0]);
        BufferedReader buffer = new BufferedReader(new FileReader(file));
        String line;
        String[] words;
        while ((line = buffer.readLine()) != null) {
            words = line.split(",");
            String s1 = words[0];
            String s2 = words[1];
            if(s1.endsWith(s2)){
                System.out.println("1");
            } else {
                System.out.println("0");
            }
        }
    }
}
  • Memory Usage: 413696 (bytes)
  • Speed: 1047 ms

Why is my first solution taking up so much memory? Is it because of the int declarations? If I remove int declarations and use the values directly, memory usage reduced by half to 2412544 bytes but still way higher compared to second solution.

\$\endgroup\$
  • \$\begingroup\$ Have you tried returning a String from your function instead of an int? I.E. return "0" and return "1" ? I bet whatever java uses to convert int to String is using some memory. \$\endgroup\$ – JS1 Aug 6 '15 at 5:46
  • \$\begingroup\$ The additional declarations will contribute to the increased memory allocation but I think the largest factor will be the additional method. Sedgewick has a breakdown on the space that is allocated (for Java) — look under the memory usage heading. It is quite an interesting exercise to pick a problem on CodeEval and solve it in a variety of ways to compare how the time and memory scores differ (you can see here the variety of scores for FizzBuzz). \$\endgroup\$ – Alex01 Nov 16 '15 at 17:49
1
\$\begingroup\$

I suggest a functional answer for this problem (In ruby but should easily be translatable into Java):

def endswith(text, appendix)
    text.last(appendix.length) == appendix
end

I did not benchmark but this approach is likely to be faster as you are only using using 2 functions and a comparison instead of all the loops and ifs that you used.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.