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 several coding interview problems

Quick Overview

This set of problems evaluates proficiency in string processing and combinatorial parsing, arbitrary-precision arithmetic using string representations, pointer/ancestor-chain intersection detection, and computational geometry for overlap counting, emphasizing algorithmic design, correctness, and performance.

Solve several coding interview problems

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

The interview included the following coding problems: 1. **Decode ambiguous Morse text**: Use the standard Morse mapping for letters `A-Z`. You are given a string `s` containing only `.` and `-`, with no separators between letters. Return all possible uppercase strings whose Morse encodings concatenate to exactly `s`. First describe a backtracking solution, then explain how to optimize it. 2. **Subtract large integers stored as strings**: Given two non-negative integers `a` and `b` represented as decimal strings, compute `a - b` without converting the inputs to built-in integer types. Return the normalized decimal string result, using a leading `-` if the result is negative and removing unnecessary leading zeros. 3. **Check whether two family chains intersect**: Each person has at most one `parent` pointer, so repeatedly following parent pointers forms a chain of ancestors. Given two people, determine whether their ancestor chains intersect, meaning the two people share at least one common ancestor node. 4. **Find the maximum overlap among squares**: You are given a set of axis-aligned squares in 2D. Each square is represented by its bottom-left corner `(x, y)` and side length `len`. Determine the maximum number of squares that cover the same point on the plane. Assume boundary points count as covered. A verbal algorithmic explanation is sufficient; full code is not required.

Quick Answer: This set of problems evaluates proficiency in string processing and combinatorial parsing, arbitrary-precision arithmetic using string representations, pointer/ancestor-chain intersection detection, and computational geometry for overlap counting, emphasizing algorithmic design, correctness, and performance.

Part 1: Decode Ambiguous Morse Text

Use the standard Morse mapping for letters A-Z: A .-, B -..., C -.-., D -.., E ., F ..-., G --., H ...., I .., J .---, K -.-, L .-.., M --, N -., O ---, P .--., Q --.-, R .-., S ..., T -, U ..-, V ...-, W .--, X -..-, Y -.--, Z --... You are given a string s containing only '.' and '-' with no separators between letters. Return every uppercase string whose Morse encodings concatenate to exactly s. Return the results in lexicographic order. The empty input has one valid decoding: the empty string ''. A naive backtracking solution tries every letter whose code matches the next prefix; an optimized solution memoizes answers for each starting index.

Constraints

0 <= len(s) <= 20
s contains only '.' and '-'
Use the standard Morse mapping for A-Z exactly as given
The number of valid decodings can be exponential, so output size may dominate runtime

Examples

Input: ('.-',)

Expected Output: ['A', 'ET']

Explanation: '.-' can be decoded as A or as E followed by T.

Input: ('...',)

Expected Output: ['EEE', 'EI', 'IE', 'S']

Explanation: There are four exact segmentations using standard Morse letters.

Input: ('--',)

Expected Output: ['M', 'TT']

Explanation: '--' is either M or T + T.

Input: ('.',)

Expected Output: ['E']

Explanation: A single dot maps only to E.

Input: ('',)

Expected Output: ['']

Explanation: The empty Morse string corresponds to the empty decoded string.

Hints

At position i, try every letter whose Morse code matches s starting at i.
Many recursive calls solve the same suffix more than once; cache results by index.

Part 2: Subtract Large Integers Stored as Strings

Given two non-negative integers a and b represented as decimal strings, compute a - b without converting the full inputs to built-in integer types. Return a normalized decimal string: remove unnecessary leading zeros, and use a leading '-' if the result is negative. For example, '0010' - '0009' should return '1', and '5' - '12' should return '-7'.

Constraints

1 <= len(a), len(b) <= 100000
a and b contain only characters '0' through '9'
Inputs may contain leading zeros
Do not convert the full strings to built-in integer types

Examples

Input: ('123', '45')

Expected Output: '78'

Explanation: 123 - 45 = 78.

Input: ('45', '123')

Expected Output: '-78'

Explanation: Since 45 < 123, the result is negative.

Input: ('1000', '1')

Expected Output: '999'

Explanation: Borrowing across zeros produces 999.

Input: ('0010', '0009')

Expected Output: '1'

Explanation: Leading zeros should not appear in the final answer.

Input: ('000', '0')

Expected Output: '0'

Explanation: Equal values normalize to '0'.

Hints

First strip leading zeros and compare magnitudes by length, then lexicographically if lengths match.
Implement elementary-school subtraction from right to left and track a borrow.

Part 3: Check Whether Two Family Chains Intersect

Each person has at most one parent, so repeatedly following parent pointers forms a single ancestor chain. The chain for a person includes that person themself, then their parent, grandparent, and so on. Given a parent mapping and two starting people, determine whether the two chains intersect, meaning they share at least one node. If a starting person is None, treat that chain as empty. If a person is missing from the map, treat them as having no parent.

Constraints

0 <= number of people in parent <= 100000
Each person has at most one parent
The parent pointers form acyclic chains
person1 and person2 may be None

Examples

Input: ({'A': 'B', 'B': 'C', 'D': 'C', 'C': None}, 'A', 'D')

Expected Output: True

Explanation: Both chains reach C.

Input: ({'A': 'B', 'B': None, 'C': 'D', 'D': None}, 'A', 'C')

Expected Output: False

Explanation: The two ancestor chains are disjoint.

Input: ({'A': 'B', 'B': None}, 'A', 'A')

Expected Output: True

Explanation: A chain always intersects itself.

Input: ({'A': None}, None, 'A')

Expected Output: False

Explanation: A None starting person has an empty chain.

Hints

This is the same shape as the linked-list intersection problem.
A two-pointer technique can align different chain lengths without extra memory.

Part 4: Find the Maximum Overlap Among Squares

You are given a list of axis-aligned squares in 2D. Each square is represented as (x, y, length), where (x, y) is the bottom-left corner and the square covers the closed region [x, x + length] x [y, y + length]. Boundary points count as covered. Return the maximum number of squares that cover the same point. If the input is empty, return 0.

Constraints

0 <= number of squares <= 500
-10^9 <= x, y <= 10^9
0 <= length <= 10^9
Squares are axis-aligned and boundary points count as covered

Examples

Input: ([] ,)

Expected Output: 0

Explanation: No squares means no covered point.

Input: ([(0, 0, 2)],)

Expected Output: 1

Explanation: Any point in the square is covered by exactly one square.

Input: ([(0, 0, 2), (1, 1, 2)],)

Expected Output: 2

Explanation: The overlap region [1, 2] x [1, 2] is covered by both squares.

Input: ([(0, 0, 1), (1, 0, 1)],)

Expected Output: 2

Explanation: The squares touch along the vertical edge x = 1, which counts as overlap.

Input: ([(0, 0, 2), (1, 0, 2), (1, 1, 1)],)

Expected Output: 3

Explanation: All three squares cover the point (1, 1).

Hints

The maximum overlap can be checked at some x-coordinate that is a square's left or right edge.
For a fixed x, reduce the problem to finding the maximum overlap among closed y-intervals, and process start events before end events at the same y.

Quick Overview

Solve several coding interview problems

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Part 1: Decode Ambiguous Morse Text

Constraints

0 <= len(s) <= 20
s contains only '.' and '-'
Use the standard Morse mapping for A-Z exactly as given
The number of valid decodings can be exponential, so output size may dominate runtime

Examples

Input: ('.-',)

Expected Output: ['A', 'ET']

Explanation: '.-' can be decoded as A or as E followed by T.

Input: ('...',)

Expected Output: ['EEE', 'EI', 'IE', 'S']

Explanation: There are four exact segmentations using standard Morse letters.

Input: ('--',)

Expected Output: ['M', 'TT']

Explanation: '--' is either M or T + T.

Input: ('.',)

Expected Output: ['E']

Explanation: A single dot maps only to E.

Input: ('',)

Expected Output: ['']

Explanation: The empty Morse string corresponds to the empty decoded string.

Hints

At position i, try every letter whose Morse code matches s starting at i.
Many recursive calls solve the same suffix more than once; cache results by index.

Part 2: Subtract Large Integers Stored as Strings

Constraints

1 <= len(a), len(b) <= 100000
a and b contain only characters '0' through '9'
Inputs may contain leading zeros
Do not convert the full strings to built-in integer types

Examples

Input: ('123', '45')

Expected Output: '78'

Explanation: 123 - 45 = 78.

Input: ('45', '123')

Expected Output: '-78'

Explanation: Since 45 < 123, the result is negative.

Input: ('1000', '1')

Expected Output: '999'

Explanation: Borrowing across zeros produces 999.

Input: ('0010', '0009')

Expected Output: '1'

Explanation: Leading zeros should not appear in the final answer.

Input: ('000', '0')

Expected Output: '0'

Explanation: Equal values normalize to '0'.

Hints

First strip leading zeros and compare magnitudes by length, then lexicographically if lengths match.
Implement elementary-school subtraction from right to left and track a borrow.

Part 3: Check Whether Two Family Chains Intersect

Constraints

0 <= number of people in parent <= 100000
Each person has at most one parent
The parent pointers form acyclic chains
person1 and person2 may be None

Examples

Input: ({'A': 'B', 'B': 'C', 'D': 'C', 'C': None}, 'A', 'D')

Expected Output: True

Explanation: Both chains reach C.

Input: ({'A': 'B', 'B': None, 'C': 'D', 'D': None}, 'A', 'C')

Expected Output: False

Explanation: The two ancestor chains are disjoint.

Input: ({'A': 'B', 'B': None}, 'A', 'A')

Expected Output: True

Explanation: A chain always intersects itself.

Input: ({'A': None}, None, 'A')

Expected Output: False

Explanation: A None starting person has an empty chain.

Hints

This is the same shape as the linked-list intersection problem.
A two-pointer technique can align different chain lengths without extra memory.

Part 4: Find the Maximum Overlap Among Squares

Constraints

0 <= number of squares <= 500
-10^9 <= x, y <= 10^9
0 <= length <= 10^9
Squares are axis-aligned and boundary points count as covered

Examples

Input: ([] ,)

Expected Output: 0

Explanation: No squares means no covered point.

Input: ([(0, 0, 2)],)

Expected Output: 1

Explanation: Any point in the square is covered by exactly one square.

Input: ([(0, 0, 2), (1, 1, 2)],)

Expected Output: 2

Explanation: The overlap region [1, 2] x [1, 2] is covered by both squares.

Input: ([(0, 0, 1), (1, 0, 1)],)

Expected Output: 2

Explanation: The squares touch along the vertical edge x = 1, which counts as overlap.

Input: ([(0, 0, 2), (1, 0, 2), (1, 1, 1)],)

Expected Output: 3

Explanation: All three squares cover the point (1, 1).

Hints

The maximum overlap can be checked at some x-coordinate that is a square's left or right edge.
For a fixed x, reduce the problem to finding the maximum overlap among closed y-intervals, and process start events before end events at the same y.