dunjen_master's blog

Hiring test question — Suffix Matching !
By dunjen_master, history, 4 years ago, In English

I am attaching a picture about the question. Kindly refer to the picture.

  • Vote: I like it
  • +4
  • Vote: I do not like it

Comments Comments (10)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Sample test cases?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You didn't tell us whether the test is finished or not. We shouldn't help you if the test is not finished yet.

→ Reply
»
4 years ago, # |
← Rev. 4   Vote: I like it +3 Vote: I do not like it

Reverse all strings, so task becomes about prefix instead of suffix. Create segment tree, where each node have a trie that contains all strings from this node's corresponding segment (each string will be in $$$log~n$$$ tries, so memory will be $$$23 \cdot n~log~n$$$). With trie it's easy to count necessary sum of all string nested in this trie in $$$O(23)$$$, so overall query's complexity will be $$$O(23 \cdot log~n)$$$.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    You can do it with a single trie

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you please explain

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        Basically what you and lemelisk said in the comment below, I'm not sure if it's better, just seems slightly easier to implement

        → Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

create a trie with reversed strings and store indices of strings in each node in sorted order then query for reversed string, you can find out for each each prefix of reversed string how many strings from given range match this prefix

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +6 Vote: I do not like it

    For updates you will need to store indices in BSTs that supports query "how many elements is smaller than given value". But that a nice alternative to segment tree's solution and it even has lower memory consumption complexity.

    → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

I solved it using map and policy based data structure My solution

→ Reply