Interview Question for Software Engineer at Cubastion Consulting Pvt Ltd

Q:
Given a string s and a set of words D, find the longest word in D that is a subsequence of s.

This is a common problem in computer science and is often asked in coding interviews. To solve this problem efficiently, you need to have a good understanding of string manipulation and algorithms. Here's a step-by-step approach to solving the problem:

• Loop through each word in the set D and check if it's a subsequence of string s.
• To check if a word is a subsequence of string s, you can use the following algorithm:
1. Initialize two pointers i and j to 0.
2. Loop through each character in string s.
3. If the current character matches the character at index j in the word, increment j.
4. If j reaches the end of the word, it means that the word is a subsequence of string s.
• Store the length of each subsequence in a list.
• Return the longest subsequence from the list.

By using this approach, you can find the longest word in D that is a subsequence of string s efficiently.

Example:

If s = "abppplee" and D = {
"able", "ale", "apple", "bale", "kangaroo"}

The longest word that is a subsequence of s is "apple".

Relevant Citations:

• Subsequence - Wikipedia
• Find the longest word in a dictionary that is a subsequence of a given string
• Find the longest word in a dictionary formed by deleting some characters in a given string