Thoughtspot Interviews

Round 1: I was asked to implement a versioned stack, which I solved using the provided link. Another question was about adding two large numbers using linked lists, which was similar to the LeetCode problem Add Two Numbers.

Round 2: The interviewer asked about alternatives to Redux for state management since my resume mentioned it. I discussed using Context API and MobX as alternatives. Then, I was asked about how GraphQL works, and I explained the query execution process. Lastly, there was a question about how streaming works in LLM chatbots, which I explained involves breaking down the response into chunks and sending them incrementally.

Round 3: This was a resume deep dive round. The interviewer discussed my projects and asked about alternate approaches to solve the same problems. There were also some behavioral questions.

I recently applied for SMT4 at Thoughtspot:
R1: DS algo
Q1. Variation of Knapsack problem.
Q2. Given a number find its equivalent excel sheet column name. Like 26 is Z, 27 is AA.
R2. DS algo
Q1. Variation of coin change problem. Given an array of numbers where each number is binary but its value is in decimal i.e [0,1,10,11 ...] have valus of 0,1,ten,eleven and so on and given a num N find min no of elements from the given array to form N.
Q2. Optimizations of above question
R3. HLD
Design a event and engagement tracker system
Vendors will onboard their product to your system.
Users will be sent different campaigns by mail or sms and if a user clicks on a campaign link it should redirect to the actual product vendor onboarded.
Show different metrices like click, impression etc to vendors
R4. LLD+System design
Design chatGpt based UI. Assume we have a LLM model that is working fine but can not retain context of the conversation.
User can have multiple chats.
User can continue some old chat and you need to make sure input to ML model should be provided such that it gives accurate response to the prompt provided by user. Do keep in mind that model can not retain context so it should be taken care by you. DB choice. Class diagram. Apis. Flow. etcetc
R5: Managerial
Explain a recent task you did.
Why do you want to leave your current org
How do you keep up with GenAi stuff
etc etc

Rejected in Managrial round.

ThoughtSpot | SDE - 2 (Backend)

Interview Date: 11 April 2024

Ques 1: Given a sorted string S of length N consisting of only lowercase english alphabets. The task is to return the length of longest substring consisting of same characters.

Input: aaabbccccdde Ans: 4 (substring is "cccc")

First Approach: Linear traversal, TC: O(N) Iterate through the string and maintain a counter of same characters. Update global answer whenever encounter a different character. Repeat till end of string is reached.

Second Approach: Binary Search, TC: 26*log(N) For every 26 characters in ['a' to 'z'], we do a binary search. Find the first and last position of the character in string 'S'. Update global answer with maximum of all answers i:e [last - first + 1].

Ques2: Course Schedule II

Ques3: LRU Cache

Ques4: https://cs.stackexchange.com/questions/144639/given-a-source-and-destination-find-the-path-with-minimum-stress-level-in-a-gra?newreg=be6125d7befc40629abefd8222eedccf

Approach: We will binary search on the answer. Suppose our current stress level to test is K.

Then we will run a BFS from source and only consider the edge with weight <= K. If there exist a path from source to destination for current K, we consider this as answer and check for lower value of K, otherwise, we check for higher value of K.

K can have value in range [min(edge weight) to max(edge weight)]

TC: E*log(max(edgeWeight))

import java.util.*;

public class code {
    private static boolean checkBFS(int n, List<Integer[]> adj[], int k, int src, int dst) {
        Queue<Integer> q = new LinkedList<>();
        int[] vis = new int[n+1];
        Arrays.fill(vis, -1);
        q.add(src);
        vis[src]=1;
        while (!q.isEmpty()) {
            int curr = q.poll();
            if (curr == dst) {
                return  true;
            }
            for (Integer [] edge : adj[curr]) {
                if (edge[1] > k || vis[edge[0]]!=-1)  continue;
                q.add(edge[0]);
                vis[edge[0]]=1;
            }
        }
        return  false;
    }

    private static int findMinStressPath(int n, int m, int[][] edges, int src, int dst) {
        int low = Integer.MAX_VALUE;
        int high = -1;
        List<Integer[]> adj[] = new ArrayList[n+1];
        Arrays.setAll(adj, a -> new ArrayList<>());

        for (int i=0; i<m; ++i) {
            int u = edges[i][0];
            int v = edges[i][1];
            int w = edges[i][2];
            low = Math.min(low, w);
            high = Math.max(high, w);
            adj[u].add(new Integer[]{v, w});
            adj[v].add(new Integer[]{u, w});
        }

        int ans = high;
        while (low <= high) {
            int mid = low + (high-low)/2;
            if (checkBFS(n, adj, mid, src, dst)) {
                ans = mid;
                high = mid-1;
            } else {
                low = mid+1;
            }m
        }

        return ans;
    }

    public static void main(String[] args) {
        int n = 5;
        int m = 6;
        int[][] edges = new int[][]{{1,2,10}, {2,3,5}, {1,4,15}, {4,3,2}, {1,5,4}, {5,3,6}};
        int source = 1;
        int destination = 3;
        System.out.println(findMinStressPath(n,m,edges, source, destination));
    }
}

ThoughtSpot LLD Design problem

You are required to design a meeting scheduler system with the following capabilities:

1. There are N predefined meeting rooms available in the system.
2. A user should be able to book a meeting available room by providing:

• Array of rooms[] with details {startTime, endTime, requiredCapacity}

3. The system should send notifications to all participants invited to the meeting
4. The system should maintain a Meeting Room Calendar to:

• Track scheduled meetings for each room
• Display meetings for the current day.

I recently interviewed at Thoughtspot SMTS position.

I felt things went really smooth.
i was also able to solve a question that was given in really less time.
but i got rejected.

here is a question i was asked.

const userStore = new Store();
userStore.save("user_id_1", "samuel jackson");


const unsubscribe1 = userStore.subscribe(
 "user_id_1",
 (value) => {
   console.log("first", value);
 }, // update function
 () => {
   console.log("cleanup1");
 } // cleanup function
);
userStore.save("user_id_1", "samuel l jackson"); //all the updaters should get called corresponding to “user_id_1”

unsubscribe1(); //should remove the update function

Coding Round 1

The first coding question involved an array and an integer k. I needed to find the count of distinct elements for each subarray of size k. I solved this problem effectively using a two-pointer approach combined with a hashmap.

Coding Round 2

The second coding problem was a classic Snake and Ladder board game scenario. I was given an M x N board, along with the start and end points for snakes and ladders. The goal was to find the minimum number of dice throws required to reach the last cell from the first. For example, with M=5, N=6 (total 30 cells), snakes at 7->4, 16->2, 29->11, and ladders at 3->19, 22->28, the answer was 3. I approached this by modeling the board as a graph. The edges in my graph included all snakes, all ladders, and for each cell, an edge to the next six cells (representing dice throws 1 to 6). My task was to find the minimum shortest path from node 1 to node M*N.

Low-Level Design (LLD) Round

The LLD round focused on designing a Logger system.