## Problem Given a list of strings, count the number of pairs `(i, j)` where `i int: ... ``` ``` Input: words = ["abc", "de", "fg", "abcd"] Pairs: ("abc","de"): no overlap -> count ("abc","fg"): no overlap -> count ("abc","abcd"): overlap 'a','b','c' -> skip ("de","fg"): no overlap -> count ("de","abcd"): overlap 'd' -> skip ("fg","abcd"): overlap -> skip Output: 3 ``` ## Follow-ups 1. Represent each word as a bitmask of 26 bits (one per letter). How does this make the disjoint check O(1)? 2. With the bitmask approach, what is the overall time complexity? How does it compare to using a set intersection? 3. Can two different words share the same bitmask? Give an example. Does this cause any issue for your algorithm? 4. Extend: count pairs where the two strings share exactly one common character. How does your bitmask approach need to change?

InterviewDB Question

Disjoint String Pairs: Count Pairs of Strings with No Shared Characters

phone

Question Details

Problem Given a list of strings, count the number of pairs (i, j) where i < j and the two strings share no common characters. Follow-ups Represent each word as a bitmask of 26 bits (one per letter). How does this make the disjoint check O(1)? With th…

Full Details

🔒

Unlock full leaked content

Full insider details, leaked discussions, and candidate experiences.

Get Premium →

Topics

Coding Onsite Phone Strings

More from Netflix

1p3a Netflix Software Engineer Screening Question Device Notification Timing Reddit Need a reality check for frontend assignment expetations Reddit Get Into FAANG with Me | Day 2: Design Netflix 1p3a Netflix Software Engineer Fulltime Tech Phone Screen Experience 1p3a Movie History Friends II

← All Netflix questions Netflix Software Engineer Questions → All Strings Questions →