FastPrepCount Subsequences Without Three Equal-Parity Elements in a Row
Problems/Count Subsequences Without Three Equal-Parity Elements in a Row

Count Subsequences Without Three Equal-Parity Elements in a Row

Google logoGoogle● MediumINTERNOA

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

Source note: The report does not give a modulus, a function signature, or examples. Here the function returns the count modulo 10^9 + 7. Our version is about 96% the same as the reported question.

You are given an integer array nums. Count its non-empty subsequences whose selected order satisfies both rules:

  • No three consecutive selected values are all even.
  • No three consecutive selected values are all odd.

A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements. Two subsequences are different when they select different index sets, even if their value sequences are equal.

Return the count modulo 10^9 + 7.

Function

countValidSubsequences(nums: int[]) → int

Examples

Example 1

nums = [1,2,3]return = 7

All seven non-empty subsequences are valid because none contains three consecutive selected values of the same parity.

Example 2

nums = [2,4,6]return = 6

The only invalid subsequence selects all three values, producing a run of three evens. The other six non-empty subsequences are valid.

Example 3

nums = [1,3,5,7]return = 10

Every selected value is odd, so a valid subsequence may contain only one or two elements. There are 4 + 6 = 10 such index sets.

Constraints

  • 1 <= nums.length <= 10^5.
  • 1 <= nums[i] <= 10^9.

More Google Online Assessment questions

  • Book Reading EveningsOA · Seen Nov 2026
  • Count Score CategoriesOA · Seen Nov 2026
  • Minimum Cars for Rental RequestsOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
  • Shortest Path in a Binary MatrixOA · Seen Nov 2026
  • Robot Assembly Line ConflictsOA · Seen Oct 2026
  • Assign LockerOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
  • Biggest Number From DigitsOA · Seen Oct 2026
  • Consolidate On-Call RotationsOA · PHONE SCREEN · Seen Oct 2026
  • Decreasing SubsequencesOA · Seen Sep 2026
  • Minimize Absolute Difference of Server LoadsOA · Seen Sep 2026

Similar questions at other companies

  • Count Strictly Increasing Subsequences of Length 3IBM · OAIBM interview questions
  • Optimize Discount Selection Under a Point BudgetPalantir · OAPalantir interview questions
  • Pressure-Isolation Shutdown OrderIntuit · OAIntuit interview questions
  • Count Good SubsequencesFlexport · OAFlexport interview questions
  • Sum of Compressed Number for All SubarraysWells Fargo · OAWells Fargo interview questions
  • Count Perfect BreaksAtlassian · OAAtlassian interview questions
  • Winning Draws for a Mahjong HandZip · PHONE SCREENZip interview questions
  • Coin Change IIApple · PHONE SCREEN · ONSITE INTERVIEWApple interview questions
  • 0/1 KnapsackConfluent · OAConfluent interview questions
  • Count Overlapping Square PairsRamp · OARamp interview questions

Interview reports that mention this question

  • Google SWE Intern OA and Interviews: 42 Experiences (Part 1 of 3)

Google interview experiences

  • Google L4 SWE Phone Screen: 1 Experience
  • Google ML Engineering Manager Onsite: 1 Experience
  • Google Experienced SWE First Round and Onsite: 1 Experience
  • Google AI Coding Interview and AI OA: 2 Experiences
  • Google SWE Intern Interview Results Timeline: 13 Experiences
All Google interview questionsSee Google hiring insights
Saved
class Solution {
    public int countValidSubsequences(int[] nums) {
      // write your code here
    }

}
Checking account…