Software Engineer III Interview Questions in Melbourne, Australia | Glassdoor

Software Engineer III Interview Questions in Melbourne, Australia

1

Software engineer iii interview questions shared by candidates

Top Interview Questions

Sort: RelevancePopular Date

- How to determine if a given string is a combination of words in the dictionary. The given string does not have space at all. - Very complex questions about big O and improve algorithms

2 Answers

1st question) It's quite unclear what defines "combination of words", ie headset is a complete combination, however pulliehanger (just made up) is not a complete combination. Solution 1) Assuming dictionary is a hashset, we can simply iterate through the length of the string and check if that string exists in hash set. If it does we can recursively check the remaining string. It's expensive to store hashset and the algorithm takes 2^n. Solution 2) We can use trie data structure so that storage complexity would be lowered. The rest would be the similar as above (we iterate through and check every possibility with trie) How do we eliminate 2^n algorithm? Well, it's fairly simple. We can do a n^2 algorithm by simply trying every possibility of words, regardless of them being overlapped. Then we store these words' indices in a order kept list (such as linked array list in java), so that we would have a list where it is sorted by the first index. Then we check whether 2 of these elements in this list do not overlap by simply looking at the first and the last element in a constant (1) time, assuming that the question is asking not complete combinations. If the question is asking about whether it's a complete combination, then we would keep the elements that start with index 0 separately and use a dynamic programming with the rest where we fill indexes fit into next index table and try to match with the index 0 elements, which would take m^2 time.

its not n^2 to try all words