Machine Coding Round (Implementations Questions)

The following are some of the most important machine coding round questions

Rate Limiter (Medium)

You need to implement a Rate Limiter in JavaScript. The rate limiter should allow a certain number of requests per user in a given time window.

Requirements:

1. Implement a function RateLimiter(limit, timeWindow) that initializes the rate limiter.

2. Implement a method allowRequest(userId) that returns true if the user can make a request, otherwise false.

3. A user can make at most limit requests in timeWindow milliseconds.

4. Use efficient data structures to optimize for performance.

5. Assume the function allowRequest(userId) will be called multiple times with different users.

Example:

const limiter = new RateLimiter(3, 10000); // Allow max 3 requests per 10 sec for a user

console.log(limiter.allowRequest("ram")); // true as limit =1 
console.log(limiter.allowRequest("ram")); // true as limit =2 
console.log(limiter.allowRequest("ram")); // true as limit =3
console.log(limiter.allowRequest("ram")); // false (exceeds limit)

Solution

Sliding Window algorithm with a Queue (Deque approach) for efficient time management.

class RateLimiter {
    constructor(limit, timeWindow) {
        this.limit = limit;
        this.timeWindow = timeWindow;
        // this map will store the user id as key and value as array of timestamps
        this.requests = new Map(); 
    }
    allowRequest(userId) {
        const currentTime = Date.now();
        if (!this.requests.has(userId)) {
            this.requests.set(userId, []);
        }
        const timestamps = this.requests.get(userId);
        // Remove outdated requests outside the time window
        while (timestamps.length > 0 && currentTime - timestamps[0] >= this.timeWindow) {
            timestamps.shift();
        }
        if (timestamps.length < this.limit) {
            timestamps.push(currentTime);
            return true; // Request allowed
        }
        return false; // Request denied (limit exceeded)
    }
}
// Example Usage
const limiter = new RateLimiter(3, 10000); // 3 requests per 10 sec

console.log(limiter.allowRequest("user1")); // true
console.log(limiter.allowRequest("user1")); // true
console.log(limiter.allowRequest("user1")); // true
console.log(limiter.allowRequest("user1")); // false (limit exceeded)
setTimeout(() => {
    console.log(limiter.allowRequest("user1")); // true (after time window resets)
}, 11000);

Explanation:

1. We store timestamps of requests per user using a Map (key-value storage).

2. Each user's request timestamps are stored in a Queue (array).

3. Every time allowRequest(userId) is called:

   • Remove old requests that are outside the timeWindow.

   • If the number of requests is within limit, allow the request and add the timestamp.

   • Otherwise, deny the request.

4. Time Complexity:

   • O(1) for insertions.

   • O(n) in the worst case for removing expired requests, but generally runs in O(1) amortized.

In-Memory Key-Value Store with Expiry ( Medium-Hard)

Problem Statement:

You need to implement an in-memory key-value store in JavaScript that supports the following operations:

1. set(key, value, ttl): Stores a key-value pair with an optional time-to-live (TTL) in milliseconds.

2. get(key): Retrieves the value of the key if it exists and hasn't expired.

3. delete(key): Removes the key from the store.

4. count(): Returns the number of active keys in the store (excluding expired ones).

Requirements:

• Keys should expire automatically after the TTL expires.

• If no TTL is provided, the key should persist indefinitely.

• Optimize for fast retrieval and expiry checks.

• Use only JavaScript, no external libraries.

• Ensure that count() does not include expired keys.

Example Usage:

const store = new KeyValueStore();
store.set("user1", "Ram", 5000); // Key expires in 5 sec
console.log(store.get("user1")); // "Ram"

setTimeout(() => {
    console.log(store.get("user1")); // null (expired)
}, 6000);

store.set("user2", "Tamanna");
console.log(store.get("user2")); // "Tamanna"
store.delete("user2");
console.log(store.get("user2")); // null
console.log(store.count()); // Should return active keys count

Solution:

class KeyValueStore {
    constructor() {
        this.store = new Map(); // Stores key -> { value, expiry }
    }
    set(key, value, ttl = null) {
        const expiry = ttl ? Date.now() + ttl : null;
        this.store.set(key, { value, expiry });
    }
    get(key) {
        if (!this.store.has(key)) return null;
        const { value, expiry } = this.store.get(key);
        if (expiry !== null && Date.now() > expiry) {
            this.store.delete(key); // Remove expired key
            return null;
        }
        return value;
    }
    delete(key) {
        this.store.delete(key);
    }
    count() {
        let validKeys = 0;
        const currentTime = Date.now();
        for (const [key, { expiry }] of this.store) {
            if (expiry === null || expiry > currentTime) {
                validKeys++;
            } else 
                this.store.delete(key); // Cleanup expired keys
        }
        return validKeys;
    }
}
// Example Usage:
const store = new KeyValueStore();

store.set("user1", "Ram", 5000); // Key expires in 5 sec
console.log(store.get("user1")); // "Ram"

setTimeout(() => {
    console.log(store.get("user1")); // null (expired)
    console.log(store.count()); // Should be 0 after expiry
}, 6000);

store.set("user2", "Tamanna");
console.log(store.get("user2")); // "Tamanna"

store.delete("user2");
console.log(store.get("user2")); // null

store.set("user3", "Bhardwaj");
store.set("user4", "Kumar", 2000); // Expires in 2 sec
console.log(store.count()); // 2 (before expiry)

setTimeout(() => {
    console.log(store.count()); // 1 (after "Kumar" expires)
}, 3000);

Thanks for watching