incorporate o(1) hash table ds and organize tests - #34

• Implement an AllOne data structure for O(1) inc/dec and min/max key lookup.
• Maintain counts via doubly-linked “buckets” and a key→bucket index.
• Add pytest suite covering ties, removals, rebucketing, and mixed operation sequences.

classDiagram
  class AllOne {
    +dict key_to_bucket
    +Bucket start
    +Bucket end
    +inc(key)
    +dec(key)
    +getMaxKey()
    +getMinKey()
  }

  class Bucket {
    +int count
    +set keys
    +Bucket prev
    +Bucket next
  }

  AllOne "1" o-- "2" Bucket : start/end
  Bucket "0..1" --> "0..1" Bucket : prev/next

Loading

The following are alternative approaches to this PR:

1. Heap-based min/max (O(log n))

• ➕ Much simpler implementation (no linked bucket maintenance)
• ➕ Lower risk of pointer/linking bugs
• ➖ Does not meet strict O(1) requirement for updates and queries
• ➖ Requires lazy deletion / extra bookkeeping for stale heap entries

2. Sorted map / balanced tree by count (O(log n))

• ➕ Clear invariants; easy to reason about correctness
• ➕ Naturally supports min/max retrieval
• ➖ O(log n) updates rather than O(1)
• ➖ Adds dependency/complexity (or relies on non-standard sorted containers in Python)

Recommendation: If the goal is the classic AllOne/LeetCode-432 contract (amortized/expected O(1) inc/dec/min/max), the bucketed doubly-linked list + key→bucket index used here is the right approach and is the standard proven design. If the project does not truly require O(1), consider a heap/tree alternative for simpler correctness, but that would be a deliberate trade-off against the stated requirement.

Enhancement (1) +105 / -0

bucket_hash_table.pyImplement AllOne bucket hash table with O(1) inc/dec and min/max +105/-0

Implement AllOne bucket hash table with O(1) inc/dec and min/max

• Adds Bucket nodes (count + key set) linked in a doubly-linked list with start/end sentinels. Implements AllOne with a key→bucket map to support constant-time increment/decrement, bucket creation, and bucket removal when empty, plus getMinKey/getMaxKey lookups.

Algorithms/datastructs/hash_table/bucket_hash_table.py

Tests (1) +120 / -0

test_bucket_hash_table.pyAdd pytest suite for AllOne bucket hash table behavior +120/-0

Add pytest suite for AllOne bucket hash table behavior

• Introduces tests covering basic incrementing, distinct counts, ties (any valid min/max), decrement-to-removal, rebucketing after dec, and mixed operation sequences. Includes edge cases for empty structure and oscillating inc/dec patterns.

tests/algorithms/test_bucket_hash_table.py

Description

test_dec_rebalance asserts getMaxKey()/getMinKey() return "b" even though the operations leave
"a" and "b" tied at count=2, so the structure can legitimately return either key and the test may
fail depending on set iteration order/hash seed.

Code

tests/algorithms/test_bucket_hash_table.py[R40-52]

+    def test_dec_rebalance(self):
+        ao = AllOne()
+        ao.inc("a")
+        ao.inc("a")
+        ao.inc("b")
+        ao.inc("b")
+        ao.inc("b")
+
+        ao.dec("b")  # b becomes 2
+
+        assert ao.getMaxKey() == "b"
+        assert ao.getMinKey() == "b"
+

Evidence

The test sequence makes a and b both have count 2, while getMaxKey/getMinKey return an
arbitrary element from a set of keys in the max/min bucket, so asserting a specific key is not
valid under ties.

tests/algorithms/test_bucket_hash_table.py[40-52]
Algorithms/datastructs/hash_table/bucket_hash_table.py[95-105]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`test_dec_rebalance` expects a deterministic key ("b") after decrementing `b` to a count that ties with `a`. The implementation returns an arbitrary key from a `set` for ties, so the test is overspecified and can be flaky.

## Issue Context
After the sequence in `test_dec_rebalance`, counts are `a=2` and `b=2`. `getMaxKey()`/`getMinKey()` return `next(iter(bucket.keys))` where `keys` is a `set`, so either key can be returned.

## Fix Focus Areas
- tests/algorithms/test_bucket_hash_table.py[40-52]

## Suggested change
Update the assertions to accept either key when counts are tied, e.g.:
- `assert ao.getMaxKey() in {"a", "b"}`
- `assert ao.getMinKey() in {"a", "b"}`

(Alternatively, change the test setup so there is a unique max/min key before asserting an exact string.)

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools

Description

AllOne.dec() directly indexes self.key_to_bucket[key] without checking existence, so
decrementing a missing key raises KeyError and can crash callers.

Code

Algorithms/datastructs/hash_table/bucket_hash_table.py[R70-72]

+    def dec(self, key: str) -> None:
+        bucket = self.key_to_bucket[key]
+        bucket.keys.remove(key)

Evidence

dec() currently does a direct dict index which raises on missing. In contrast, existing hash-table
DS code/tests demonstrate “missing key” handling as expected control flow (no exception) for similar
operations like remove.

Algorithms/datastructs/hash_table/bucket_hash_table.py[70-77]
Algorithms/datastructs/hash_table/hash_table.py[15-27]
tests/algorithms/test_hash_table.py[6-22]

Agent prompt

The issue below was found during a code review. Follow the provided context and guidance below and implement a solution

## Issue description
`AllOne.dec()` assumes the key exists and will raise `KeyError` for unknown keys. This makes the API brittle in normal control flow (e.g., decrementing something already removed).

## Issue Context
Other data structures in this repo commonly treat missing elements as non-exceptional (e.g., `RandomizedSet.remove` returns `False` when the value is absent, and tests explicitly exercise that behavior).

## Fix Focus Areas
- Algorithms/datastructs/hash_table/bucket_hash_table.py[70-77]

## Suggested change
Add an early guard:
```python
if key not in self.key_to_bucket:
   return
```

If you prefer strict behavior, raise a clearer exception (e.g., `KeyError` with message) or `ValueError`, but ensure callers/tests match the intended contract.

ⓘ Copy this prompt and use it to remediate the issue with your preferred AI generation tools