Quick Overview

Validate business records for required values, field length, prohibited description text, and name-to-nickname overlap while preserving input order.

Verify Business Records with Field and Name Rules

Company: Stripe

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Technical Screen

Implement `verifyBusinesses(records, requiredFields, lengthField, forbiddenPhrases, ignoredSuffixes)`. Apply the validation stages below and return one status line for each record that has a business name, preserving input order. ### Inputs and Output - `records` is a list of string-to-string maps. The designated fields are `business_name`, `description`, and `nickname`; other fields, such as `url`, may also be present. - `requiredFields` lists the fields that must have values. It includes `description` and `nickname`, and excludes `business_name`, which has its own skip rule. - `lengthField` names the field whose original value must contain between 5 and 32 characters, inclusive. It is either `business_name` or one of `requiredFields`. - `forbiddenPhrases` contains prohibited description substrings, including any prohibited single words or multiword phrases. - `ignoredSuffixes` contains normalized legal suffix words, such as `llc` or `inc`, to ignore at the end of a business name. Return strings of the form `"verified <business_name>"` or `"not verified <business_name>"`, replacing the placeholder with the record's original business-name value. ### Validation Rules 1. A missing field is treated as an empty string. A value is blank if it is empty or contains only ASCII spaces. Skip records with a blank `business_name`; they produce no output. 2. Every field in `requiredFields` must be nonblank. 3. Count every character in the original `lengthField` value, including spaces. Its length must be from 5 through 32. 4. The original `description` must not contain any string in `forbiddenPhrases`. This practice version uses case-sensitive literal substring matching, including spaces inside a phrase; it does not require word boundaries. 5. For the name-overlap check, split `business_name` and `nickname` into maximal runs of ASCII letters and digits, and lowercase those tokens. Repeatedly remove trailing business-name tokens listed in `ignoredSuffixes`. Do not remove suffix words from the middle of the name. 6. At least half of the remaining business-name token occurrences must appear as whole tokens in `nickname`. Each business-name occurrence counts separately, even if repeated; a matching nickname token can satisfy each occurrence of that word. A name with no remaining tokens fails this check. A record is verified only if it passes all checks after the skip rule. No additional URL, legal-identity, or business-validity check is part of this exercise. ### Constraints - There are at most 2,000 records, with at most 20 fields each. Values contain only printable ASCII characters and are at most 200 characters long. - Field names are nonempty and case-sensitive. `requiredFields` contains no duplicates. - There are at most 50 nonempty forbidden phrases, each at most 50 characters long. An empty phrase list imposes no description restriction. - There are at most 50 ignored suffixes. Each is a nonempty lowercase ASCII letter-or-digit token. An empty suffix list removes nothing. - An empty record list returns an empty list. ### Example 1 ```text records = [ {"business_name": " ", "url": "", "nickname": "", "description": ""}, {"business_name": "Acme Labs LLC", "url": "acme.test", "nickname": "Acme Labs", "description": "Software tools"}, {"business_name": "North Star Inc.", "url": "north.test", "nickname": "North", "description": "Payment tools"} ] requiredFields = ["url", "nickname", "description"] lengthField = "nickname" forbiddenPhrases = ["loan", "cash advance"] ignoredSuffixes = ["llc", "inc"] Output: ["verified Acme Labs LLC", "verified North Star Inc."] ``` The blank-name record is skipped. After removing `inc`, one of the two name tokens in the last record appears in its nickname, meeting the half-overlap requirement exactly. ### Example 2 ```text records = [ {"business_name": "Bright Oak LLC", "url": "bright.test", "nickname": "Bright", "description": "loan services"}, {"business_name": "Red Pine LLC", "url": "red.test", "nickname": "Green", "description": "Garden tools"}, {"business_name": "Blue Sky LLC", "url": "", "nickname": "Blue Sky", "description": "Travel tools"}, {"business_name": "Tiny Studio", "url": "tiny.test", "nickname": "Tiny", "description": "Design tools"} ] requiredFields = ["url", "nickname", "description"] lengthField = "nickname" forbiddenPhrases = ["loan", "cash advance"] ignoredSuffixes = ["llc", "inc"] Output: ["not verified Bright Oak LLC", "not verified Red Pine LLC", "not verified Blue Sky LLC", "not verified Tiny Studio"] ``` The records fail because of a forbidden description substring, insufficient name overlap, a blank required field, and a nickname shorter than five characters, respectively.

Overview: Validate business records for required values, field length, prohibited description text, and name-to-nickname overlap while preserving input order.

Read the full Stripe Software Engineer interview experience this question came from

Implement `verifyBusinesses(records, requiredFields, lengthField, forbiddenPhrases, ignoredSuffixes)`. Apply the validation stages below and return one status line for each record that has a business name, preserving input order. ### Inputs and Output - `records` is a list of string-to-string maps. The designated fields are `business_name`, `description`, and `nickname`; other fields, such as `url`, may also be present. - `requiredFields` lists the fields that must have values. It includes `description` and `nickname`, and excludes `business_name`, which has its own skip rule. - `lengthField` names the field whose original value must contain between 5 and 32 characters, inclusive. It is either `business_name` or one of `requiredFields`. - `forbiddenPhrases` contains prohibited description substrings, including any prohibited single words or multiword phrases. - `ignoredSuffixes` contains normalized legal suffix words, such as `llc` or `inc`, to ignore at the end of a business name. Return strings of the form `"verified <business_name>"` or `"not verified <business_name>"`, replacing the placeholder with the record's original business-name value. ### Validation Rules 1. A missing field is treated as an empty string. A value is blank if it is empty or contains only ASCII spaces. Skip records with a blank `business_name`; they produce no output. 2. Every field in `requiredFields` must be nonblank. 3. Count every character in the original `lengthField` value, including spaces. Its length must be from 5 through 32. 4. The original `description` must not contain any string in `forbiddenPhrases`. This practice version uses case-sensitive literal substring matching, including spaces inside a phrase; it does not require word boundaries. 5. For the name-overlap check, split `business_name` and `nickname` into maximal runs of ASCII letters and digits, and lowercase those tokens. Repeatedly remove trailing business-name tokens listed in `ignoredSuffixes`. Do not remove suffix words from the middle of the name. 6. At least half of the remaining business-name token occurrences must appear as whole tokens in `nickname`. Each business-name occurrence counts separately, even if repeated; a matching nickname token can satisfy each occurrence of that word. A name with no remaining tokens fails this check. A record is verified only if it passes all checks after the skip rule. No additional URL, legal-identity, or business-validity check is part of this exercise. ### Constraints - There are at most 2,000 records, with at most 20 fields each. Values contain only printable ASCII characters and are at most 200 characters long. - Field names are nonempty and case-sensitive. `requiredFields` contains no duplicates. - There are at most 50 nonempty forbidden phrases, each at most 50 characters long. An empty phrase list imposes no description restriction. - There are at most 50 ignored suffixes. Each is a nonempty lowercase ASCII letter-or-digit token. An empty suffix list removes nothing. - An empty record list returns an empty list. ### Example 1 ```text records = [ {"business_name": " ", "url": "", "nickname": "", "description": ""}, {"business_name": "Acme Labs LLC", "url": "acme.test", "nickname": "Acme Labs", "description": "Software tools"}, {"business_name": "North Star Inc.", "url": "north.test", "nickname": "North", "description": "Payment tools"} ] requiredFields = ["url", "nickname", "description"] lengthField = "nickname" forbiddenPhrases = ["loan", "cash advance"] ignoredSuffixes = ["llc", "inc"] Output: ["verified Acme Labs LLC", "verified North Star Inc."] ``` The blank-name record is skipped. After removing `inc`, one of the two name tokens in the last record appears in its nickname, meeting the half-overlap requirement exactly. ### Example 2 ```text records = [ {"business_name": "Bright Oak LLC", "url": "bright.test", "nickname": "Bright", "description": "loan services"}, {"business_name": "Red Pine LLC", "url": "red.test", "nickname": "Green", "description": "Garden tools"}, {"business_name": "Blue Sky LLC", "url": "", "nickname": "Blue Sky", "description": "Travel tools"}, {"business_name": "Tiny Studio", "url": "tiny.test", "nickname": "Tiny", "description": "Design tools"} ] requiredFields = ["url", "nickname", "description"] lengthField = "nickname" forbiddenPhrases = ["loan", "cash advance"] ignoredSuffixes = ["llc", "inc"] Output: ["not verified Bright Oak LLC", "not verified Red Pine LLC", "not verified Blue Sky LLC", "not verified Tiny Studio"] ``` The records fail because of a forbidden description substring, insufficient name overlap, a blank required field, and a nickname shorter than five characters, respectively.

Constraints

  • records has at most 2000 maps and each map has at most 20 fields; record values are printable ASCII strings of length at most 200.
  • Field names are nonempty and case-sensitive. requiredFields has no duplicates, includes description and nickname, and excludes business_name.
  • lengthField is business_name or a required field; its original untrimmed value must have length 5 through 32.
  • At most 50 nonempty forbidden phrases, each at most 50 characters long; at most 50 nonempty lowercase ASCII alphanumeric ignored suffixes.
  • Missing values are empty strings. Blank means empty or all ASCII spaces. Skip blank business names.
  • Forbidden description matching is case-sensitive literal substring matching. Remove only repeated trailing business-name suffix tokens.
  • At least half of the remaining business-name token occurrences must appear among nickname tokens, with repeated occurrences counted separately.
  • Emit exact status prefixes plus each original non-skipped business name in input order; perform no additional business or URL validation.

Examples

Input: ([{'business_name': ' ', 'url': '', 'nickname': '', 'description': ''}, {'business_name': 'Acme Labs LLC', 'url': 'acme.test', 'nickname': 'Acme Labs', 'description': 'Software tools'}, {'business_name': 'North Star Inc.', 'url': 'north.test', 'nickname': 'North', 'description': 'Payment tools'}], ['url', 'nickname', 'description'], 'nickname', ['loan', 'cash advance'], ['llc', 'inc'])

Expected Output: ['verified Acme Labs LLC', 'verified North Star Inc.']

Explanation: Published sample 1: omit the blank name and accept both records, including the exact half-overlap boundary.

Input: ([{'business_name': 'Bright Oak LLC', 'url': 'bright.test', 'nickname': 'Bright', 'description': 'loan services'}, {'business_name': 'Red Pine LLC', 'url': 'red.test', 'nickname': 'Green', 'description': 'Garden tools'}, {'business_name': 'Blue Sky LLC', 'url': '', 'nickname': 'Blue Sky', 'description': 'Travel tools'}, {'business_name': 'Tiny Studio', 'url': 'tiny.test', 'nickname': 'Tiny', 'description': 'Design tools'}], ['url', 'nickname', 'description'], 'nickname', ['loan', 'cash advance'], ['llc', 'inc'])

Expected Output: ['not verified Bright Oak LLC', 'not verified Red Pine LLC', 'not verified Blue Sky LLC', 'not verified Tiny Studio']

Explanation: Published sample 2: substring, overlap, required-field and length failures remain in original record order.

Community answers

Answer by bitsgoanpieces2018

#include using namespace std; class Solution { public: vector words(const string& s) { vector result; string current; for (char c : s) { bool isLetter = (c >= 'A' && c <= 'Z') || (c >= 'a' && c <= 'z'); bool isDigit = (c >= '0' && c <= '9'); if (isLetter || isDigit) { if (c >= 'A' && c <= 'Z') { c = c - 'A' + 'a'; } current += c; } else if (!current.empty()) { result.push_back(current); current.clear(); } } if (!current.empty()) { result.push_back(current); } return result; } bool isBlank(const string& s) { for (char c : s) { if (c != ' ') { return false; } } return true; } bool check1(map &m, vector& reqd) { for(string s: reqd) { string v = m[s]; // cout << v.length() <<" "; if(isBlank(v)) return false; } return true; } bool check2(map &m, string field) { string v = m[field]; if(v.length()<5 or v.length()>32) return false; return true; } bool check3(map& m, vector& forbidden) { string desc = m["description"]; for (const string& phrase : forbidden) { if (desc.find(phrase) != string::npos) { return false; } } return true; } vector toLowerCase(vector& v) { vector ans; string curr = ""; for(auto s: v) { curr = ""; for(char c: s) { if(c>='A' && c<='Z') c = (char)(c + 32); else if(c >= '0' and c<='9'); else if(c >= 'a' and c<='z'); else continue; curr += c; } ans.push_back(curr); } return ans; } vector removeSuffix(vector& v, vector & ignore) { unordered_map vis; for(auto s: ignore) vis[s] = 1; while(!v.empty() and vis[v.back()] == 1) { v.pop_back(); } return v; } bool check4(map

Loading coding console...

Show the approach

Approach

Process records in their original order. Read missing fields as empty strings and skip a record immediately when its business name is empty or contains only ASCII spaces. For every other record, test all configured required fields for nonblank values, check the original chosen length-field value against the inclusive 5-to-32 range, and reject any literal case-sensitive forbidden substring in the original description.

For a record still eligible, tokenize its business name and nickname into maximal ASCII alphanumeric runs and lowercase those runs. Store the ignored suffixes as a membership set and repeatedly remove only matching tokens from the end of the business-name list. Build a set of nickname tokens. Count business-name token occurrences whose value belongs to that set, without deduplicating the business-name list. Require a nonempty remaining list and twice the matching count to be at least its size.

Each early check is exactly one required predicate. The tokenizer forms precisely the runs stated in the contract; repeated removal stops at the first trailing token not in the suffix set, leaving middle occurrences untouched. Membership in the nickname set asks whether a whole token appears at least once, while iterating the business list preserves repeated occurrences. The integer inequality expresses the half-overlap threshold without rounding errors. Thus the status is verified exactly when every required check passes. Prefixing the untouched original name and appending only non-skipped records preserves spelling, punctuation, spacing and order.

Let N be the record count, F the required-field count, P the forbidden-phrase count, L <= 200 the maximum record-value length, and W <= 50 the maximum phrase length. A direct implementation takes O(N*(FL + PL*W + L)) string work in a conservative substring-search bound, plus field-name lookup/hashing/comparison costs. C++ map lookup additionally costs O(log D) comparisons for D <= 20 fields, and copies selected field values. Suffix and nickname hash lookups are expected constant-time aside from their string processing. Working storage is O(L + S) for tokens and suffix strings, where S is the total supplied suffix text; returned status strings occupy their required output space. The inputs are not mutated.

Time complexity:
O(N*(F*L + P*L*W + L)) conservative string work, plus field-name/map lookup costs and suffix-set construction; record values have L <= 200 and phrases have W <= 50.
Space complexity:
O(L + S) auxiliary token/suffix storage, plus returned status strings; S is total ignored-suffix text.