Lifesight Interview Questions and Answers

Find the longest substring with at most K distinct characters in a given string.

• Use a sliding window approach to keep track of the characters and their counts in the substring.

• Maintain a hashmap to store the characters and their frequencies.

• Update the window size and characters count as you iterate through the string.

• Return the maximum length of the substring with at most K distinct characters.

Find all unique combinations in an array where the sum is equal to a given target sum, with elements in non-decreasing order.

• Use backtracking to generate all possible combinations of elements in the array that sum up to the target sum.

• Sort the array to ensure elements in each combination are in non-decreasing order.

• Handle duplicate elements in the array to avoid duplicate combinations.

• Consider edge cases like empty array, target sum of 0, and negative integers in the array.

Validate if a given binary tree is a Binary Search Tree (BST) or not.

• Check if the left subtree of a node contains only nodes with data less than the node's data.

• Check if the right subtree of a node contains only nodes with data greater than the node's data.

• Recursively check if both the left and right subtrees are also binary search trees.

• Example: For each node, validate if its left child is less than the node and right child is greater than the node.

Detect if an undirected graph contains a cycle.

• Use depth-first search (DFS) to detect cycles in the graph.

• Maintain a visited array to keep track of visited vertices.

• If a visited vertex is encountered again during DFS, a cycle exists.

• Consider disconnected graphs as well.

• Example: For input N=3, Edges=[[1, 2], [2, 3], [1, 3]], output is Yes.

Given constraints and rules, find maximum vaccines administered on a specific day during a vaccination drive.

• Iterate through each test case and calculate the maximum number of vaccines distributed on the specified day.

• Distribute vaccines evenly across days while maximizing the number on the specified day.

• Ensure that the sum of vaccines administered does not exceed the maximum allowed.

• Consider edge cases like when the number of days is equal to the maximum number of vaccines a...read more

Sliding window maximum problem where we find maximum element in each window of size K.

• Use a deque to store indices of elements in decreasing order within the window.

• Pop elements from the deque that are out of the current window.

• Append the maximum element from the front of the deque to the result for each window.