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 Technical Screen rounds at Google.

What role is this question designed for?

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

Solve Grid and Counting Problems | Google Coding Question

Solve Grid and Counting Problems

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

A software engineering intern phone screen included two coding tasks: 1. **Count islands in a grid** Given an `m x n` grid of characters where `'1'` represents land and `'0'` represents water, return the number of islands. An island is formed by connecting adjacent land cells horizontally or vertically. You may assume all four edges of the grid are surrounded by water. 2. **Count ways to form a target word** Given an array of uppercase letters, count how many different ways you can choose letters from the array so that the chosen letters can be rearranged to spell `GOOGLE`. Each array element can be used at most once, and letters at different indices are considered different choices even if they contain the same character. Design efficient algorithms for both tasks, and discuss the time and space complexity of your approach.

Quick Answer: This question evaluates skills in grid-based graph traversal and connected-component detection for the island counting task, and combinatorial counting with multiset considerations for the target-word formation task.

Part 1: Count Islands in a Grid

Given a 2D grid of characters where each cell is either '1' (land) or '0' (water), return the number of islands. An island is a group of adjacent land cells connected only horizontally or vertically. Diagonal cells do not count as connected. You may assume the grid edges are surrounded by water.

Constraints

0 <= number of rows <= 300
0 <= number of columns <= 300
grid[r][c] is either '0' or '1'
All rows have the same length

Examples

Input: []

Expected Output:

Explanation: Empty grid contains no land, so there are no islands.

Input: [['1']]

Expected Output:

Explanation: A single land cell forms one island.

Input: [['1','1','0','0','0'],['1','1','0','0','0'],['0','0','1','0','0'],['0','0','0','1','1']]

Expected Output:

Explanation: There are three separate groups of connected land cells.

Input: [['1','0','1'],['0','1','0'],['1','0','1']]

Expected Output:

Explanation: Diagonal connections do not count, so each '1' here is its own island.

Hints

Whenever you find an unvisited land cell, start a DFS or BFS to mark the entire island.
Only 4-directional neighbors matter: up, down, left, and right.

Part 2: Count Ways to Form the Word GOOGLE

Given an array of uppercase letters, count how many different ways you can choose letters so that the chosen letters can be rearranged to spell GOOGLE. Each array element can be used at most once. Letters at different indices count as different choices even if they contain the same character. The word GOOGLE requires exactly 2 G's, 2 O's, 1 L, and 1 E.

Constraints

0 <= len(letters) <= 200000
Each element is an uppercase English letter from 'A' to 'Z'
The answer may be large, but fits in Python's integer type

Examples

Input: []

Expected Output:

Explanation: No letters means it is impossible to form GOOGLE.

Input: ['G','O','O','G','L','E']

Expected Output:

Explanation: There is exactly one way to choose all six letters.

Input: ['G','G','G','O','O','O','L','E']

Expected Output:

Explanation: Choose 2 of 3 G's and 2 of 3 O's: C(3,2) * C(3,2) * 1 * 1 = 9.

Input: ['G','G','O','O','L','L','E']

Expected Output:

Explanation: There is 1 way to choose the 2 G's, 1 way to choose the 2 O's, 2 choices for L, and 1 choice for E.

Input: ['G','G','G','G','O','O','O','L','L','E','E','X']

Expected Output:

Explanation: C(4,2) * C(3,2) * 2 * 2 = 6 * 3 * 2 * 2 = 72. Extra letters like X do not matter.

Hints

First count how many G, O, L, and E letters appear in the array.
You need to choose 2 of the G positions and 2 of the O positions, then 1 L and 1 E.

Quick Overview

This question evaluates skills in grid-based graph traversal and connected-component detection for the island counting task, and combinatorial counting with multiset considerations for the target-word formation task.