Algorithms : add 02-data_structures 03-hash_tables

5 files changed, 104 insertions, 0 deletions

diff --git a/02-data_structures/03-hash_tables/01-phone_book/phone_book.cpp b/02-data_structures/03-hash_tables/01-phone_book/phone_book.cpp
new file mode 100644
index 0000000..182c36f
--- /dev/null
+++ b/02-data_structures/03-hash_tables/01-phone_book/phone_book.cpp
@@ -0,0 +1,72 @@
+#include <iostream>
+#include <vector>
+#include <string>
+
+using std::string;
+using std::vector;
+using std::cin;
+
+struct Query {
+    string type, name;
+    int number;
+};
+
+vector<Query> read_queries() {
+    int n;
+    cin >> n;
+    vector<Query> queries(n);
+    for (int i = 0; i < n; ++i) {
+        cin >> queries[i].type;
+        if (queries[i].type == "add")
+            cin >> queries[i].number >> queries[i].name;
+        else
+            cin >> queries[i].number;
+    }
+    return queries;
+}
+
+void write_responses(const vector<string>& result) {
+    for (size_t i = 0; i < result.size(); ++i)
+        std::cout << result[i] << "\n";
+}
+
+vector<string> process_queries(const vector<Query>& queries) {
+    vector<string> result;
+    // Keep list of all existing (i.e. not deleted yet) contacts.
+    vector<Query> contacts;
+    for (size_t i = 0; i < queries.size(); ++i)
+        if (queries[i].type == "add") {
+            bool was_founded = false;
+            // if we already have contact with such number,
+            // we should rewrite contact's name
+            for (size_t j = 0; j < contacts.size(); ++j)
+                if (contacts[j].number == queries[i].number) {
+                    contacts[j].name = queries[i].name;
+                    was_founded = true;
+                    break;
+                }
+            // otherwise, just add it
+            if (!was_founded)
+                contacts.push_back(queries[i]);
+        } else if (queries[i].type == "del") {
+            for (size_t j = 0; j < contacts.size(); ++j)
+                if (contacts[j].number == queries[i].number) {
+                    contacts.erase(contacts.begin() + j);
+                    break;
+                }
+        } else {
+            string response = "not found";
+            for (size_t j = 0; j < contacts.size(); ++j)
+                if (contacts[j].number == queries[i].number) {
+                    response = contacts[j].name;
+                    break;
+                }
+            result.push_back(response);
+        }
+    return result;
+}
+
+int main() {
+    write_responses(process_queries(read_queries()));
+    return 0;
+}
diff --git a/02-data_structures/03-hash_tables/01-phone_book/tests/01 b/02-data_structures/03-hash_tables/01-phone_book/tests/01
new file mode 100644
index 0000000..e335b06
--- /dev/null
+++ b/02-data_structures/03-hash_tables/01-phone_book/tests/01
@@ -0,0 +1,13 @@
+12
+add 911 police
+add 76213 Mom
+add 17239 Bob
+find 76213
+find 910
+find 911
+del 910
+del 911
+find 911
+find 76213
+add 76213 daddy
+find 76213
diff --git a/02-data_structures/03-hash_tables/01-phone_book/tests/01.a b/02-data_structures/03-hash_tables/01-phone_book/tests/01.a
new file mode 100644
index 0000000..b9367b9
--- /dev/null
+++ b/02-data_structures/03-hash_tables/01-phone_book/tests/01.a
@@ -0,0 +1,6 @@
+Mom
+not found
+police
+not found
+Mom
+daddy
diff --git a/02-data_structures/03-hash_tables/01-phone_book/tests/02 b/02-data_structures/03-hash_tables/01-phone_book/tests/02
new file mode 100644
index 0000000..0391451
--- /dev/null
+++ b/02-data_structures/03-hash_tables/01-phone_book/tests/02
@@ -0,0 +1,9 @@
+8
+find 3839442
+add 123456 me
+add 0 granny
+find 0
+find 123456
+del 0
+del 0
+find 0
diff --git a/02-data_structures/03-hash_tables/01-phone_book/tests/02.a b/02-data_structures/03-hash_tables/01-phone_book/tests/02.a
new file mode 100644
index 0000000..c715c98
--- /dev/null
+++ b/02-data_structures/03-hash_tables/01-phone_book/tests/02.a
@@ -0,0 +1,4 @@
+not found
+granny
+me
+not found