C# Coding Interview

interview_questions.sh

# ==============================================================================
# 1 - C# program to determine if any two integers in array sum to given integer
# ==============================================================================
dotnet new console -n arrayprograms

echo 'using System;
 
namespace CodingAlgorithm {
  sealed class Algorithm {
    //Brute force solution, O(n^2) time complexity
    public static bool TwoIntegersSumToTarget(int[] arr, int target) {
      int numElements = arr.Length;

      for (int outer = 0; outer < numElements; outer++) {
        for (int inner = 0; inner < numElements; inner++) {
          if (outer != inner) {
            int sum = arr[outer] + arr[inner];
            if (sum == target) return true;
          }
        }
      }
      return false;
    }
  }

  class Program {
    static void Main(string[] args) {
      Console.WriteLine(@"Given an integer and an array of integers determine
          whether any two integers in the array sum to that integer.");
      int[] arr = new int[4] { 2, 5, 66, 8 };
      
      bool result = Algorithm.TwoIntegersSumToTarget(arr, 10);
      Console.WriteLine($"Result:  {result}");
    }
  }
}' >> arrayprograms/Practice.cs

cd arrayprograms && dotnet run

# ==============================================================================
# 2 - Write a method to sort the elements of an array in descending order.
# ==============================================================================
rm arrayprograms/Practice.cs
dotnet new console -n arrayprograms

echo 'using System;
 
namespace CodingAlgorithm {
  sealed class Algorithm {
    public static int[] SortDesc(int[] arr) {
      Sort(ref arr);
      Reverse(ref arr);

      return arr;
    }

    public static void Sort(ref int[] arr) {
      var numElements = arr.Length;

      for (int outer = 1; outer <= numElements-1; ++outer) {
        for (int inner = 0; inner < numElements-1; ++inner) {
          if (arr[inner] > arr[inner + 1]) {
            Swap(ref arr[inner], ref arr[inner + 1]);
          }
        }
      }
    }

    private static void Reverse(ref int[] arr) {
      for(int i=0; i<arr.Length/2; i++){
        Swap(ref arr[i], ref arr[arr.Length-1-i]);
      }
    }

    private static void Swap(ref int x, ref int y){
      int temp = x;
      x = y;
      y = temp;
    }
  }

  class Program {
    static void Main(string[] args) {
      Console.WriteLine("Write a method to sort the elements of an array in descending order.");
      int[] arr = new int[4] { 5, 2, 66, 8 };
      
      var result = Algorithm.SortDesc(arr);
      Console.WriteLine("Result:  " + string.Join(",", result));
    }
  }
}' >> arrayprograms/Practice.cs

cd arrayprograms && dotnet run

# ==============================================================================
# 3 - Find majority element in an unsorted array.
# ==============================================================================
rm arrayprograms/Practice.cs
dotnet new console -n arrayprograms

echo 'using System;
using System.Collections.Generic;
 
namespace CodingAlgorithm {
  sealed class Algorithm {
    // Ex. {1,2,3,4,5,2,2,2,2}, 2 is the majority element because it 
    // accounts for more than 50% of the array.
    public static int GetMajorityElement(params int[] arr)  {
      Dictionary<int, int> d = new Dictionary<int, int>();
      int majority = arr.Length / 2;

      //Stores the number of occcurences of each item in the passed array in a dictionary
      foreach (int i in arr) {
        if (d.ContainsKey(i)) {
          d[i]++;
          //Checks if element just added is the majority element
          if (d[i] > majority) return i;
        } else { d.Add(i, 1); }
      }
      throw new Exception("No majority element in array");
    }
  }

  class Program {
    static void Main(string[] args) {
      Console.WriteLine("Find majority element in an unsorted array.");
      int[] arr = new int[7] { 2, 8, 8, 2, 66, 8, 8 };
      
      int result = Algorithm.GetMajorityElement(arr);
      Console.WriteLine($"Result:  {result}");
    }
  }
}' >> arrayprograms/Practice.cs

cd arrayprograms && dotnet run

# ==============================================================================
# 4 - Sort 2 merged arrays
# ==============================================================================
rm arrayprograms/Practice.cs
dotnet new console -n arrayprograms

echo 'using System;
using System.Collections.Generic;
 
namespace CodingAlgorithm {
  sealed class Algorithm {
    // x array is assumed to be the length of x + y, and lastX is 
    // the position of the last stored element in x array
    public static int[] MergeSortedArrays(int[] arr1, int[] arr2) {
      var combined = new int[arr1.Length + arr2.Length];
      
      Array.Copy(arr1, combined, arr1.Length); 
      Array.Copy(arr2, 0, combined, arr1.Length, arr2.Length);

      return Sort(combined);
    }
    
    private static int[] Sort(int[] arr) {
      var numElements = arr.Length;

      for (int outer = 1; outer <= numElements - 1; ++outer) {
        for (int inner = 0; inner < numElements - 1; ++inner) {
          if (arr[inner] > arr[inner + 1]) {
            Swap(ref arr[inner], ref arr[inner + 1]);
          }
        }
      }
      return arr;
    }

    private static void Swap(ref int x, ref int y){
      int temp = x;
      x = y;
      y = temp;
    }
  }

  class Program {
    static void Main(string[] args) {
      Console.WriteLine("You are given two sorted arrays, A and B, where A " +
        "has a large enough buffer at the end to hold B.  Write a method to " +
        "merge B into A in sorted order..");
      var arr1 = new int[5] { 3, 4, 5, 0, 0 };
      var arr2 = new int[2] { 1, 2 };
      
      var result = Algorithm.MergeSortedArrays(arr1, arr2);
      Console.WriteLine($"Result:  {string.Join(",", result)}");
    }
  }
}' >> arrayprograms/Practice.cs

cd arrayprograms && dotnet run

# ==============================================================================
# 5 - Merge 0s to end
# ==============================================================================
rm arrayprograms/Practice.cs
dotnet new console -n arrayprograms

echo 'using System;
 
namespace CodingAlgorithm {
  // For example, given nums = [0, 1, 0, 3, 12], after calling your function, 
  // nums should be [1, 3, 12, 0, 0].
  // You should do this in-place without making a copy of the array.
  sealed class Algorithm {
    public static int[] MoveZeros(params int[] x) {
      for (int i = 0; i < x.Length; i++) {
        if (x[i] == 0) MoveZeroToEnd(x, i);
      }    
      return x;        
    }
    private static void MoveZeroToEnd(int[] x, int index) {
      for (int i = index; i < x.Length - 1; i++) {
        Swap(ref x[i], ref x[i+1]);
      }
    }
    private static void Swap(ref int x, ref int y){
      int temp = x;
      x = y;
      y = temp;
    }      
  }

  class Program {
    static void Main(string[] args) {
      Console.WriteLine(@"Given an array nums, write a function to move all
          0s to the end of it while maintaining the relative order of
          the non-zero elements.");

      int[] arr = new int[6] { 0, 3, 4, 0, 5, 2 };
      
      int[] result = Algorithm.MoveZeros(arr);
      Console.WriteLine($"Result:  {string.Join(",", result)}");
    }
  }
}' >> arrayprograms/Practice.cs

cd arrayprograms && dotnet run

# ==============================================================================
# 6 - Check for duplicate number
# ==============================================================================
rm arrayprograms/Practice.cs
dotnet new console -n arrayprograms

echo 'using System;
using System.Collections.Generic;

namespace CodingAlgorithm {
  sealed class Algorithm {
    public static bool ContainsDuplicates(params int[] arr) {
      Dictionary<int, int> d = new Dictionary<int, int>();
      foreach (int i in arr) {
        if (d.ContainsKey(i)) return true;
        else d.Add(i, 1);
      }
      return false;
    }
  }

  class Program {
    static void Main(string[] args) {
      Console.WriteLine(@"Given an array of integers, find if the
          array contains any duplicates. Your function should
          return true if any value appears at least twice in
          the array, and it should return false if every element is distinct.");

      int[] arr = new int[6] { 0, 3, 4, 0, 5, 2 };
      
      bool result = Algorithm.ContainsDuplicates(arr);
      Console.WriteLine($"Result:  {result}");
    }
  }
}' >> arrayprograms/Practice.cs

cd arrayprograms && dotnet run

# ==============================================================================
# 7 - Binary Search
# ==============================================================================
rm arrayprograms/Practice.cs
dotnet new console -n arrayprograms

echo 'using System;

namespace CodingAlgorithm {
  sealed class Algorithm {
    public static bool BinarySearch(int[] arr, int target) {
      int upperBound = arr.Length;
      int lowerBound = 0;

      Sort(ref arr);

      while (lowerBound <= upperBound) {
        int mid = (int)Math.Floor((decimal)(lowerBound + upperBound) / 2);
        if (arr[mid] < target) {
          lowerBound = mid + 1;
        } else if (arr[mid] > target) {
          upperBound = mid - 1;
        } else { return true; }
      }
      return false;
    }
    private static void Sort(ref int[] x){
      int numElements = x.Length;
      for(int outer = 1; outer <= numElements-1; ++outer){
        for(int inner = 0; inner < numElements-1; ++inner){
          if(x[inner] > x[inner+1]){
            Swap(ref x[inner], ref x[inner+1]);
          }
        }
      }
    }
    private static void Swap(ref int x, ref int y){
      int temp = x;
      x = y;
      y = temp;
    }
  }
  public class Program {
    static void Main(string[] args){
      Console.WriteLine("Repeatedly divide half of the array we find the target value.");
      
      int[] arr = new int[5] { 8, 99, 7, 14, 9};
      bool result = Algorithm.BinarySearch(arr, 9);
      Console.WriteLine($"Result:  {string.Join(",", result)}");
    }
  }
}' >> arrayprograms/Practice.cs

cd arrayprograms && dotnet run

# ==============================================================================
# 8 - Check which numbers are prime numbers
# ==============================================================================
rm arrayprograms/Practice.cs
dotnet new console -n arrayprograms

echo 'using System;
using System.Linq;

namespace CodingAlgorithm {
  sealed class Algorithm {
    // A prime number is a number greater than 1 that cannot be 
    // formed by multiplying two smaller numbers.
    public static int[] CheckForPrimes(int[] arr) {
      foreach(int n in arr) {
        if (n != 2) {
          if (n <= 1 || n % 2 == 0) RemoveFromArray(ref arr, n);
        }

        int boundary = (int)Math.Floor(Math.Sqrt(n));

        for (int i = 3; i <= boundary; i+=2) {
          if (n % i == 0) RemoveFromArray(ref arr, n);
        }
      }
      return arr;
    }
    private static void RemoveFromArray(ref int[] x, int target){
      x = x.Where(val => val != target).ToArray();
    }
  }
  public class Program {
    static void Main(string[] args){
      Console.WriteLine("Check which numbers in a given array are prime numbers");

      int[] arr = new int[11] { 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 };
      int[] result = Algorithm.CheckForPrimes(arr);
      Console.WriteLine($"Result:  {string.Join(",", result)}");
    }
  }
}' >> arrayprograms/Practice.cs

cd arrayprograms && dotnet run

# ==============================================================================
# 9 - Quick sort
# ==============================================================================
rm arrayprograms/Practice.cs
dotnet new console -n arrayprograms

echo 'using System;

namespace codinginterview {
  sealed class Algorithm{
    // Divide a given arrays elements into two partitions based on a pivot point. 
    // Then, recursively call itself to sort the two partions. 
    public static int[] QuickSort(int[] arr, int low, int high){
      int pivot_location = 0;

      if (low < high) {
        pivot_location = Partition(arr, low, high);
        
        // recursively list both sub lists, those less than the pivot & more than the pivot
        QuickSort(arr, low, pivot_location - 1);
        QuickSort(arr, pivot_location + 1, high);
      }
      return arr;
    }
    private static int Partition(int[] arr, int low, int high) {
      int pivot = arr[high];
      int i = low - 1;
      
      //elements less than the pivot are moved to before the pivot
      for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
          i++;
          Swap(ref arr[i], ref arr[j]);
        }
      }
      
      //elements greater than pivot are moved to after the pivot
      Swap(ref arr[i + 1], ref arr[high]);
      return i + 1;
    }
    private static void Swap(ref int x, ref int y){
      int temp = x;
      x = y;
      y = temp;
    }
  }
  public class Program {
    static void Main(string[] args){
      Console.WriteLine("Quicksort on a given pivot.");

      int[] arr = new int[5] { 45, 2, 66, 1, 72};
      int[] result  = Algorithm.QuickSort(arr,arr.Length-3,arr.Length-1);
      Console.WriteLine($"Result:  {string.Join(",", result)}");
    }
  }
}' >> arrayprograms/Practice.cs

cd arrayprograms && dotnet run