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.

# Category: Algorithms

## 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; }

## Trees: Find count of unival or single valued subtrees

## Towers of Hanoi

https://www.youtube.com/watch?v=q6RicK1FCUs

Karumanchi, pg 37.

## 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–

## Longest Common Subsequence

https://www.youtube.com/watch?v=NnD96abizww

if (input1[i] == input2[j]) { M[i][j] = M[i-1][j-1] + 1 } else { M[i][j] = max(M[i-1,j], M[i,j-1]) }

## 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); } }

## Find kth largest element in an unsorted array

Method 1 (Simple Solution)

A Simple Solution is to sort the given array using a O(nlogn) sorting algorithm like Merge Sort, Heap Sort, etc and return the element at index k-1 in the sorted array. Time Complexity of this solution is O(nLogn).

Method 2 (QuickSelect)

Using technique similar to quicksort.

Complexity is O(n^2) but avg case is O(n)

Method 3 (Using Min Heap – HeapSelect)

We can find k’th smallest element in time complexity better than O(nLogn). A simple optomization is to create a Min Heap of the given n elements and call extractMin() k times.