How do I practice coding and algorithm questions?

Use PracHub's coding console to write, test, and debug your solutions in Python or JavaScript. View hints, test against sample inputs, and compare with official solutions.

What difficulty level is this coding question?

This is a medium difficulty Coding & Algorithms question, commonly asked during Technical Screen rounds at Apple.

What role is this question designed for?

This question is commonly asked for Machine Learning Engineer candidates at Apple during technical interviews.

Implement bag-of-words similarity search from scratch

Quick Overview

This question evaluates knowledge and implementation skills in text processing, vector-space models, and information retrieval, covering tokenization, term-frequency and TF–IDF weighting, cosine similarity, and ranking for similarity search within the Coding & Algorithms domain.

Company: Apple

Role: Machine Learning Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement a bag-of-words–based text similarity search engine from scratch. Write code that: ( 1) tokenizes text (lowercasing, punctuation handling, Unicode support, and optional stopword removal/stemming—justify your choices), ( 2) builds document vectors using term frequency and supports TF–IDF weighting, ( 3) computes similarity scores (implement cosine similarity; optionally compare with Jaccard), and ( 4) returns the top-k most similar document IDs for a given query along with their scores. Clearly define each function’s purpose and inputs/outputs, and provide a short example demonstrating end-to-end usage. Analyze time and space complexity for indexing and querying, and briefly discuss how you would scale to large corpora (e.g., inverted index, pruning, or approximate search).

Quick Answer: This question evaluates knowledge and implementation skills in text processing, vector-space models, and information retrieval, covering tokenization, term-frequency and TF–IDF weighting, cosine similarity, and ranking for similarity search within the Coding & Algorithms domain.

Part 1: Unicode Text Tokenization with Optional Stopword Removal and Stemming

Implement a tokenizer for bag-of-words processing. Given a text string, return a list of tokens after Unicode-aware lowercasing, punctuation handling, optional stopword removal, and optional simple stemming. Use Python's Unicode-aware string behavior: a character is part of a token if ch.isalnum() is true; all other characters, including punctuation, spaces, emoji, and symbols, split tokens. Use casefold() instead of lower() for better Unicode lowercasing. Stopwords are removed after casefolding and before stemming. If stemming is enabled, apply this intentionally simple suffix stemmer: remove 'ing' when token length is greater than 4, else remove 'ed' when length is greater than 3, else remove trailing 's' when length is greater than 3. This is not a production linguistic stemmer, but it is deterministic and sufficient for this exercise.

Constraints

0 <= len(text) <= 100000
stopwords is None or contains at most 10000 strings
Tokens consist of consecutive Unicode alphanumeric characters as determined by str.isalnum()
Stemming uses only the simple suffix rules defined in the statement

Examples

Input: ('Hello, WORLD! It\'s 2024.', None, False)

Expected Output: ['hello', 'world', 'it', 's', '2024']

Explanation: Punctuation splits tokens, casefolding lowercases words, and digits are kept.

Input: ('Café naïve — 東京! 😊', [], False)

Expected Output: ['café', 'naïve', '東京']

Explanation: Accented Latin letters and Japanese characters are Unicode alphanumeric; punctuation and emoji split or are ignored.

Hints

Build tokens by scanning characters one by one; when you see a non-alphanumeric character, finish the current token.
Use casefold() instead of lower() to handle more Unicode casing rules.

Part 2: Build Term-Frequency and TF-IDF Document Vectors

Given tokenized documents, build sparse bag-of-words vectors. Each document is represented by a dictionary from term to weight. If use_tfidf is false, each weight is the raw term frequency in that document. If use_tfidf is true, each weight is TF multiplied by smoothed IDF: idf(term) = ln((N + 1) / (df(term) + 1)) + 1, where N is the total number of documents, including empty documents, and df(term) is the number of documents containing the term at least once. Round TF-IDF weights to 6 decimal places for deterministic output.

Constraints

0 <= len(doc_ids) == len(documents) <= 10000
Each doc_id is unique
Each token is a non-empty string
Total number of tokens across all documents <= 200000
TF-IDF values must be rounded to 6 decimal places

Examples

Input: (['d1', 'd2'], [['apple', 'banana', 'apple'], ['banana', 'carrot']], False)

Expected Output: {'d1': {'apple': 2, 'banana': 1}, 'd2': {'banana': 1, 'carrot': 1}}

Explanation: With raw term frequency, weights are just counts within each document.

Input: (['d1', 'd2'], [['apple', 'banana', 'apple'], ['banana', 'carrot']], True)

Expected Output: {'d1': {'apple': 2.81093, 'banana': 1.0}, 'd2': {'banana': 1.0, 'carrot': 1.405465}}

Explanation: For N=2, apple and carrot appear in one document, so their IDF is ln(3/2)+1 = 1.405465. Banana appears in both documents, so its IDF is 1.

Hints

First count term frequencies per document, then compute document frequency from the set of terms in each document.
Keep vectors sparse: do not store terms with frequency 0.

Part 3: Compute Cosine or Jaccard Similarity Between Sparse Vectors

Implement similarity scoring for two sparse bag-of-words vectors. Each vector is a dictionary from term to numeric weight. If metric is 'cosine', compute cosine similarity: dot(a,b) / (||a|| * ||b||). If either vector has zero norm, return 0.0. If metric is 'jaccard', ignore weights except that zero-weight terms are excluded, and compute set Jaccard similarity: |terms(a) intersect terms(b)| / |terms(a) union terms(b)|. If both sets are empty, return 0.0. Round the returned similarity to 6 decimal places.

Constraints

0 <= len(vector_a), len(vector_b) <= 100000
Term keys are strings
Weights are finite numbers
metric is either 'cosine' or 'jaccard'

Examples

Input: ({'apple': 2, 'banana': 1}, {'apple': 1, 'carrot': 1}, 'cosine')

Expected Output: 0.632456

Explanation: The dot product is 2, and the norms are sqrt(5) and sqrt(2), so the cosine is 2/sqrt(10).

Input: ({'apple': 2, 'banana': 1}, {'apple': 1, 'carrot': 1}, 'jaccard')

Expected Output: 0.333333

Explanation: The nonzero term sets share only apple; the union has 3 terms.

Hints

For cosine similarity, compute the dot product by iterating over the smaller dictionary and looking up matching terms in the larger one.
For Jaccard similarity, convert nonzero-weight keys to sets and compare overlap with union size.

Part 4: Return Top-K Similar Documents for a Tokenized Query

Build a small TF-IDF similarity search over tokenized documents and return the top-k most similar document IDs for a tokenized query. Use the same smoothed IDF formula as in Part 2: idf(term) = ln((N + 1) / (df(term) + 1)) + 1. Use raw term frequency times IDF for both document vectors and the query vector. Ignore query terms that do not appear in the corpus vocabulary. Score each document with cosine similarity. Return only documents with positive similarity, sorted by descending score; break ties by lexicographically smaller doc_id. Round scores to 6 decimal places in the output.

Constraints

0 <= len(doc_ids) == len(documents) <= 10000
Each doc_id is unique and comparable as a string
Total number of tokens across all documents <= 200000
0 <= len(query_tokens) <= 10000
0 <= k <= len(doc_ids)
Scores are rounded to 6 decimal places

Examples

Input: (['d1', 'd2', 'd3'], [['apple', 'banana', 'apple'], ['banana', 'carrot'], ['apple', 'carrot', 'carrot']], ['apple', 'banana'], 2)

Expected Output: [['d1', 0.948683], ['d2', 0.5]]

Explanation: All three terms have the same IDF. d1 best matches both query terms, d2 matches banana, and d3 matches apple with a lower cosine score. Only top 2 are returned.

Input: (['b', 'a', 'c'], [['x'], ['x'], ['y']], ['x'], 5)

Expected Output: [['a', 1.0], ['b', 1.0]]

Explanation: Documents a and b tie with score 1.0, so lexicographic doc_id order puts a before b. Document c has zero similarity and is omitted.

Hints

After computing IDF from the corpus, vectorize the query using the same IDF values as the documents.
A scalable version would use an inverted index so that only documents containing query terms need to be scored.

Quick Overview