Meta Software Engineer Interview Experience — A Four-Part In-Memory Database OA on CodeSignal

Just finished it, seems like a new OA, I haven't seen this one on the forum before. The first two parts were pretty easy. The third was a bit annoying but manageable. The fourth needed some time.

It was on CodeSignal. Implement an in-memory database.

This database is basically a double hashmap, something like:

{
  "user1": {
     "age": 12
  },
  "user2": {
     "age": 18,
     "height": 180
  }
}

The key is user1, user2, the field is age, height, and the value is 12, 180.

Step 1:

class InMemoryDatabase {

// Store this value under key, field. timestamp is an integer representing the current time, can be ignored
set(timestamp, key, field, value): void

// Read the value. If the key or field doesn't exist, return null
get(timestamp, key, field): number | null

// If the current value equals expectedValue, change it to newValue and return true.
// Otherwise (if it doesn't exist or the value doesn't match) return false.
compareAndSet(timestamp, key, field, expectedValue, newValue): bool

// If the current value equals expectedValue, delete it. Return true.
// Otherwise return false
compareAndDelete(timestamp, key, field, expectedValue): bool

}

Step 2:

// Output all fields and values for this key. Should be sorted in alphabetical order. For example if key is user2, output
// ["age(18)", "height(180)"]
scan(timestamp, key): array[string]

// scan, but only output fields that have this prefix
scanByPrefix(timestamp, key, prefix): array[string]

Step 3:

This step uses the timestamp. The test cases guarantee the timestamp is incremental, so you won't get something like set(12, key, field, value); get(11, key, field);

All the previous functions default to having no expiration.

// Same as set, but this adds an expiration to the value. When time reaches timestamp+ttl, it's automatically deleted.
setWithTtl(timestamp, key, field, value, ttl): void

// Same as compareAndSet, but also adds an expiration
compareAndSetWithTtl(timestamp, key, field, value, ttl): bool

Step 4:

You need to find the value at some earlier timestamp. The test cases guarantee atTimestamp < timestamp.

getWhen(timestamp, key, field, atTimestamp): number | null

For example, a value was originally set to 10 at time = 10, expired at time = 12, then set again to 18 at time = 18:

getWhen(timestamp, key, field, 5) == null
getWhen(timestamp, key, field, 11) == 10
getWhen(timestamp, key, field, 15) == null
getWhen(timestamp, key, field, 20) == 18

I solved the first three, with a little over 30 minutes left. I finished writing the fourth one, but couldn't get it to pass debugging — didn't pass a single test case.