Toggling US Electoral Districts in O(log N) - Coding Interview Problem
Given a Boolean array of districts, write two methods:
isDem(i) - to determine if the district at position i is Democratic or Republican
toggle(i, j) - to toggle all of the districts in the range form i to j
But here is the kicker - both methods should run in less than O(n) time complexity.
This is a fun brain teaser problem that you may face during a coding/programming interview for Software Engineer jobs. It has a very elegant solution that involves a Fenwick Tree (Binary Index Tree), which was discussed in the previous episode:
• Fenwick Tree (Binary Index Tree) - Quick T...
Source code written in Java: https://bitbucket.org/StableSort/play...
Source code for XOR Fenwick Tree:
https://bitbucket.org/StableSort/play...
Thanks to MehrdadAP for solving the original formulation of the problem and providing inspiration for this solution that makes use of XOR Fenwick Tree. The following is the original formulation of the problem (https://bit.ly/37fYjGb):
Given n light bulbs, write two methods.
isOn(i) to determine if a light bulb is on
toggle(start, end) to toggle all the light bulbs in the range
One caveat, write toggle so that it is less than O(n) complexity
For more information on Binary Index Trees:
https://en.wikipedia.org/wiki/Fenwick...
Written and narrated by Andre Violentyev