Re: [algogeeks]
on first iteration *ptr == 'h' so it will enter in the loop. ptr++ -- *ptr == 'e'; comparing *ptr with least i.e 127 (ascii) *ptr will be 'e' now; 2nd iteration *ptr == e ptr++ - *ptr = 'l' comparing 'e' with 'l' and 'e' will be assgined to least and so on; coz 'e' has the lowest ascii value in given set of characters so least will never change when first time it is assgined to 'e'; -- Anshuman Mishra | Software Development Engineer | Amazon -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Directi Interview Ques
two arrays are suppose x[n], y[n];
take a function
f( x(i, n), y(j, n) , 0) -- taking x[i] as a first element of merged array
then max sum;
f( x(i, n), y(j, n), 1) -- taking y[j] as a first element of merged array
then max sum;
f( x(i, n), y(j, n) ,0) = max( { x[i] * x[i+1] + f( x(i+1, n), y(j, n),
0) }, { x[i] * y[j] + f( x(i+1, n), y(j, n), 1 ) } );
f( x(i, n), y(j, n) ,1) = max( { x[i] * y[j] + f( x(i, n), y(j+1, n), 0)
}, { y[j] * y[j+1] + f( x(i, n), y(j+1, n), 1 ) } );
final sol = max ( f( x(0, n), y(0, n) ,0), f( x(0, n), y(0, n) ,1) );
Now it's looking a very simple *dp *problem with O(n^2) time and space
complexity. :)
--
Anshuman Mishra | Software Development Engineer | Amazon
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: candies - interviewstreet -- how to go about solving this problem
@sanjay it's not like that e.g : (3 5 6 7 8 4) 7 1 2 3 4 5 1 2 Yes we have to increase just by one, but while decreasing choose the lowest possible such that each trivial component, if it is in decreasing phase, should end with 1. On Mon, Jul 9, 2012 at 12:53 PM, sanjay pandey sanjaypandey...@gmail.comwrote: does ur sol seems lyk incerasing 1 if next number is greater that prev n decreasing 1 if less..??? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anshuman Mishra | Software Development Engineer | Amazon -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MS Design Ques
Best will be storing BIG_INT in array of integers.
int [] val; //store actual number
int size; // required length of val array.
take the string as input for constructors and convert it into 2's
complement form, maintaining little endian order or big endian order.
Perform other operation keeping order in mind.
On Sat, Jul 7, 2012 at 5:23 PM, sravanreddy001 sravanreddy...@gmail.comwrote:
i was thinking of character array. which is same as string.
Any thoughts on better alternatives?
On Friday, 6 July 2012 13:34:01 UTC-4, anshu wrote:
yes, We can have much better data structure for storing big integer
instead of string just for simplicity I have taken string.
On Fri, Jul 6, 2012 at 11:11 AM, Mithun Kumar mithunsi...@gmail.comwrote:
@anshuman...
Are you converting numbers to string because data types ranges
and precision differs? or is there any other reason?
-mithun
On Fri, Jul 6, 2012 at 12:58 AM, payal gupta gpt.pa...@gmail.comwrote:
thnx...4 d rply..
Regards,
PAYAL GUPTA,
NIT-B.
On Fri, Jul 6, 2012 at 12:43 AM, Anshu Mishra
anshumishra6...@gmail.com wrote:
First define all the basic operation you can apply on two numbers.
Binary operation : +, -, *, /, %, optional((and), |(or), ^(xor))
Unary operation : !, ~, -
Comparison : , ==, !=
Define all these operation.
Most simplest one can be,
class BIG_INT {
private string val;
//Define constructor
private BIG_INT(){}
public BIG_INT(int x) {
this.val = x.toString();
}
public BIG_INT(long x) {
this.val = x.toString();
}
public BIG_INT(string x) {
this.val = x;
}
public BIG_INT add(BIG_INT x);
public BIG_INT add(int x);
public BIG_INT add(long x);
similarly write methods for other operation also;
}
If this question asked for only design testing purpose only all method
declaration will be sufficient.
--
Anshuman Mishra | Software Development Engineer | Amazon
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+unsubscribe@**
googlegroups.com algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en
.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+unsubscribe@**
googlegroups.com algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to algogeeks+unsubscribe@**
googlegroups.com algogeeks%2bunsubscr...@googlegroups.com.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en http://groups.google.com/group/algogeeks?hl=en.
--
Anshuman Mishra | Software Development Engineer | Amazon
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/pkUNaazktKAJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Anshuman Mishra | Software Development Engineer | Amazon
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MS Design Ques
yes, We can have much better data structure for storing big integer instead
of string just for simplicity I have taken string.
On Fri, Jul 6, 2012 at 11:11 AM, Mithun Kumar mithunsi...@gmail.com wrote:
@anshuman...
Are you converting numbers to string because data types ranges
and precision differs? or is there any other reason?
-mithun
On Fri, Jul 6, 2012 at 12:58 AM, payal gupta gpt.pa...@gmail.com wrote:
thnx...4 d rply..
Regards,
PAYAL GUPTA,
NIT-B.
On Fri, Jul 6, 2012 at 12:43 AM, Anshu Mishra
anshumishra6...@gmail.comwrote:
First define all the basic operation you can apply on two numbers.
Binary operation : +, -, *, /, %, optional((and), |(or), ^(xor))
Unary operation : !, ~, -
Comparison : , ==, !=
Define all these operation.
Most simplest one can be,
class BIG_INT {
private string val;
//Define constructor
private BIG_INT(){}
public BIG_INT(int x) {
this.val = x.toString();
}
public BIG_INT(long x) {
this.val = x.toString();
}
public BIG_INT(string x) {
this.val = x;
}
public BIG_INT add(BIG_INT x);
public BIG_INT add(int x);
public BIG_INT add(long x);
similarly write methods for other operation also;
}
If this question asked for only design testing purpose only all method
declaration will be sufficient.
--
Anshuman Mishra | Software Development Engineer | Amazon
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Anshuman Mishra | Software Development Engineer | Amazon
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MS Design Ques
First define all the basic operation you can apply on two numbers.
Binary operation : +, -, *, /, %, optional((and), |(or), ^(xor))
Unary operation : !, ~, -
Comparison : , ==, !=
Define all these operation.
Most simplest one can be,
class BIG_INT {
private string val;
//Define constructor
private BIG_INT(){}
public BIG_INT(int x) {
this.val = x.toString();
}
public BIG_INT(long x) {
this.val = x.toString();
}
public BIG_INT(string x) {
this.val = x;
}
public BIG_INT add(BIG_INT x);
public BIG_INT add(int x);
public BIG_INT add(long x);
similarly write methods for other operation also;
}
If this question asked for only design testing purpose only all method
declaration will be sufficient.
--
Anshuman Mishra | Software Development Engineer | Amazon
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Reverse Engg.
awesome question :D :D -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] LCA of a Binary tree not a binary search tree
first try to understand the sol then comment. it is for binary tree not for
BST.
On Mon, Nov 21, 2011 at 10:25 PM, Piyush Grover
piyush4u.iit...@gmail.comwrote:
For BST it would be rather simpler. find the first node which lies in
between the two.
On Wed, Nov 16, 2011 at 1:44 PM, anshu mishra
anshumishra6...@gmail.comwrote:
Node *LCA(node *root, node *e1, node *e2, int x)
{
Node *temp =NULL;
Int y = 0;
If (root-left) temp = LCA(root-left, e1, e2, y);
x+=y;
if (temp) return temp;
if (x==2) return node;
y = 0;
If (root-right) temp = LCA(root-right, e1, e2, y);
x+=y;
if (temp) return temp;
if (x==2) return node;
If (root == e1 || root == e2) x++;
Return null;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Anshuman Mishra | Software Development Engineer | Amazon
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] LCA of a Binary tree not a binary search tree
Node *LCA(node *root, node *e1, node *e2, int x)
{
Node *temp =NULL;
Int y = 0;
If (root-left) temp = LCA(root-left, e1, e2, y);
x+=y;
if (temp) return temp;
if (x==2) return node;
y = 0;
If (root-right) temp = LCA(root-right, e1, e2, y);
x+=y;
if (temp) return temp;
if (x==2) return node;
If (root == e1 || root == e2) x++;
Return null;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Ques Suggest Algo
index = 0 1 2 3 4 5 6 ar = 0 1 2 -4 -3 6 -3 sumar = 0 1 3 -1 -4 2 -1 first index where we get the number which has already appeared in sumar will be the last index of sub array whose sum will be zero and (index of first apperance of this number + 1) in sumar will be the start index. so start index = 3 + 1 = 4; last index = 6; By set or treeMap we can solve it in O(nlogn) and by hashMap we can solve it in O(n). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array
@Ravindra To check the particular number square can be written as sum of two squares or not. If it has any prime factor x such that x % 4 == 1 then only. Now about time complexity. suppose u have given array is. 10 6 13 9 17 4 18 12 1 5. now u can easily skip the numbers(1, 4, 6, 9, 12, 18); and u have to check only for these numbers(5, 10, 13, 17); so time complexity will reduce to O(n * (number of side which can be largest one for any triplet) ). -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reconstruct BST from preorder traversal
this is an O(n^2) solution. By pre processing the array we can also solve it
O(n)
int find_mid(int ar[], int s, int e, int val)
{
int i;
for (i = s; ar[i] val; i++);
return i;
}
node * constructTree(int ar[], int s, int e)
{
node *root;
root = new node();
root-val = ar[s];
root-left = root-right = NULL;
int mid = find_mid(ar, s+1, e, ar[s]);
if (s+1 mid)
root - left = constructTree(ar, s+1, mid);
if (mid e)
root - right = constructTree(ar, mid, e);
return root;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Reconstruct BST from preorder traversal
@Anand As given it is a BST so any single traversal(pre or post or in) is sufficient to construct the tree. :P -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon Question - Find Pythagorean triplet in an unsorted array
@Ravindra may be the interviewer wants from u that instead of blindly checking for every number. first check that particular number can be written as the sum of two squares or not if yes than only search for that number. So the order will be decrease from O(n^2) to O(n * (number of side which is largest one for any triplet)) and in practical it will be much less compare to O(n^2); -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
If O(k*logk) solution is acceptable then it is very simple.
maintain a min heap.
push a[0][0],
i = 0;
while ( i k)
{
pop an element. --- O(log(i)) -- coz number of elements in heap is i;
push the two adjacent element that is one right and right below. ---
O(log(i));
i++;
}
last element popped will be answer.
size of heap at every iteration will increase by one coz we are inserting
two elements and removing one element at every iteration.
If anyone has doubt on correctness of this solution can ask.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
push the two adjacent element that is one right and below -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Algo for Search in a 2D Matrix
struct data
{
int row, col,
int val;
};
priority_queuedata heap;
now fine?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to Solve This
@amol
I was not sure that for every number that has 3 in its unit place has one
multiple which has all one. So I used that is if the remainder is coming
that already appeared stop there coz it will make stuck in a loop.
for ex. remainders are
1 3 19 23 37 1 3 19 that will repeat.
but it in this case u can remove the set. Code will look more simpler.
string all1Multiple(int x)
{
string s;
int r=1;
do
{
s += '1';
r = r % x;
r = r * 10 + 1;
} while(r != 1);
return s;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] How to Solve This
string all1Multiple(int x)
{
string s;
setint mySet;
mySet.push(0);
int psize, r=1;
do
{
psize = mySet.size();
s += '1';
r = r % x;
mySet.push(r);
r = r * 10 + 1;
} while(mySet.size() psize);
if (r != 1) return not Possible;
return s;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] subset of an array
the simplest code could be for this question is
void printAllSubsetSum(int ar[], int n, int x)
{
for (i = 0; i (1n); i++)
{
int sum = 0;
for (j = 0; j n; j++)
{
if ( (1 j) i) sum += ar[j];
}
if (sum == x)
{
for (j = 0; j n; j++)
{
if ( (1 j) i) printf(%d , ar[j]);
}
printf(\n);
}
}
}
Time complexity O(2^n)
this can be solved using DP in O(n * given number);
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Algo
wat is ur question finding maximum path sum or anything other than this? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Tree Center Problem
do this way. start with any node(k) calculate sk = sum(k, i) for all i 0 = i n; and u can easily get sj = sum(j,i) where j is adjacent to k; in O(n); suppose nj = number of nodes remains after removing edge(j,k) in subtree containing node j; suppose nk = number of nodes remains after removing edge(j,k) in subtree containing node k; sj = sk - nj * edgecost(j,k) + nk * edgecost(j,k); traverse the tree in bfs or dfs manner. maintain a minsum at every node compare it and modify accordingly. for ni (for all 0=i n) you have to preprocess the tree and u can get all in O(n); avgcost = minsum/n; -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem??
int count(int x, int tree[], int s, int e, int n)
{
tree[n]++;
if (s==e) return 0;
int cnt = 0;
int mid = (s+e)/2;
if (mid x) return tree[2*n+1]+count(x, tree, mid+1, e, 2*n+2);
else return count(x, tree, s, mid, 2*n+1);
}
main()
{
for(i=n-1;i=0; i--)
{
sol[i] = insert(ar[i], tree, 0, n-1, 0)
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: best way to learn data structure
In which year you are now. May i can give you some idea. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem??
use segment tree or binary index tree to solve O(nlogn) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Find lowest common ancestor of Binary Tree
node* LCA(node *root, node *n1, node *n2, int x)
{
int y = 0;
node *temp;
if (root-left) temp = LCA(root-left, n1, n2, y);
x += y;
if (temp != NULL) return temp;
if (x == 2) return node;
if (root-right) temp = LCA(root-right, n1, n2, y);
x += y;
if (temp != NULL) return temp;
if (x == 2) return node;
if (root == e1 || root == e2) x++;
return NULL:
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: MS Question - Median of a BST without using extra space and in O(n)
*@all to median of BST time O(n) space O(1) (modified code of nitin to get median) medianBST*(node, n) int x = 0; *while* hasleftchild(node) *do* node = node.left *do* x++; if (x == n/2) return node-val; *if* (hasrightchild(node)) *then* node = node.right *while* hasleftchild(node) *do* node = node.left *else* *while* node.parent ≠ *null* *and* node == node.parent.right *do* node = node.parent node = node.parent *while* node ≠ *null* @dheeraj u U can get the number of elements by just traversing the who tree by above method -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] doubt???
You cant do. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MS Question - Median of a BST without using extra space and in O(n)
do the inorder traversal as soon as reached at n/2th element that will be median. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MS Question - Median of a BST without using extra space and in O(n)
int bstMedian(node *root, int n, int x)
{
if (node-left) return bstMedian(root-left, n, x);
x++;
if (x == n/2) return node-val;
if (node-right) return bstMedian(root-right, n, x);
}
call bstMedian(root, n, 0);
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: MS Question - Median of a BST without using extra space and in O(n)
its not o(n) it is O(max height of tree) :P i have not seen the constraint. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks]
suppose adress of a = 0x12; 0x12 has 0x13 has 0001 so p = 0x12; p++ = 0x13; now modifying the value pointed p by will modify the only 0x13 bcoz it is char type pointer and its value wiil be 0010 so finally 0x12 to 0x15 will have 512 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: What is the time to get min element from the binary max heap !!
If we know the size of heap we can get the minimum element in O(n);
int findMinFromMaxHeap(int ar[], int n)
{
if ( (n+1) n == 0)
{
for (i = n1; i n; i++)
min = min ar[i] ? ar[i] : min;
}
else
{
int x = n, y = 1;
while(x 1)
{
y = 1;
x = 1;
}
y -= 1;
x = (n - y + 1) / 2;
for (i = y / 2 + x; i n; i++)
min = min ar[i] ? ar[i] : min;
}
return min;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon SDE onsite interview question
explanation: Node : lock - that node is locked or not; lockedDesc - number of descendents locked of that node left, right,par as name sugest; unLock(): when we unlock a node than all its ancestor has to decrease its lockedDesc value by 1. Lock(): when we lock a node than all its ancestor has to increase its lockedDesc value by 1. I hope now it should be clear. :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Function pointer
as function object also -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Array A and B
you can use mergesort technique, segment tree, binary index tree or BST -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon SDE onsite interview question
for simplicity i doing it for binary tree
struct node
{
bool lock;
int lockedDesc;
node *left, *right, *par;
};
bool Islock(node *cur)
{
return cur-bool;
}
void unLock(node *cur)
{
node *temp;
cur-lock = false;
temp = cur-par;
while (temp != NULL)
{
temp-lockedDesc--;
temp = temp-par;
}
}
bool Lock(node *cur)
{
if (cur-anydesc) return false;
node *temp = cur-par;
while (temp != NULL temp-lock== false)
{
temp-lockedDesc++;
temp = temp-par;
}
if (temp == NULL)
{
cur-lock = true;
return true;
}
cur = cur-par;
while (cur != temp)
{
cur-lockedDesc--;
cur= cur-par;
}
return false;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Amazon SDE onsite interview question
for simplicity i am doing it for binary tree (liittle modification)
struct node
{
bool lock;
int lockedDesc;
node *left, *right, *par;
};
bool Islock(node *cur)
{
return cur-bool;
}
void unLock(node *cur)
{
node *temp;
cur-lock = false;
temp = cur-par;
while (temp != NULL)
{
temp-lockedDesc--;
temp = temp-par;
}
}
bool Lock(node *cur)
{
if (cur-lockedDesc) return false;
node *temp = cur-par;
while (temp != NULL temp-lock== false)
{
temp-lockedDesc++;
temp = temp-par;
}
if (temp == NULL)
{
cur-lock = true;
return true;
}
cur = cur-par;
while (cur != temp)
{
cur-lockedDesc--;
cur= cur-par;
}
return false;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] MICROSOFT WRITTEN IN VASAVI
void allCase(string r)
{
int n = s.sise();
string s;
for (i = 0; i (1 n); i++)
{
s = r;
for ( j = 0; j n; j++)
{
if ( i ( 1 j) )
{
s[j] = s[j] + ('a' - 'A');
}
}
cout s endl;
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: convert a word into a palindrome with minimum addition of letters to it
http://www.spoj.pl/problems/AIBOHP/ same problem u have asked!! -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding Blocks in a matrix
@ akash solution is complete. :P first try to understand the solution. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding Blocks in a matrix
@ross no, a particular element has to read only 5 times maximum. 1 reading (i,j) (if its flag is already false skip) 2 read by top element 3. read by bottom element 4 read by left element 5 read by right element coz atleast one of the this operation its flag will be unset(false), then we have to just skip it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: A Graph Problem
biaprtie graph is special case when we can color the whole graph just by two colors. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding Blocks in a matrix
main()
{
for (i = 0; i n; i++)
{
for (j = 0; j n; j++)
{
if (flag[i][[j])
{
bfs(mat, flag, i, j);
count++;
}
}
}
}
bfs(mat[][], flag[][], i, j)
while (!q.empty())
{
x = q.top();
q.pop();
if(node notvisited already adjacent to x value = x)
add to queue
}
}
this is thw whole code
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Binary Tree Problem
this is a very standard problem :D start with any node(x) find the node which is at maximum distance. now start with x travese the tree and find the node(y) which is at maximum distance. so finally answer wil be (x, y) traversing the tree two times. so the order for finiding the such nodes equals to O(n); -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Binary Tree Problem
little modification start with any node(r) find the node(x) which is at maximum distance. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] A Graph Problem
it is exactly a graph coloring problem. so it has no polynomial order solution. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: posix threads
write these three lines in ur function, it will bind that particular thread
to (id)th processor wher
void func(int id)
{
unsigned long mask;
mask = 1id;
pthread_setaffinity_np(pthread_self(), sizeof(mask), mask);
}
main()
{
pthread_t *thread;
thread = (pthread_t*)malloc(8*sizeof(pthread_t));
int ret;
for (i = 0; i n; i++) ret = pthread_create(thread[i], NULL,
(void*(*)(void*))func, (void*)i);
for (i = 0; i n; i++) pthread_join(thread[i], NULL);
return 0;
}
this fucntion will bind ith thread with ith processor.
u can set the mulitple bits of mask that will allow to run particular
thread only on that set of processor.
suppose mask = 101001;
that will allow to run the that particular thread only on 1st, 4th, 6th
processor. if there is 6 processor(core) on ur system.
u can use the TOP command to see the utilization of every core.
Run any highly compute intesive problem (like matrix multiplication) create
as many threads in as many processor in ur system. and the run the program.
open another terminal type top and u can see the utilization of every core
is about 99 to 100%. ;)
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: posix threads
PS dont forget to bind ith thread with ith processor -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding Blocks in a matrix
it is a simple graph problem. travese the whole matrix using BFS. it will be
O(n^2).
for (i = 0; i n; i++)
{
for (j = 0; j n; j++)
{
if (flag[i][[j])
{
bfs(mat, flag, i, j);
count++;
}
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding Blocks in a matrix
@vishal ur sol wil give wrong answer for this 1 1 2 1 3 1 2 3 4 answer should be 6 but ur sol wil give 4. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Finding Blocks in a matrix
@piyush
void bfs(int mat[][n], bool flag[][n], int i, int j)
{
queue.push(mat[i][j]);
while (!q.empty())
{
x = q.top();
q.pop();
add top bottom, left right element in qeuue if their flag is true and their
value is equal to x and mark their flag false;
}
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: sum of two
map is internally implemented with balanced binary tree and inserting in a BST is o(logn); -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Google Interview Question
@all go through this code
#includeiostream
#includealgorithm
using namespace std;
bool compare(int a, int b)
{
string u, v;
u = v = ;
while (a)
{
u += (a % 10 + '0');
a/=10;
}
while (b)
{
v += (b % 10 + '0');
b/=10;
}
int i = 0, j = 0;
reverse(u.begin(), u.end());
reverse(v.begin(), v.end());
while (i u.size() || j v.size())
{
if (i == u.size()) i = 0;
if (j == v.size()) j = 0;
for (; i u.size() j v.size(); i++, j++)
{
if (u[i] == v[j]) continue;
return (u[i] v[j]);
}
}
if (u.size() == v.size()) return true;
}
int main()
{
int n;
cin n;
int ar[n];
int i;
for (i = 0; i n; i++)
{
cin ar[i];
}
sort (ar, ar +n, compare);
for (i = 0; i n; i++) cout ar[i];
cout endl;
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] threading
it is os responsibility to map user level thread to kernel level thread. Usually os implements many to many mapping. In pthread we can bind a particular thread to particular processor or set of processor. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Round Robin Schedulling Problem
@gopi by mistake i have written i in place of IN[i]; my fault, 2nd thing( (F[i].idx - F[i-1].idx - (F[i].rep - F[i-1].rep) ) i have really not think of that. thanks :) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Round Robin Schedulling Problem
first for every element get the number of element before its index have less
value.
example
L[]= 0 0 1 1 3
D[] = 8 1 3 3 8
IN[] = 0 1 2 3 4
you can use segment tree for this it will give solution in o(nlogn);
after that sort the array and start from 0th index
D[] = {1 3 3 8 8}
IN[] = {1 2 3 0 4}
rem = n;
curtime = 0;
last = 0;
for (i = 0; i n;)
ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (i - L[IN[i]] + 1);
i++;
while (i n D[i] == D[i-1])
{
ans[IN[i]] = ans[IN[i-1]]; i++;
}
curtime += (D[i] - last) * rem;
}
finally answer will be solution;
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Round Robin Schedulling Problem
two thing i have forgot do; that is at every iteration rem--; last = D[i-1]; -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Round Robin Schedulling Problem
L[i] tells how many elements D[j] less than D[i] such that j i ;
for this u have to use BIT, segment tree, or any balanced BST(balanced
implies to avoid the worst case that is o(n^2));
rem = n;
curtime = 0;
last = 0;
for (i = 0; i n;)
ans[IN[i]] = curtime + (D[i] - last - 1) * rem + (i - L[IN[i]] + 1);
curtime += (D[i] - last) * rem;
i++;
rem--;
while (i n D[i] == D[i-1])
{
ans[IN[i]] = ans[IN[i-1]] + 1; i++;
rem--;
}
last = d[i-1];
}
curtime = total time till the iteration in which last event(which has burst
time just less than current event) has been completed.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find closest point
@sravanreddy001 u r not at plain surface its sphere :P :D. u have to go by angle -- Anshuman Mishra IIIT Allahabad - anshumishra6...@gmail.com rit2007...@iiita.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find closest point
@sravanreddy001 no u will go from point A to point B by walking on the surface not by making the tunnel in the earth. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find closest point
@piyush suppose A is latitude nd B is longitude, R is raduis of earth z = Rsin(A); r' = Rcos(A); radius of circle at z height; x = r'cos(B); y = r'sin(B); (x,y,z) is coordinate of point assuming (0,0,0) is the center of earth; -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: AMAZON Q
@all
it is simple binary search problem
we can write
f(n) = f(n/2 + 2)*f(n/2) + {f(n/2 + 1)}^2 if n is even similary u can get
formula when n is odd.
f(3), f(4), f(5) f(6)
f(6), f(7), f(8) f(12)
.
.
.
as soon as you got a fibnocci number greater than n suppose p-- than you
have two ranges p, p/2;
now apply binary search in range (p/2 p)
that is cal f(p+p/2) compare the value from n. accordigly move left or
right.
till (p - p/2 != 1)
solution is o(log(n));
hopefully i am clear.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Facebook Interview Question from glassdoor
for 12 answer will be 36? is it ur question? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Facebook Interview Question from glassdoor
the same question i have asked in microsoft interview. (if it is the same
:P)
for 12 perutation are (ad, ae, af, bd, be, bf, cd, ce ,cf);
i have given them 3 solution(recusrsive, stack based) and the last one what
they wanted.
take a tertiary number(n) = 3^(number of digits) in case of 12 it is equals
to 2;
i m solving the save problem. assuming on every key there are only 2
alphabets.
char c[][2] = {ab , cd, ..};
char n[] = 2156169 (number is pressed);
so k = 7;
for (i = 0; i (1k); i++){
string s = ;
for (j = 0; j k; j++){
s += c[n[j]][i (1j)]
}
print(s);
}
same logic u can use for tertiary too.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Spoj Problem Help
@sravanreddy001
suppose u have to calulate A^n u can calculate in O(d^3*log(n));
d is dimesion of matrixl
while (n)
{
if (n1) mul(ans, A, d);
mul(A, A, d);
n =1;
}
--
Anshuman Mishra
IIIT Allahabad
-
anshumishra6...@gmail.com
rit2007...@iiita.ac.in
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Print Subsets
its DP problem can be solved in O(m*n) where m is number of elements in array and n is value of the given number. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: first fit bin packing
void query(int w, int s, int e, int node)
{
if (s==e)
{
tree[node] -= w;
prpogateNewMax(node);
return;
}
mid = (s+e)1;
if (tree[(node1)+1] = w) query(w, s, mid, (node1)+1);
else query(w, mid+1, e, (node1)+2);
}
void prpogateNewMax(int node)
{
if (node == 0) return;
int par = (node-1)1;
int a = tree[(par1)+1];
int b = tree[(par1)+2];
tree[par] = a b ? a : b;
prpogateNewMax(par);
}
Now I think everything is clear. For a single query we have traverse from
root to leaf than leaf to root. total 2*log(n); So finally for n queries
order will be O(n*logn);
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Array problem
@amit ur code is wrong. just check it for this {5, 4, 1, 8, 4, 4};
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Inversion Count
no all these data structure also take time O(nlogn)
solving this problem using segment tree
map all elements to its index on the sorted array.
ex. 2 3 8 6 1 -- 1 2 4 3 0
intialiize all element in segment tree wid zero
start from the last index of array
whenever u visit a node increase its value by 1 -- one more value came in
this range
if u have go right child then increase the count by number of element in
left child(that is value left node). thats it;
void query(int a, int s, int e, int node, unsigned long long count)
{
int mid = (s+e)1;
tree[node] += 1;
if (s == e) return;
if (a = mid)
{
query(a, s, mid, (node1)+1, count);
}
else
{
count += tree[(node1)+1];
query(a, mid+1, e, (node1)+2, count);
}
return;
}
I have written another code using ur logic its giving correct answer. I m
not getting where u r wrong. :P
#include stdio.h
unsigned long long int merge_and_count (int *a, int start, int mid, int end)
{
int len_a = mid - start + 1;
int len_b = end - mid;
int C[end - start + 1];
int k = 0;
int i = start;
int j = mid + 1;
unsigned long long int count = 0;
int rem = len_a;
while ( i = mid j = end ) {
C[k++] = a[i] a[j] ? a[i] : a[j];
if ( a[j] = a[i] ) {
count += rem;
j++;
} else {
i++;
rem--;
}
}
while ( i = mid ) {
C[k++] = a[i++];
}
while ( j = end ) {
C[k++] = a[j++];
}
for ( i = start; i = end; i++ ) {
a[i] = C[i-start];
}
return count;
}
unsigned long long int sort_and_count(int *a, int start, int end)
{
int mid;
unsigned long long int rA, rB, r;
if ( end == start )
return 0;
else {
mid = (start + end) 1;
rA = sort_and_count (a, start, mid);
rB = sort_and_count (a, mid + 1, end);
r = merge_and_count (a, start, mid, end);
} return (rA+rB+r);
}
int main()
{
int t, n, i;
int a[200100];
scanf (%d, t);
while ( t-- ) {
scanf (%d, n);
for ( i = 0; i n; i++ ) {
scanf (%d, a[i]);
}
printf (%llu\n, sort_and_count(a, 0, n - 1));
}
return 0;
}
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Inversion Count
explain your logic instead of posting code, use binary index tree or segment tree or bst to solve this problem. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Amazon Interview Question
@pacific you are perfectly right but the order is not o(kn) its is O(k*n*log(n)) because to get the least number u have to use priority queue nd at every iteration (from 1 to k*n) u have to push and pop one single element. -- Anshuman Mishra IIIT Allahabad - anshumishra6...@gmail.com rit2007...@iiita.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: partitioning the array
@gaurav
f(i, j) = {(total number we need to make sum j including ith number in
array), if its not possible than -1};
f(i, j) = f(i-1, j-ar[i]) + 1 -- if (i-1, j-ar[i]) != -1;
answer will be the largest j for which f(i, j) will be exactly equals to
n/2;
there is something more in this but when you start to write the code you can
easily get that.
https://www.spoj.pl/problems/AMR10D/ a little bit similar problem on spoj.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
