Powershell Coding Interview

interview_questions.sh

# ==============================================================================
# 1 - Powershell program to determine if any two integers in array sum to given integer
# ==============================================================================
echo '$myArray = @{}

class Algorithm {
  #Brute force solution, O(n^2) time complexity
  [bool] TwoIntegersSumToTarget([int[]] $arr, [int] $target) {
    $numElements = $arr.length
    for ([int] $outer = 0; $outer -lt $numElements; $outer++) {
      for ([int] $inner = 0; $inner -lt $numElements; $inner++) {
        if ($outer -ne $inner) {
          [int] $sum = $arr[$outer] + $arr[$inner]
          if ($sum -eq $target) { return $true }
        }
      }
    }
    return $false
  }
}

"Given an integer and an array of integers determine whether 
any two integers in the array sum to that integer."
$myArray = 5, 2, 66, 8
$a = [Algorithm]::new()
$a.TwoIntegersSumToTarget($myArray,3)' >> arrayprograms/practice.ps1

pwsh ./arrayprograms/practice.ps1

# ==============================================================================
# 2 - Write a method to sort the elements of an array in descending order.
# ==============================================================================
echo '$myArray = @{}

class Algorithm {
  Sort([ref] $arr) {
    $numElements = $arr.value.length
    for ([int] $outer = 1; $outer -le $numElements-1; ++$outer) {
      for ([int] $inner = 0; $inner -lt $numElements-1; ++$inner) {
        if ($arr.value[$inner] -gt $arr.value[$inner + 1]) {
          $arr.value[$inner],$arr.value[$inner+1] = 
              $arr.value[$inner+1],$arr.value[$inner]
        }
      }
    }
  }

  Reverse([ref] $arr) {
    $numElements = $arr.value.length
    for([int] $i=0; $i -lt $numElements/2; $i++) {
      $arr.value[$i],$arr.value[$numElements-1-$i] = 
          $arr.value[$numElements-1-$i],$arr.value[$i]
    }
  }

  [int[]] SortDesc([int[]] $arr) {
    $this.Sort([ref] $arr)
    $this.Reverse([ref] $arr)
    return $arr
  }
}

"Write a method to sort the elements of an array in descending order."
$myArray = 5, 2, 66, 8
$a = [Algorithm]::new()
$a.SortDesc($myArray)' >> arrayprograms/practice2.ps1

pwsh ./arrayprograms/practice2.ps1

# ==============================================================================
# 3 - Find majority element in an unsorted array.
# ==============================================================================
echo '$myArray = @{}

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.
  [int] GetMajorityElement([int[]] $arr)  {
    $dict = @{}
    $majority = $arr.length/2

    #Stores the number of occcurences of each item in the passed array in a dictionary
    foreach ($i in $arr) {
      if ($dict.contains($i)) {
        $dict[$i]++
        #Checks if element just added is the majority element
        if ($dict[$i] -gt $majority) { return $i }
      } else { $dict.add($i, 1) }
    }
    throw "No majority element in array";
  }
}

"Find majority element in an unsorted array."
$myArray = 2, 8, 8, 2, 66, 8, 8
$a = [Algorithm]::new()
$a.GetMajorityElement($myArray)' >> arrayprograms/practice3.ps1

pwsh ./arrayprograms/practice3.ps1

# ==============================================================================
# 4 - Sort 2 merged arrays
# ==============================================================================
echo '$myArray1, $myArray2 = @{}

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
  [int[]] MergeSortedArrays([int[]] $arr1, [int[]] $arr2) {
    $combined = [int[]]::new($arr1.length + $arr2.length)
    $combined = $arr1 + $arr2
    return $this.Sort($combined)
  }
    
  [int[]] Sort([int[]] $arr) {
    $numElements = $arr.length
    for ([int] $outer = 1; $outer -le $numElements-1; ++$outer) {
      for ([int] $inner = 0; $inner -lt $numElements-1; ++$inner) {
        if ($arr[$inner] -gt $arr[$inner + 1]) {
          $arr[$inner],$arr[$inner+1] = 
              $arr[$inner+1],$arr[$inner]
        }
      }
    }
    return $arr
  }
}
"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.."
$myArray1 = 3, 4, 5, 0, 0
$myArray2 = 1, 2
$a = [Algorithm]::new()
$a.MergeSortedArrays($myArray1,$myArray2)' >> arrayprograms/practice4.ps1

pwsh ./arrayprograms/practice4.ps1

# ==============================================================================
# 5 - Merge 0s to end
# ==============================================================================
echo '$myArray = @{}

# 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.
class Algorithm {
  [int[]] MoveZeros([int[]] $x) {
    for ([int] $i = 0; $i -lt $x.length; $i++) {
      if ($x[$i] -eq 0) { $this.MoveZeroToEnd($x, $i) }
    }    
    return $x      
  }
  MoveZeroToEnd([int[]] $x, [int] $index) {
    for ([int] $i = $index; $i -lt $x.Length - 1; $i++) {
      $x[$i], $x[$i+1] = $x[$i+1], $x[$i]
    }
  }  
}
"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."
$myArray = 0, 3, 4, 0, 5, 2
$a = [Algorithm]::new()
$a.MoveZeros($myArray)' >> arrayprograms/practice5.ps1

pwsh ./arrayprograms/practice5.ps1

# ==============================================================================
# 6 - Check for duplicate number
# ==============================================================================
echo '$myArray = @{}

class Algorithm {
  [bool] ContainsDuplicates([int[]] $arr) {
    $dict = @{}
    foreach ($i in $arr) {
      if ($dict.contains($i)) { return $true }
      else { $dict.Add($i, 1) }
    }
    return $false;
  }
}

"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."
$myArray =  0, 3, 4, 0, 5, 2
$a = [Algorithm]::new()
$a.ContainsDuplicates($myArray)' >> arrayprograms/practice6.ps1

pwsh ./arrayprograms/practice6.ps1

# ==============================================================================
# 7 - Binary Search
# ==============================================================================
echo '$myArray = @{}

class Algorithm {
  [bool] BinarySearch([int[]] $arr, [int] $target) {
    $upperBound = $arr.length
    $lowerBound = 0;

    $this.Sort([ref] $arr)

    while ($lowerBound -le $upperBound) {
      $mid = [System.Math]::Floor(($lowerBound + $upperBound) / 2);
      if ($arr[$mid] -lt $target) {
        lowerBound = mid + 1
      } elseif ($arr[$mid] -gt $target) {
        $upperBound = $mid - 1
      } else { return $true; }
    }
    return $false;
  }
  Sort([ref] $arr) {
    $numElements = $arr.value.length
    for ([int] $outer = 1; $outer -le $numElements-1; ++$outer) {
      for ([int] $inner = 0; $inner -lt $numElements-1; ++$inner) {
        if ($arr.value[$inner] -gt $arr.value[$inner + 1]) {
          $arr.value[$inner],$arr.value[$inner+1] = 
              $arr.value[$inner+1],$arr.value[$inner]
        }
      }
    }
  }
}

"Repeatedly divide half of the array we find the target value."
$myArray =  8, 99, 7, 14, 9
$a = [Algorithm]::new()
$a.BinarySearch($myArray,9)' >> arrayprograms/practice7.ps1

pwsh ./arrayprograms/practice7.ps1

# ==============================================================================
# 8 - Check which numbers are prime numbers
# ==============================================================================
echo '$myArray = @{}

class Algorithm {
  # A prime number is a number greater than 1 that cannot be 
  # formed by multiplying two smaller numbers.
  [int[]] CheckForPrimes([int[]] $arr) {
    foreach($n in $arr) {
      if ($n -ne 2) {
        if ($n -le 1 -or $n % 2 -eq 0) { $this.RemoveFromArray([ref] $arr, $n) }
      }

      $boundary = [int][System.Math]::Floor([System.Math]::Sqrt($n))

      for ([int] $i = 3; $i -le $boundary; $i+=2) {
        if ($n % $i -eq 0) { $this.RemoveFromArray([ref] $arr, $n) }
      }
    }
    return $arr
  }
  RemoveFromArray([ref] $x, [int] $target){    
    $x.value = [System.Linq.Enumerable]::ToArray(
      [System.Linq.Enumerable]::Where([int[]] $x.value, 
          [Func[int,bool]] { param($val) $val -ne $target }) 
    )    
  }
}

"Check which numbers in a given array are prime numbers"
$myArray = 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
$a = [Algorithm]::new()
$a.CheckForPrimes($myArray)' >> arrayprograms/practice8.ps1

pwsh ./arrayprograms/practice8.ps1

# ==============================================================================
# 9 - Quick sort
# ==============================================================================
echo '$myArray = @{}

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

    if ($low -lt $high) {
      $pivot_location = $this.Partition($arr, $low, $high)
      
      # recursively list both sub lists, those less than the pivot & more than the pivot
      $this.QuickSort($arr, $low, $pivot_location - 1)
      $this.QuickSort($arr, $pivot_location + 1, $high)
    }
    return $arr;
  }
  [int] Partition([int[]] $arr, [int] $low, [int] $high) {
    $pivot = $arr[$high]
    $i = $low - 1
    
    #elements less than the pivot are moved to before the pivot
    for ([int] $j = $low; $j -lt $high; $j++) {
      if ($arr[$j] -le $pivot) {
        $i++;
        $arr[$i], $arr[$j] = $arr[$j], $arr[$i]
      }
    }
    
    #elements greater than pivot are moved to after the pivot
    $arr[$i + 1], $arr[$high] = $arr[$high], $arr[$i + 1]
    return $i + 1
  }
}

"Quicksort on a given pivot."
$myArray = 45, 2, 66, 1, 72
$a = [Algorithm]::new()
$a.QuickSort($myArray,$myArray.length-3,$myArray.length-1)' >> arrayprograms/practice9.ps1

pwsh ./arrayprograms/practice9.ps1