Coding Interview — Mauricio Saglietto

ESTCV Approach
- Write Examples and Clarify the Question
- Come up with Solutions
- Write down Test cases
- Write Code
- Verify code and test cases
Problems
- Given a matrix where 0 are water and 1 are island find how many islands there are
  - set count 0
  - Traverse the matrix
    - if 1
      - Check neighbours and mark them (ex -1)
        
        Use recursion to check neighbours neighbours
      - Add +1 to count
  - return count
- Given an array of number, replace each even number with 2 of the same
- GIven an array of number move all 0 to the end
- Reverse the order of elements in an array
- Two sum problem, find 2 numbers in a sorted array that sum to X
- Remove Islands
  - As more advance case of mark islands problems you have to remove the islands that are not connected to the border
  - to solve it you have to check all the 1 that are adjacent to a border and recursively check all the neighbour (make sure to not check twice the same island)
  - once you have all the 1 that belong to border island you have to go over the matrix again and see if the 1 is not in a border island just replace it by a 0
  - use a map to store the 1 that are part of an island
- Pair Sums
  - given an array get the amount of pairs that sum to a value
  - for that we create a map with the frequency since the values could be repeated
  - then we check the array if there is a value for the complement of value given and the actual value
  - if there is one we increment the count by the frequency
  - be careful to not overcount the values that are just half of the given sum
  - this way you are counting all pairs twice so return the half of it
Techniques
- Arrays / Strings
  - Traverse from Both Ends
  - Partitioning Arrays