Telephone screen round

Started with a brief Introduction
Asked to draw an HLD of the current services you’re working upon

• TPS in each service
• Queuing write semantics
• DB consistency levels
• Authorization and authentication in the current Applicatio (home-grown or LDAP etc)
• Challenges faced in current projects

Design a thread - hashMap of your own

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

Round 1

• Given a list of strings denoting function name, START or END marker, and 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.

In the above example, inclusive time for function "abc" is 200-100=100, while exclusive time for function "abc" is (200-100) - (180-150) = 70

Given such a list of strings, figure out the inclusive and exclusive time for any given function call.

• Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), 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.

Round 2

• Order tree nodes in the order in which they will fall. Child nodes fall first, then parent nodes fall whose child nodes have already fallen.

• Find all palindromic subsequences in a string.

Round 3

We have a big deployment with hundreds of machines each of which is exposing thousands of statistics. You can think that each statistic is represented by the tuple [source, metric-name, value].

We want to be able to collect and aggregate those tuples in a scalable manner.
The main consumers for this system are:
The engineer who wants to see how the application’s latency is from last 1 month
As an alert service we setup alerts
Source metric ( t1 to t2) we want to see the metrics how to query the values

Round 4 (Concurrency round)

• Basic questions on concurrency
• Design a blocking queue that is written by n Writers and read by 1 Reader. This was later extended to n Readers and n Writers.

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

Result: Reject as I couldn't solve - find all palindromic subsequences.