Programming Interview Questions 23: Find Word Positions in Text | Arden DertatArden Dertat

Programming Interview Questions 23: Find Word Positions in Text | Arden DertatArden Dertat

Given a text file and a word, find the positions that the word occurs in the file. We'll be asked to find the positions of many words in the same file.

Since we'll have to answer multiple queries, precomputation would be useful. We'll build a data structure that stores the positions of all the words in the text file. This is known as inverted index in Information Retrieval. It's basically a mapping between the words in the file and their positions.

X. Using HashTable

def createIndex1(text): index=collections.defaultdict(list) words=getWords(text) for pos, word in enumerate(words): index[word].append(pos) return index

X. Using Trie
we can do better by using a more space efficient data structure for text, namely a trie, also known as prefix tree. Trie is a tree which is very efficient in text storage and search. It saves space by letting the words that have the same prefixes to share data. And most languages contain many words that share the same prefix. - See more at:

The complexity of adding or finding an element in a trie is also constant O(1), like hashtable. It doesn’t depend on the number of words stored in the trie, it only depends on the number of characters in the word, just like hashing. And maximum number of characters in a word for a particular language is constant.

Read full article from Programming Interview Questions 23: Find Word Positions in Text | Arden DertatArden Dertat