Trie Interview Questions

Array String Backtracking Trie Matrix

Rank

#1125MediumFrequency: 72.7%

Design File System

Asked at DoorDash

Rank

#3356MediumFrequency: 67.9%

Shortest Uncommon Substring in an Array

Asked at Airbnb

Rank

#588HardFrequency: 65.6%

Design In-Memory File System

Asked at DoorDash

Hash Table String Design Trie Sorting

Rank

#139MediumFrequency: 60.5%

Word Break

Array Hash Table String Dynamic Programming Trie Memoization Brute-Force Search

Rank

#140HardFrequency: 59.3%

Word Break II

Array Hash Table String Dynamic Programming Backtracking Trie Memoization

Rank

#692MediumFrequency: 59.1%

Top K Frequent Words

Array Hash Table String Trie Sorting Heap (Priority Queue)Bucket Sort Counting

#10

Rank

#208MediumFrequency: 55%

Implement Trie (Prefix Tree)

Asked at Apple

#11

Rank

#211MediumFrequency: 54.4%

Design Add and Search Words Data Structure

String Depth-First Search Design Trie

#12

Rank

#472HardFrequency: 53%

Concatenated Words

Asked at Amazon

Array String Dynamic Programming Depth-First Search Trie Sorting

#13

Rank

#648MediumFrequency: 52.1%

Replace Words

#14

Rank

#2339MediumFrequency: 47.5%

K Divisible Elements Subarrays

Array Hash Table Trie Rolling Hash Hash Function Enumeration

#15

Rank

#677MediumFrequency: 43.2%

Map Sum Pairs

Asked at Flipkart

#16

Rank

#808MediumFrequency: 41.6%

Number of Matching Subsequences

Array Hash Table String Binary Search Dynamic Programming Trie Sorting

#17

Rank

#642HardFrequency: 39.1%

Design Search Autocomplete System

String Depth-First Search Design Trie Sorting Heap (Priority Queue)Data Stream

#18

Rank

#3329MediumFrequency: 39.1%

Find the Length of the Longest Common Prefix

#19

Rank

#421MediumFrequency: 35.3%

Maximum XOR of Two Numbers in an Array

Array Hash Table Bit Manipulation Trie

#20

Rank

#616MediumFrequency: 33%

Add Bold Tag in String

Array Hash Table String Trie String Matching Aho–Corasick Algorithm

#21

Rank

#440HardFrequency: 29.7%

K-th Smallest in Lexicographical Order

Trie

#22

Rank

#839MediumFrequency: 29.5%

Short Encoding of Words

Asked at Apple

#23

Rank

#1350MediumFrequency: 28.9%

Remove Sub-Folders from the Filesystem

Array String Depth-First Search Trie

#24

Rank

#386MediumFrequency: 28.1%

Lexicographical Numbers

Depth-First Search Trie

#25

Rank

#2550MediumFrequency: 24.4%

Words Within Two Edits of Dictionary

Array String Trie

#26

Rank

#746HardFrequency: 23.4%

Prefix and Suffix Search

Asked at Meta

Array Hash Table String Design Trie

#27

Rank

#676MediumFrequency: 22.1%

Implement Magic Dictionary

Hash Table String Depth-First Search Design Trie

#28

Rank

#1097HardFrequency: 22.1%

Stream of Characters

Array String Design Trie Data Stream Aho–Corasick Algorithm

#29

Rank

#1826HardFrequency: 22.1%

Maximum XOR With an Element From Array

Array Bit Manipulation Trie

#30

Rank

#3905MediumFrequency: 20.9%

Partition String

Hash Table String Trie Simulation

#31

Rank

#3305HardFrequency: 20.3%

Count Prefix and Suffix Pairs II

Array String Trie Rolling Hash String Matching Hash Function Z Algorithm

#32

Rank

#1838MediumFrequency: 20.3%

Number of Distinct Substrings in a String

String Trie Rolling Hash Suffix Array Hash Function

#33

Rank

#1075EasyFrequency: 20%

Index Pairs of a String

Asked at Amazon

Array String Trie Sorting Aho–Corasick Algorithm

#34

Rank

#2494HardFrequency: 19.5%

Sum of Prefix Scores of Strings

Array String Trie Counting

#35

Rank

#3376HardFrequency: 19.5%

Longest Common Suffix Queries

Array String Trie

#36

Rank

#527HardFrequency: 18%

Word Abbreviation

Array String Greedy Trie Sorting

#37

Rank

#1244HardFrequency: 18%

Distinct Echo Substrings

String Trie Rolling Hash Suffix Array Hash Function Suffix Automaton Suffix Tree

#38

Rank

#425HardFrequency: 16.4%

Word Squares

Array String Backtracking Trie

#39

Rank

#760MediumFrequency: 16.4%

Bold Words in String

Array Hash Table String Trie String Matching Aho–Corasick Algorithm

#40

Rank

#1080MediumFrequency: 16.4%

Camelcase Matching

Array Two Pointers String Trie String Matching

#41

Rank

#2009MediumFrequency: 16.4%

Longest Word With All Prefixes

Array String Depth-First Search Trie

#42

Rank

#2755MediumFrequency: 14.6%

Extra Characters in a String

Array Hash Table String Dynamic Programming Trie

#43

Rank

#2079HardFrequency: 8.1%

Delete Duplicate Folders in System

Array Hash Table String Depth-First Search Trie Sorting Hash Function

#44

Rank

#3238HardFrequency: 7.3%

Minimum Cost to Convert String II

Asked at Microsoft

Array String Dynamic Programming Graph Theory Trie Shortest Path

#45

Rank

#720MediumFrequency: 7.3%

Longest Word in Dictionary

Asked at Microsoft

Array Hash Table String Trie Sorting

#46

Rank

#3309EasyFrequency: 5%

Count Prefix and Suffix Pairs I

Array String Trie Rolling Hash String Matching Hash Function

#47

Rank

#1433HardFrequency: 5%

Encrypt and Decrypt Strings

Array Hash Table String Design Trie

#48

Rank

#1949MediumFrequency: 5%

Implement Trie II (Prefix Tree)

Asked at Amazon