OA Questions: What are the Optimal Solutions?

In the world of competitive programming and technical interviews, algorithmic questions often revolve around efficiency, creativity, and the ability to tackle complex problems systematically. Today, we will explore two intriguing questions that can commonly appear in these contexts.

Question 1: Counting Username Appearances

Problem Statement

You are given two arrays: sentences, containing strings of text, and usernames, containing the usernames you want to count. Your task is to determine how many times each username appears in total across all the sentences.

Clarification

Before diving into the solution, let’s clarify an important aspect of the problem. One user asked whether the username “abc” would match in the string “xabcx”. The answer is no; we are looking for exact matches of the username within the sentences.

Optimal Solution Approaches

To solve this problem efficiently, we can consider two primary approaches:

1. Using a HashMap: This is a straightforward method. We can iterate through each sentence, tokenize it into words, and maintain a count in a HashMap for each username.

2. Rolling Hash or KMP Algorithm: For a more advanced approach, we can use string matching algorithms like the Knuth-Morris-Pratt (KMP) algorithm or rolling hash techniques. These algorithms allow us to search for the usernames within the sentences more efficiently, especially if the input sizes are large.

Implementation Example

Here’s a simple implementation using a HashMap in Python:

def count_usernames(sentences, usernames):
    count_map = {username: 0 for username in usernames}
    for sentence in sentences:
        words = sentence.split()
        for word in words:
            if word in count_map:
                count_map[word] += 1
    return count_map

This implementation initializes a count for each username and iterates through each sentence, counting occurrences efficiently.

Question 2: Removing Prefix Words

Problem Statement

Given an array of strings words, your task is to remove each word from the array that is a prefix of another word.

Optimal Solution Approach

A highly efficient way to solve this problem is by using a Trie (prefix tree). A Trie allows us to store words in a tree-like structure, where each node represents a character. This feature makes it easy to identify prefixes.

How the Trie Works

1. Insert each word into the Trie.
2. While inserting, mark nodes as “end nodes” for words that are not prefixes of any other word.
3. After inserting all the words, the end nodes will represent the words that are not prefixes of any other words.

Example Walkthrough

Consider the following list of words:

words = ["apple", "app", "banana", "band", "bandage"]

1. Insert “apple”:

   • Trie: a -> p -> p -> l -> e (end node at ‘e’)

2. Insert “app”:

   • Trie: a -> p -> p (end node at second ‘p’)

3. Insert “banana”:

   • Trie: b -> a -> n -> a -> n -> a (end node at second ‘a’)

4. Insert “band”:

   • Trie: b -> a -> n -> d (end node at ’d’)

5. Insert “bandage”:

   • Trie: b -> a -> n -> d -> a -> g -> e (end node at ‘e’)

After constructing the Trie, we can determine that “app” is a prefix of “apple”, so we will remove “app”. The remaining words are “banana”, “band”, and “bandage”.

Implementation Example

Here’s a Python implementation of the Trie approach:

class TrieNode:
    def __init__(self):
        self.children = {}
        self.is_end_of_word = False

class Trie:
    def __init__(self):
        self.root = TrieNode()

    def insert(self, word):
        node = self.root
        for char in word:
            if char not in node.children:
                node.children[char] = TrieNode()
            node = node.children[char]
        node.is_end_of_word = True

    def collect_words(self, node, prefix, results):
        if node.is_end_of_word:
            results.add(prefix)
        for char, child in node.children.items():
            self.collect_words(child, prefix + char, results)

def remove_prefix_words(words):
    trie = Trie()
    for word in words:
        trie.insert(word)

    results = set()
    trie.collect_words(trie.root, "", results)
    return results

words = ["apple", "app", "banana", "band", "bandage"]
print(remove_prefix_words(words))

This code builds a Trie from the provided words

Related Posts

• Leetcode 648 - Replace Words with Code