CareerCup

My answer:
Well the idea is to 1st process all node whose in-degree is 0. Then keep processing newly added nodes whose in-degree 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 in-degree is 0) to a ready-process-queue
- Either use SMP or Master-Slave architecture to assign processing of each node present in the ready queue.
- For efficient tracking of changing in-degrees, 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 in-degree has become 0) rather than staying in a busy-wait loop.

The interviewer shared how people would use this approach, and how computationally intensive it is. Better go the route of sorting to create a unique 'key' for all anagrams.

Nice solution.

@Mukesh
Read the answer completely. He said end the loop after N iterations.

At 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)

Your solution works, but needs to traverse the tree twice.

Your algorithm does not work for cases like: (a*b)+c, where the parenthesis around a*b is un-necessary

Isn't the question same as asking find the kth largest element in the sorted matrix, where k happens to be (N^2)/2 in a NXN matrix.
Time complexity: N^2 * log 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)

This approach fails in below case:
abcdecba

Both the original strings suffix array, and inverted one'ss will have a entry that has a prefix of 'abc'...but this does not mean that they form a palindrome

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

Nice approach.
But this only works if we are getting bits from MSB to LSB, but what if the bit stream is from LSB to MSB?

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.

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)

This approach does not work when, say root only has right sub-tree.

Assuming that both statements are correct, then in the 1st one i is a pointer which can be casted to int *. In the second one i is an integer (or any variable whose address can be casted to int *.

Assuming that both statements are currect, then in the 1st one i is a pointer which can be casted to int *. In the second one i is an integer (or any variable whose address can be casted to int *.

Wont a simple Buddy system work??
Google Buddy memory allocation. In my view this is the easiest solution which can be programmed during an interview.

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.

why is this down voted?? This approach works

Good luck with finding 26 primes in an interview!!!
Hashing does not take O(N), we just need to keep track of 26 values, a single integer would do if you use bitmap.

nice solution

Do we want sub-sequence or subarray?

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();
}

Nice approach. But we need not calculate values for all i. Instead it is sufficient to find n/2 numbers whose sum is as close as possible to total/2. So the time complexity is C(N,N/2)

Please ignore this solution, I just realized my mistake.

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=height-baseY;
  cout << node->val << ": (" << x << ", " << y << ")" << endl;
  printCoord(node->right,height+1);
}

Initialize baseX, and baseY to -1
Do and inorder traversal, and when processing a node its X and Y co-ordinates 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=height-baseY;
  cout << node->val << ": (" << x << ", " << y << ")" << endl;
}

@sahil
the answer should be
root - 0,0 - as it is the left most node
root's right child - (-1,-1)

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

Buddy system

1-50: use BFS

51-100: infinity unless any constraints are placed

On a side note I think single linked list with random pointers (ladder, snake) might be a good DS to represent snake and ladder board.

The maximum virtual memory that can be allocated depends on the address space that's available. Say you are running a 32 bit processor and have 2GB RAM, then the maximum you can allocate is 2GB.

The maximum virtual memory that can be allocated depends on the address space that's available. Say you are running a 32 bit processor and have 2GB RAM, then the maximum you can allocate is 2GB.

Use buddy system

@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 re-populate my set and advance to 'c'; which essentially tells me that the permutation of 'abc' is not present. Am I missing something obvious??

c-sharpcorner.com/Blogs/9782/differences-between-hashtable-and-dictionary.aspx

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

Inorder takes O(N) time, where as solution by JSDUDE is O(logN)

Trie is how routing tables are stored. Best part about trie is there is no wasted space. And at each iteration (byte) you only bring in corresponding subtree into memory

Probably would not work for 4, 3, 2, 1

Nice solution. You are however not checking for diagonal conditions though :)

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

This can be done in O(N) if we maintain a minHeap with the values in Count array, only when they are not -1 (i.e a heap of all the previously seen indices)
The best case complexity is O(N)
Worst case: O(N Log |T|)

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

Use the below recurrence

F(N) = Max (F(N-1)+1, 2 * F(N-3))

The base cases are: F(1)=1, F(2)=2, F(3)=3

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.

This does not work say when the unique number is obtained from ORing the other numbers.
Example: {1,4,5,1,1,4,4} does not give you the right result