Coding Problems -Elementary

Github link for some of the problems:

DS_CodeProb

Fibonacci Series

numbers of the series is calculated as: 

    F(n) = F(n-1) + F(n-2) where:

      F(n) is the term number.
      F(n-1) is the previous term (n-1).
      F(n-2) is the term before that (n-2)

1. Problem: find nth number of Fibonacci series 

recursive function - time complexity: O(2n) and space complexity: O(n)

public int Fib(int num)
{  
        if(num<=0)return -1;

    if(num==1) return 0;
    if(num==2) return 1;
    return (fib(num-2) + fib(num-1);
}

optimized Fibonacci function using Memoization and Bottom-up Dynamic Programming

Time Complexity: $O(n)$

public int Fib(int n)

{

    if (n<=0) return -1;

    if (n==1) return 0;

    if(n==2) return 1;

    Dictionary<int, int> map = new Dictionary<int, int>();

    if(map.ContainsKey(n))

    {

        return map[n];

      }

    result = Fib(n-2) + Fib(n-1);

    map[n] = result;

    

   return result; 
}

2. Factorial problem with Big O(n)

 public static int Factorial(int n)

{

int result = 1;
if (n > 1)
for(int i=2; i<=n; i++)

{

result *= i;

}

return result; 

}

Transpose 2D Matrix 

  public int[,] TransposedMatix(int[,] matrix)

     {

      int rows = matrix.GetLength(0);

      int cols = matrix.GetLength(1);

      int[,] result = new int[cols, rows];

 

      for (int r = 0; r < rows; r++)

      {

          for (int c = 0; c < cols; c++)

          {

              result[c, r] = matrix[r, c];

          }

      }

      return result;

}

3. Find out Two numbers from a given array having sum as number (target) given   

public static int[] FindOut(int[] nums, int target)

{
    Dictionary<int, int> map = new Dictionary<int, int>();
    for (int i = 0; i < nums.Length; i++)
      {
                int complement = target - nums[i];
                if (map.ContainsKey(complement))
                {
                        //Return the subarray (pair of numbers)
                            return new int[] { complement, nums[i] };
                        //Return position of the numbers in the array
                            //return new int[] { map[complement], i };
                 }
              map[nums[i]] = i;
      }
    // Return an empty array if no solution is found
return new int[] { };
}

4. Is Anagram

(two loops solution - O(n2) - time complexity, while  sort string array and compare will reduce to O(nlogn), in case of using HashTable (dictionary in C#) will reduce to O(n)

 
public static bool IsAnagram(string str1, string str2)

{
    bool result = false;
    if (str1.Length != str2.Length)
    {
        return result;
    }
    for(int i=0;i<str1.Length;i++)
    {
        result = false;
        for (int j=0; j<str2.Length;j++)
        {
            if (str1[i] == str2[j])
            {
                result = true;
                break;
            }
        }
    }

    return result;
}