Balanced Brackets

$handle = fopen ("php://stdin","r");
fscanf($handle,"%d",$t);
for($a0 = 0; $a0 < $t; $a0++){
    fscanf($handle,"%s",$str);
    $stack = array();
    $unevenFlag = false;
    $matchingP = array(
        '}' => '{',
        ']' => '[',
        ')' => '('
    );
    $closingP = array_keys($matchingP);
    $openingP = array_values($matchingP);
    for ($i=0; $i < strlen($str); $i++) {
      if (in_array($str[$i], $openingP)) {
        array_push($stack, $str[$i]);
      } elseif (in_array($str[$i], $closingP)) {
        $openP = array_pop($stack);
        if ($matchingP[$str[$i]] != $openP) {
            $unevenFlag = true;
            break;
        }  
      }
    }
    if (count($stack) != 0 || $unevenFlag === true) {
      print "NO\n";
    } else {
      print "YES\n";
    }
}

Algorithms on Graphs

1) DFS
Remember its recursive

2) BFS
Queue based

3) Shortest Path in unweighted graph.

4) Shortest Path in weighted graph.

5) Determine if directed graph has a cycle
Karumanchi , pg 236

If a node is seen a second time before all of its descendants are visited then there is a cycle.

Detect Cycle(G) {
  Initialize Visited array and Predecessor array; 
  call HasCycle
}

HasCycle(G, u) {
 Visited[u] = true; 
 Loop i over all vertices v
   Check if edge present in Adjacency Matrix 
      If Predecessor P[i] != u and Visited[u] then 
          Cycle exists; 
}

General Algorithm Questions

1) http://javarevisited.blogspot.com/2013/03/top-15-data-structures-algorithm-interview-questions-answers-java-programming.html

2) Binary Search
1) while (low <= high) 2) mid = low + high-low/2 ; // to avoid overflow 3) Implement LRU Cache http://www.geeksforgeeks.org/implement-lru-cache/

4) Given a string “{ab}{}{{dhk}}” write a program to find if the parenthesis are balanced.

System Design

1) “Design and code a system that can accept millions of events in real time and report the number of events for the last 10 minutes (sliding window). The system has to account for performance and concurrency.”

http://www.glassdoor.com/Interview/Design-and-code-a-system-that-can-accept-millions-of-events-in-real-time-and-report-the-number-of-events-for-the-last-10-mi-QTN_187032.htm

2) Design a URL shortner service :

http://www.hiredintech.com/app#the-system-design-process

3) Design a unique id service like youtube
http://kvz.io/blog/2009/06/10/create-short-ids-with-php-like-youtube-or-tinyurl/

4) Design an Elevator System and give the objects involved and their interactions.

http://www.careercup.com/question?id=1808669

Binary Tree Algorithms

1) Find deepest node of a binary tree
(Karumanchi, pg 120)

2) Find height of a binary tree (recursion method)
(Karumanchi, pg 119 , with small correction)

3) Find height of binary tree (non recursion)
(Karumanchi, pg 120, with small correction)

4) Find Least Common Ancestor of 2 nodes in a binary tree
(Karumanchi, pg 126)
https://www.youtube.com/watch?v=13m9ZCB8gjw

5) Find Least Common Ancestor of 2 nodes in a binary SEARCH tree
(Karumanchi, pg 153)

6) Find Shortest path of 2 nodes in a binary SEARCH tree
(Hint: Find LCA and then calculate path from LCA to each node)

7) Determine if a Binary Tree is a Binary Search Tree
http://leetcode.com/2010/09/determine-if-binary-tree-is-binary.html
(Karumanchi : pg 155, prob 52)

8) Serialize and Deserialize a Binary Tree
http://www.geeksforgeeks.org/serialize-deserialize-binary-tree/
http://www.careercup.com/question?id=6228581160058880
http://leetcode.com/2010/09/serializationdeserialization-of-binary.html

8 b) Serialize and Deserialize a Binary Search Tree
https://www.youtube.com/watch?v=H594EV9OuDI
http://leetcode.com/2010/09/saving-binary-search-tree-to-file.html

9) Given a string of html tags like “< a >< b >< c >< /c >< d >< /d >< a >< /a >< /b >< /a >“, construct a tree where each node is like
Node { string tag, ArrayOfChildren[] };
Note that the tree need not be binary tree.
This was asked in SugarCRM.

 


BuildTree(root, parent) {
   tag = readTag(); // assume function readTag will output each tag serially 
   if (isOpenTag(tag)) {
       node = new Node;  // create a new Node
       node.tag = tag; 
       Stack.push(node); // push into stack 
       if (root == NULL) { 
           root = node;  
       } elseif (parent != NULL) {
           AddChild(parent, node);
           BuildTree(root, node);  // Build tree with node as parent 
       } else {
          // error
       }
   } else {
       temp = Stack.pop();
       if (Stack.NotEmpty()) { 
          parent = Stack.pop; 
          BuildTree(root, parent);  
       }
   }
   return root; 
}

Find Longest Palindrome in a string

Find longest palindrome in a string.

Brute Force: N^3

Below Method by Dynamic Programming is N^2. Video for below method:
https://www.youtube.com/watch?v=obBdxeCx_Qs

There is another algorithm called Mancher’s Algorithm which is in linear time.

Note that here since we are dealing with single string we just need to populate top triangle of matrix. In longest substring since we were dealing with 2 strings we populated the whole matrix.

$str = "BANANA";
$len = strlen($str);
$matrix = array();
$palindromeBegins = 0;
$max = 1;

// single letter palindromes
for ($i=0; $i < $len; $i++) {
    $matrix[$i][$i] = 1;
};

// 2 character palindromes
for ($i=0; $i < $len-1; $i++) {
    if ($str[$i] == $str[$i+1]) {
        $matrix[$i][$i+1] = 1;
        $max = 2;
        $palindromeBegins = $i;
    }
}

// 3 character and above
for ($curr_len=3; $curr_len <= $len ; $curr_len++) {

    for ($i=0; $i < $len-$curr_len+1; $i++) {
        $j = $i+$curr_len-1;
        // 1. first and last chars should match
        // 2. rest of string from previous calculations should be a palindrome
        if (($str[$i] == $str[$j]) &&
            ($matrix[$i+1][$j-1] == 1)) {
            $matrix[$i][$j] = 1;
            $max = $curr_len;
            $palindromeBegins = $i;
        }
    }
}

echo "Max Palindome: $max\n";
echo "Palindrome: " . substr($str, $palindromeBegins, $max);
echo "\n";

Another approach:
http://krenzel.org/articles/longest-palnidrome