1. some questions about networking.
2. Algorithm question:
We have a string (lets call it main string), its format is like following:
a/b/c/... (where a,b,c could be a world and "a" is level 1, "b" is level 2 and etc.
Ex: animal/pet/dog
L1 L2 L3

we have a list of input strings with same structure. check which one if them is a match to the main string. we need to start checking from level 1.

animal/pet/dog/white -- is a match
animal/pet/cat -- is not a match
pet/animal/dog/ -- is not a match
animal/pet -- is not a match

3. Imagine you have the best algorithm for this problem (in term of time and memory complexity), how would you make it run even faster?

Question

1. some questions about networking.
2. Algorithm question:
We have a string (lets call it main string), its format is like following:
a/b/c/... (where a,b,c could be a world and "a" is level 1, "b" is level 2 and etc. 
Ex: animal/pet/dog
           L1          L2   L3   

we have a list of input strings with same structure. check which one if them is a match to the main string. we need to start checking from level 1. 

animal/pet/dog/white --> is a match
animal/pet/cat --> is not a match
pet/animal/dog/  --> is not a match
animal/pet --> is not a match

3. Imagine you have the best algorithm for this problem (in term of time and memory complexity), how would you make it run even faster?

Anonymous · Accepted Answer

Javascript Solution. TimeComplexity O(n) where n is the str.length * path.length. Memory Complexity O(n) where n is the number of non path matches

Memoization: Cache the paths thats have been matched so you wont need to do duplicate work

e.g
const cache = {
   "animal/pet/dog": ["animal/pet/dog/white", "animal/pet/dog/test"]
}

const dataPathMatch = (path, str) => {
  return (cache[path] && cache[path].includes(str)) || str.split(path)[0].length === 0
}

const path = 'animal/pet/dog'

dataPathMatch(path, 'animal/pet/dog/white') -> true
dataPathMatch(path, 'animal/pet/cat') -> false
dataPathMatch(path, 'pet/animal/dog/') -> false
dataPathMatch(path, 'animal/pet')  -> false

Anonymous · Answer

1. I answer those questions based on my knowledge.

2. Briefly, I said I would use a hash table to add main string words and their level into it (like pair ) and then I will iterate over input strings words and check if their words are in  the hash and if they have a same level like the main string.

Hash Table would be like:




Then I discussed the time and memory complexity of my idea.

3. I said since the input strings checking process is independent from each other, we can use multi-treading.

Solace

Solace interview question

Interview Answers

Want the inside scoop on your own company?

Bowls

Followed companies

Job searches