diff options
Diffstat (limited to 'Phone Book/Instant search')
| -rw-r--r-- | Phone Book/Instant search/task-info.yaml | 85 | ||||
| -rw-r--r-- | Phone Book/Instant search/task-remote-info.yaml | 2 | ||||
| -rw-r--r-- | Phone Book/Instant search/task.html | 29 |
3 files changed, 116 insertions, 0 deletions
diff --git a/Phone Book/Instant search/task-info.yaml b/Phone Book/Instant search/task-info.yaml new file mode 100644 index 0000000..6fd9cf2 --- /dev/null +++ b/Phone Book/Instant search/task-info.yaml @@ -0,0 +1,85 @@ +type: edu +custom_name: stage4 +files: +- name: src/phonebook/Main.java + visible: true + text: | + package phonebook; + + public class Main { + public static void main(String[] args) { + System.out.println("Hello World!"); + } + } + learner_created: false +- name: test/PhoneBookTest.java + visible: false + text: "import org.hyperskill.hstest.stage.StageTest;\nimport org.hyperskill.hstest.testcase.CheckResult;\n\ + import org.hyperskill.hstest.testcase.TestCase;\n\nimport java.util.ArrayList;\n\ + import java.util.Arrays;\nimport java.util.List;\nimport java.util.regex.Matcher;\n\ + import java.util.regex.Pattern;\n\npublic class PhoneBookTest extends StageTest\ + \ {\n\n private long timeOnTestStart;\n \n @Override\n public List<TestCase>\ + \ generate() {\n timeOnTestStart = System.currentTimeMillis();\n \ + \ return Arrays.asList(\n new TestCase().setTimeLimit(30 * 60 * 1000)\n\ + \ );\n }\n \n \n private CheckResult checkPhrases(String reply,\ + \ String... phrases) {\n reply = reply.toLowerCase();\n for (String\ + \ phrase : phrases) {\n if (!reply.contains(phrase.toLowerCase()))\ + \ {\n return CheckResult.wrong(\"Not found the part `\" + phrase\ + \ + \"` in your output.\");\n }\n }\n return CheckResult.correct();\n\ + \ }\n \n private List<String> findAll(String reply, String regex) {\n\ + \ Matcher matcher = Pattern.compile(regex).matcher(reply);\n List<String>\ + \ groups = new ArrayList<>();\n while (matcher.find()) {\n groups.add(matcher.group());\n\ + \ }\n return groups;\n }\n \n private String timeRegex\ + \ = \"(\\\\d+)\\\\s*min.*?(\\\\d+)\\\\s*sec.*?(\\\\d+)\\\\s*ms\";\n private\ + \ Pattern timeRegexPattern = Pattern.compile(timeRegex);\n \n private long\ + \ parseTimestamp(String timestamp) {\n Matcher matcher = timeRegexPattern.matcher(timestamp);\n\ + \ if (!matcher.matches() || matcher.groupCount() < 3) {\n throw\ + \ new IllegalStateException(\"???Not matches the line \" + timestamp);\n \ + \ }\n int min = Integer.parseInt(matcher.group(1));\n int sec\ + \ = Integer.parseInt(matcher.group(2));\n int ms = Integer.parseInt(matcher.group(3));\n\ + \ return ms + sec * 1000 + min * 1000 * 60;\n }\n \n \n \n\ + \ @Override\n public CheckResult check(String reply, Object clue) {\n \ + \ long realTime = System.currentTimeMillis() - timeOnTestStart;\n \ + \ reply = reply.toLowerCase();\n CheckResult res = checkPhrases(reply,\n\ + \ \"found\",\n \"min.\",\n \"sec.\"\ + ,\n \"ms.\",\n \"sorting time\",\n \ + \ \"searching time\",\n \"linear search\",\n \"\ + bubble sort\",\n \"jump search\",\n \"quick sort\"\ + ,\n \"binary search\",\n \"hash table\",\n \ + \ \"creating time\"\n );\n if (!res.isCorrect()) {\n \ + \ return res;\n }\n \n List<String> stat1 = findAll(reply,\ + \ \"500 / 500\");\n List<String> stat2 = findAll(reply, \"500/500\");\n\ + \ \n if (stat1.size() + stat2.size() < 4) {\n return CheckResult.wrong(\"\ + Your output should contain 4 times the phrase `500 / 500`\");\n }\n \ + \ \n List<String> timestamps = findAll(reply, timeRegex);\n if (timestamps.size()\ + \ != 10) {\n return CheckResult.wrong(\"Your output should contain\ + \ 10 timer outputs, but found \"\n + timestamps.size());\n\ + \ }\n // should not fail..\n long t1 = parseTimestamp(timestamps.get(0));\n\ + \ long t2 = parseTimestamp(timestamps.get(1));\n long t3 = parseTimestamp(timestamps.get(2));\n\ + \ long t4 = parseTimestamp(timestamps.get(3));\n // qsort\n \ + \ long t5 = parseTimestamp(timestamps.get(4));\n long t6 = parseTimestamp(timestamps.get(5));\n\ + \ long t7 = parseTimestamp(timestamps.get(6));\n // hash table\n\ + \ long t8 = parseTimestamp(timestamps.get(7));\n long t9 = parseTimestamp(timestamps.get(8));\n\ + \ long t10 = parseTimestamp(timestamps.get(9));\n \n if (Math.abs(t3\ + \ + t4 - t2) > 100) {\n return CheckResult.wrong(\"Your third and fourth\ + \ timer outputs in total (bubble sorting and searching) \" +\n \ + \ \"should be equal to the second (total search time).\");\n }\n \ + \ if (Math.abs(t6 + t7 - t5) > 100) {\n return CheckResult.wrong(\"\ + Your 6-th and 7-th timer outputs in total (qsort and searching) \" +\n \ + \ \"should be equal to the 5-th (total search time).\");\n \ + \ }\n if (Math.abs(t9 + t10 - t8) > 100) {\n return CheckResult.wrong(\"\ + Your 9-th and 10-th timer outputs in total (creating hashtable and searching)\ + \ \" +\n \"should be equal to the 8-th (total search time).\"\ + );\n }\n \n long estimatedTime = t1 + t2 + t5 + t8;\n \ + \ if (realTime < 1000) {\n return CheckResult.wrong(\"Your program\ + \ completes too fast. Faster than a second!\");\n }\n\n if (Math.abs(estimatedTime\ + \ - realTime) > estimatedTime * 0.3) {\n return CheckResult.wrong(\"\ + Your estimated time is not similar to real time the program works. \" +\n \ + \ \"Real time: \" + realTime + \"ms, estimated time: \" + estimatedTime\ + \ + \"ms\");\n }\n \n if (t8 >= t5) {\n return\ + \ CheckResult.wrong(\"Your hashtable works slower, than quick sort + binary search.\"\ + );\n }\n return CheckResult.correct();\n }\n}\n" + learner_created: false +feedback_link: https://hyperskill.org/projects/63/stages/475/implement#comment +status: Unchecked +record: -1 diff --git a/Phone Book/Instant search/task-remote-info.yaml b/Phone Book/Instant search/task-remote-info.yaml new file mode 100644 index 0000000..188c90c --- /dev/null +++ b/Phone Book/Instant search/task-remote-info.yaml @@ -0,0 +1,2 @@ +id: 7721 +update_date: Tue, 28 Dec 2021 18:04:22 UTC diff --git a/Phone Book/Instant search/task.html b/Phone Book/Instant search/task.html new file mode 100644 index 0000000..77782f1 --- /dev/null +++ b/Phone Book/Instant search/task.html @@ -0,0 +1,29 @@ +<h5 style="text-align: center;" id="description">Description</h5> + +<p>The search is pretty fast, but is it possible to come up with something even faster?</p> + +<p>In the previous stage, you prepared the data using an algorithm with a complexity of <code class="java">O(n log n)</code> and found the data using an algorithm with a complexity of <code class="java">O(log n)</code>. At this stage, you will implement faster data preparation and a faster search. The preparation will have a complexity of <code class="java">O(n)</code>, and the search will have a complexity of <code class="java">O(1)</code>. A <strong>hash table</strong> will help you with this.</p> + +<p>You need to add all the elements to the hash table and then find the necessary phone numbers, as in the previous stages. Since the hash table is filled once, you need to measure the hash table creation time separately (just like you did with sorting in the previous stage).</p> + +<h5 style="text-align: center;" id="example">Example</h5> + +<p>Output all four approaches one after another and see which one is faster. The output example is shown below. Note that you can get totally different sorting and searching times!</p> + +<pre><code class="java">Start searching (linear search)... +Found 500 / 500 entries. Time taken: 1 min. 56 sec. 328 ms. + +Start searching (bubble sort + jump search)... +Found 500 / 500 entries. Time taken: 9 min. 15 sec. 291 ms. +Sorting time: 8 min. 45 sec. 251 ms. +Searching time: 0 min. 30 sec. 40 ms. + +Start searching (quick sort + binary search)... +Found 500 / 500 entries. Time taken: 1 min. 21 sec. 996 ms. +Sorting time: 1 min. 17 sec. 381 ms. +Searching time: 0 min. 4 sec. 615 ms. + +Start searching (hash table)... +Found 500 / 500 entries. Time taken: 0 min. 4 sec. 256 ms. +Creating time: 0 min. 4 sec. 121 ms. +Searching time: 0 min. 0 sec. 135 ms.</code></pre>
\ No newline at end of file |