Stars Between Bars in Ranges
Updated
Problem statement
You are given a string s made of stars '*' and bars '|', and a list of queries. Each query [left, right] picks the part of s from position left to position right, both included. Positions start at 0.
For one query, look at the bars inside that part. Find the first bar and the last bar there, and count the stars that lie between them. Stars before the first bar or after the last bar do not count. If the part holds fewer than two bars, the answer is 0.
Return an array with one answer for each query, in the order of the queries.
Function
countStarsBetweenBars(s: String, queries: int[][]) → int[]Examples
Example 1
s = "**|*|***|*"queries = [[0,9],[3,3],[2,4],[5,9],[1,6]]return = [4,0,1,0,1]The bars are at positions 2, 4 and 8. For [0, 9] the first bar is at 2 and the last at 8, and the stars at 3, 5, 6 and 7 lie between them: 4. [3, 3] holds one star and no bar: 0. [2, 4] starts and ends on a bar, with one star at 3 between: 1. [5, 9] holds only one bar, so no star is between two bars: 0. [1, 6] holds the bars at 2 and 4 with one star between: 1.
Example 2
s = "|||*|"queries = [[0,4],[0,2],[1,3],[3,4]]return = [1,0,0,0]Bars can sit next to each other. [0, 4] runs from the bar at 0 to the bar at 4 and has one star, at 3, between them: 1. [0, 2] holds the bars at 0, 1 and 2 and no star: 0. [1, 3] holds the bars at 1 and 2 and the star at 3, which is after the last bar of this range: 0. [3, 4] holds only the bar at 4: 0.
Example 3
s = "*|*****|**"queries = [[0,9],[2,8],[1,7],[0,0]]return = [5,0,5,0]The five stars at positions 2 to 6 sit between the bars at 1 and 7. The stars at 0, 8 and 9 are outside those bars and never count. [0, 9] and [1, 7] both give 5. [2, 8] reaches only the bar at 7, so it gives 0. [0, 0] is one star: 0.
Constraints
1 <= s.length <= 104scontains only the characters'*'and'|'.1 <= queries.length <= 2000queries[i].length == 2and0 <= queries[i][0] <= queries[i][1] < s.length
More Expedia Online Assessment questions
- Balanced NumbersOA · Seen Aug 2026
- REST API: Discounted PriceOA · Seen Aug 2026
- Maximum Team SizeOA · Seen Mar 2026
- Per-Domain Request LimiterOA · Seen Oct 2025
- Count Equal-Frequency SubsequencesOA · Seen Mar 2025
- Count Increasing Stock PeriodsOA · Seen Mar 2025
- Get Minimum StepsOA · Seen Oct 2024
- Rank Songs by PopularityOA · Seen Oct 2024
- Calculate the SumOA · Seen Oct 2024
- Get Maximum EfficiencyOA · Seen Oct 2024
Similar questions at other companies
- Earliest Time to Schedule a MeetingMathWorks · OAMathWorks interview questions
- Earliest Meeting Start on a 24-Hour ClockIMC Trading · OAIMC Trading interview questions
- Earliest Time to Schedule a MeetingMicrosoft · OAMicrosoft interview questions
- Prefix-Length Letter ShiftsChewy · PHONE SCREEN
- Calculate the Sum After Range TogglesBlink Health · OA
- Compress Editor Actions into Operational Transform OperationsReplit · OA · PHONE SCREEN · ONSITE INTERVIEW
- Count One-Swap Number PairsCapital One · OACapital One interview questions
- Optimal TransferSnowflake · OASnowflake interview questions
- Count Attack Vectors by Divisor RangeVisa · OAVisa interview questions
- Smallest Most-Lit Street PositionHudson River Trading · OAHudson River Trading interview questions
Expedia interview experiences
- Expedia Intern Final Round in 2021: 28 Experiences (Part 4 of 6)
- Expedia Intern Finals Before 2020: 14 Experiences (Part 6 of 6)
- Expedia Intern Final Round in 2020: 24 Experiences (Part 5 of 6)
- Expedia Intern Final Round in 2022: 15 Experiences (Part 3 of 6)
- Expedia Intern Final Round in 2023: 17 Experiences (Part 2 of 6)
- Expedia SWE Intern Final Round: 126 Experiences (Part 1 of 6)