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