Find fair split of a two-color necklace
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
Given a circular necklace represented by a string s over {'a','b'}, you may cut the necklace at most twice (yielding three contiguous pieces). Can you assign these three pieces to two people so that each person receives exactly the same number of 'a' beads and the same number of 'b' beads? If it is possible, return any valid pair of cut indices on the circle and the assignment of pieces to each person; otherwise return 'impossible'. Explicitly state feasibility conditions (e.g., necessary parity constraints) and design an algorithm that runs in O(n) time with O(
1) or O(n) extra space. Analyze correctness and complexity. Follow-up: extend to three gem types (e.g., {'a','b','c'}) where you may make at most three cuts (producing four pieces) and still split between two people so each receives equal counts of every type. Provide the generalized algorithm, state required conditions, and discuss how your approach scales with the number of gem types.
Overview: This question evaluates algorithm design and combinatorial reasoning on circular sequences in the coding & algorithms domain, testing string/array manipulation, feasibility-condition analysis (e.g., parity constraints), and the ability to produce linear-time, low-space partitioning algorithms.
Community answers
Answer by kishoma
str = i will go from 0 to < 2n and we use sliding to count counts of bead inside them if we find that is the possible cut and we can position as well
Answer by pramyesterday
#include
using namespace std;
int main(){
vectornecklace={0, 1, 1, 0, 1, 0, 0, 1};
int numZero=0;
int numOnes=0;
int countZero=0;
int countOne=0;
// int countTwo=0;
int i=0,j=0;
int n=necklace.size();
for(int i=0;i(numOnes/2)){
while(countOne>(numOnes/2)){
if(necklace[i]==0)countZero--;
else if(necklace[i]==1)countOne--;
i++;
}
}
else if(i < j && countZero>(numZero/2)){
while(countZero>(numZero/2)){
if(necklace[i]==0)countZero--;
else if(necklace[i]==1)countOne--;
i++;
}
}
}
cout<<"Impossible";
return 0;
}
Answer by Coderka14
#include
using namespace std;
class Solution
{
public:
vector fairSplit(string s)
{
int n = s.size();
int totalA = 0;
int totalB = 0;
for (char ch : s)
{
if (ch == 'a')
totalA++;
else
totalB++;
}
if (totalA % 2 || totalB % 2)
return {};
int needA = totalA / 2;
int needB = totalB / 2;
string t = s + s;
int a = 0;
int b = 0;
int left = 0;
for (int right = 0; right < 2 * n; right++)
{
if (t[right] == 'a')
a++;
else
b++;
while (left <= right && (a > needA || b > needB))
{
if (t[left] == 'a')
a--;
else
b--;
left++;
}
if (a == needA && b == needB)
{
if (right - left + 1 < n)
{
int cut1 = left % n;
int cut2 = (right + 1) % n;
return {cut1, cut2};
}
}
}
return {};
}
};