Count Clean Attendance Logs
Updated
Problem statement
A school keeps one log per student for each term. The log has one letter for every school day: 'P' means the student came on time, 'L' means the student came in after the bell, and 'A' means the student missed the day.
A log is clean when both of these rules hold:
- The letter
'A'appears at most once in the whole log. - No three days next to each other are all
'L'. Two'L'days next to each other are fine.
Given the number of school days n, count how many different logs of length n are clean. This count grows very fast, so return it modulo 1,000,000,007.
Function
checkRecord(n: int) → intExamples
Example 1
n = 3return = 19There are 3 × 3 × 3 = 27 logs of length 3. Six of them have exactly two 'A' (AAP, AAL, APA, ALA, PAA, LAA) and one, AAA, has three, so 7 logs have too many 'A'. One more log, LLL, has three 'L' in a row. That leaves 27 - 7 - 1 = 19 clean logs.
Example 2
n = 4return = 43There are 81 logs of length 4. Of these, 16 have no 'A' and 4 × 8 = 32 have exactly one, so 81 - 16 - 32 = 33 have two or more. Among the logs with at most one 'A', five have three 'L' in a row: LLLP, PLLL, LLLL, LLLA and ALLL. That leaves 81 - 33 - 5 = 43 clean logs.
Example 3
n = 40return = 27329510The full count of clean logs of length 40 is 1,121,027,337,357, which is larger than 1,000,000,007. Its remainder modulo 1,000,000,007 is 27329510.
Constraints
1 <= n <= 100000
More Rippling Phone Screen questions
- Filter, Sort, and Deduplicate Scheduled TasksPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Stateful Log Transform and SearchPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Dependency-Aware Task SchedulerPHONE SCREEN · Seen Nov 2026
- Delivery Cost Tracker with Effective-Dated RatesPHONE SCREEN · Seen Nov 2026
- Camel CardsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Best and Worst Camel Card CompletionsPHONE SCREEN · Seen Nov 2026
- Corporate Card Expense RulesOA · PHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- In-Memory Priority Task SchedulerPHONE SCREEN · Seen Oct 2026
- Limit an Organization Tree's HeightPHONE SCREEN · ONSITE INTERVIEW · Seen Oct 2026
- Median Across N Sorted ArraysPHONE SCREEN · Seen Oct 2026
Similar questions at other companies
- Election District Budget Allocation AnalysisIMC Trading · PHONE SCREENIMC Trading interview questions
- Biased Coin: Probability of Exactly h HeadsAkuna Capital · PHONE SCREENAkuna Capital interview questions
- Probability of Consecutive HeadsSquarepoint Capital · PHONE SCREENSquarepoint Capital interview questions
- Median of Uniform Draws in an IntervalSusquehanna International Group (SIG) · PHONE SCREENSusquehanna International Group (SIG) interview questions
- Count Array DerangementsInMobi · PHONE SCREENInMobi interview questions
- Count Nondecreasing Digit-Sum ArraysMicrosoft · OAMicrosoft interview questions
- Stable Workload Redistribution TreesTower Research Capital · OA
- Count Valid A-B-C Sequences Under a Modulo-Four RuleInfosys · OAInfosys interview questions
- Count Permutations Without Three Equal Parities in a RowGoogle · OAGoogle interview questions
- Count Staircases with Strictly Increasing StepseBay · ONSITE INTERVIEWeBay interview questions
Interview reports that mention this question
Rippling interview experiences
- Rippling No-Level Older Reports: 31 Experiences (Part 6 of 6)
- Rippling No-Level Onsite Loops: 24 Experiences (Part 5 of 6)
- Rippling No-Level Screens and Loops: 18 Experiences (Part 4 of 6)
- Rippling No-Level Coding Screens: 37 Experiences (Part 3 of 6)
- Rippling No-Level Design, Screens: 30 Experiences (Part 2 of 6)