thoughtspot logo
Thoughtspot· SDE-2 Backend

ThoughtSpot | SDE-2 Backend | Bangalore

Location
Bangalore
Posted
3 May 2025
355 reads

Summary

This post outlines a backend SDE-2 interview experience at ThoughtSpot on April 11, 2024, detailing four technical questions covering string manipulation, graph algorithms, and system design, along with approaches and code for some problems.

How it went

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

Questions asked (4)

  1. 01

    Longest Substring of Same Characters in Sorted String

    Data Structures & Algorithms

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

  2. 02

    Course Schedule II

    Data Structures & Algorithms

    Course Schedule II

  3. 03

    LRU Cache

    Data Structures & Algorithms

    LRU Cache

  4. 04

    Path with Minimum Stress Level in a Graph

    Data Structures & Algorithms

    Given an undirected graph with N vertices and M edges. Each edge (u,v) has a weight w. Given a source S and destination D. We have to find a path from S to D such that the maximum edge weight in the path is minimized. This maximum edge weight in the path is called the stress level. We have to find the minimum possible stress level.

    Open the problem

Know someone preparing? Send it to them:WhatsAppLinkedInX

Interviewed at Thoughtspot recently?

Write up your rounds while you still remember the questions. It helps the next person more than you would think.

Share your experience
Discussion 0

Questions for the author, or how your own interview compared.

Join the discussion

Sign in with Google to comment or ask the author a question.

No comments yet

Be the first to share your thoughts and start the discussion!