-
Notifications
You must be signed in to change notification settings - Fork 0
/
Copy pathtask.html
74 lines (55 loc) · 2.38 KB
/
task.html
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
<h5 style="text-align: center;">Description</h5>
<p>Now your program can successfully search for all matching lines, ignoring cases and extra spaces. There is one problem though: you need to check whether each line contains a query string or not.</p>
<p>To optimize your program, you can use a data structure called <strong>Inverted Index</strong>. It maps each word to all positions/lines/documents in which the word occurs. As a result, when we receive a query, we can immediately find the answer without any comparisons.</p>
<p>At this stage, build an inverted index when the program starts, and then use the index for searching operations. You can implement it using a <code class="java">Map</code> class. It connects an item with a list (or set) of indexes belonging to the lines that contain the item.</p>
<p>Suppose you have the following array or list of lines:</p>
<pre><code class="language-no-highlight">0: Katie Jacobs
1: Erick Harrington [email protected]
2: Myrtle Medina
3: Erick Burgess</code></pre>
<p>For these lines, the inverted index will look like this:</p>
<pre><code class="language-no-highlight">Katie -> [0]
Jacobs -> [0]
Erick -> [1, 3]
Harrington -> [1]
[email protected] -> [1]
Myrtle -> [2]
Medina -> [2]
Burgess -> [3]</code></pre>
<p>The order of pairs is not important. If you are searching for Erick, you can immediately get the target fields using this mapping.</p>
<p>Note that the Inverted Index is<strong> </strong>not intended to search for parts of a word, it is only used to search for full words.</p>
<h5 style="text-align: center;">Example</h5>
<p>The lines that start with <code class="java">> </code> represent the user input. Note that these symbols are not part of the input. </p>
<pre><code class="language-no-highlight">=== Menu ===
1. Find a person
2. Print all people
0. Exit
> 1
Enter a name or email to search all suitable people.
> ERICK
2 persons found:
Erick Harrington [email protected]
Erick Burgess
=== Menu ===
1. Find a person
2. Print all people
0. Exit
> 1
Enter a name or email to search all suitable people.
> [email protected]
1 persons found:
Richard Roy [email protected]
=== Menu ===
1. Find a person
2. Print all people
0. Exit
> 1
Enter a name or email to search all suitable people.
> john
No matching people found.
=== Menu ===
1. Find a person
2. Print all people
0. Exit
> 0
Bye!</code></pre>