mock interview discussion

Mock interview discussion

Discussion - 
Given a set of strings, e.g. {“one”, “cat”, “two”, “four”}, 
and a target string, e.g. “fouroneone”, return true if the target string is composed of elements from the set. 	

“onecat” -> true
“fouron” -> false
“twone” -> false

one, cat, two, four

a target string fouroneone
target string is composed of elementes from the set

n^2, each string in the set, if string is in substring of target strong 
n - hashset, each element -> target string -> substring -> O(n^2)
fouroneone -> n^2

substring - start/ end, start index from 0 to n - 1, end startIndex to n - 1, total O(n^2)


start index 0, 1, 2, 3, 4, 5, 6, 7, 8, 9
start index -> 0 , n options 
when to end
f
fo
fou
four
four
fouro
fouron
fourone
fouroneo
fouroneon
fouroneone

substring total O(n^2)

brute force -> 

four-> one-> one 

build all string in set to a trie

 four, one, cat,
 two

trie -> 

f
o
u
r

o
n
e \ 

o

build trie -> O(chars in words) -> build trie time complexity

O(m)  - target words

O((m + chars in set) )

Trie -> look -> set 

class Trie
{
  char node[26]; 
  Trie children; 
  bool isWord; // false
}

public static Trie buildTrie(HashSet,)

public static bool checkTarget(string)
public static bool isInTrie(string target, Trie trie) // Assume this function works properly...don't impelment it...jsut foucus how you pass
//string to this function
{
   if(target == null)
   return false;
   
   for(int i = 0; i < length; i++)
   {
     var current = target[i]; 
     
   }
}

// Assume you have implemented trie with given input...now implement remaining algorithm


end dog -> valid words

input to check
endog  -> end ->o -> return false
enddog -> end -> dog ->return true