Databases
StackOverflow2013
Postsdbo
POJava programming task efficiency
 

Note that there are some explanatory texts on larger screens.

plurals
  1. POJava programming task efficiency
    primarykey
    data
    text
    <p>I am trying to learn to write more efficient code. Any chance that some of you genius developers could help me out and let me know where my code is going wrong? How can I make it more efficient?</p> <p>I just completed a task on Codility.com, and I passed all the tests, but my code wasn't efficient enough when larger strings were passed in.</p> <p>Task description:</p> <blockquote> <p>A prefix of a string S is any leading contiguous part of S. For example, "c" and "cod" are prefixes of the string "codility". For simplicity, we require prefixes to be non-empty. The product of prefix P of string S is the number of occurrences of P multiplied by the length of P. More precisely, if prefix P consists of K characters and P occurs exactly T times in S, then the product equals K * T.</p> </blockquote> <p>For example, S = "abababa" has the following prefixes:</p> <blockquote> <p>"a", whose product equals 1 * 4 = 4,</p> <p>"ab", whose product equals 2 * 3 = 6,</p> <p>"aba", whose product equals 3 * 3 = 9,</p> <p>"abab", whose product equals 4 * 2 = 8,</p> <p>"ababa", whose product equals 5 * 2 = 10,</p> <p>"ababab", whose product equals 6 * 1 = 6,</p> <p>"abababa", whose product equals 7 * 1 = 7.</p> </blockquote> <p>The longest prefix is identical to the original string. The goal is to choose such a prefix as maximizes the value of the product. In above example the maximal product is 10.</p> <p>In this problem we consider only strings that consist of lower-case English letters (a-z).</p> <p>Write a function</p> <pre><code>class Solution { public int solution(String S); } </code></pre> <p>that, given a string S consisting of N characters, returns the maximal product of any prefix of the given string. If the product is greater than 1,000,000,000 the function should return 1,000,000,000.</p> <p>For example, for a string:</p> <blockquote> <p>S = "abababa" the function should return 10, as explained above,</p> <p>S = "aaa" the function should return 4, as the product of the prefix "aa" is maximal.</p> </blockquote> <p>Assume that:</p> <blockquote> <p>N is an integer within the range [1..300,000];</p> <p>string S consists only of lower-case letters (a-z).</p> </blockquote> <p>Complexity:</p> <p>Expected worst-case time complexity is O(N);</p> <p>Expected worst-case space complexity is O(N) (not counting the storage required for input arguments).</p> <p>Here were my failed results:</p> <blockquote> <p>easy_morphism a -> a?a 2.150 s. TIMEOUT ERROR running time: >2.15 sec. large_random_string cyclic + random string 1.180 s. TIMEOUT ERROR running time: >1.18 sec.</p> <p>large_cyclic large cyclic tests 2.170 s. TIMEOUT ERROR running time: >2.17 sec.</p> <p>single_letter_with_some_tweaks 2.170 s. TIMEOUT ERROR running time: >2.17 sec.</p> <p>same_small_pattern_with_small_tweaks 2.160 s. TIMEOUT ERROR running time: >2.16 sec.</p> <p>same_big_pattern_with_small_tweaks 4.660 s. TIMEOUT ERROR running time: >4.66 sec.</p> <p>small_pattern_with_tweaks_in_one_place 4.700 s. TIMEOUT ERROR running time: >4.70 sec.</p> </blockquote> <p>Any help or hints would be handy!</p> <pre><code>public class test { public static void main(String[] args) { long startTime = System.nanoTime(); System.out.println("solution: " + solution("abababa")); long endTime = System.nanoTime(); long duration = endTime - startTime; System.out.println("duration: " + duration/1000000.0 + " seconds"); } public static int solution(String S) { int solution = 0, N = S.length(); String P; for (int K = 1; K &lt;= N; K++) { P = S.substring(0, K); int T = calculateT(P, S); int tmpSolution = K * T; if (tmpSolution &gt; solution) { solution = tmpSolution; } } return solution; } public static int calculateT(String P, String S) { int T = 0, indexOfStart = 0; while (indexOfStart &gt; -1) { T++; indexOfStart = S.indexOf(P, indexOfStart+1); } return T; } } </code></pre>
    singulars
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PTQuestion
    1. USPeter Mortensen
    1. USjakedunc
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. PO
      singulars
      1. PTAnswer
    1. VO
      singulars
      1. POJava programming task efficiency
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. POJava programming task efficiency
      1. This table or related slice is empty.
      1. VTUpMod
    1. COHere's a few hints: http://en.wikipedia.org/wiki/Trie http://en.wikipedia.org/wiki/Suffix_tree
      singulars
      1. POJava programming task efficiency
      1. USafk5min
    2. CO@afk5min Nice, I wonder did you know it beforehand or did you google it?
      singulars
      1. POJava programming task efficiency
      1. USFabinout
    3. COI recently had a lecture titled 'Suffix structures' all about memory-hogging structures that optimize various operations within strings :P
      singulars
      1. POJava programming task efficiency
      1. USafk5min
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload