CareerCup

Treat the given matrix as graph where a point will have a connection to its neighbours iff the adjacent point is 1. Using BSF/DSF we can find the path from given point to other point.

The question is to find the maximum steps we can go.
If there exists an integer solution to quadratic equation(as you mentioned), then we can skip the first step to escape on landing kth step.
Then the solution would be something like follows.
1+2+...x = k --> solve this, if there exists integer solution, answer would be n(n+1)/2 -1 else, n(n+1)/2

Here we have to consider 2 things.
- N is too big number
- Interview is more interested on quick updating of values.

In minHeap, how do you update the existing node somewhere in the middle of tree?

We can have a lock for some time(T) whenever someone adds an item to cart. Before any item is being added to cart, we check whether the item is not locked.

We can define the time T based on the demand. On bonanza sale, the time T would be very less.

It would be better not to change the question. If needed, you can edit/add more information to the existing question, but don't change it. If needed, you can always add a new question. It doesn't make sense for people whoever looks at the answer now.

Say n is the number of highly rated books we are looking for and V is the number of vertices, E is the number of edges in the graph.

While running BSF, we should maintain minHeap(at max size of n). When ever we encounter a book with rating more than the min of heap tree, replace it with top.

Complexity: O((E+V)logn)

Do we really require to check all the previous matches when we select a new word. It follows transitive closure. I mean...when MatchedCharsAnswer(W1)=M1, then we should search for a word W2, whose MatchedChars(W1, W2) >=M1 then MatchedCharsAnswer(W2)>=M1.

Though this works perfectly, I guess interviewer is looking for something better as the array is sorted.
BST approach works better.

@CollinSchupman : read the answer correctly... "keep popping from the stack till value of stack top is more than current node. Then make current node the right child of last popped element" --> while inserting '6' , you pop till stack top is 10, and last poped element is 5, make '6' as right child of '5' and push '6'.

@Nan :
It works fine. Do it on paper, u'll get.
When 12 comes, 10 will be poped and made 12 as right child of 10. when 14 comes, 12 will be poped and made right child of 12.

@Chris :
It is sequence .. not max block. so the ans will be 2nd one.

@Chris :
Nice. But, the above algo takes O(m^2*n^2) right ? We are basically searching for the longest sequence from all possible places ..
Can't we do any optimization here? I feel if we apply DP, we can do this in O(m*n) time. Any way we are using extra space.

it can be both horizontal and vertical.

@Loler : I understood the above logic ..
but I didn't get how u come to know it is "r choose t" ? By just looking at, I couldn't get the idea of "r choose t" .. Can u pls explain ?

what r u doing ?
where are u comparing sum with k...

This approach gives false positives ..
Ex:
123, 132 --> don't form same BSTs but , sorted order is same....

quick sort works .. but there is a catch ..
For the first time, we take first element as pivot from both arrays and divided the arrays..
For the 2nd iteration onwards, we have to take the same element as pivot in both arrays .. this needs O(n) time or we have to do some kind of pre-processing ...

Second approach is not accepted as it was stated in the question itself that we should give answer without constructing BSTs.

Take first element as root and insert from then onwards in BST...
Ex:
A1[]={2,1,3}
2
1 3

A2[]={2,3,1}
2
1 3

@Gabriel: your idea is good .. but there is a catch..
In the above example, it worked because , all the persons are needed to move in continuous floors. What if they are not continuous ?
Ex: F[1]=P[2],F[2]=P[6],F[6]=P[1] etc....
here the above one is a connected component .. as per u'r algo .. 3 lift movements are sufficient.. but actually ..1+4+5=10 lift movements(Initially lift position is at Floor 1).

#of persons = #of floors

yes. what u said is correct.. but, will it give minimum travelled distance by lift ?

input is person's tag number(to which floor he has to go) and current floor(in which floor he is now).

I think ans is 4..
b shifted by 1
c shifted by 1
d shifted by 2.
If this is correct ans, then it can be done in O(n^2) time .. if we take an array of 26, then it can be done in one scan O(n).

small modification is needed ..
if we can't able to find a word at some point of time, we have to discard the latest word which we committed ....and go with other alternatives ... recursion is the best way to do this...
And for searching whether the word is present with some letter or not, trie is the best suitable data structure(searching can be done in amortizedO(1))....

If someone gives best psuedo code .. that will be appreciated :)

@EJ : condition mid==0 is needed ..
take this case .. low=0,high=1 ==> mid=0 and a[mid]==1 then this condition is needed.

@srikath.mujjiga : This works with one element also.. when there is single element .. a[]={0} or a[]={1}..
low=0,high=0, mid=0.
In first case,
binSearch(a, mid + 1, high); will be executed and return -1.
In second case,
if (a[mid] == 1 && (mid == 0 || a[mid - 1] == 0)) will be true and return index 0.

small correction needed..
here
b=c-1; and c has to start from size-1 to 0;
since a^2+b^2=c^2 ... only when c>a &c>b;

@Nbob : ideally we should not maintain m_level in class...
we can print level by level without maintaining this also ..
push a dummy node each time u push all the friends of a member node.... while pop() ing, when ever we come across dummy node .. means we have covered a level ...

maintain 2 tries.. one for names and one for phone numbers...so while we are typing a phone number, we can give matched names up to typed numbers...

why to use space.. as it can be done in O(m+n) without any space... already this solution is suggested above.

yes, its just intersection which takes O(n) where n is the number of friends each one has.
All nodes are white colour.
Mark each friend of A as black and while visiting the friends of B, if any one the friends is black, then he/she is a mutual friend of both. ---> O(n) where n is avg. number of friends one has.

By intuition, we can say ab>ba, bc>cb, then ac>ca...
can any one give mathematical proof for this ?

This is just sorting algo (descending order ).. the only modification we need to do is .. while comparing 2 integers , we have concat one with other and compare ....
ex: {9,10} --> then while comparing 9 and 10 .. we have concat these two...910 > 109 ... so 9 comes before 10
Ex: {9,900}--> 9900>9009 --> 9 comes before 900..
Ex {10,107} --> 10710 > 10107 --> 107 comes before 10....

here k=2.
kd tree =k dimensions tree..

This is basically a K-nearest neighbours search .
Build a tree as in K-d algorithm on world's long/lat arraylist.
when an amazon long/lat point is given, search for that element in tree and find K nearest neighbours.

But, here we don't know the end time. we have to chose which one is end time and which one is start time optimally... that is the problem here .. I don't think this is good way to think for solution.

if we treat the matrix as a graph.. which has connections from every [i][j] to [i+1][j],[i+1][j+1],[i+1][j-1]. find the shortest path from given [i][j] where the weight of the edge is negative of value at respective place..

@Lybo : As per question .. rows are sorted

We need to convert this into prefix or postfix expr .. it will be easier to tackle precedence and associativity of operators.
Then using stack, expr. evaluation can be done in O(n) time .. total complexity is O(n).

@ kamy : r u taking care of operator precedancy ?
Ex : 5+(3*4+5) , 5+(3+4*5) .. u follow the same procedure for these two ..
and also u'r algo fails if it doesn't contain any paranthesis ..
Ex: 5+6

maintain 2 hashmaps on each set. when ever a element comes from set s1, check whether the element already exists in s2, if not keep in union set.

Here s1 and s2 are sets . union also should be a set .. means all the elements in set should be unique.

@startup : if u know the answer, why don't u write u'r algo here. Others will learn. Please write algorithm not code

@ anshul : r u sure that seek() gets its functionality done in O(1) time.

@mavrick :As per the question, we can't store the whole file in RAM, How can we save B-Tree in main memory.

@anushul : r u sure ,if we write a word in position 0 every time in a file, it will be added to file without overwriting on the existing word?

draw on paper as per co-ordinates to understand the problem better ..
ex: (5,10,25) ==> 4 co-ordinates of rectangle will become(x,y)=> (5,0),(5,10),(30,10),(30,0).

I don't think this is a good solution. Problem already stated that the file is very big. means we may have some millions of words. Creating some millions of tmp files is not good .. and even OS has a limitation of allowing these many files to create.

@anthony: UTF16 Encoding represents 1,112,064 characters.

it will take O(n^2) time in worst case.
what if the number we are searching for, is not present in the matrix?

How can we implement counting sort if the range of the numbers is too high.Ex: {1,999999,4}