## Expand a random range from 1–5 to 1–7

You have a random number generator between 1 and 5. Make a random number between 1 and 7

```int rand7()
{
int vals[5][5] = {
{ 1, 2, 3, 4, 5 },
{ 6, 7, 1, 2, 3 },
{ 4, 5, 6, 7, 1 },
{ 2, 3, 4, 5, 6 },
{ 7, 0, 0, 0, 0 }
};

int result = 0;
while (result == 0)
{
int i = rand5();
int j = rand5();
result = vals[i-1][j-1];
}
return result;
}
```

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

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

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

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

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)

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 b) Serialize and Deserialize a Binary Search Tree
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.

```

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) {
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:

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