Implement substring search and weighted sampling

Q: Implement substring search and weighted sampling

This question evaluates algorithm design and analysis skills across string processing (efficient substring search) and randomized/data-structure techniques (weighted random sampling with update considerations), testing time/space complexity reasoning and probabilistic thinking for large-scale inputs.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

Loading...

Two coding questions were asked in the onsite.

Substring search : Given two strings text and pattern , return the starting index of the first occurrence of pattern in text , or -1 if pattern does not occur. Assume the input can be large enough that a purely naive O(n * m) scan may be too slow.
Weighted random picker : Design a class initialized with an array of positive integer weights. Implement a method pickIndex() that returns index i with probability weights[i] / sum(weights) . Follow-up: briefly discuss how the design would change if weights were updated frequently.

Implement substring search and weighted sampling

Quick Overview

Comments (0)