How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Onsite rounds at Guidewire.

What role is this question designed for?

This question is commonly asked for Software Engineer candidates at Guidewire during technical interviews.

Minimize Boys Needed Beside Girls | Guidewire Coding Question

Minimize Boys Needed Beside Girls

Company: Guidewire

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

You are given a row of seats in a kindergarten classroom, represented by a string `seats`. - `G` means the seat is occupied by a girl. - `-` means the seat is empty. You may place boys only in empty seats. A girl is considered satisfied if at least one of her immediate neighboring seats, either directly to the left or directly to the right, contains a boy. Return the minimum number of boys that must be placed so that every girl is satisfied. If it is impossible, return `-1`. Example: ```text Input: seats = "-G-GG--" Output: 2 ``` Explanation: Place boys at positions that can cover adjacent girls, for example: ```text -G-GG-- --B--B- ``` The first boy satisfies the first two girls, and the second boy satisfies the last girl.

Quick Answer: This question evaluates string and array manipulation skills, the ability to model adjacency-based constraints, and optimization reasoning for minimizing resource placement.

You are given a string seats representing a row of seats in a kindergarten classroom. 'G' means the seat is occupied by a girl, and '-' means the seat is empty. You may place boys only in empty seats. A girl is satisfied if at least one of her immediate neighboring seats, either directly to the left or directly to the right, contains a boy. Return the minimum number of boys that must be placed so that every girl is satisfied. If it is impossible, return -1.

Constraints

0 <= len(seats) <= 200000
seats contains only 'G' and '-'

Examples

Input: "-G-GG--"

Expected Output: 2

Explanation: Place one boy in the gap between the first two girls to satisfy both, and one boy next to the last girl.

Input: "GGG"

Expected Output: -1

Explanation: The middle girl has no empty neighboring seat, so it is impossible.

Input: "G-G-G"

Expected Output: 2

Explanation: Only one of the two 'G-G' gaps can be shared for the middle girl, so two boys are required in total.

Input: "-GG-"

Expected Output: 2

Explanation: The two girls are adjacent, so they cannot share one boy. Each needs a different neighboring empty seat.

Input: ""

Expected Output: 0

Explanation: There are no girls, so no boys are needed.

Input: "--G--"

Expected Output: 1

Explanation: The single girl needs one boy in either neighboring empty seat.

Hints

A single boy can satisfy two girls only when he sits in the middle of a 'G-G' pattern.
Scan from left to right. If a girl cannot be paired with the next girl using one shared boy, then she must eventually need her own boy.

Quick Overview

This question evaluates string and array manipulation skills, the ability to model adjacency-based constraints, and optimization reasoning for minimizing resource placement.