Category: Algorithms

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

$sortFunc = function($val) {
   $strArr = str_split($val);
   sort($strArr);
   return implode("", $strArr);
};

$arr = array("cat", "dog", "tac", "god", "act");

$words = array();
$index = array();

// form a new array with each string sorted within itself
$words = array_map($sortFunc, $arr);
// form a index array in order to remember original index
foreach ($words as $key => $val) {
    $index[$key] = $val;
}
asort($index);  // sort the values but maintain index association
foreach ($index as $key => $val) {
    // use index value in the original array to print
    echo $arr[$key] . "\n";
}

http://www.geeksforgeeks.org/given-a-sequence-of-words-print-all-anagrams-together/

1) Sorting a list of words such anagrams are grouped together. (Soundhound.com)
Input: [‘abc’,’test’,’vac’, ‘bac’, ‘london’, ‘cba’, ‘cav’, ‘lon’, ‘pst’]
Output: [‘abc’, ‘bac’, ‘cba’, ‘vac’, ‘cav’, ‘london’, ‘test’, ‘lon’, ‘pst’]

2. Design Twitter algorithm to retrieve top 10 new feeds (Soundhound.com)

$bigString = "I am a really big realtor in the bay area";
$pattern = "realtor";

$i = 0;
$j = 0;
$bigStringLen = strlen($bigString);
$patternLen = strlen($pattern);
$found = false;
while ($i <= ($bigStringLen - $patternLen)) {
   if ($bigString[$i] == $pattern[$j]) {

   } else {
       $j=0;
   }
   $i++; $j++;
   if ($j >= $patternLen) {
       $found = true;
       break;
   }
}
if ($found) {
    print "found at " . ($i-$patternLen) . "\n";
} else {
    echo "\nnot found\n";
}

http://www.geeksforgeeks.org/search-in-row-wise-and-column-wise-sorted-matrix/

Given a singly linked list devise an algorithm to find the mth-to-last element of the list.

http://www.geeksforgeeks.org/nth-node-from-the-end-of-a-linked-list/

1. Williams Coding Book: http://wlcoding.blogspot.com/