FastPrepInterval Usage with Non-Overlapping Overrides
Problems/Interval Usage with Non-Overlapping Overrides

Interval Usage with Non-Overlapping Overrides

Crusoe logoCrusoe● HardFULLTIMEONSITE INTERVIEW

Updated Nov 2026

QuestionFunctionExamplesConstraints

Problem statement

You are given a timeline of days 1 to days. On each day a resource is either in use (1) or not in use (0). Two lists describe the timeline.

Every row of usage and every row of overrides is [l, r, v]. It describes the interval from day l to day r, with both days included, and a value v that is 0 or 1.

By default, a day is in use if at least one usage interval with value 1 covers it. A usage interval with value 0 adds nothing. It does not clear another usage interval.

An override interval forces every day it covers to its value v. Override intervals never overlap each other. On the days an override covers, the override wins over usage.

Return a string of length days made of the characters '0' and '1'. The character at position i, counting from 1, is the final state of day i.

For example, take days = 10, usage = [[1, 2, 1], [4, 10, 1]] and overrides = [[2, 4, 0]]. Usage puts days 1, 2 and 4 to 10 in use. The override sets days 2, 3 and 4 to 0. The final states are "1000111111".

Try to do better than simulating day by day. For example, O((U + O) log (U + O) + days) is possible, where U and O are the numbers of usage and override rows.

Function

dayStates(days: int, usage: int[][], overrides: int[][]) → String

Examples

Example 1

days = 10usage = [[1, 2, 1], [4, 10, 1]]overrides = [[2, 4, 0]]return = "1000111111"

The usage intervals with value 1 cover days 1 to 2 and days 4 to 10. So before overrides, the states are 1, 1, 0, 1, 1, 1, 1, 1, 1, 1. The override [2, 4, 0] sets days 2, 3 and 4 to 0. The final states are 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, so the answer is "1000111111".

Constraints

  • 1 <= days
  • Each row of usage and overrides is [l, r, v], where v is 0 or 1. The intervals include both day l and day r.
  • Usage is the union of all covering value 1 usage intervals.
  • Override intervals do not overlap and take precedence over usage.

Similar questions at other companies

  • Meeting Scheduling SystemHevo Data · ONSITE INTERVIEW
  • Peak Task Concurrency IntervalsGoogle · ONSITE INTERVIEWGoogle interview questions
  • Detect a Server RAM Capacity BreachMyntra · ONSITE INTERVIEWMyntra interview questions
  • Peak Chat Load Across AgentsCresta · PHONE SCREENCresta interview questions
  • Earliest Time to Schedule a MeetingMathWorks · OAMathWorks interview questions
  • Earliest Meeting Start on a 24-Hour ClockIMC Trading · OAIMC Trading interview questions
  • Majority Labels over Audio IntervalsNooks · PHONE SCREEN
  • Earliest Time to Schedule a MeetingMicrosoft · OAMicrosoft interview questions
  • Earliest Common Meeting StartVisa · OAVisa interview questions
  • Smallest Most-Lit Street PositionHudson River Trading · OAHudson River Trading interview questions

Crusoe interview experiences

  • Crusoe SWE In-Person Onsite Interview Experience: 1 Experience
  • Crusoe Inference Engineer Interview Experience: 1 Experience
See Crusoe hiring insights
Saved
class Solution {
    public String dayStates(int days, int[][] usage, int[][] overrides) {
        // write your code here
    }

}
Checking account…