Monday, 8 February 2016

Suman microsoft arrays

Problem 1 
 Count frequencies of all elements in array Given an unsorted array of n integers which can contain integers from 1 to n. Some  elements can be repeated multiple times and some other elements can be absent from the array.   Count frequency of all elements that are present and print the missing elements.   
Solution : A Simple Solution is to create a count array of size n as the elements are in range from 1 to n.  This solution works in O(n) time, but requires O(n) extra space.   
In Below solution we are not taking any extra space but it requires more processing          /// </summary>          public static void CountFrequency()          {              int[] arr = { 4, 4, 4, 4 };              int n = 4;               // minus one value from each elements              for (int j = 0; j < n; j++)              {                  arr[j] = arr[j] - 1;              }               // take the mod of each elements it would be the element number              for (int i = 0; i < n; i++)              {                  int index = arr[i] % n;                  arr[index] = arr[index] + n;              }               //iterate and print the result dividing by n              for (int i = 0; i < n; i++)              {                  Console.WriteLine(i + 1 + " -> " + arr[i] / n);              }          }    

Problem 2 
/// <summary>  /// Find the nearest smaller numbers on left side in an array /// We can solve this in two way: /// 1- Start with element 1 (as first element does not have anything in left) ///    and iterate till 0 element if you find any element value less than the          current index print it and break ///    if loop ends then print "_". this approach will have 2 loops so solution is O(n*2)  /// 2- We have better solution with STACK in O(n) time /// </summary>          public static void FindNearestNumber()          {              int[] arr = { 1, 6, 4, 10, 2, 5 };              int n = arr.Length;              // Create an empty stack              Stack<int> S = new Stack<int>();               // Traverse all array elements              for (int i = 0; i < n; i++)              {                  // Keep removing top element from S while the top                  // element is greater than or equal to arr[i]                  while (S.Count > 0 && S.Peek() >= arr[i])                      S.Pop();                   // If all elements in S were greater than arr[i]                  if (S.Count == 0)                      Console.WriteLine("_ , ");                  else  //Else print the nearest smaller element                      Console.WriteLine(S.Peek() + ", ");                   // Push this element                  S.Push(arr[i]);                        } 

Problem 3 
        /// <summary>          /// Sort an almost sorted array where only two elements are swapped          /// </summary>          public static void SortAndSwap()          {              int[] arr = { 10, 20, 60, 40, 50, 30 };              int n = arr.Length;              // Travers the given array from rightmost side              for (int i = n - 1; i > 0; i--)              {                  // Check if arr[i] is not in order                  if (arr[i] < arr[i - 1])                  {                      // Find the other element to be                      // swapped with arr[i]                      int j = i - 1;                      while (j >= 0 && arr[i] < arr[j])                          j--;                       // Swap the pair                      swap(arr[i], arr[j + 1]);                      break;                  }              }          } 
Problem 4 
/// <summary>  /// Find the largest pair sum in an unsorted array  /// Given an unsorted array, find the largest pair sum in it. For example, the largest pair sum in {12, 34, 10, 6, 40} is 74  (34 + 40). /// This problem is to find first and second larget number and sum them /// </summary>          public static void LargestSumPair()          {              int[] arr = {12, 34, 10, 6, 40};              int n = arr.Length;              // Initialize first and second largest element              int first, second;              if (arr[0] > arr[1])              {                  first = arr[0];                  second = arr[1];              }              else              {                  first = arr[1];                  second = arr[0];              }               // Traverse remaining array and find first and second largest              // elements in overall array              for (int i = 2; i < n; i++)              {                  /* If current element is greater than first then update both                    first and second */                  if (arr[i] > first)                  {                      second = first;                      first = arr[i];                  }                   /* If arr[i] is in between first and second then update second  */                  else if (arr[i] > second && arr[i] != first)                      second = arr[i];              }               Console.WriteLine(first + second);          }   
Problem 5 
/// <summary>          /// Find missing number from an sequence array          /// </summary>          public static void FindMissingNumber()          {              int[] a = { 1, 2, 3, 4, 5, 6, 0, 8, 9 };              double MaxSum = (a.Length + 1) * ((double)a.Length / 2);              int arrSum = 0;              for (int i = 0; i < a.Length; i++)              {                  arrSum += a[i];              }               Console.WriteLine("Missing Number is {0}", MaxSum - arrSum);          } 
Problem 6 
/// <summary>          /// find out the number which occurs only one time in pair array          /// </summary>          /// <returns></returns>          public static int singleNumber()          {              int[] A = new int[] { 1, 1, 2, 2, 3, 4, 4, 5, 5 };              int ans = A[0];              for (int i = 1; i < A.Length; i++)              {                  ans = ans ^ A[i];              }               return ans;          } 
Problem 7 
/// <summary> /// Write a C program that, given an array A[] of n numbers and another number x,  /// determines whether or not there exist two elements in S whose sum is exactly x.  /// </summary>          public static void PairWiseSumonSortedArray()          {              int[] arr = new int[] { 2, 3, 4, 5, 6, 7, 8, 9, 10};              int sum = 10;              int left = 0, right = arr.Length - 1;              while(left < right)              {                  int add = arr[left] + arr[right];                   if (add == sum)                  {                   Console.WriteLine("Pair exists with {0} and {1} On Index {2} and {3}"                                                    arr[left], arr[right], left, right);                      left++;                      right--;                  }                  else                  {                      if (add > sum)                          right--;                      else                          left++;                  }              }          }  
Problem 8 
/// <summary> /// Write an efficient C program to find the sum of contiguous subarray within a one-dimensional array of  /// numbers which has the largest sum. /// </summary>          public static void LargestSumArray()          {              int[] a = {-2, -3, 4, -1, -2, 1, 5, -3};              int max_so_far = 0, max_ending_here = 0;              int start = 0, end = 0;              for (int i = 0; i < a.Length; i++)              {                  max_ending_here += a[i];                  if (max_ending_here < 0)                      max_ending_here = 0;                  else if (max_so_far < max_ending_here)                  {                      if (max_so_far == 0)                          start = i;                      else                          end = i;                       max_so_far = max_ending_here;                  }              }      Console.WriteLine("Maximum Sum : {0}, Index from {1} to {2}",  max_so_far, start, end);          } 
Problem 9 
/// <summary>         /// Find the Factorial of a given number and the result is more than int max value         /// </summary>         /// <param name="n"></param>         private static void FindFactorial(int n)         {             int max=500;             int[] arr = new int[max];             arr[0] = 1;             int res_size = 1;               for (int i = 2; i <= n; i++)             {                 res_size = Multiply(i, arr,  res_size);             } 
            for (int x = arr.length-1; x >=0 x--)             {                  print(arr[x]);             } 

                                  }           private static int Multiply(int i,int[] arr,  int res_size)         {             int carry = 0;             for (int j = 0; j < res_size; j++)             {                 int prod = (arr[j] * i) + carry;                 arr[j]= prod % 10;                 carry = prod / 10;                             }               while (carry!=0)             {                 arr[res_size] = carry % 10;                 carry=carry / 10;                 res_size++;             }                return res_size;           } 
Problem 10 
/// <summary>         /// Write a C program that, given an unsorted array A[] of n numbers and another number x,          /// determines whether or not there exist two elements in S whose sum is exactly x.          /// </summary>         public static void PairWiseSum()         {             int[] arr = new int[] { 2, 10, 5, 6, 4, 3, 7, 7 };             int sum = 10;               bool[] values = new bool[10];               for (int i = 0; i < arr.Length; i++)             {                 int temp = sum - arr[i];                 if (temp > 0 && values[temp])                 {                     Console.WriteLine("Paie sum exists with {0} and {1}", temp, arr[i]);                 }                 else                 {                     values[arr[i]] = true;                 }             }         } 




Problem 1: 
/// <summary>          /// Rotate Matrix on 90 degree in place          /// 1- We have to perform this in Layer (rows)          /// </summary>          public static void RotateMatrix()          {              int[,] arr = new int[,] { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } };              int n = 4;              for (int layer = 0; layer < n / 2; layer++)              {                  int first = layer;                  int last = n - 1 - layer;                  for (int i = first; i < last; i++)                  {                      int offset = i - first;                      //save top                      int top = arr[first, i];                      // left -> top                      arr[first, i] = arr[last - offset, first];                      // bottom -> left                      arr[last - offset, first] = arr[last, last - offset];                      // right -> bottom                      arr[last, last - offset] = arr[i, last];                      // top-> right                      arr[i, last] = top;                  }              }               for (int i = 0; i < n; i++)              {                  for (int j = 0; j < n; j++)                  {                      Console.Write(arr[i, j] + "\t");                  }                  Console.WriteLine();              }          } 
Problem 2: 
/// <summary>          /// Write an algorithm such that is an element in an MxN matrix is 0, its entire row and column set to 0.          /// </summary>          public static void SetZeros()          {              int[,] arr = new int[,] { { 1, 2, 3 }, { 5, 0, 7 }, { 9, 10, 11 } };              bool[] row = new bool[3];              bool[] col = new bool[3];               //Set bool array to identify row/column where we have zero              for (int i = 0; i < 3; i++)              {                  for (int j = 0; j < 3; j++)                  {                      if (arr[i, j] == 0)                      {                          row[i] = true;                          col[j] = true;                      }                  }              }             // Iterate matrix and set element value 0 if its row/column match bit bool array              for (int i = 0; i < 3; i++)              {                  for (int j = 0; j < 3; j++)                  {                      if (row[i] || col[j])                      {                          arr[i, j] = 0;                      }                  }              }               for (int i = 0; i < 3; i++)              {                  for (int j = 0; j < 3; j++)                  {                      Console.Write(arr[i, j]);                      Console.Write("\t");                  }                  Console.WriteLine();              }          } 
Problem 3: 
/// <summary>          /// Print Matrix in spiral format          /// </summary>          public static void PrintSpiral()          {              int[,] a = new int[4, 4] { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 }, { 13, 14, 15, 16 } };              int row = 4, col = 4;              int t = 0, b = row - 1, l = 0, r = col - 1, dir = 0;               while (t <= b && l <= r)              {                  switch (dir)                  {                      // right                      case 0:                          for (int i = l; i <= r; i++)                              Console.WriteLine(a[t, i]);                          t++;                          dir = 1;                          break;                      // bottom                      case 1:                          for (int i = t; i <= b; i++)                              Console.WriteLine(a[i, r]);                          r--;                          dir = 2;                          break;                      // left                      case 2:                          for (int i = r; i >= l; i--)                              Console.WriteLine(a[b, i]);                          b--;                          dir = 3;                          break;                      // top                      case 3:                          for (int i = b; i >= t; i--)                              Console.WriteLine(a[i, l]);                          l++;                          dir = 0;                          break;                  }              }          } 



No comments:

Post a Comment