Dota2 Senate — Solution in Python, Java & C++
Dota2 Senate solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem on strings and greedy.
Dota2 Senate is a medium coding problem on strings, greedy and queue, asked in Amazon and Microsoft interviews.
- Difficulty: Medium
- Topics: Strings, Greedy, Queue
- Asked at: Amazon, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The senate has senators from the Radiant and Dire parties, given as a string of 'R' and 'D' in seating order. Voting proceeds in rounds; in each round every remaining senator, in order, may either ban one senator from the other party for the rest of the game, or — if only their own party remains — declare victory.
Assuming every senator plays optimally, return the winning party: "Radiant" or "Dire".
Example 1
Input: senate = "RD"
Output: Radiant
Example 2
Input: senate = "RDD"
Output: Dire
Example 3
Input: senate = "DRRDRDRDRDDRDRDR"
Output: Radiant
Constraints
1 <= senate.length <= 40senate consists of 'R' and 'D'.
Hints for Dota2 Senate
Hint 1
A senator's best move is always to ban the next opposing senator who would otherwise act.
Hint 2
Keep two queues of indices, one per party, and pop the front of each.
Hint 3
Whoever has the smaller index bans the other and rejoins the queue with index
i + n, representing the next round.
How to solve Dota2 Senate
A senator's best move is to ban the next opposing senator in turn order. Keep a queue of indices per party; the smaller index bans the other and rejoins with index + n for the next round.
Approach
- Fill two queues with the indices of
RandD. - While both are non-empty, pop one from each; the smaller index survives and is re-pushed as
i + n. - Return the party with senators left.
Why it works
Banning the nearest upcoming opponent removes the most imminent threat, and adding n preserves round order so the simulation is exact.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
- Re-pushing without the
+ noffset breaks the round ordering.
Reference solution
Python
from collections import deque
def predictPartyVictory(senate: str) -> str:
n = len(senate)
radiant = deque(i for i, ch in enumerate(senate) if ch == "R")
dire = deque(i for i, ch in enumerate(senate) if ch == "D")
while radiant and dire:
r = radiant.popleft()
d = dire.popleft()
if r < d:
radiant.append(r + n)
else:
dire.append(d + n)
return "Radiant" if radiant else "Dire"Java
public static String predictPartyVictory(String senate) {
int n = senate.length();
List<Integer> radiant = new ArrayList<>();
List<Integer> dire = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (senate.charAt(i) == 'R') radiant.add(i);
else dire.add(i);
}
int r = 0, d = 0;
while (r < radiant.size() && d < dire.size()) {
int ri = radiant.get(r++);
int di = dire.get(d++);
if (ri < di) radiant.add(ri + n);
else dire.add(di + n);
}
return r < radiant.size() ? "Radiant" : "Dire";
}C++
string predictPartyVictory(string senate) {
int n = (int) senate.size();
vector<int> radiant, dire;
for (int i = 0; i < n; i++) {
if (senate[i] == 'R') radiant.push_back(i);
else dire.push_back(i);
}
size_t r = 0, d = 0;
while (r < radiant.size() && d < dire.size()) {
int ri = radiant[r++];
int di = dire[d++];
if (ri < di) radiant.push_back(ri + n);
else dire.push_back(di + n);
}
return r < radiant.size() ? "Radiant" : "Dire";
}JavaScript
var predictPartyVictory = function(senate) {
const n = senate.length;
const radiant = [], dire = [];
for (let i = 0; i < n; i++) {
if (senate.charAt(i) === "R") radiant.push(i);
else dire.push(i);
}
let r = 0, d = 0;
while (r < radiant.length && d < dire.length) {
const ri = radiant[r++];
const di = dire[d++];
if (ri < di) radiant.push(ri + n);
else dire.push(di + n);
}
return r < radiant.length ? "Radiant" : "Dire";
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 515 strings problems · the whole catalogue
Learn the technique: Strings · Greedy Algorithms