Algorithms : add 02-data_structures 03-hash_tables

7 files changed, 136 insertions, 0 deletions

diff --git a/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp b/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp
new file mode 100644
index 0000000..8af47d2
--- /dev/null
+++ b/02-data_structures/03-hash_tables/02-hash_chains/hash_chains.cpp
@@ -0,0 +1,81 @@
+#include <iostream>
+#include <string>
+#include <vector>
+#include <algorithm>
+
+using std::string;
+using std::vector;
+using std::cin;
+
+struct Query {
+    string type, s;
+    size_t ind;
+};
+
+class QueryProcessor {
+    int bucket_count;
+    // store all strings in one vector
+    vector<string> elems;
+    size_t hash_func(const string& s) const {
+        static const size_t multiplier = 263;
+        static const size_t prime = 1000000007;
+        unsigned long long hash = 0;
+        for (int i = static_cast<int> (s.size()) - 1; i >= 0; --i)
+            hash = (hash * multiplier + s[i]) % prime;
+        return hash % bucket_count;
+    }
+
+public:
+    explicit QueryProcessor(int bucket_count): bucket_count(bucket_count) {}
+
+    Query readQuery() const {
+        Query query;
+        cin >> query.type;
+        if (query.type != "check")
+            cin >> query.s;
+        else
+            cin >> query.ind;
+        return query;
+    }
+
+    void writeSearchResult(bool was_found) const {
+        std::cout << (was_found ? "yes\n" : "no\n");
+    }
+
+    void processQuery(const Query& query) {
+        if (query.type == "check") {
+            // use reverse order, because we append strings to the end
+            for (int i = static_cast<int>(elems.size()) - 1; i >= 0; --i)
+                if (hash_func(elems[i]) == query.ind)
+                    std::cout << elems[i] << " ";
+            std::cout << "\n";
+        } else {
+            vector<string>::iterator it = std::find(elems.begin(), elems.end(), query.s);
+            if (query.type == "find")
+                writeSearchResult(it != elems.end());
+            else if (query.type == "add") {
+                if (it == elems.end())
+                    elems.push_back(query.s);
+            } else if (query.type == "del") {
+                if (it != elems.end())
+                    elems.erase(it);
+            }
+        }
+    }
+
+    void processQueries() {
+        int n;
+        cin >> n;
+        for (int i = 0; i < n; ++i)
+            processQuery(readQuery());
+    }
+};
+
+int main() {
+    std::ios_base::sync_with_stdio(false);
+    int bucket_count;
+    cin >> bucket_count;
+    QueryProcessor proc(bucket_count);
+    proc.processQueries();
+    return 0;
+}
diff --git a/02-data_structures/03-hash_tables/02-hash_chains/tests/01 b/02-data_structures/03-hash_tables/02-hash_chains/tests/01
new file mode 100644
index 0000000..543e44b
--- /dev/null
+++ b/02-data_structures/03-hash_tables/02-hash_chains/tests/01
@@ -0,0 +1,14 @@
+5
+12
+add world
+add HellO
+check 4
+find World
+find world
+del world
+check 4
+del HellO
+add luck
+add GooD
+check 2
+del good
diff --git a/02-data_structures/03-hash_tables/02-hash_chains/tests/01.a b/02-data_structures/03-hash_tables/02-hash_chains/tests/01.a
new file mode 100644
index 0000000..2089645
--- /dev/null
+++ b/02-data_structures/03-hash_tables/02-hash_chains/tests/01.a
@@ -0,0 +1,5 @@
+HellO world 
+no
+yes
+HellO 
+GooD luck 
diff --git a/02-data_structures/03-hash_tables/02-hash_chains/tests/02 b/02-data_structures/03-hash_tables/02-hash_chains/tests/02
new file mode 100644
index 0000000..3ebfc0e
--- /dev/null
+++ b/02-data_structures/03-hash_tables/02-hash_chains/tests/02
@@ -0,0 +1,10 @@
+4
+8
+add test
+add test
+find test
+del test
+find test
+find Test
+add Test
+find Test
diff --git a/02-data_structures/03-hash_tables/02-hash_chains/tests/02.a b/02-data_structures/03-hash_tables/02-hash_chains/tests/02.a
new file mode 100644
index 0000000..95b2d9a
--- /dev/null
+++ b/02-data_structures/03-hash_tables/02-hash_chains/tests/02.a
@@ -0,0 +1,4 @@
+yes
+no
+no
+yes
diff --git a/02-data_structures/03-hash_tables/02-hash_chains/tests/03 b/02-data_structures/03-hash_tables/02-hash_chains/tests/03
new file mode 100644
index 0000000..0893cf3
--- /dev/null
+++ b/02-data_structures/03-hash_tables/02-hash_chains/tests/03
@@ -0,0 +1,14 @@
+3
+12
+check 0
+find help
+add help
+add del
+add add
+find add
+find del
+del del
+find del
+check 0
+check 1
+check 2
diff --git a/02-data_structures/03-hash_tables/02-hash_chains/tests/03.a b/02-data_structures/03-hash_tables/02-hash_chains/tests/03.a
new file mode 100644
index 0000000..8f5237c
--- /dev/null
+++ b/02-data_structures/03-hash_tables/02-hash_chains/tests/03.a
@@ -0,0 +1,8 @@
+
+no
+yes
+yes
+no
+
+add help 
+