IntwPrep
BAN USERAt each node check the balanced property, and quit when found a node that does not satisfy it.
bool isBalanced(Node *node, int &height) {
int hleft, hright;
bool lBal, rBal;
if (!node) {
height=0
return true;
}
lBal=isBalanced(node>left, hleft);
if (!lBal) return false;
rBal=isBalanced(node>right, hright);
if (!rBal) return false;
height=max(hleft,hright);
return true;
}
Time complexity: O(N)
Space complexity: O(N)
From above comments looks like O(n^2) is the best approach. If so wont it be simpler to check each subarray, of the given string, for palindrome.
for(int i=0; i<str.length(); i++)
for(int j=i; j<str.length(); j++)
if (isPalindrome(str.substring(i,j)) cout << str.substring(i,j)

IntwPrep
December 05, 2013 1) Build an index array for each character, say if index[a]=3,9,10 then character 'a' is present as 3rd, 9th and 10th character in the given string.
2) Now sort the given string
3) Scan the given string and whenever you encounter a sequence then use recursion to see even if their indexes can be consecutive. If yes then keep track of the largest interval.
Recursive procedure to check if indexes are consecutive:
1) Use recursion to build various combination of indexes of each character. Say we are looking at indices of characters 'a','b','c','d', then we build a set of 4 indices where each element is taken from index[a], index[b], index[c], index[d]
2) Now sort this set. If it contains consecutive numbers (indices) then return true
Datastructure is a struct of the below form
struct Node {
Image value;
Node *left,*right,*top,*bottom;
};
Assumption: existence of a method isNeighbor(Node *A, Node *B) which checks if B is the neighbor of A and assigns the A's pointer accordingly
Algorithm:
1) for each piece B
a) if 1st piece, initialize node and continue
b) for each node A that is already created
i) call isNeighbor(A,B)
2) The only node that does not have a top and left pointers set is the top left corner square, and from it we can traverse the picture.

IntwPrep
December 04, 2013 A simple approach would be is look at it as printing the 1st and last node at each level, and also all the leaves.
Algorithm:
1) Find the height of the tree. Say H. Then initialize two strings level[H][2], and leaves[2^H] arrays to NULL
2) Do a DFS by keeping track of the height and at each node X, say at height h
a) if level[h][0] is NULL then level[h][0]=X
b) else if X is a leaf then leaves.append(X)
c) else level[h][1]=X
3) Once done with the DFS then print nodes in level[h][0] (marks the beginning node at each level), then nodes within leaves array, and then those in level[h][1] (marks the last node at each level)
Time complexity: O(N)
Space complexity: O(N)
Total amount is X
Total loosing moves are N
To survive these N loosing moves and still have some cash left, the amount we can bet on a move is X/(N+1)
Therefore at each stage of the game we bet X/(N+1) amount, where X is the total amount left after each move, and N is the number of loosing cards remaining in the deck.
An attempt for log N solution (for sure in best case, but unable to prove for worst case)
Algorithm:
curNode=root
while(true) {
print curNode value if the level is not already processed, mark this level as done
if (curNode>left) && (curNode>right) {
stack.push(curNode>left);
curNode=curNode>right;
}
else if (curNode) curNode=(curNode>left?curNode>left:curNode>right)
if (!curNode && !stack.isEmpty() && notAllLevelsProcessed) curNode=stack.top(); stack.pop();
}

IntwPrep
December 02, 2013 Below is a linear algorithm
void sortOnBits(int N) {
int maxBits = ceil(log N);
int mask=0;
for (int i=1; i<=maxBits; i++) {
mask=(mask<<1)1;
if (mask>N) break;
temp=mask;
while(temp<N) {
cout << temp;
temp=temp<<1;
}
}
}
Logic:
 Print all numbers that have one bit set, then two bits and so on
 To get the numbers in increasing order which have the same number of bits set, we start by initializing the least significant bits, and then keep shifting right until N
In my above code forgot to add the recursive call to right Child. Here is the corrected code:
int main() {
printCoord(root,0);
return 0;
}
void printCoord(Node *node, int height) {
if (!node) return;
int x, y;
static int baseX=1;
static int baseY=1;
printCoord(node>left,height+1);
x=baseX+1;
if (baseY==1){
y=0; baseY=height;
}
else y=heightbaseY;
cout << node>val << ": (" << x << ", " << y << ")" << endl;
printCoord(node>right,height+1);
}

IntwPrep
December 01, 2013 Initialize baseX, and baseY to 1
Do and inorder traversal, and when processing a node its X and Y coordinates are computed as:
X = baseX+1
if (baseY==1)
Y=0; baseY=height_of_node;
else
Y=height_of_node  baseY
Implementation:
int main() {
printCoord(root,0);
return 0;
}
void printCoord(Node *node, int height) {
if (!node) return;
int x, y;
static int baseX=1;
static int baseY=1;
printCoord(node>left,height+1);
x=baseX+1;
if (baseY==1){
y=0; baseY=height;
}
else y=heightbaseY;
cout << node>val << ": (" << x << ", " << y << ")" << endl;
}

IntwPrep
December 01, 2013 All three operations (insert, delete and getRandom) can be done in constant time O(1), if the order of the elements is irrelevant
Data structure: Array, and HashTable which holds the value as key and index as value
Insert (X):
 push X as the last element in the array, update hashTable
 increment array size
Delete (X):
 get index of X
 swap it with last element in the array, say Y
 update index of Y in hash table to index(X)
 delete X from array and hash table
 decrement array size
getRandom:
generate a random index less than array size, and return value in that index
Big int is 123456 is represented as a[0]=6, a[1]=5...a[5]=1
int genMod(byte *a, int start, int end, byte *b) {
byte number=b[0]+(10*b[1]);
if(start>end) return;
elseif (start=end) return a[start]%number;
int temp = a[start]+(10*a[start+1]);
temp = temp%number;
return (((genMod(a, start+2, end, b))*(100%number))%number + temp)%number;
}
Logic: 123456 % 45 = (1234*100+56)%45 = (((1234%45)*(100%45))%45 + (56%45))%45
 IntwPrep December 01, 2013@Loler and @showell
will this solution work if we are looking to find 'abc' within 'abac'
With this solution, when I hit the 2nd 'a' within 'abac' I would repopulate my set and advance to 'c'; which essentially tells me that the permutation of 'abc' is not present. Am I missing something obvious??
1) Use BFS to compute all the positions that are reachable from the knight.
2) For each position, store it in a Hash
3) Compute a trie structure when doing BFS, basically is you can reach positions Y and Z from X, then X has two children Y and Z; and also maintain parent pointer for Y and Z which point to X
If the query is if P can be reached, then look the hashtable and return true if present.
If path is requested, then trace the path from P to root (starting position) using parent pointers.
If the query is to
If an expression that has brackets results in the same postfix expression as the one without any brackets. Then all the brackets can be removed.
Algorithm  assuming that brackets are legally placed
1) Compute the postfix expression of the given expression (say STR) with brackets, lets call this postFix(STR) = orgPost
2) For each pair of bracket with STR
a) Remove the pair of bracket and compute STR'
b) if postFix(STR')=orgPost then STR=STR'
3) Return STR
I think what he is trying to do is:
 Maintain two heaps: MinHeap and MaxHeap
 Steps
o Insert first node into MinHeap
o Insert second node into MaxHeap
o From then now, insert X into MinHeap if it is less than the top of MinHeap; if not put it in MaxHeap
o After insertion if the size of the heaps is greater than 1, then remove the top of the bigger heap and insert it into the smaller one
o At any given point the median is top of either heaps if they have equal nodes, or top of the heap that has greater nodes
1) Initialize an array 'Count' of size T to 1, where Count[i] refers to the last seen index of T[i] within S
2) Scan through S, and update Count array, and from the point when all the characters within T are 'seen' and say we are currently scanning S[i] (this is easy to keep track of, say have a counter X which is incremented whenever a value Count[i] is changed FROM 1)
 Get the lowest value within Count array, and subtract it with current index i.
 Keep track of the smallest difference found so far
The BST solution does not work if the conflicting appointment spans over to conflict with further appointments.
Example: (1,4), (2,8), (5,8)
Now you 1st process (1,4) and create a node for it.
Add (2,8) as its middle child
You add (5,8) as its right child
Clearly using your solution (5,8) will not be marked as conflicting even though it is. This BST only gives you conflicting appointments wrt the root node.
Repjuanitajboon, Applications Developer at 247quickbookshelp
Hi everyone, I am from Pelham. I currently work in the Hechinger as Cashier.I like to do creative things ...
Repkristinedavila9, Android Engineer at ABC TECH SUPPORT
I am Kristine Davila Professor and director at Clinical Psychology. Having experience of 6 years in my career. I have ...
RepEdithJHarden, Random at Axiom Sources
Je suis un professionnel de la gestion des soins de santé avec 2 ans d'expérience en supervision d'établissements ...
Repjenniferdray9, Accountant at ABC TECH SUPPORT
Hi I am Jennifer D. Ray from san Diego.Currently i am working as a parts salesperson in Rite solution ...
Reploreleijhansen, Aghori Mahakal Tantrik at ABC TECH SUPPORT
I am Lorelei.I am working in a store as a Bonus clerk promoting the development, and implementation and solutions ...
Repkathyrnunez, Area Sales Manager at Advent
I am manager in a Star Bright Investment Group company. I like to solve puzzles for Has excellent problemsolving and ...
Repmartinskrull, Analyst at A9
Hi everyone, I am from new york,USA. I currently work in the Affiliate Marketing industry. I love all things ...
Repwaynebgrover, AT&T Customer service email at ASAPInfosystemsPvtLtd
I am 31 years old and live in San Jose with my family. I have all types of books and ...
Repmarkemorgan007, Applications Developer at Big Fish
I am Mark From Fresno city in USA.I working as a tour guide and also help for make a ...
Open Chat in New Window
My answer:
 IntwPrep January 17, 2014Well the idea is to 1st process all node whose indegree is 0. Then keep processing newly added nodes whose indegree becomes 0. The main part is coming up with a parallel solution.
Algorithm:
 Dedicate a process to go through the graph and add ready nodes (whose indegree is 0) to a readyprocessqueue
 Either use SMP or MasterSlave architecture to assign processing of each node present in the ready queue.
 For efficient tracking of changing indegrees, maintain a hash<nodeID,indegreeCount>, which is updated for all the outDegree nodes of the currently processed node. Say if we have a link A>B. When processing A we can decrement the indegree count of B.
 Few enhancements are the main process which scans the graph for 0 indegree nodes can be designed to receive a signal when new nodes are ready (whose indegree has become 0) rather than staying in a busywait loop.