summaryrefslogtreecommitdiff
path: root/Sources
diff options
context:
space:
mode:
authorHaidong Ji2019-03-12 22:27:24 -0500
committerHaidong Ji2019-03-12 22:27:24 -0500
commit9735d05bae6c6cdb86789bc74def31e402c469a3 (patch)
tree0892b8af4da58ef1d45178b24ffd50194d151ffd /Sources
parent28191582b58f35e9d6d4d28f33cb76f45a08c183 (diff)
Hashing with Chains done!
Didn't write test cases because the starter code wasn't easy for testing. Tested using sample input. Fun stuff :)
Diffstat (limited to 'Sources')
-rw-r--r--Sources/DataStructure.cpp246
1 files changed, 71 insertions, 175 deletions
diff --git a/Sources/DataStructure.cpp b/Sources/DataStructure.cpp
index 07f8b43..064ca45 100644
--- a/Sources/DataStructure.cpp
+++ b/Sources/DataStructure.cpp
@@ -1,190 +1,86 @@
#include <iostream>
-#include <vector>
#include <string>
+#include <vector>
+#include <algorithm>
using std::string;
using std::vector;
using std::cin;
struct Query {
- string type, name;
- int number;
+ string type, s;
+ size_t ind;
};
-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;
-}
+class QueryProcessor {
+ int bucket_count;
+ // store all strings in one vector
+ 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;
+ }
-void write_responses(const vector<string>& result) {
- for (size_t i = 0; i < result.size(); ++i)
- std::cout << result[i] << "\n";
-}
+public:
+ explicit QueryProcessor(int bucket_count) :
+ bucket_count(bucket_count) {
+ }
-vector<string> process_queries(const vector<Query>& queries) {
- vector<string> result;
- // Keep list of all existing (i.e. not deleted yet) contacts.
- vector<string> contacts(10000000);
- for (size_t i = 0; i < contacts.size(); i++) {
- contacts[i] = "not found";
- }
- for (size_t i = 0; i < queries.size(); ++i)
- if (queries[i].type == "add") {
- contacts[queries[i].number] = queries[i].name;
- } else if (queries[i].type == "del") {
- contacts[queries[i].number] = "not found";
- } else {
- result.push_back(contacts[queries[i].number]);
- }
- return result;
-}
+ 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[query.ind].size()) - 1; i >= 0;
+ --i)
+ std::cout << elems[query.ind][i] << " ";
+ std::cout << "\n";
+ } else {
+ int hashIndex = hash_func(query.s);
+ vector<string>::iterator it = std::find(elems[hashIndex].begin(), elems[hashIndex].end(),
+ query.s);
+ if (query.type == "find")
+ writeSearchResult(it != elems[hashIndex].end());
+ else if (query.type == "add") {
+ if (it == elems[hashIndex].end())
+ elems[hashIndex].push_back(query.s);
+ } else if (query.type == "del") {
+ if (it != elems[hashIndex].end())
+ elems[hashIndex].erase(it);
+ }
+ }
+ }
+
+ void processQueries() {
+ int n;
+ cin >> n;
+ elems.resize(n);
+ for (int i = 0; i < n; ++i)
+ processQuery(readQuery());
+ }
+};
int main() {
- write_responses(process_queries(read_queries()));
- return 0;
+ std::ios_base::sync_with_stdio(false);
+ int bucket_count;
+ cin >> bucket_count;
+ QueryProcessor proc(bucket_count);
+ proc.processQueries();
+ return 0;
}
-
-//#include <cstdio>
-//#include <cstdlib>
-//#include <vector>
-//#include <algorithm>
-//#include <iostream>
-////#include <gtest/gtest.h>
-//
-//using std::cin;
-//using std::cout;
-//using std::endl;
-//using std::max;
-//using std::vector;
-//
-//struct Table {
-// int numberOfRows;
-// int setID;
-//
-// Table(int numberOfRows, int setID) :
-// numberOfRows(numberOfRows), setID(setID) {
-// }
-//};
-//
-//int maximumNumberOfRows = -1;
-//vector<int> parent;
-//vector<int> rank;
-//vector<Table> tables;
-//
-//int find(int i) {
-// if (i != parent[i])
-// parent[i] = find(parent[i]);
-// return parent[i];
-//}
-//
-//void unite(int destination, int source) {
-// int destination_id = find(destination);
-// int source_id = find(source);
-// if (destination_id == source_id)
-// return;
-// if (rank[destination_id] > rank[source_id])
-// parent[source_id] = destination_id;
-// else {
-// parent[destination_id] = source_id;
-// if (rank[destination_id] == rank[source_id])
-// rank[source_id] = rank[source_id] + 1;
-// }
-//}
-//
-//void merge(int destination, int source) {
-// int d = find(destination);
-// int s = find(source);
-// Table* realDestination = &tables[d];
-// Table* realSource = &tables[s];
-// if (d == s) {
-// return;
-// }
-// maximumNumberOfRows = max(maximumNumberOfRows,
-// tables[realDestination->setID].numberOfRows + tables[realSource->setID].numberOfRows);
-// realDestination->numberOfRows = tables[realDestination->setID].numberOfRows
-// + tables[realSource->setID].numberOfRows;
-// realSource->numberOfRows = 0;
-// realSource->setID = d;
-// realDestination->setID = d;
-// unite(destination, source);
-//}
-//
-//int main() {
-// int n, m;
-// cin >> n >> m;
-//
-// parent.resize(n);
-// rank.resize(n);
-//// tables.resize(n);
-// for (int i = 0; i < n; i++) {
-// int numberOfRows;
-// cin >> numberOfRows;
-// tables.push_back(Table(numberOfRows, i));
-//// tables[i] = Table(numberOfRows, i);
-// parent[i] = i;
-// rank[i] = 0;
-// maximumNumberOfRows = max(maximumNumberOfRows, numberOfRows);
-// }
-//
-// for (int i = 0; i < m; i++) {
-// int destination, source;
-// cin >> destination >> source;
-// --destination;
-// --source;
-//
-// merge(destination, source);
-// cout << maximumNumberOfRows << endl;
-// }
-//
-// return 0;
-//}
-//
-////TEST(MergingTables, t) {
-//// maximumNumberOfRows = 1;
-//// rank = {0, 0, 0, 0, 0};
-//// parent = {0, 1, 2, 3, 4};
-//// tables = {Table(1, 0), Table(1, 1), Table(1, 2), Table(1, 3), Table(1, 4)};
-////
-//// merge(2, 4);
-//// ASSERT_EQ(2, maximumNumberOfRows);
-////
-//// merge(1, 3);
-//// ASSERT_EQ(2, maximumNumberOfRows);
-////
-//// merge(0, 3);
-//// ASSERT_EQ(3, maximumNumberOfRows);
-////
-//// merge(4, 3);
-//// ASSERT_EQ(5, maximumNumberOfRows);
-////
-//// merge(4, 2);
-//// ASSERT_EQ(5, maximumNumberOfRows);
-////}
-////
-////TEST(MergingTables, t1) {
-//// maximumNumberOfRows = 10;
-//// rank = {0, 0, 0, 0, 0, 0};
-//// parent = {0, 1, 2, 3, 4, 5};
-//// tables = {Table(10, 0), Table(0, 1), Table(5, 2), Table(0, 3), Table(3, 4), Table(3, 5)};
-////
-//// merge(5, 5);
-//// ASSERT_EQ(10, maximumNumberOfRows);
-////
-//// merge(5, 4);
-//// ASSERT_EQ(10, maximumNumberOfRows);
-////
-//// merge(4, 3);
-//// ASSERT_EQ(10, maximumNumberOfRows);
-////
-//// merge(3, 2);
-//// ASSERT_EQ(11, maximumNumberOfRows);
-////}