leetcode

commit 84a3cd17f51fe800375975739e0021953b946469
parent baba1cee5c4d126d4199111814ec107871ca9f5e
Author: AndrewLockVI <andrewlaack1@gmail.com>
Date:   Mon, 29 May 2023 19:25:56 -0500

Completed design hashset using dart

Diffstat:
A
design-hashset/design-hashset.dart
 | 
41
+++++++++++++++++++++++++++++++++++++++++

1 file changed, 41 insertions(+), 0 deletions(-)
diff --git a/design-hashset/design-hashset.dart b/design-hashset/design-hashset.dart
@@ -0,0 +1,41 @@
+//Design your own hashset where you can add, remove, and
+//check to see if a value is contained in the map all in constant* time.
+//The time compexity of add, remove, contains are
+//ideally constant, but there are many cases in which the
+//efficency divulves into near O(n) search time. As an example
+//if all values have the same hashed value then they all need
+//to be traversed to find the value you are searching for.
+
+//How does it work? Well when a key is added it is divided by 100
+//and the remainder is what the hash value is. Given that every time
+//the value is searched for the same hash appears this works albeit this solution
+//is quite lazy because depending on the data set there may be lots of collisions.
+//For removing you simply hash the value then find the key in the map and remove it.
+//For contains you simply search the given hash index for the key.
+
+//Time: 545ms Beats: 75%
+//Memory: 177.3MB Beats: 75%
+class MyHashSet {
+  List<List<int>> hash_set = List.filled(100 , []);
+  MyHashSet() {
+  }
+  
+  void add(int key) {
+      if(contains(key)){
+          return;
+      }
+      ((hash_set[key%100]).add(key));
+  }
+  
+  void remove(int key) {
+      (hash_set[key%100]).remove(key);
+  }
+  
+  bool contains(int key) {
+      if((hash_set[key%100]).contains(key)){
+          return true;
+      }
+      return false;
+  }
+}
+