Category: Algorithms

Atlassian Hackerrank Interview

1) Implement a method ‘find’ that will find the starting index (zero based) where the second list occurs as a sub-list in the first list. It should return -1 if the sub-list cannot be found. Arguments are always given, not empty.

Combinations of a String

Implement a function that prints all possible combinations of a string.

A string “12” is the same as string “21”.

Note : The below function will work for unique strings like “wxyz” but not for “aabc”.  One quick to fix it for “aabc” would be to store the output strings in a hash and then output the hash.

Check this video for good explanation of “AABC” :

function combine($instr, $outstr, $index)
{
    for ($i = $index; $i < strlen($instr); $i++)
    {

        $outstr = $outstr . $instr[$i];
        echo "$outstr\n";
        combine($instr, $outstr, $i + 1);
        $outstr = substr($outstr, 0, -1);
    }
}

combine("wxyz", "", 0);

Given Array of positive negative numbers find 2,3 of them that sum to zero

Given an array of numbers with positive and negative, find pairs that sum to zero  
a) sort the numbers
b) start 2 pointers from from begin and end
c) if sum is > or < = then move appropriate pointer. Above question, but now finding 3 numbers which sums to zero. a) for each number in array as target (index:0, 1, 2, etc) start 2 pointers from i+1 and len-1 if sum of target + 2 pointers is > 0 decrement second pointer
if sum of target + 2 pointers is < 0 increment first pointer

Find if an integer is a prime number

The algorithm can be improved further by observing that all primes are of the form 6k ± 1, with the exception of 2 and 3. This is because all integers can be expressed as (6k + i) for some integer k and for i = -1, 0, 1, 2, 3, or 4; 2 divides (6k + 0), (6k + 2), (6k + 4); and 3 divides (6k + 3). So a more efficient method is to test if n is divisible by 2 or 3, then to check through all the numbers of form 6k ± 1.

function isPrime($n)
{
    // Corner cases
    if ($n <= 1)  return false;
    if ($n <= 3)  return true;

    // This is checked so that we can skip
    // middle five numbers in below loop
    if ($n % 2 == 0 || $n % 3 == 0) return false;

    for ($i=5; $i*$i<=$n; $i=$i+6) {
        if ($n % $i == 0 || $n % ($i+2) == 0)
           return false;
    }

    return true;
}

Sort an array of 0s, 1s and 2s

Given an array A[] consisting 0s, 1s and 2s, write a function that sorts A[]. The functions should put all 0s first, then all 1s and all 2s in last.

Example
Input = {0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1};
Output = {0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2}

This is a variation of famous Dutch national flag problem
The problem was posed with three colours, here `0?, `1? and `2?. The array is divided into four sections:

a[1..Lo-1] zeroes (red)
a[Lo..Mid-] ones (white)
a[Mid..Hi] unknown
a[Hi+1..N] twos (blue)
The unknown region is shrunk while maintaining these conditions

Lo := 1; Mid := 1; Hi := N;
while Mid <= Hi do
Invariant: a[1..Lo-1]=0 and a[Lo..Mid-1]=1 and 
a[Hi+1..N]=2; a[Mid..Hi] are unknown.

case a[Mid] in
0: swap a[Lo] and a[Mid]; Lo++; Mid++
1: Mid++
2: swap a[Mid] and a[Hi]; Hi–

http://www.geeksforgeeks.org/sort-an-array-of-0s-1s-and-2s/

Sort Algorithms

Stable Sort: A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort,

Complete Binary Tree: A complete binary tree is a binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible. A Binary Heap is a complete Binary Tree.

Heap Sort:
http://quiz.geeksforgeeks.org/heap-sort/
Karumanchi is also good for explanation , pg 180-185

// To heapify a subtree rooted with node i which is
// an index in arr[]. n is size of heap
void heapify(int arr[], int n, int i)
{
    int largest = i;  // Initialize largest as root
    int l = 2*i + 1;  // left = 2*i + 1
    int r = 2*i + 2;  // right = 2*i + 2
 
    // If left child is larger than root
    if (l < n && arr[l] > arr[largest])
        largest = l;
 
    // If right child is larger than largest so far
    if (r < n && arr[r] > arr[largest])
        largest = r;
 
    // If largest is not root
    if (largest != i)
    {
        swap(arr[i], arr[largest]);
 
        // Recursively heapify the affected sub-tree
        heapify(arr, n, largest);
    }
}
 
// main function to do heap sort
void heapSort(int arr[], int n)
{
    // Build heap (rearrange array)
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);
 
    // One by one extract an element from heap
    for (int i=n-1; i>=0; i--)
    {
        // Move current root to end
        swap(arr[0], arr[i]);
 
        // call max heapify on the reduced heap
        heapify(arr, i, 0);
    }
}