Suffix arrays in Data Structures Theory - Interactive Code Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to create a suffix array by sorting all suffixes of the string s.

Data Structures Theory

suffixes = [s[i:] for i in range(len(s))]
suffix_array = sorted([1])

Drag options to blanks, or click blank then click option'

Asuffixes

Bs

Crange(len(s))

Dsorted(s)

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting the string itself instead of suffixes.

Sorting the range of indices instead of suffixes.

The suffix array is created by sorting all suffixes of the string. Here, suffixes is the list of all suffixes, so sorting suffixes gives the suffix array.

2fill in blank

medium

Complete the code to build the suffix array as a list of starting indices of sorted suffixes.

Data Structures Theory

suffix_array = sorted(range(len(s)), key=lambda i: [1])

Drag options to blanks, or click blank then click option'

As

Bi

Clen(s)

Ds[i:]

Attempts:

3 left

💡 Hint

Common Mistakes

Sorting indices without a key function.

Using the index i itself as the key.

The suffix array stores the starting indices of suffixes sorted lexicographically. The key function lambda i: s[i:] sorts indices by their suffixes.

3fill in blank

hard

Fix the error in the code that tries to build a suffix array but incorrectly sorts characters instead of suffixes.

Data Structures Theory

suffix_array = sorted(range(len(s)), key=lambda i: s[[1]])

Drag options to blanks, or click blank then click option'

Alen(s)

B0

Ci

D-1

Attempts:

3 left

💡 Hint

Common Mistakes

Using a fixed index like 0 instead of i.

Using an index out of range like len(s).

The code sorts indices by the character at position i, which is correct to access the first character of each suffix. However, sorting by only one character is not a full suffix array. Still, the blank must be i to avoid errors.

4fill in blank

hard

Fill both blanks to create a dictionary comprehension mapping each suffix to its starting index.

Data Structures Theory

{s[i:]: [1] for i in range([2])}

Drag options to blanks, or click blank then click option'

Ai

Blen(s)

C0

Ds

Attempts:

3 left

💡 Hint

Common Mistakes

Using the suffix string as the value instead of the index.

Using an incorrect range that misses suffixes.

The dictionary comprehension maps each suffix s[i:] to its starting index i. The range must go from 0 to len(s) to cover all suffixes.

5fill in blank

hard

Fill all three blanks to create a suffix array by sorting indices with a key function that returns suffixes.

Data Structures Theory

suffix_array = sorted(range([1]), key=lambda [2]: s[[3]:])

Drag options to blanks, or click blank then click option'

Alen(s)

Bi

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using a fixed number instead of len(s).

Using different variable names in lambda and slice.

Using 0 as the slice start instead of the index.

The suffix array is built by sorting indices from 0 to len(s). The key function takes an index i and returns the suffix s[i:] for sorting.