$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"; } }

# Category: Algorithms

## How to compare two integers using bitwise operator without using any comparative operator.

1)

int x = 10;

int y = 12;

int z = 0;

z = x ^ y;

If the value of z is 0 then the two integer is equal. If the value is not zero the two integer is not equal.

2)

function isEqual() {

return !(x-y)

}

## Complexity of Algorithms

**Sorting :**

O(n^2) : Bubble Sort, Selection Sort, Insertion Sort

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

## Linked List, Stack, Queue Algorithms

**1) Given a stack how to reverse the elements of the stack using push() and pop() only. **

Karumanchi : pg 91

2) Implement a queue using 2 stacks

Karumanchi : pg 104

3) Implement a stack using 2 queues

Karumanchi : pg 105

## General Algorithm Questions

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.

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