ThoughtSpot | SDE-2 Backend | Bangalore

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