Problems - general notes

Question 1

Time complexity for this - https://leetcode.com/problems/longest-string-chain/

Answer 1

Time complexity: O(NSS)
(Substring generation)
Space: O(NS) (each word length matters in hash?)

Question 2

https://leetcode.com/problems/maximum-of-absolute-value-expression

Answer 2

Manhattan distance

Question 3

HashTable, HashMap, HashSet - what’s the difference?

Answer 3

Hash Table (CS) = HashMap (Java) = Dictionary (Python)
Hash Set (CS) = HashSet (Java) = Set (Python)

Question 4

What’s run length encoding in strings

Answer 4

https://www.geeksforgeeks.org/run-length-encoding/

Question 5

https://leetcode.com/problems/game-of-life - followup

Answer 5

open ended question

Question 6

Combination vs perumtation

Answer 6

Combination - order doesn’t matter. Perumation - order matters. HTH, HHT are two permutations, but just one H, H, T combination.

Question 7

Given n elements, choose c elements without repetition. Order doesn’t matter. What’s the formula?

Answer 7

n! / (n-c)! c!

Question 8

Amortized complexity - what is it?

Answer 8

https://leetcode.com/problems/binary-search-tree-iterator/discuss/52525/My-solutions-in-3-languages-with-Stack/53502
It’s averaged out complexity - especially if a datastructure retains state between multiple calls.

Question 9

Time complexity for sorting a list of words (or strings).

Answer 9

nm.log(n) (m is the avg length of word, n is the total no. of words)