YOE: 6YOE

Online Assessment: 2 DS Question Solved Both.

Problem Statement 1

A classification system evaluates whether given texts are spam based on a list of spam words.
A text is labeled “spam” if it contains at least two spam words (each occurrence of a spam word in the text counts toward the total).
Spam word matching is case-sensitive.

Example:

texts = {
    "This is a limited offer just for you",
    "Win cash now! Click here to claim your prize",
    "Hello friend, just checking in",
    "Congratulations! You have won a free gift"
};

spamWords = {
    "offer", "cash", "Click", "prize", "Congratulations", "free"
};

Output:
["not_spam", "spam", "not_spam", "spam"]

Function Signature:
vector<string> classifyTexts(vector<string> texts, vector<string> spamWords);

Input:
 texts: a list of strings (the texts to evaluate).
 spamWords: a list of strings (the spam words).

Output:
 A list of strings, each either "spam" or "not_spam" for each text.

Constraints:
1 ≤ n ≤ 10^3 (number of texts)
1 ≤ k ≤ 10^5 (number of spam words)
1 ≤ len(text) ≤ 10^5
1 ≤ len(spamWord) ≤ 10^5
Combined length of all spam words does not exceed 10^7

Solution

  List < String > result = new ArrayList < >();

  // Convert spam words to lowercase for case-insensitive comparison
  Set < String > lowerSpamWords = new HashSet < >();
  for (String word: spamwords) {
    lowerSpamWords.add(word.toLowerCase());
  }

  // Process each text
  for (String text: texts) {
    // Split text into words and convert to lowercase
    String[] words = text.toLowerCase().split("\W+");

    int spamCount = 0;

    // Count spam word occurrences (each occurrence counts)
    for (String word: words) {
      if (!word.isEmpty() && lowerSpamWords.contains(word)) {
        spamCount++;
      }
    }

    // Classify: spam if >= 2 spam words found, otherwise not_spam
    if (spamCount >= 2) {
      result.add("spam");
    } else {
      result.add("not_spam");
    }
  }

  return result;
}

Problem Statement 2 : Longest Subsequence

Determine the maximum length of a subsequence from one string that is also a substring of another string. A subsequence of a string is created by removing zero or more characters from it, while a substring consists of consecutive characters from the string.
Given two strings x and y, determine the length of the longest subsequence of x that is also a substring of y.

Example:
x = "abcd"
y = "bbdc"

The subsequences of "abcd" are: "a", "b", "c", "d", "ab", "ac", "ad", "bc", "bd", "cd", "abc", "abd", "acd", "bcd", and "abcd".
The substrings of "bbdc" are: "b", "b", "d", "c", "bb", "bd", "dc", "bbd", "bdc", and "bbdc".

The longest subsequence of x that is also a substring of y is "bd" with length 3.
Function Description:
Complete the function longestSubsequence in the editor with the following parameter(s):
string x: a string to find the subsequence of
string y: a string to find the substring of
Returns:
int: the length of the longest subsequence of x that is a substring of y
Constraints:
1 ≤ lengths of x and y ≤ 2000
Strings x and y consist of lowercase English letters (ascii[a-z])

Solution

public static int longestSubsequence(String x, String y) {
        int maxLength = 0;
        
        // For each starting position in y (try all possible substrings)
        for (int start = 0; start < y.length(); start++) {
            int xIndex = 0;
            int yIndex = start;
            int currentLength = 0;
            
            // Greedily match consecutive characters from y[start...] 
            // as a subsequence in x
            while (xIndex < x.length() && yIndex < y.length()) {
                if (x.charAt(xIndex) == y.charAt(yIndex)) {
                    currentLength++;
                    yIndex++;
                }
                xIndex++;
            }
            
            maxLength = Math.max(maxLength, currentLength);
        }
        
        return maxLength;
    }