---
# System prepended metadata

title: 'Homework 15 February, 2022'

---

# Homework 15 February, 2022

## Focus on previous days' unsolved problems first.

1. **Minimum Passes of Matrix:**
    You are given an 2D array(matrix) of integers of potentially unequal height and width. Write a program that calculates minimum number of passes required to convert all negative integers in the matrix to positive integers. Note: We don't consider `0` either positive or negative.
    
    **Rule:** A negative integer can only be converted to positive if it's adjacent(left,right,top,bottom, BUT NOT diagonal) to a positive element.
    
    Regardless of how many passes are run, if there is any negative integer that can't be converted to positive, program should output `-1`.
    
    **Input and Output:**
    
    1.
    ```php
    [
        [0, -1, -3, 2, 0],
        [1, -2, -5, -1, -3],
        [3, 0, 0, -4, -1]
    ]
    ```
    ```
    3
    ```
    2.
    ```php
    [
        [1, 0, 0, -2, -3],
        [-4, -5, -6, -2, -1],
        [0, 0, 0, 0, -1],
        [-1, 0, 3, 0, 3]
    ]
    ```
    ```
    -1
    ```
    3.
    ```php
    [
        [-2, -3, -4, -1, -9],
        [-4, -3, -4, -1, -2],
        [-6, -7, -2, -1, -1],
        [0, 0, 0, 0, -3],
        [1, -2, -3, -6, -1]
    ]
    ```
    ```
    12
    ```

2. **Cycle In Graph:**
    You are given an Adjacency List of a **unweighted** and **directed** graph. In the given list, each index `i` in the list contains vertex(node) `i`'s ***outbound*** edges. Each edge is represented by a integer that signifies an index (a destination vertex) in the list that this vertex is connected to.
    
    Write a program to output a boolean showing if the graph contains a cycle. (There can be self cycle).  
    
    Hint: Start a DFS tree, if you encounter a edge going to an Ancestor Node, then cycle is detected and program completes.

    **Input and Output:**

    1.
    ```php
    [
        [1, 3],
        [2, 3, 4],
        [0],
        [],
        [2, 5],
        []
    ]
    ```
    ```
    true
    ```
    2.
    ```php
    [
        [1],
        [2, 3, 4, 5, 6, 7],
        [],
        [2, 7],
        [5],
        [],
        [4],
        []
    ]
    ```
    ```
    false
    ```
    3.
    ```php
    [
        [0]
    ]
    ```
    ```
    true
    ```


3. **Levenshtein Distance:**
    Definition: the Levenshtein distance between two words is the minimum number of single-character edits (insertion, deletion or substitution) required to change one word into the other.
    
            
    **Input (string one, string two) and Output:**
    - `abc` `yabd` `2`
    - `abc` `abc` `0`
    - `biting` `mitten` `4`
