diff options
Diffstat (limited to '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 Binary files differnew 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 + |