Phone Interview 1

You are given an array of strings:

["ad", "awe", "cat", "apple", "dog", ...]

You are also provided with an API:

bool isValid(string s)

This API internally contains a constant string P and returns true if P is a prefix of s. Example:

P = "a"

isValid("ad")   -> true
isValid("awe")  -> true
isValid("apple")-> true
isValid("cat")  -> false
isValid("dog")  -> false

Your task is to rearrange the array so that all valid strings appear at the beginning, while minimizing the number of movements in-memory where the array is stored. The relative order of valid strings does not necessarily need to be preserved.

Also, tell the time and space complexity accounting for the API call as well.

Phone Interview 2

Standard Googlyness round. Questions around conflicts, my work experience, situations and my approach to dealing with them.

Onsite Round 1

Design a class that generates unique strings to be used for URL shortening.

Each generated string must follow the constraints below:

1. Strings consist only of lowercase characters a-z.
2. A threshold value T is provided.
3. The frequency of any character in a generated string must be ≤ T.
4. Every time the API is called, it must return a unique string.
5. The generator must optimize for shorter strings first.

This means:

• All valid strings of length 1 must be generated before length 2.
• All valid strings of length 2 must be generated before length 3, and so on.
• The order within the same length does not matter, but shorter strings must always be returned first.

API Design

You need to implement a class similar to:

class URLShortener {
public:
    URLShortener(int threshold);
    string getNext();  // Returns the next unique valid string
};

Behavior

• URLShortener(int threshold) initializes the generator.
• getNext() returns the next unique string satisfying the constraints.

Example

Threshold = 2

Possible sequence of outputs:

Length 1
a
b
c
...
z

Length 2
aa
ab
ac
...
zz

All characters in each string appear at most 2 times.

Onsite Round 2

Implement LRU Cache with Expiration

Part 1: Standard LRU cache question. Design and implement an LRU (Least Recently Used) Cache that supports the following operations:

• get(key) → Returns the value associated with the key if it exists in the cache, otherwise return -1.
• put(key, value) → Insert or update the value of the key.

API Design

class LRUCache {
public:
    LRUCache(int capacity);

    int get(int key);
    void put(int key, int value);
};

Part 2: Extend the cache to support time-based expiration.

Each entry should expire after a fixed time window, for example 5 minutes.

Updated API

class LRUCache {
public:
    LRUCache(int capacity, int expirationTime);

    int get(int key);
    void put(int key, int value);
};

My solutions during interviews

The questions aren't very tricky so I'll drop just hints/statements of what I did during the interviews.

Phone Interview 1 - 2 pointer approach - I thought about first how is the movement minimized. And then was going with maintaining an extra array to track valid strings but then interviewer hinted and I caught the 2 pointer approach. Important to tell time complexity accounting for the API call, how is the prefix match done, O(L) - string length in API class. The API class wasn't implemented but I needed to just think it with the best design possible.
Passed to onsite interviews.

Onsite Interview 1 - I went with enumerating the strings like digits with base 26. So essentially digits 0..25 map to char a..z and then simple addition with carry over logic. Important to note that in this approach you need to make sure that an output is valid, otherwise generate next string because enumeration ensures exhaustiveness, uniqueness and 'shorter strings first' property but doesn't guarantee that a string will be valid. For. ex. with Threshold = 2, digits 110 and 112 are valid but 111 is invalid.
Told the time and space complexity.

Onsite Interview 2 - Simple LRU implementation with unordered_map and LinkedList. For expiration I lazily deleted keys when a get or put is done for an entry. The linked list maintains order of addition of keys, so if a node has expired all the previous nodes can also be cleaned up in the list.
Discussed further what if we go with a recurring job approach to clean the cache, advantages and disadvantes, time complexities in each case.