FastPrepSelf-Describing Indices in Pi Digits

Self-Describing Indices in Pi Digits

Google logoGoogle● EasyNEW GRADONSITE INTERVIEW
Learn

Problem statement

A string digits contains a sequence of decimal digits. The interview scenario uses a prefix of the digits of pi after the decimal point. Positions are one-based.

An index i is self-describing when the decimal representation of i exactly equals the substring ending at position i. If i has d digits, compare it with positions i - d + 1 through i. Positions before 1 cannot match.

Return every self-describing index in increasing order.

Function

findSelfDescribingIndices(digits: String) → int[]

Examples

Example 1

digits = "123456789"return = [1,2,3,4,5,6,7,8,9]

At every one-digit position, the stored digit equals that index.

Example 2

digits = "000000000012"return = [12]

Positions 11 and 12 form 12, so index 12 matches.

Example 3

digits = "1204"return = [1,2,4]

Indices one, two, and four match their one-character suffixes.

Constraints

  • 1 <= digits.length <= 1000000.
  • digits contains only characters '0' through '9'.

More Google problems

See Google hiring insights
public int[] findSelfDescribingIndices(String digits) {
    // Write your code here.
}
digits"123456789"
expected[1,2,3,4,5,6,7,8,9]
Checking account…