KotaHemanthUC · January 8, 2025 03:37
diff --git a/tries.collection b/tries.collection
 Q1 : Given list of words and a string of numerals, output a list of words from the dict that could be reached by the given numbers as typed on a phone dialpad.

 Originally I though, hmm, words, maybe a trie. Then I realized there's no need, you can just hashmap. 
 The inteviewer actually seemed more junior than me, so she had me implement both? But I couldn't really think of 
 why the trie would be more efficient than hashmap. Either way storage is O(NK), creating the structure is O(NK) but 
 querying is O(1) for hashmap and O(N) for trie. She asked me why it's O(NK) storage for the trie implementation and 
 I said well we could either be exponential with respect to K or be lower bounded by NK, which seems better. 
 Did I miss something?

 Test1 : ["barb, "lane", "aasa"], "2272" -> ["barb", "aasa"]

 Q2 : Given a list of words and a string, find the first index at which every word in the list is written contiguously.

 Again I thought trie, that's still O(NK) for construction and O(NM) for querying because ostensbily you might need to start a trie at each step (can't greed, I can show counter example).

 But he asked what's the simple solution I said well we could do a greedy/dp sort of solution, at every letter attempt every word or go to next letter, and 
 ended up just coding that one (he came 15 minutes late to a 45 minute interview so honestly didn't really have time to do more).
 I made some notes to do memoization and the trie method but we didn't get there. Not sure I passed this one.

 Test2 : ["pot", "ato", "foo], "whats your atopotfoo?" -> 11

 Q3 : Undo/redo

 This is "straightforward" insofar as the algorithm portion, but I like it more as an example of IRL coding, because for 
 example if you delete an item in a list and undo it, you need to put it in the same place in the list.

 DSA-wise, you use a stack for undo, and a stack for redo. When you undo something, put it on the the redo stack and vice versa. 
 And when the user does any action add it to the undo stack and clear the redo stack.
	Q1 : Given list of words and a string of numerals, output a list of words from the dict that could be reached by the given numbers as typed on a phone dialpad.

	Originally I though, hmm, words, maybe a trie. Then I realized there's no need, you can just hashmap.
	The inteviewer actually seemed more junior than me, so she had me implement both? But I couldn't really think of
	why the trie would be more efficient than hashmap. Either way storage is O(NK), creating the structure is O(NK) but
	querying is O(1) for hashmap and O(N) for trie. She asked me why it's O(NK) storage for the trie implementation and
	I said well we could either be exponential with respect to K or be lower bounded by NK, which seems better.
	Did I miss something?

	Test1 : ["barb, "lane", "aasa"], "2272" -> ["barb", "aasa"]

	Q2 : Given a list of words and a string, find the first index at which every word in the list is written contiguously.

	Again I thought trie, that's still O(NK) for construction and O(NM) for querying because ostensbily you might need to start a trie at each step (can't greed, I can show counter example).

	But he asked what's the simple solution I said well we could do a greedy/dp sort of solution, at every letter attempt every word or go to next letter, and
	ended up just coding that one (he came 15 minutes late to a 45 minute interview so honestly didn't really have time to do more).
	I made some notes to do memoization and the trie method but we didn't get there. Not sure I passed this one.

	Test2 : ["pot", "ato", "foo], "whats your atopotfoo?" -> 11

	Q3 : Undo/redo

	This is "straightforward" insofar as the algorithm portion, but I like it more as an example of IRL coding, because for
	example if you delete an item in a list and undo it, you need to put it in the same place in the list.

	DSA-wise, you use a stack for undo, and a stack for redo. When you undo something, put it on the the redo stack and vice versa.
	And when the user does any action add it to the undo stack and clear the redo stack.
No results found