Rotate an n sized array by m
1) Method-1 : Use temp array
2) Method-2 : Rotate one by one
3) Method-3 : Rotate by GCD
http://www.geeksforgeeks.org/array-rotation/
4) Method-4 : Reversal algo
http://www.geeksforgeeks.org/program-for-array-rotation-continued-reversal-algorithm/
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;
}
$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";
}
}
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)
}
Sorting :
O(n^2) : Bubble Sort, Selection Sort, Insertion Sort
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;
}
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
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.
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.
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;
}