Skip to content

Instantly share code, notes, and snippets.

@Fawers

Fawers/description.md

Created November 25, 2023 17:52
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save Fawers/8cb96ae369e8df8c12942e15df5ebbda to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save Fawers/8cb96ae369e8df8c12942e15df5ebbda to your computer and use it in GitHub Desktop.
Download ZIP
n buckets problem solutions
Raw
description.md

There are N buckets arranged in a row. Each bucket either is empty or contains a ball. The buckets are specified as a string buckets consisting of characters "." (empty bucket) and " B " (bucket with aball). For example, for buckets = "B. BB. B. . B" the row of buckets appears as follows: In one move you can take the ball out of any bucket and place it in another (empty) bucket. Your goal is to arrange the balls to create an alternating sequence of full and empty buckets. In other words, the distance between two consecutive balls should be equal to 2. Note that the sequence may start at any bucket. For example, in the figure below, the balls are placed correctly: On the other hand, in both of the figures below, the balls are placed incorrectly: What is the minimum number of moves required to create a correct sequence of balls in buckets

Replits:

Raw
solution.py
from functools import reduce
def solution(buckets):
left = buckets.find('B')
right = buckets.rfind('B')
balls_substr = buckets[left:right+1]
balls = balls_substr.count('B')
if len(buckets) // 2 <= balls:
return -1
arranged_balls = '.'.join('B' * balls)
return reduce(
lambda moves, pair: (moves + 1) if pair == ('.', 'B') else moves,
zip(buckets[left:], arranged_balls),
0)
print(solution('BB...B.B..BB.BBB.B....'))
@MarcAbonce
Copy link

MarcAbonce commented Sep 24, 2025

I also failed this interview question and it took me a long time to finally understand the solution.

For anyone struggling with unemployment, you should study sliding window algorithms.
In this case, the correct "textbook" solution for this problem is a fixed-sized sliding window algorithm.

The code above fails some of my test cases because it assumes that the minimum solution is always to move the balls towards the left. However, in cases like B.............................B.B the minimum solution is 1, not 2.
That's why we need to slide the window (arranged_balls) rather than just zip it to one spot.

I made a longer explanation here:
https://gist.github.com/MarcAbonce/f442dc85796f1bd4481f8c85dacb31a8

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment