TikTok Initial Coding Round

I just finished my phone interview with TikTok, where I was asked a question about an LRU Cache. Here are the full details of the question. Design a cache class with...

I just finished my phone interview with TikTok, where I was asked a question about an LRU Cache. Here are the full details of the question.

Design a cache class with two public APIs: set(id, object), cache the object according to id get(id), get the object related to id.
Requirements:
1. Lifetime Limit: Every object inside the cache has a same lifetime S seconds. If an object in the cache hasn\'t been get o set for S seconds, it becomes invalid and no longer can be retrieved from the cache.
2. Number limit: the cache can only store up to N objects.
3. LRU mechanism: when doing the set operation, if the number of objects inside the cache reaches N, it will remove the object that was least recently used and put the new object inside.

The question is a bit more challenging than the original LRU Cache problem because we need to remove expired objects from the cache.

I asked clarifying questions about the data types that needed to be stored, and the interviewer specified integers. Therefore, I implemented the original solution with a few modifications, such as updating the lastAccessTime for the Node.

You can view my submission here: https://leetcode.com/problems/lru-cache/submissions/612336594/

Additionally, I added a method for cleanup to remove the expired nodes. The code for this method looks like this:

public class LRUCache {
 // Rest of Imple
 public void cleanup(){
 Node current = head;
 while(current != null){
\t if(isExpired(current, System.currentTimeMillis())) {
\t\t removeTail(current);
\t\t cacheMap.remove(current.key);
\t\t}
\t\t current = current.next;
\t }
 }

 private boolean isExpired(CacheObject<V> cacheObject, long currentTime) {

**return** (currentTime - cacheObject.getLastAccessTime()) >= expiryTime;
 }
}

Then, the interviewer asked me to make the code thread-safe. To achieve this, I modified the code to use synchronized methods/blocks and Java Concurrent Collections. ConcurrentHashMap and CopyOnWriteArrayList and Locks

ChatGPT Solution

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.locks.ReentrantLock;

public class LRUCache<K, V> {
 private final int capacity;
 private final long expiryTime;
 private final ConcurrentHashMap<K, CacheObject<V>> cacheMap;
 private final ConcurrentLinkedDeque<K> accessOrder;
 private final ReentrantLock lock;

 public LRUCache(int capacity, int lifetimeSeconds) {
 this.capacity = capacity;
 this.expiryTime = lifetimeSeconds * 1000L; // convert seconds to milliseconds
 this.cacheMap = new ConcurrentHashMap<>();
 this.accessOrder = new ConcurrentLinkedDeque<>();
 this.lock = new ReentrantLock();
 }

 public void set(K key, V value) {
 long currentTime = System.currentTimeMillis();
 lock.lock();
 try {
 if (cacheMap.size() >= capacity) {
 removeExpiredOrLRU();
 }
 cacheMap.put(key, new CacheObject<>(value, currentTime));
 accessOrder.remove(key);
 accessOrder.addFirst(key);
 } finally {
 lock.unlock();
 }
 }

 public V get(K key) {
 long currentTime = System.currentTimeMillis();
 CacheObject<V> cacheObject = cacheMap.get(key);
 if (cacheObject == null) {

**return** null;
 }
 lock.lock();
 try {
 if (isExpired(cacheObject, currentTime)) {
 cacheMap.remove(key);
 accessOrder.remove(key);

**return** null;
 }
 cacheObject.setLastAccessTime(currentTime);
 accessOrder.remove(key);
 accessOrder.addFirst(key);

**return** cacheObject.getValue();
 } finally {
 lock.unlock();
 }
 }

 private void removeExpiredOrLRU() {
 Iterator<K> iterator = accessOrder.descendingIterator();
 while (iterator.hasNext()) {
 K key = iterator.next();
 CacheObject<V> cacheObject = cacheMap.get(key);
 if (isExpired(cacheObject, System.currentTimeMillis())) {
 iterator.remove();
 cacheMap.remove(key);
 } else {
 iterator.remove();
 cacheMap.remove(key);
 break;
 }
 }
 }

 private boolean isExpired(CacheObject<V> cacheObject, long currentTime) {

**return** (currentTime - cacheObject.getLastAccessTime()) >= expiryTime;
 }

 private static class CacheObject<V> {
 private V value;
 private long lastAccessTime;

 public CacheObject(V value, long lastAccessTime) {
 this.value = value;
 this.lastAccessTime = lastAccessTime;
 }

 public V getValue() {

**return** value;
 }

 public long getLastAccessTime() {

**return** lastAccessTime;
 }

 public void setLastAccessTime(long lastAccessTime) {
 this.lastAccessTime = lastAccessTime;
 }
 }

 public static void main(String[] args) throws InterruptedException {
 LRUCache<Integer, String> cache = new LRUCache<>(3, 5);

 // Test with multiple threads
 Runnable writer = () -> {
 for (int i = 1; i <= 5; i++) {
 cache.set(i, "value" + i);
 System.out.println("Set key: " + i + ", value: value" + i);
 try {
 Thread.sleep(1000);
 } catch (InterruptedException e) {
 Thread.currentThread().interrupt();
 }
 }
 };

 Runnable reader = () -> {
 for (int i = 1; i <= 5; i++) {
 System.out.println("Get key: " + i + ", value: " + cache.get(i));
 try {
 Thread.sleep(1500);
 } catch (InterruptedException e) {
 Thread.currentThread().interrupt();
 }
 }
 };

 Thread writerThread = new Thread(writer);
 Thread readerThread = new Thread(reader);

 writerThread.start();
 readerThread.start();

 writerThread.join();
 readerThread.join();
 }
}