Palindrome

$a_inputString = "raddar"
function isPalindrome($a_inputString)
{
    $frontPointer = 0;
    $backPointer = str_length(inputString)-1;
   
    while ($frontPointer < $backPointer)
    {
       if ( strcmp(substr($inputString, $frontPointer, 1)
                  (substr($inputString, $backPointer, 1) == false)
           return false;
       $frontPointer ++;
       $backPointer --;
    }
   
    return true;
}

Merge sorted lists

Question:
n lists, each is sorted, each has size m
merge into one sorted list, overall size n*m

Easy Solution:
1. Pointers pointing to each position of the array
2. Compare the element at the positions
3. Find the minimum and insert in the outputArray

Complexity
1. Traverse all the lists (n*m)
2. Comparisons to find the minimum element ((n-1) comparisons) 
O((n*m)(n-1)) = O(n^2*m)

MinHeap heap = new MinHeap();

// $inList[n] - Input Lists
$outputArr = array();

// Push first elements of all the lists in the MinHeap
for (int i=0; i<n; i++)
{
    heap.push(i, array_pop($inList[i]));
}   

/*
  1. Pop element from MinHeap
  2. Push the next element from the inList from which the element was pop'd
  3. Do this till the MinHeap is empty  
*/
$popObj = heap.pop();
while (!empty($popObj))
{
    $listId = $popObj["listId"];
    $elementPop = $popObj["leastElement"];
   
    $outputArr[] = $elementPop;
    heap.push($listId, array_pop($inList[$listId]));
}

// Complexity
1. n-size heap
2. log n to insert in heap
3. O(n*m*logn)

Using XOR operator for finding duplicate element

A XOR statement has the property that 'a' XOR 'a' will always be 0, that is they cancel out, thus, if you know that your list has only one duplicate and that the range is say x to y, 601 to 607 in your case, it is feasible to keep the xor of all elements from x to y in a variable, and then xor this variable with all the elements you have in your array. Since there will be only one element which will be duplicated it will not be cancelled out due to xor operation and that will be your answer.

void main()
{
    int a[8]={601,602,603,604,605,605,606,607};
    int k,i,j=601;

    for(i=602;i<=607;i++)
    {
        j=j^i;
    }

    for(k=0; k<8; k++)
    {
        j = j^a[k];
    }
    // j = duplicate element
}

Variation:

An array of 2 elements - one element occurs even number of times & the other odd number of times. How would you find the value that occurs odd number of times ?

Get all the unique numbers in the array using a set in O(N) time. Then we XOR the original array and the unique numbers all together. Result of XOR is the even occurring element. Because every odd occurring element in the array will be XORed with itself odd number of times, therefore producing a 0. And the only even occurring element will be XORed with itself even number of times, which is the number itself.

Reason:  
XOR a number with itself odd number of times we get 0,.
XOR a number with itself even number of times then we get the number itself.

You are given an array of integers and a sum. Find all pairs of integers that equal that sum. Assume you have some sort of data structures that will be able to store the pairs. Write an algorithm to find all these pairs

Solution1
O(n^2) solution - Have two for loops

Solution2
Using a hashMap

Solution3
Most efficient - as no extra storage like hashMap

Sort the array

Two pointer - one to the begining and the other to the end of the array.

Compare the values pointed by the pointers untill the pointers collide
If the sum is lesser than m then increment the left pointer by one
If the sum is greater than m then decrement the right pointer by one
If the sum is equal to m then return "YES"

Swap without using 3rd variable

Swap Algorithm

A = A + B
B = A - B
A = A - B

You can not use this approach as while adding A & B (A + B), it could result in a "OVERFLOW"

Hence, we use this approach

X := X XOR Y
Y := X XOR Y
X := X XOR Y

Interview Websites

• http://www.leetcode.com/
• http://programming-puzzle.blogspot.com/
• http://www.geeksforgeeks.org/
• http://puddleofriddles.blogspot.com/
• http://www.ardendertat.com/

http://formatmysourcecode.blogspot.com/