Amazon Text lInk for IR Testing

Image and link Iframe -
Here To Stay

Programming Questions with code in Ruby

Insertion Sort

INSERTION-SORT(A)
   for i = 1 to n
    key ← A [i]
     j ← i – 1
    while j > = 0 and A[j] > key
     A[j+1] ← A[j]
     j ← j – 1
    End while 
    A[j+1] ← key 
   End for

# Insertion Sort in Ruby
def insertion_sort(array)
    (1..array.size - 1 ).each do |i|
        position = array[i]
        j = i-1
        while (j >= 0 && array[j] > position)
           array[j+1] = array[j]
           j = j - 1
       end
       array[j+1] = position
    end
    array
end
p insertion_sort([12,21,32,7,2])

Worst Case Time Complexity [ Big-O ]: O(n2)

Best Case Time Complexity [Big-omega]: O(n)

Average Time Complexity [Big-theta]: O(n2)

Merge Sort

# Merge Sort in Ruby
def merge(array1, array2)
    iter1=iter2=iter=0
    result = []
    while(iter1 < array1.size || iter2 < array2.size)
        if(iter1 >= array1.size)
            result[iter] = array2[iter2]
            iter2=iter2+1
        elsif(iter2 >= array2.size)
            result[iter] = array1[iter1]
            iter1 = iter1+1
        elsif(array1[iter1] < array2[iter2])
            result[iter] = array1[iter1]
            iter1 = iter1+1
        else
            result[iter] = array2[iter2]
            iter2=iter2+1
        end
        iter=iter+1
    end
    result
end

def merge_sort(array)
    return array if (array.size == 1)
    mid = (array.size/2.0).round
    split_array = array.each_slice(mid).to_a 
    array1 = split_array[0]
    array2 = split_array[1]
    array1 = merge_sort(array1)
    array2 = merge_sort(array2)
    return merge(array1, array2)
end

p merge_sort([12,21,32,7,2,34])

Time Complexity : Ο(n log n)

Space Complexity : O(n)

Quick Sort

# Quick Sort in Ruby
def partition(array, low, high)
    pivot = array[high]
    i = low -1
    (low..high-1).each do |j|
        if(array[j] <= pivot)
            i = i+1
            temp = array[i]
            array[i] = array[j]
            array[j] = temp
        end
    end
    temp = array[i+1]
    array[i+1] = array[high]
    array[high] = temp
    return i+1
end

def quick_sort(array, low, high)
    if (low < high)
        index = partition(array, low, high)
        quick_sort(array, low, index-1)
        quick_sort(array, index+1, high)
    end
end

array = [12,21,32,7,2,14]
quick_sort(array, 0, array.size-1)
p array

Time Complexity : O(n2)

Space Complexity : In-Place

Problem:

Given a non-negative number represented as an array of digits, add 1 to the number ( increment the number represented by the digits ).The digits are stored such that the most significant digit is at the head of the list.
Example:
If the vector has [1, 2, 3]
the returned vector should be [1, 2, 4]
as 123 + 1 = 124.

class Solution
    # @param a : array of integers
    # @return an array of integers
    def plusOne(a)
        num = a.join.to_i+1
        num.to_s.split('')
    end
end