3

Preparing for interviews and I came across something that is making me question my understanding of big O constant time algorithms.

A question on LeetCode asks to create a solution to the LFU cache problem.

There are 3 methods to implement:

Constructor - Input: int Capacity

get - Input: int key - output: int

set - input: int key, int value

The capacity represents the maximum number of cached key/value pairs you can hold at one time. When capacity is breached, you have to eject the least frequently accessed pair.

So obviously, you have to keep track of the number of times each item is accessed.

At the bottom of the question, it asks if you can both get and set in O(1) time.

I am looking at multiple proposed implementations of this, with long lists of people agreeing they are examples of constant time implementations, but to me they look like O(N).

For a full example, see here: https://leetcode.com/problems/lfu-cache/discuss/94515/Java-O(1)-Accept-Solution-Using-HashMap-DoubleLinkedList-and-LinkedHashSet?page=1

But the relevant methods from this example are in the following code block. Note that valueHash and nodeHash are both java hash tables.

public int get(int key) {
    if (valueHash.containsKey(key)) {
        increaseCount(key);
        return valueHash.get(key);
    }
    return -1;
}

    public void set(int key, int value) {
    if ( cap == 0 ) return;
    if (valueHash.containsKey(key)) {
        valueHash.put(key, value);
    } else {
        if (valueHash.size() < cap) {
            valueHash.put(key, value);
        } else {
            removeOld();
            valueHash.put(key, value);
        }
        addToHead(key);
    }
    increaseCount(key);
}

The methods call Hashtable.containsKey and Hashtable.get, which implement linear search. So worst case time complexity is O(N) right? What am I missing?

Zabuzard
  • 25,064
  • 8
  • 58
  • 82
Jimbo
  • 1,685
  • 3
  • 12
  • 15
  • 3
    I guess the relevant question here is: What is n? – Hermann Döppes Mar 04 '18 at 16:09
  • Hashtable and HashMap are hasing based and `containsKey()` and `get()` is O(1), backed by array and in case of collision elements are linked at an index of array. Using Hasing algorithm, key is converted to an int representing an index in the array. Accessing element at an index in an Array is O(1) – nits.kk Mar 04 '18 at 17:31

1 Answers1

4

Whatever data structure you use it has some pessimistic time of search T(n), dependent on number of items stored, n. If you set some maximum capacity Nmax, and keep it constant for the time of your program's execution, as specifically required in the problem statement, then the maximum time to handle any request is T(Nmax), which is constant.

Credit to @Zabuza for emphasise on constant nature of Nmax.

CiaPan
  • 9,381
  • 2
  • 21
  • 35
  • 1
    To extend the answer, this only applies as long as `Nmax` really is a constant, which means it not depends on `n`. So something like `Nmax = 10 * n` would be no constant. – Zabuzard Mar 04 '18 at 16:12
  • Thank you. That makes perfect sense. This was kind of confidence shaking. – Jimbo Mar 04 '18 at 16:14
  • In this case the capacity is set by the constructor and can't be changed, but yes, it would definitely have to be considered if the implementation was slightly different to that required by the question in this case. – Jimbo Mar 04 '18 at 16:16
  • @Zabuza I didn't bother to emphasise that, because it's a part of the problem definition (_'The capacity represents the maximum number of cached key/value pairs you can hold at one time'_). But you're right to point it out; that's a crucial requirement, which leads to the counter-intuitive result. – CiaPan Mar 04 '18 at 18:22