Design a method to find how many times a given word appears in an article. Below is a clean, interview-friendly Java approach plus Big-O, trade-offs, and a takeaway you can reuse.
import java.util.Locale;
import java.util.regex.Matcher;
import java.util.regex.Pattern;
public class WordFrequency {
// Words with Unicode letters; allow inner apostrophes/hyphens
private static final Pattern WORD = Pattern.compile("[\\p{L}][\\p{L}\\p{M}'-]*");
public static int frequencyOfWord(String article, String target) {
if (article == null || target == null || target.isBlank()) return 0;
String needle = normalize(target);
Matcher m = WORD.matcher(article);
int count = 0;
while (m.find()) {
String w = normalize(m.group());
if (w.equals(needle)) count++;
}
return count;
}
// Normalize: lowercase + strip trailing possessive 's / ’s
private static String normalize(String s) {
String lower = s.toLowerCase(Locale.ROOT);
// Replace curly apostrophe with straight for uniformity
lower = lower.replace('’', '\'');
// Strip a single trailing possessive "'s"
if (lower.endsWith("'s")) {
lower = lower.substring(0, lower.length() - 2);
}
return lower;
}
public static void main(String[] args) {
String article = "Time, times, and timing—TIME! Time's up.";
System.out.println(frequencyOfWord(article, "time")); // -〉 3
}
}
⏱️ Complexity (Big-O)
▪️Single-query streaming (frequencyOfWord)
- Time: O(n) where n is the article length (scan once).
- Space: O(1) extra (ignores regex engine overhead; no token arrays).
▪️Multi-query with index (WordIndex)
- Build Time: O(n)
- Build Space: O(u) where u = number of unique words
- Query Time: O(1) average per word (hash map lookup)
✅ Takeaway
Choose the strategy by usage:
▪️One or few lookups? Stream once: O(n) time, O(1) extra space.
▪️Many lookups? Build an index once: O(n) build, then O(1) per query.
Always normalize consistently (case, apostrophes/hyphens), and prefer streaming or indexing over split() for large inputs.
#️⃣ #Java #CodingInterview #Algorithms #BigO #DataStructures #CleanCode #ProblemSolving #SoftwareEngineering
Matcher JavaDoc: https://lnkd.in/e97D3Hpz