LinkedIn Interview | Senior Software Engineer | Bangalore | 2022 | Reject

The interviewer asked me to draw a High-Level Design (HLD) of the current services I am working on. We then discussed aspects like TPS in each service, queuing write semantics, database consistency levels, authorization and authentication mechanisms (home-grown or LDAP etc), and challenges faced in current projects.

I was asked to design my own thread-safe HashMap. The code I provided was:

class HashMap {

private static int bucketSize = 1000;
List<Entry>[] map = new List[bucketSize];//value;

public void put(String key, String value) {
    int idx = hashCode(key, bucketSize);

    synchronized {
        if(map[idx] == null) map[idx] = new ArrayList();

        for(Entry e : map[idx]) {
            if(e.key == key) {
                e.value = value;
                return;
            }
        }
        map[idx].add(new Entry(key, value);
    }
}

public String get(String key) {

    int idx = hashCode(key, bucketSize);
    List<Entry> list = map[idx];

    if(list==null) return "Key not found";

    for(Entry e : list) {
        if(e.key == key) return e.value;
    }
    return "Key not found"
}

}
public class Entry {
String key, value;
public(String key, String value) {
this.key = key;
this.value = value;
}
}

I was given a list of strings, each denoting a function name, a 'START' or 'END' marker, and a timestamp. Calls can be nested, and one function can call child functions. Inclusive time is defined as all the time spent on a particular function, including time spent on its child calls. Exclusive time is defined as the time spent on a particular function only, excluding time spent on its child calls. For example, if function 'abc' starts at 100 and ends at 200, and a child function starts at 150 and ends at 180, then inclusive time for 'abc' is 200-100=100, while exclusive time for 'abc' is (200-100) - (180-150) = 70. I needed to figure out the inclusive and exclusive time for any given function call from such a list.

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), I had to write a function to check whether these edges make up a valid tree.
For example:
 Given n = 5 and edges = [[0, 1], [0, 2], [0, 3], [1, 4]], return true.
 Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [1, 3], [1, 4]], return false.

I was asked to order tree nodes in the sequence in which they would fall. The rule was that child nodes fall first, and then parent nodes fall only after all their child nodes have already fallen.

The problem was to find all palindromic subsequences in a given string.

I was presented with a scenario involving a large deployment with hundreds of machines, each exposing thousands of statistics, represented as [source, metric-name, value] tuples. The task was to design a system to collect and aggregate these tuples in a scalable manner. The main consumers for this system included engineers needing to view application latency over the last month, an alert service for setting up alerts, and the ability to query metric values for specific sources within a given time range (t1 to t2).

I was asked to design a blocking queue that supports n writers and 1 reader. This problem was then extended to support n writers and n readers. My approach included the following Java code:

import java.util.PriorityQueue;
import java.util.concurrent.Semaphore;

public class BlockingQueue {
PriorityQueue heap;
Semaphore read;
Semaphore write;

BlockingQueue() {
    write = new Semaphore(1);
    read = new Semaphore(0);
    this.heap = new PriorityQueue<Tuple>((a,b) -> a.key - b.key);
}

public void write(Tuple tuple) throws InterruptedException {
    synchronized (heap) {
        write.acquire();
        heap.add(tuple);

        write.release();
        read.release();
    }
}

public Tuple read() throws InterruptedException {
    read.acquire();
    synchronized (heap) {

        Tuple t = (Tuple)heap.peek();

        heap.poll();
        return t;
    }
}

}
public class Tuple {
int key;
int value;

public Tuple(int key, int value) {
    this.key = key;
    this.value = value;
}

}