AdvancedLRUCache solution has bugs and wrong complexity rating

[apatrida]

The solution claims it is O(1) yet it is O(log(N)) due to the PriorityQueue offer/poll complexity. And really would need to be O(N) because to update the lastUsed time it would need to use remove(item); offer(item) and that is O(N) complexity on remove(item)

The advanced LRU has a bug:

        fun get(key: String): Int? {
            val item = map[key]

            return if (item == null || item.expiryTime < getSystemTimeForExpiry()) {
                null
            } else {
                item.lastUsed = System.currentTimeMillis()
                item.value
            }
        }

You cannot mutate the value used for calculating priority for the PriorityQueue and expect that the order will change. The item must be removed and added back to the PriorityQueue after this mutation.

Other bug in the description vs. solution, considering CacheItem method compareTo

    override fun compareTo(other: CacheItem) = when {
        expiryTime != other.expiryTime -> expiryTime.compareTo(other.expiryTime)
        priority != other.priority -> priority.compareTo(other.priority)
        else -> lastUsed.compareTo(other.lastUsed)
    }

The question description says:

If there are no items past their validity, identify the items with the lowest priority rating and from these, remove the item that was least recently accessed or used.

So that would mean you would need a second PriorityQueue ordered by priority rating + last used, otherwise you are removing within a combined sort order of expiry time + priority instead of just by priority. The above sort helps to be smart within an expiry time window for times, but those are less likely as expiry times will vary by nanoseconds/milliseconds due to timing of inserts.

So the current implementation orders by more than the spec requires (for expiry time with secondary sort orders), and does not handle priority ordering correctly.

[apatrida]

Note, it would be more standard to pass in a Clock instance fo the class with a default of Clock.systemDefaultZone() so that a fixed clock could be passed in for testing and adjusted by the tests if needed.

[apatrida]

Also, could someone be confused by:

• inserting an item that would already be expired (by time or lowest priotity), does that expire an existing item anyways?

[apatrida]

other bug in given solution:

            val item = map[key]

            item?.let {
                it.expiryTime = 0L // Mark as expired for next eviction
                map.remove(key)
            }
        }

this does not cause a re-sort of the priority queue so it isn't clear when this item will be evicted from the queue.

[apatrida]

I think this is just a bad test, as the number of edge cases and performance problems/opportunities could cause a stall-out in advanced programmers who know that there is no simple performant solution to this that isn't too complex to solve during a coding challenge.

[apatrida]

Using a Priority Queue on a data class with default equals() and default hashCode() is invalid as a keyed object. This should be immutable to guarantee the remove/add calls. And only the key field should be used for equality in those structures.