Lifesight Software Developer 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