Sugarcane_farmer
BAN USERI am a sugarcane farmer from west UP, India
I cut and grow sugarcane very good.
 1of 1 vote
AnswersPrint permutations of a string.
 Sugarcane_farmer in India
I started with the recursive answer. He asked me the complexity. (Had no idea). But is was large
Then he asked me, if i could optimise it. I said i could sense this can be done using DP. Could not get how to do it though.
I had quick perm code, but dint understand it(saw it night prev to interview) so dint answer that. Report Duplicate  Flag  PURGE
Amazon SDE1 Algorithm
This is not iterative
 Sugarcane_farmer June 02, 2014Add prune step, if y<x return true; :)
 Sugarcane_farmer June 01, 2014Last two points are not correct. If by sibling you mean the node that is in same level and comes before this node in level order traversal consider this tree
12
/ \
10 11
/ \
6 9
/ \ \
2 5 8
/ / \ \
1 3 4 7
Here sibling of node 3 is 1. But pred is 2. I think for any target node, if v is a ancestor which has a left child, lc, then lc will be the pred
 Sugarcane_farmer May 30, 2014Two points are colinear if they
1) pass through same point.
2) Have same slope.
pick one point and calculate slope of each point w.r.t this point. Store all these in an array. Sort this array. find duplicates. (there will be different sets). each set will be of collinear points. (Since we have calculated this wrt one point the first condition is prechecked)
Second part is tough man
It is 'if' not 'if else'
 Sugarcane_farmer May 19, 2014Though i highly doubt Msoft would ask this..
but why do u traverse the whole matrix Simply this would do
string diagonal1="";
string diagonal2="";
for(int i=0;i<n;i++)
{
cout<<a[i][i];
cout<< a[n1i][i];
}

Sugarcane_farmer
May 18, 2014 Yes. It seems very simple.
1. Represent nodes in adjecency list. Keep a bool visited[total_nodes] array. Initially all values set to false.
2. Write a dfs function for a given node.
signature: bool Print_cycle(int node_number)
2. call above Print_cycle in a function say Make_work_Disjoint. In this iterate on visited[] and call Print_cycle for every node which is not visited.
I think N,M would also be coordinates. N(x1,y1) and M(x2,y2)
 Sugarcane_farmer May 17, 2014Very good explanation
Basic funda
1. Search on keys
2. balancing on frequency
h t t p www geeksforgeeks org/dynamicprogrammingset24optimalbinarysearchtree
If you notice the reason we go to each node is because we dont know in which subtree, left or right will nth fall. This wasteful traversal causing O(n)
Well if you modify the data structure and save number of left and right child and assume that it is kind of balanced tree in average case then you can do something near to O(logn).
I think the interviewer was looking if you could come up with this idea.
In an interview i would give three successive solutions
1. O(n2) .
Iterate and create a duplicate list with arbit pointing to null.
for each node in copy search in original and fix arbit.
2. Since in above the complexity is because of search. Use Hash map. So complexity is O(n) and space O(n)
3. The best solution as given by anirban.
{([}]) is not a right test cae
@IAmIronMan You cannot maintain a last_parantheses variable. Suppose your expression is { ( [ ] ) }
after [ your last parantheses will be [ . When you see ] you can check that this is fine. But what will you reinitialize last parantheses to after this step?
Basically an insertion sort kind of thing running everytime a[i]<=0
 Sugarcane_farmer May 14, 2014C++ code:
bool ensure_all_even_odd(char arr[], int n)
{
if(n==1 && arr[n1]%2 == 0)
return true;
else
return false;
int even=0;
int odd=1;
while(even<n && odd<n)
{
while(even<n && arr[even]%2 == 0)
{
even+=2;
}
while(odd<n && arr[odd]%2 == 1)
{
odd+=2;
}
if(even < n && odd <n)
{
SWAP(arr[even], arr[odd]);
}
}
return true;
}

Sugarcane_farmer
May 14, 2014 If a list is such that L1 = A>R>K>M (eg A can be completed if R is completed, R can be completed only if K is completed etc.)
Then L3 can never be completed because of the cycle?
What am i missing?
will you be iterating the array (a,b,a,a,a) multiple times?
I dont see what you want to do
I dont think it is possible if the link list has values which are not sorted. I can think by inplace sort it means the node is heavy and create a 'key' array and sort it in O(nlogn) and then rearrange. Or maybe hash the keys and then point them. So a hashtable of only keys will still be required.
 Sugarcane_farmer May 13, 2014I dont understand what you are doing. It says that you have to populate high pointers. So we can assume they all point to null or random junk. So after say 5th node is minNode. so its high pointer points to null. Hence minNode>high will be null and your second loop won't execute.
 Sugarcane_farmer May 13, 2014adding few things
1. It must be lightweight in itself
2. Must be able to get added in browser as a plugin so that it is picked whenever a download starts.
3. Must be world ready so that a user in Japan can also use it without a hastle
Open Chat in New Window
Its really irritating how people just paste code without explaining what they are doing
 Sugarcane_farmer June 22, 2014