1

I have a class and method

class Dictionary {
    public Dictionary(List<String> dic) {
        // ...
    }
    
    public int getCount(String substr) {
        // ...
    }
}

What should occur:
in method getCount you need to use list from constructor of the class and find all strings which starts on substring substr

I use this solution on my interview

return (int) this.dic.stream().filter(s -> s.startsWith(substr)).count();

Complexity is O(n)

Are there better solutions?

Thank you!

Eugene Shevchugov
  • 77
  • 5
  • You could sort the list, then stop searching once you hit an item that doesn't start with your search term (only after you've found one, though). You could make a hash and group stuff by starting letters, then only look in the bucket for that letter. Either way, if this is not just for school, profile before trying to optimize. – Robert Nov 19 '20 at 16:26
  • 2
    Your solution seems fine the way you have constructed the problem. But normally, a dictionary isn't just a List, it's a sorted List if that's the case, then you could use a modified binary search to find the first substring that matches, and then interate from there until finding the last. After finding the last, you can return - no other entries will match – ControlAltDel Nov 19 '20 at 16:26
  • 1
    @pshemo when suggesting users post on CR it would be great if there was also a suggestion like "_Please read the relevant help center pages like '[What topics can I ask about here?](https://codereview.stackexchange.com/help/on-topic)' and '[How do I ask a good question?](https://codereview.stackexchange.com/help/how-to-ask)_". In the current form the code above would likely be closed as off-topic because the methods are stubs... which happens **all too often** – Sᴀᴍ Onᴇᴌᴀ Nov 19 '20 at 16:28
  • @SᴀᴍOnᴇᴌᴀ Thanks for guidance. Removed my comment since as you claim question (in current form) doesn't fulfill CR requirements. – Pshemo Nov 19 '20 at 16:31

0 Answers0