Alternating Jumps to the Last Index
Updated
Problem statement
You are given an integer array arr. From a starting index you make jumps numbered 1, 2, 3, and so on. Every jump goes right, from the current index i to some index j > i:
- On an odd-numbered jump (1st, 3rd, 5th, ...), go to the index
jwhose valuearr[j]is the smallest value that is at leastarr[i]. - On an even-numbered jump (2nd, 4th, 6th, ...), go to the index
jwhose valuearr[j]is the largest value that is at mostarr[i].
If several indexes to the right hold that value, jump to the smallest of those indexes. If no index fits the rule, you are stuck and the jumps end.
A starting index is good if its jumps reach the last index, n - 1. The last index itself is good, since you are already there. Return the number of good starting indexes.
Function
oddEvenJumps(arr: int[]) → intExamples
Example 1
arr = [40,10,40,30,20]return = 2Index 4 is the last index, so it is good with no jumps. From index 1 (value 10), jump 1 goes to the smallest value of at least 10 to its right, which is 20 at index 4: good. From index 0 (40), jump 1 goes to the 40 at index 2, jump 2 goes to the largest value of at most 40 after index 2, which is 30 at index 3, and jump 3 needs a value of at least 30 after index 3, but only 20 is left: stuck. Index 2 (40) and index 3 (30) have no larger-or-equal value to their right, so their first jump fails. The good starting indexes are 1 and 4.
Example 2
arr = [5,8,8,2,8]return = 5Every index is good. From index 0, jump 1 can reach an 8 at index 1, 2 or 4; ties go to the smallest index, so it lands on index 1. Jump 2 then needs the largest value of at most 8 after index 1: the 8s at indexes 2 and 4 tie, so it lands on index 2. Jump 3 goes to the 8 at index 4, the end. Index 1 reaches the end through index 2, index 2 and index 3 each jump straight to index 4, and index 4 is the end.
Example 3
arr = [3,9,4,6,5]return = 2From index 0 (3), jump 1 goes to 4 at index 2, the smallest value of at least 3. Jump 2 needs a value of at most 4 after index 2, but 6 and 5 are both larger: stuck. Index 2 (4) jumps once to 5 at index 4, the end. Index 1 (9) and index 3 (6) have no larger-or-equal value to their right. The good starting indexes are 2 and 4.
Constraints
1 <= arr.length <= 50000 <= arr[i] < 10^6
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
- Maximize Shipment Order by Sorting One WindowAmazon · OA
- Most Segments That Sort the ArrayRippling · OARippling interview questions
- Maximum Sum of HeightsVirtu Financial · OAVirtu Financial interview questions
- Trapping Rain WaterGoogle · OAGoogle interview questions
- Maximum Escape Game ScoreMicrosoft · OAMicrosoft interview questions
- Maximum Taxi EarningsWells Fargo · OAWells Fargo interview questions
- Russian Doll EnvelopesInMobi · ONSITE INTERVIEWInMobi interview questions
- Rain Kept Between WallsDocuSign · PHONE SCREENDocuSign interview questions
- Rain Water Held Between BarsAdobe · PHONE SCREENAdobe interview questions
- Longest Chain of Nested BoxesBloomberg LP · PHONE SCREENBloomberg LP 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)