Google Interview L4

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);

};