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.
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.
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.