Algorithms : add 02-data_structures 03-hash_tables

21 files changed, 325 insertions, 0 deletions

diff --git a/02-data_structures/03-hash_tables/00_hash_tables.pdf b/02-data_structures/03-hash_tables/00_hash_tables.pdf
new file mode 100644
index 0000000..2b00534
--- /dev/null
+++ b/02-data_structures/03-hash_tables/00_hash_tables.pdf
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
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 
+
diff --git a/02-data_structures/03-hash_tables/03-hash_substring/hash_substring.cpp b/02-data_structures/03-hash_tables/03-hash_substring/hash_substring.cpp
new file mode 100644
index 0000000..3a3680a
--- /dev/null
+++ b/02-data_structures/03-hash_tables/03-hash_substring/hash_substring.cpp
@@ -0,0 +1,38 @@
+#include <iostream>
+#include <string>
+#include <vector>
+
+using std::string;
+typedef unsigned long long ull;
+
+struct Data {
+    string pattern, text;
+};
+
+Data read_input() {
+    Data data;
+    std::cin >> data.pattern >> data.text;
+    return data;
+}
+
+void print_occurrences(const std::vector<int>& output) {
+    for (size_t i = 0; i < output.size(); ++i)
+        std::cout << output[i] << " ";
+    std::cout << "\n";
+}
+
+std::vector<int> get_occurrences(const Data& input) {
+    const string& s = input.pattern, t = input.text;
+    std::vector<int> ans;
+    for (size_t i = 0; i + s.size() <= t.size(); ++i)
+        if (t.substr(i, s.size()) == s)
+            ans.push_back(i);
+    return ans;
+}
+
+
+int main() {
+    std::ios_base::sync_with_stdio(false);
+    print_occurrences(get_occurrences(read_input()));
+    return 0;
+}
diff --git a/02-data_structures/03-hash_tables/03-hash_substring/tests/01 b/02-data_structures/03-hash_tables/03-hash_substring/tests/01
new file mode 100644
index 0000000..88aa221
--- /dev/null
+++ b/02-data_structures/03-hash_tables/03-hash_substring/tests/01
@@ -0,0 +1,2 @@
+aba
+abacaba
diff --git a/02-data_structures/03-hash_tables/03-hash_substring/tests/01.a b/02-data_structures/03-hash_tables/03-hash_substring/tests/01.a
new file mode 100644
index 0000000..45d56c5
--- /dev/null
+++ b/02-data_structures/03-hash_tables/03-hash_substring/tests/01.a
@@ -0,0 +1 @@
+0 4 
diff --git a/02-data_structures/03-hash_tables/03-hash_substring/tests/02 b/02-data_structures/03-hash_tables/03-hash_substring/tests/02
new file mode 100644
index 0000000..4ca249f
--- /dev/null
+++ b/02-data_structures/03-hash_tables/03-hash_substring/tests/02
@@ -0,0 +1,2 @@
+Test
+testTesttesT
diff --git a/02-data_structures/03-hash_tables/03-hash_substring/tests/02.a b/02-data_structures/03-hash_tables/03-hash_substring/tests/02.a
new file mode 100644
index 0000000..8adb55b
--- /dev/null
+++ b/02-data_structures/03-hash_tables/03-hash_substring/tests/02.a
@@ -0,0 +1 @@
+4 
diff --git a/02-data_structures/03-hash_tables/03-hash_substring/tests/03 b/02-data_structures/03-hash_tables/03-hash_substring/tests/03
new file mode 100644
index 0000000..4977bbb
--- /dev/null
+++ b/02-data_structures/03-hash_tables/03-hash_substring/tests/03
@@ -0,0 +1,2 @@
+aaaaa
+baaaaaaa
diff --git a/02-data_structures/03-hash_tables/03-hash_substring/tests/03.a b/02-data_structures/03-hash_tables/03-hash_substring/tests/03.a
new file mode 100644
index 0000000..46786e9
--- /dev/null
+++ b/02-data_structures/03-hash_tables/03-hash_substring/tests/03.a
@@ -0,0 +1 @@
+1 2 3 
diff --git a/02-data_structures/03-hash_tables/check b/02-data_structures/03-hash_tables/check
new file mode 100755
index 0000000..b73ff99
--- /dev/null
+++ b/02-data_structures/03-hash_tables/check
@@ -0,0 +1,38 @@
+#! /bin/bash
+
+RESET="\033[0m"
+RED="\033[0;31m"
+GREEN="\033[0;32m"
+BROWN="\033[0;33m"
+
+BIN=/tmp/bin
+OUTA=/tmp/_outa
+OUTB=/tmp/_outb
+GPP_OPTS="-std=c++11 -O2"
+
+for path in $(find -name \*.cpp | sort); do
+    src=${path##*/}
+    dir=${path%/*}
+    echo -e "${RED}validate $BROWN$dir$RESET/$GREEN$src$RESET"
+    pushd $dir >/dev/null || exit 1
+    echo -e "   ${RED}compile $GREEN$src$RESET" && g++ $GPP_OPTS $src -o $BIN || exit 1
+    if [ -d tests ]; then
+        echo -e "   ${RED}check $GREEN$src$RESET"
+        for t in $(find ./tests -name "*[^a~]"|sort); do
+            if [ -f $t -a -f "$t.a" ]; then
+                cat $t | $BIN > $OUTA
+                cat $t.a > $OUTB
+                cmp $OUTA $OUTB >/dev/null
+                if [ $? -ne 0 ]; then
+                    echo -e "     $BROWN$t$RESET is ${RED}KO$RESET"
+                else
+                    echo -e "     $BROWN$t$RESET is ${GREEN}ok$RESET"
+                fi
+            fi
+        done
+    else
+        echo -e "   ${RED}no tests$RESET"
+    fi
+    popd > /dev/null
+done
+