Author: shahprashant

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.

Algorithm:
1) Make a matrix m x n where m = string1 length and n = string2 length
2) if str1[i] != str2[j] then put matrix element as 0
3) if str1[i] == str2[j] then put matrix element as 1 + previous diagonal element. set max
4) form the longest substring by examining max element in matrix and going back diagonally to collect previous characters

$str1 = "GeeksForGeeks";
$str2 = "AllGeeksQuiz";
$len1 = strlen($str1);
$len2 = strlen($str2);
$matrix = array();
$max = 0;
for ($i = 0; $i < $len1 ; $i++) {
    for ($j = 0; $j < $len2 ; $j++) {
        if ($str1[$i] == $str2[$j]) {
            if (($i == 0) || ($j == 0))
                $matrix[$i][$j] = 1;
            else
                $matrix[$i][$j] = $matrix[$i-1][$j-1] + 1;
            if ($matrix[$i][$j] > $max) {
                $maxI = $i;
                $maxJ = $j;
                $max = $matrix[$i][$j];
            }
        }
    }
}

if ($max > 0) {
    $substring = '';
    for ($k = 0; $k < $max ; $k++) {
        $substring = $str1[$maxI-$k] . $substring;
    }
    echo "Longest Substring: $substring\n";
} else {
    echo "No substring\n";
}

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

Generate Prime Numbers in the 1..x range.

http://leetcode.com/2010/04/finding-prime-numbers.html

/* Generate a prime list from 0 up to n, using The Sieve of Erantosthenes
param n The upper bound of the prime list (including n)
param prime[] An array of truth value whether a number is prime
*/

void prime_sieve(int n, bool prime[]) {
  prime[0] = false;
  prime[1] = false;
  int i;
  for (i = 2; i <= n; i++) {
    prime[i] = true;
  }
  int limit = sqrt(n);
  for (i = 2; i <= limit; i++) {
    if (prime[i]) {
      for (int j = i * i; j <= n; j += i)
        prime[j] = false;
    }
  }
}

Find all permutations of a given string:

// function to generate and print all N! permutations of $str. (N = strlen($str)).
function permute($str,$i,$n) {
   if ($i == $n)
       print "$str\n";
   else {
        for ($j = $i; $j < $n; $j++) {
          swap($str,$i,$j);
          permute($str, $i+1, $n);
          swap($str,$i,$j); // backtrack.
       }
   }
}

// function to swap the char at pos $i and $j of $str.
function swap(&$str,$i,$j) {
    $temp = $str[$i];
    $str[$i] = $str[$j];
    $str[$j] = $temp;
}   

$str = "hey";
permute($str,0,strlen($str)); // call the function.

Diagram: http://www.geeksforgeeks.org/write-a-c-program-to-print-all-permutations-of-a-given-string/

PHP Implementation:
http://stackoverflow.com/questions/2617055/how-to-generate-all-permutations-of-a-string-in-php