Google | Online Assessment | 2023
Summary
I recently took an online assessment for Google in 2023, where I was presented with a challenging dynamic programming problem focused on counting special subsequences with specific properties.
Full Experience
I participated in an online assessment for Google in 2023. The assessment posed a single, intricate problem that demanded a deep understanding of subsequences, character frequencies, and modular arithmetic. The core task was to identify and count 'special subsequences' based on length, distinct characters, and maximizing the sum of character frequencies from the original string. I meticulously analyzed the problem statement, noting the constraints and the modulo operation requirement, which suggested a dynamic programming approach with careful state definition would be necessary.
Interview Questions (1)
A Special Subsequence of a string S of length N is a subsequence that satisfies following properties:
- Length of Subsequence is exactly K.
- All the characters in the subsequence are distinct.
- Let fi be the frequency of character i in the original string. Then the summation of fi for all characters i in the subsequence is maximum among all such subsequences.
Given a string S and an integer K. Find the number of distinct Special Subsequences of string S. As this number can be large print answer modulo 109 +7.
Note: A subsequence of a string is a new string which is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters.
Example:
Given N=12, K=8, S= "fpbavjsmppt"
Output: 108