Interview Prep Notes

TIL.md

1. Reading std C lib header contents from command line:

   echo "#include<string.h>" | cpp | grep "strstr" Displays strstr() function definition

2. Finding multiple char in a string, handle case where last char is unique

3. To find a number which occurs odd number of times from a list, make use of the XOR ‘^’ operator. The result will be the number which occurs for odd number of times.

   Example: 3 XOR 5 XOR 3 = 5

4. Number reversal in python can be done as: str(num)[::-1] => means that take all numbers, and stride is -1

5. Kadane's Algorithm for Finding max sum of subarray in O(n) time

6. DP:

   For any dynamic programming question, there are two ways to think about it:

   1. Top down approach (recursive+memoized)
   2. Bottom up DP - iterative approach

   Measuring the complexity: Approach 1: Time for Number of subproblems O(1) ~ for fibonacci, n O(1) = n

7. For longest common subsequence:

   Recursively: If last letter is same, then do 1 + lcs(a[m-1], b[n-1])

8. Perfectly balanced binary tree has

   i. Median at root (odd numbers of entries) ii. Median as average of middle two elements (even entries)

9. Bit manipulation:

   1. Logical shift - drop sign
   2. Arithmetic shift - keep sign
   3. Find ith bit - left shift 1 by i bits, and then 'and': x&(1<<i)
   4. Set ith bit - left shift 1 by i bits, and then 'or': x | (1<<i)
   5. Clear ith bit - left shift 1 by i bits, take 1's complement, then 'and': ~(i<<i) & x

10. Use string[i].isalnum() for checking if a char in the string is alpha numeric or not

11. If numbers are stored as strings in array:

    use a[i].isdigit() to check if number For negative numbers, we need to remove the '-' first: a[i].lstrip('-').isdigit*()

12. For finding difference in two strings, create dictionary with first string letter,

13. Use sets in python when want unique elements. Example: used in candy distribution

14. For finding the prime numbers, use Eratosthenes Sieve:

    def SieveOfEratosthenes(n):
     
     Create a boolean array "prime[0..n]" and initialize
     all entries it as true. A value in prime[i] will
     finally be false if i is Not a prime, else true.
     prime = [True for i in range(n+1)]
     p = 2
     while (p * p <= n):
     
         If prime[p] is not changed, then it is a prime
         if (prime[p] == True):
     
             Update all multiples of p
             for i in range(p * 2, n+1, p):
                 prime[i] = False
         p += 1

15. Difference to remember in Least Common Substring and Subsequence:

    Substring: continguous: 'aabbcd' - 'abbc'

    Subsequence: not continguous: 'aabbcd' - 'abd'

    Difference in matrices:

    Substring: if letters match - put diagonal+1

    if letters don't match, put 0

    Subsequence: if letters match - put diagonal+1

    if letters don't match, put max(top, left)

16. Python list splicing takes O(k) time, where k->len of spliced array

17. Use enumerate() instead of range(len(something)) when using indices multiple times

18. Conversion in python: format(num, "0b") -> binary, format(num, "0x") -> hex

19. Check if power of 2: simply take math.log(n,2) and see it is int. i.e: math.log(n,2) %1 == 0

20. For length of substring problems, use sliding window for O(n) complexity.

    Problems which can be solved with this:
    1. length of longest substring without repeating char

21. Quicksort's partition function can be used in many problems such as the dutch flag (red, white, blue) problem.

    def parition(pivot,a):
        i = -1
        j = 0
        while j <= pivot:
            if a[j] <= a[pivot]:
                swap(a[i+1],a[j])
                j += 1
                i += 1
            else:
                j += 1
     
    For the flag problem, there are 3 parts we want to divide into
    so modify partition function as follows:
     
    def modified_partition(a):
        low = 0
        mid = 0
        high = len(a)-1
        while mid <= high:
            if a[mid] == 1:
                mid += 1
            if a[mid] == 0:
                swap(a[low],a[mid])
                mid += 1
                low += 1
            if a[mid] == 2:
                swap(a[mid],a[high])
                high -= 1

22. For storing the value of each level in subarray during tree traversal, store (root, level) in q/stack

    Example:
    Binary Tree Level Order Traversal II Problem:
     
    def levelOrderBottom(self, root):
        """
        :type root: TreeNode
        :rtype: List[List[int]]
        """
     
        if not root:
            return []
        res = []
        q = list()
        level = 0
        q.append((root,level))
        self.bfs(q, res)
        return res[::-1]
     
    def bfs(self, q, res):
        while q:
            curr, level = q.pop(0)
            if level == len(res):
                res.append([])
            res[level].append(curr.val)
            if curr.left:
                q.append((curr.left, level+1))
            if curr.right:
                q.append((curr.right, level+1))
     
        return res