Re: [algogeeks] Facebook Question
Find the distance between each of the points and the origin(0,0) and sort the points based on this distance. Also, divide the points based on which quadrant they belong. If the difference between their distance(from origin) between 2 points is less and they belong to the same quadrant, then they are likely to be close. So, instead of comparing each point with every other point as in the O(N^2) solution. We can compare a given point only with a subset of points that appear to be close. On Wed, Dec 21, 2011 at 1:00 AM, SAMMM somnath.nit...@gmail.com wrote: You are given a list of points in the plane, write a program that outputs each point along with the three other points that are closest to it. These three points ordered by distance. The order is less then O(n^2) . For example, given a set of points where each line is of the form: ID x-coordinate y-coordinate 1 0.0 0.0 2 10.1 -10.1 3 -12.212.2 4 38.3 38.3 5 79.99 179.99 Your program should output: 1 2,3,4 2 1,3,4 3 1,2,4 4 1,2,3 5 4,3,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. -- 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 Question
Yup, it could be O(n^2) in the worst case. On Wed, Dec 21, 2011 at 1:59 PM, Carol Smith carol.interv...@gmail.comwrote: @Algoose, in worst case, this is still O(n^2), ain't it? On Wed, Dec 21, 2011 at 12:50 PM, Algoose chase harishp...@gmail.comwrote: Find the distance between each of the points and the origin(0,0) and sort the points based on this distance. Also, divide the points based on which quadrant they belong. If the difference between their distance(from origin) between 2 points is less and they belong to the same quadrant, then they are likely to be close. So, instead of comparing each point with every other point as in the O(N^2) solution. We can compare a given point only with a subset of points that appear to be close. On Wed, Dec 21, 2011 at 1:00 AM, SAMMM somnath.nit...@gmail.com wrote: You are given a list of points in the plane, write a program that outputs each point along with the three other points that are closest to it. These three points ordered by distance. The order is less then O(n^2) . For example, given a set of points where each line is of the form: ID x-coordinate y-coordinate 1 0.0 0.0 2 10.1 -10.1 3 -12.212.2 4 38.3 38.3 5 79.99 179.99 Your program should output: 1 2,3,4 2 1,3,4 3 1,2,4 4 1,2,3 5 4,3,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. -- 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.
Re: [algogeeks] Re: Interview question
n = x%2 ? x can be any integer. On Fri, Dec 2, 2011 at 5:19 PM, Don dondod...@gmail.com wrote: (!x || !(x^1)) !(x1) !((x|1)-1) (x*x)==x (x==(x==x))||(x==(x!=x)) etc. On Nov 29, 9:07 pm, Nitin Garg nitin.garg.i...@gmail.com wrote: *What are the different ways to say, the value of x can be either a 0 or a 1.* -- Nitin Garg Personality can open doors, but only Character can keep them open -- 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.
Re: [algogeeks] Re: sort the array
Reverse the 2nd part of the Array so that they are sorted in descending order. Then apply bitonic sort On Wed, Jun 22, 2011 at 2:34 PM, ross jagadish1...@gmail.com wrote: @himanshu: I dont think, the approach works, in present form. in place merge sort or insertion sort is fine. Test with, 12 13 19 16 and 0 20 10 14 as 2 parts of the array. On Jun 22, 8:42 am, Sriganesh Krishnan 2448...@gmail.com wrote: ya...we can do it in O(n) n time!!! nice question! On Tue, Jun 21, 2011 at 11:01 PM, himanshu kansal himanshukansal...@gmail.com wrote: @anika: yar merge sort vl tk nlogn timeinstead u cn do dt maintain two ptrs one at the beginning and one intitially pointing to middle of the array... thn compare the elemnts pointed by them and swap the values if necesary nd incremnt d ptr as u go on... ths vl tk (n/2)+(n/2)-1 =O(n) time corrct me if m wrong On Tue, Jun 21, 2011 at 10:56 PM, Anika Jain anika.jai...@gmail.com wrote: its like inplace mergesort On Tue, Jun 21, 2011 at 10:13 PM, aanchal goyal goyal.aanch...@gmail.com wrote: you have an array of size n where first n/2 is sorted and the sencond half is sorted . You need to sort the entire array inplace Its second modification version is where first part is sorted and other is NOT sorted . You need to make entire sorted . -- Regards,* Aanchal Goyal*. -- 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. -- Regards Himanshu Kansal Msc Comp. sc. (University of Delhi) -- 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.
Re: [algogeeks] Re: Scheduling
Will this work ? Order by choosing the last element of the permutation first. initially Calculate T = Total time of all tasks and calculate for all i, (T-Ti)*Ci and choose the task with min among them as last. To find the next last element , re-calculate T = T-Ti(i being the element chosen in prev step) and proceed with the same steps as mentioned above. On Tue, Jun 7, 2011 at 6:43 PM, ross jagadish1...@gmail.com wrote: @Aakash Johari: Sorting works fine if all jobs can be completed in a day.. I have a modification to this question - suppose the time to do a job is not one day and is given as Ti for job i, then how should one solve it? On Jun 7, 11:58 am, Aakash Johari aakashj@gmail.com wrote: yes, it's correct. simply sort according to their costs (in decreasing order) On Mon, Jun 6, 2011 at 11:52 PM, sunny agrawal sunny816.i...@gmail.com wrote: Sort in decreasing order of Ci ? On Tue, Jun 7, 2011 at 8:22 AM, aanchal goyal goyal.aanch...@gmail.comwrote: Given n jobs, each ith job has a cost Ci associated with it. The waiting time for a job i is defined as Ci*Delay, where Delay is the number of days it takes from the first day to complete a job. Assume each job can be completed in 1 day. So, a job started at day 1 will have delay=1, the one started at day 2 will have delay=2, etc. Order the jobs in such a way that waiting time is minimum. -- Regards,* Aanchal Goyal*. -- 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. -- Sunny Aggrawal B-Tech IV year,CSI Indian Institute Of Technology,Roorkee -- 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. -- -Aakash Johari (IIIT Allahabad) -- 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.
Re: [algogeeks] Re: BST+Heap
1. Insert the node(order of insertion is irrelevant) in any order according to the binary search tree properties. 2. Compare the j value of node with its parent recursively (bottom up) and then perform rotations to restore the Heap property. On Thu, Jun 9, 2011 at 12:38 AM, mukesh tiwari mukeshtiwari.ii...@gmail.com wrote: What you explained is the property of Treap data structure . You can have a look at wiki [ http://en.wikipedia.org/wiki/Treap ] or you can search google for treap. On Jun 8, 8:15 pm, Akshata Sharma akshatasharm...@gmail.com wrote: A rooted binary tree with keys in its nodes has the binary search tree property (BST property) if, for every node, the keys in its left subtree are smaller than its own key, and the keys in its right subtree are larger than its own key. It has the heap property if, for every node, the keys of its children are all smaller than its own key. You are given a set of n binary tree nodes that each contain an integer i and an integer j. No two i values are equal and no two j values are equal. We must assemble the nodes into a single binary tree where the i values obey the BST property and the j values obey the heap property. If you pay attention only to the second key in each node, the tree looks like a heap, and if you pay attention only to the first key in each node, it looks like a binary search tree.Describe a recursive algorithm for assembling such a tree -- 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.
Re: [algogeeks] SPOJ PROBLEM
Can you explain your code ?
On Thu, Mar 10, 2011 at 10:22 AM, UTKARSH SRIVASTAV usrivastav...@gmail.com
wrote:
WELL I HAVE DONE THIS PROBLEM .HERE IS THE CODE
#includestdio.h
#includealgorithm
using namespace std;
main()
{
long long int t[2][2010],price[2010],r,c,i,j,n;
scanf(%lld,n);
for(i=0;in;i++)
{
scanf(%lld,price[i]);
}
for(r=n-1,c=0;r=0c=n-1;r--,c++)
{
for(i=r,j=n-1;i=0j=c;j--,i--)
t[i1][j]=max(price[i]*(n+i-j)+t[(i+1)1][j],price[j]*(n+i-j)+t[i1][j-1]);
}
printf(%lld\n,t[0][n-1]);
return 0;
}
On Wed, Mar 9, 2011 at 5:10 PM, Algoose chase harishp...@gmail.comwrote:
Hi,
Any solution other than brute force(exponential growth) for this problem ?
On Sun, Mar 6, 2011 at 6:42 PM, UTKARSH SRIVASTAV
usrivastav...@gmail.com wrote:
can anyone please tell me why i am getting wrong answer for
problem.https://www.spoj.pl/problems/TRT/
.
.
.
MY CODE IS THIS AND TO BE TESTED IN gcc COMPILER
#includestdio.h
double a[2100];
double fun(long long int m,long long int n,double count)
{
double k,l;
count++;
if(m==n)
{
return count*a[m];
}
if((k=(fun(m+1,n,count)))(l=(fun(m,n-1,count
{
return (count*a[m]+k);
}
else
{
return (count*a[n]+l);
}
}
int main()
{
long long int i,m,n;
double ans,c=0;
scanf(%lld,n);
for(i=1;i=n;i++)
{
scanf(%lf,a[i]);
}
m=1;
ans=fun(m,n,c);
printf(%.0lf\n,ans);
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.
--
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.
--
UTKARSH SRIVATAV
CSE-3
B-TECH 2nd YEAR
MNNIT ALLAHABAD
--
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.
Re: [algogeeks] SPOJ PROBLEM
Hi,
Any solution other than brute force(exponential growth) for this problem ?
On Sun, Mar 6, 2011 at 6:42 PM, UTKARSH SRIVASTAV
usrivastav...@gmail.comwrote:
can anyone please tell me why i am getting wrong answer for
problem.https://www.spoj.pl/problems/TRT/
.
.
.
MY CODE IS THIS AND TO BE TESTED IN gcc COMPILER
#includestdio.h
double a[2100];
double fun(long long int m,long long int n,double count)
{
double k,l;
count++;
if(m==n)
{
return count*a[m];
}
if((k=(fun(m+1,n,count)))(l=(fun(m,n-1,count
{
return (count*a[m]+k);
}
else
{
return (count*a[n]+l);
}
}
int main()
{
long long int i,m,n;
double ans,c=0;
scanf(%lld,n);
for(i=1;i=n;i++)
{
scanf(%lf,a[i]);
}
m=1;
ans=fun(m,n,c);
printf(%.0lf\n,ans);
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.
--
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: Byte or Bite...Its byte Array
@Jammy in case of 1X Since X is the start of a character, thus the preceding byte couldn't the first byte of the 2-byte character.. So the MSb of the byte preceding X must be a dont care. So in that case shouldn't we delete 2 bytes preceding X ? On Thu, Feb 17, 2011 at 12:20 AM, bittu shashank7andr...@gmail.com wrote: case 1. |-|--| | 0 | remaining 7 bit| |-|--| MSB When Character is represented by 1 Byte case 2. ||-||-| | 1 | last 7 bit | dont care | last 7 bit of 2nd Byte | ||-||-| MSB of 1st MSB of 2nd Byte First Byte Second Byte When Character is represented by 1 Byte Thanks Regards Shashank -- 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.
Re: [algogeeks] Directory Structure
I think we can build a n-ary tree from the n directory paths that are
already available in the computer and then for each of the m directory paths
we can traverse the tree up until the directory which is already available
in the tree and then count the remaining directories in the path.
1 Question :
Can a test case be like this ?
1 2
/chicken
/chicken/egg
/chicken/egg/chicken
if yes then while processing second of the 2 directories that should be
created, should we consider egg folder is already created while processing
the previous one ?
On Thu, Feb 17, 2011 at 6:23 PM, Akshata Sharma
akshatasharm...@gmail.comwrote:
On Unix computers, data is stored in directories. There is one root
directory, and this might have several directories
contained inside of it, each with di fferent names. These directories might
have even more directories contained inside of them,
and so on.
A directory is uniquely identified by its name and its parent directory
(the directory it is directly contained in). This is usually
encoded in a path, which consists of several parts each preceded by a
forward slash ('/'). The final part is the name of the
directory, and everything else gives the path of its parent directory. For
example, consider the path: /home/facebook/people
This refers to the directory with name people in the directory described
by /home/facebook, which in turn refers to the
directory with name facebook in the directory described by the path
/home. In this path, there is only one part, which means it
refers to the directory with the name home in the root directory.
To create a directory, you can use the mkdir command. You specify a path,
and then mkdir wi ll create the directory described by
that path, but only if the parent directory al ready exists. For example, i
f you wanted to create the /home/facebook/people and
/home/facebook/tech directories from scratch, you would need four
commands:
mkdir /home
mkdir /home/facebook
mkdir /home/facebook/people
mkdir /home/facebook/tech
Given the full set of directories already existing on your computer, and a
set of new directories you want to create if they do not
already exist, how many mkdir commands do you need to use?
Input The first line of the input gives the number of test cases, T. T test
cases follow. Each case begins with a line containing two
integers N and M, separated by a space.
The next N lines each give the path of one directory that already exists on
your computer. This list will include every directory
already on your computer other than the root directory. (The root directory
is on every computer, so there is no need to l ist it
explicitly.)
The next M lines each give the path of one directory that you want to
create.
Each of the paths in the input is formatted as in the problem statement
above. Speci fically, a path consists of one or more lower -
case alpha-numeric strings (i .e., strings containing only the symbols
'a'-'z' and '0'-'9'), each preceded by a single forward slash.
These alpha-numeric strings are never empty.
Output For each test case, output one l ine containing Case #x: y, where
x is the case number (starting from 1) and y is the
number of mkdir you need.
Note: If a directory is listed as being on your computer, then its parent
directory will also be listed, unless the parent is the root
directory.
INPUT
2
1 2
/chicken
/chicken/egg
/chicken
1 3
/a
/a/b
/a/c
/b/b
OUTPUT
Case #1: 1
Case #2: 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.
--
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: top search queries
Going by the hint given in the problem Divide the stream into windows and assume that we have enough space to store all the queries from the stream window in a hash table along frequency count. Also maintain a global Hash table that will contain the frequency counts of top n queries seen so far. Make sure that n100 .Once the window is filled with enough queries, merge them into the global hash table. If a query is already available in the global hash table update the frequency count.Again this solution cannot be accurate due to limited memory and it allows for some error. larger the value of n lesser the error proneness. On Thu, Feb 3, 2011 at 9:51 PM, Srikar srikar2...@gmail.com wrote: @algoose I see what you are saying. what do you propose? checking out your link now... On Thu, Feb 3, 2011 at 11:44 AM, Algoose chase harishp...@gmail.comwrote: @Srikar In your first approach you cant simply ignore the queries that are not present in the heap because you have a stream of queries and you never know if the query that you are about to ignore is going be received frequently or not in future. Your approach is like find the top 100 queries from the stream and keep updating the frequencies of only those queries using heap and hash table. If you have to process some 1,00,000 , with a space for only 100 elements you cant find the frequencies correctly. this is a nice article related to this : http://www.americanscientist.org/issues/pub/the-britney-spears-problem On Tue, Feb 1, 2011 at 8:09 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: @guy above juver++ The solution , i don't think can get better than this , because you need to store the querries anyway (at least for the output ) -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: top search queries
@Srikar In your first approach you cant simply ignore the queries that are not present in the heap because you have a stream of queries and you never know if the query that you are about to ignore is going be received frequently or not in future. Your approach is like find the top 100 queries from the stream and keep updating the frequencies of only those queries using heap and hash table. If you have to process some 1,00,000 , with a space for only 100 elements you cant find the frequencies correctly. this is a nice article related to this : http://www.americanscientist.org/issues/pub/the-britney-spears-problem On Tue, Feb 1, 2011 at 8:09 PM, sankalp srivastava richi.sankalp1...@gmail.com wrote: @guy above juver++ The solution , i don't think can get better than this , because you need to store the querries anyway (at least for the output ) -- 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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] number of brackets
The DP solution to this problem is very similar DP solution for counting the
number of Dyck words with some additional conditions.
while calculating DP[i][j] you need to check if i+j equals one from the
list of k values. if yes copy the value from the prev row(i.e DP[i-1][j])
instead of assigning it to DP[i-1][j] + DP[i][j-1] since we can add only an
a '(' in position i+j and no ')' can be placed there
On Wed, Jan 26, 2011 at 11:07 PM, Avayukth suresh_iyeng...@yahoo.comwrote:
How do we solve the problem http://www.spoj.pl/problems/SQRBR/ using
dynamic programming?
--
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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: Amazon Question
@ritu how would you find a successor without extra space if you dont have a parent pointer ? for Instance from the right most node of left subtree to the parent of left subtree(root) ? @Juver++ Internal stack does count as extra space !! On Wed, Jan 26, 2011 at 3:02 PM, ritu ritugarg.c...@gmail.com wrote: No,no extra space is needed. Right children which are NULL pointers are replaced with pointer to successor. On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote: If you convert the given binary tree into right threaded binary tree, won't you be using extra space while doing so? Either the given tree should already be right-threaded (or with parent pointers at each node) or internal stack should be allowed for recursion but no extra space usage apart from that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: Amazon Question
@Ritu, Right ! I misread you post On Wed, Jan 26, 2011 at 3:44 PM, Ritu Garg ritugarg.c...@gmail.com wrote: @Algoose I said ..*.For every node x,go to the last node in its left subtree and mark the right child of that node as x.* it is to be repeated for all nodes except leaf nodes. to apply this approach ,you need to go down the tree.No parent pointers required. for every node say x whose left sub tree is not null ,go to the largest node in left sub-tree say y. Set y-right = x y is the last node to be processed in left sub-tree of x hence x is successor of y. On Wed, Jan 26, 2011 at 3:27 PM, Algoose chase harishp...@gmail.comwrote: @ritu how would you find a successor without extra space if you dont have a parent pointer ? for Instance from the right most node of left subtree to the parent of left subtree(root) ? @Juver++ Internal stack does count as extra space !! On Wed, Jan 26, 2011 at 3:02 PM, ritu ritugarg.c...@gmail.com wrote: No,no extra space is needed. Right children which are NULL pointers are replaced with pointer to successor. On Jan 26, 1:18 pm, nphard nphard nphard.nph...@gmail.com wrote: If you convert the given binary tree into right threaded binary tree, won't you be using extra space while doing so? Either the given tree should already be right-threaded (or with parent pointers at each node) or internal stack should be allowed for recursion but no extra space usage apart from that. On Wed, Jan 26, 2011 at 3:04 AM, ritu ritugarg.c...@gmail.com wrote: it can be done in O(n) time using right threaded binary tree. 1.Convert the tree to right threaded tree. right threaded tree means every node points to its successor in tree.if right child is not NULL,then it already contains a pointer to its successor Else it needs to filled up as following a. For every node x,go to the last node in its left subtree and mark the right child of that node as x. It Can be done in O(n) time if tree is a balanced tree. 2. Now,Traverse the tree with Inorder Traversal without using additional space(as successor of any node is available O(1) time) and keep track of 5th largest element. Regards, Ritu On Jan 26, 8:38 am, nphard nphard nphard.nph...@gmail.com wrote: Theoretically, the internal stack used by recursive functions must be considered for space complexity. On Mon, Jan 24, 2011 at 5:40 AM, juver++ avpostni...@gmail.com wrote: internal stack != extra space -- 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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com algogeeks%252bunsubscr...@googlegroups.comalgogeeks%25252bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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
Re: [algogeeks] Re: Amazon Question
If we shouldn't use recursion at it uses internal stack, then I hope we can use Morris tree traversal and use a counter to find the 5th max. On Fri, Jan 21, 2011 at 11:19 PM, juver++ avpostni...@gmail.com wrote: @above yes, posted solution needs parent links. Another solution is to process tree in reverse inorder: right subtree, root, left subtree and keeping counter k, when k is zero return current node -- 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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Distance in a dictionary
To add to what nishaanth mentioned, I think we should also track all the state transitions so that we can back track and make alternate transitions if the path that was already taken was later found to be incorrect one which will not help to reach the given target (with the given set of words). On Fri, Jan 21, 2011 at 10:09 PM, Manmeet Singh mans.aus...@gmail.comwrote: whts complexity for this movegen() On Fri, Jan 21, 2011 at 9:52 PM, nishaanth nishaant...@gmail.com wrote: Ok lets define the following functions. movegen()- gives the list of next move given the state. This is basically all the 1 distance words given the current word. heuristic()- this gives the number of non-matching characters of the given word with the goal word. Start from start state and expand. Now always choose the move which gives a lesser heuristic valued state. Stop if you reach the goal. You can refer to Russel Norvig book on AI for detailed explanation. Regards, S.Nishaanth, Computer Science and engineering, IIT Madras. -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: Google Question
hope this works :
#includestdio.h
#define MAX(A,B) AB?A:B
#defineMIN(A,B) AB?A:B
int FindMaxA(int n)
{
int i,k,factor,max = 0,cur,prev;
int* arr = new int[n+1];
int p = MIN(n,4);
for( int j = 1;j = p;j++)
arr[j] = j;
for(i=5;i=n;i++)
{
k = i-4;
factor = 2;
prev = 0;
while(k=1)
{
cur = arr[k]*factor;
if( cur max ) //find max among multiples of Arr[k] for k i
max = cur;
if( cur prev )
break; // once the decreasing pattern starts its safe to
break out of loop.
k--;
factor++;
prev = cur;
}
arr[i] = MAX(i,max);
}
int result = arr[n];
delete[] arr;
return result;
}
int main()
{
int n;
scanf(%d,n);
printf(%d\n,FindMaxA(n));
return 0;
}
--
On Fri, Jan 21, 2011 at 11:28 AM, Preetam Purbia
preetam.pur...@gmail.comwrote:
Hi,
I think this method will work
Possible Number of A's = N/2(1+R)
where R=N-(N/2+3)
assuming 11/2 = 5
Thanks
Preetam
On Fri, Jan 21, 2011 at 2:29 AM, Anand anandut2...@gmail.com wrote:
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20.
Try this on a notepad. you will only 15A's
On Thu, Jan 20, 2011 at 12:46 PM, Saikat Debnath saikat@gmail.comwrote:
According to me Nishaanth's solution is incorrect, as let for n =10, your
output : m=16
but my output : m =20: For first 5 times hit 'A', then ctrl+A, ctrl+C
resulting in 7 keystrokes. then 3 times ctrl+V, which result in m = 20.
On Thu, Jan 20, 2011 at 9:24 PM, abhijith reddy d
abhijith200...@gmail.com wrote:
I think its correct.
On Jan 19, 9:35 pm, nishaanth nishaant...@gmail.com wrote:
How about the following dynamic programming solution.
Let dp[i] be the max no of As with i keystrokes.
dp[i]=max(dp[i-1]+1,2*dp[i-3])
dp[N] is the required solution.
Correct me if i am wrong.
On Wed, Jan 19, 2011 at 9:20 PM, Raj rajmangaltiw...@gmail.com
wrote:
http://www.ihas1337code.com/2011/01/ctrla-ctrlc-ctrlv.html
On Jan 19, 8:28 pm, bittu shashank7andr...@gmail.com wrote:
Given
1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V
If you can only press the keyboard for N times (with the above
four
keys), please write a program to produce maximum numbers of A. If
possible, please also print out the sequence of keys.
So the input parameter is N (No. of keys that you can press), the
output is M (No. of As that you can produce).
Thanks Regards
Shashank Mani
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
S.Nishaanth,
Computer Science and engineering,
IIT Madras.
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards
Saikat Kumar Debnath
IIIrd year, Computer Science Deptt.,
Delhi Technological University,
(formerly Delhi College of Engineering)
Delhi
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Preetam Purbia
http://twitter.com/preetam_purbia
--
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
Re: [algogeeks] Re: amazon c questn
@avpostnikov In my reply I meant TCHAR ( maybe it doesnt apply to the example given in the problem) when your project is being compiled as Unicode, the TCHAR would translate to wchar_t. If it is being compiled as ANSI/MBCS, it would translated to char Not always we explicitly use wchar_t. On Fri, Jan 14, 2011 at 12:44 PM, juver++ avpostni...@gmail.com wrote: @Harish You are wrong. It doesn't matter when it is Unicode or ASCII application. Size of the char type is ALWAYS 1 byte. To use unicode characters introduce wchar_t or something related. -- 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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: google mcqs
Pipeline : Choice B : 165 ( this pipeline wastes 20 ns between last 2 stages for each item ) Scheduling : Choice B Ram : Choice B Synchronization : Choice B On Mon, Jan 17, 2011 at 10:01 AM, Bhavesh agrawal agr.bhav...@gmail.comwrote: On Mon, Jan 17, 2011 at 10:00 AM, Bhavesh agrawal agr.bhav...@gmail.comwrote: sry ,answer is a mistakingly written b. On Mon, Jan 17, 2011 at 9:58 AM, Sarma Tangirala tvssarma.ome...@gmail.com wrote: Are larger RAMs faster? I am so sure about that. Sent from my BlackBerry -- *From: * Bhavesh agrawal agr.bhav...@gmail.com *Sender: * algogeeks@googlegroups.com *Date: *Mon, 17 Jan 2011 09:36:20 +0530 *To: *algogeeks@googlegroups.com *ReplyTo: * algogeeks@googlegroups.com *Subject: *Re: [algogeeks] Re: google mcqs answer is b Increasing the RAM of a computer typically improves performance because: a. Virtual memory increases b. Larger RAMs are faster c. Fewer segmentation faults occur d. Fewer page faults occur -- 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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: amazon c questn
Apart from that ,
In Unicode application each char would be 2 bytes in length and its always
advisable to use malloc(sizeof(char) * 25) which seamlessly works fine in
ASCII application as well.
On Wed, Jan 12, 2011 at 7:20 AM, Kiran K kira...@gmail.com wrote:
p= (char*)malloc(25);
KK: p should be checked for null after this statment
q = (char*)malloc(25);
KK: q should be checked for null after this statement
-Kiran
On Jan 11, 9:44 pm, snehal jain learner@gmail.com wrote:
what is the wrong in the program?
main()
{
char *p,*q;
p=(char *)malloc(25);
q=(char *)malloc(25);
strcpy(p,amazon);
strcpy(q,hyd);
strcat(p,q);
printf(%sp);
}
--
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.comalgogeeks%2bunsubscr...@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.
Re: [algogeeks] Re: Amazon Intrerview
@Juver++ I am not sure if your input represents a path as asked in the problem. We typically think of a path within a binary tree as a downward path(from root to a leaf) thats not spread across different branches. Of course, if you consider that example as a valid case, then DFS wont work ! On Sun, Jan 9, 2011 at 9:57 PM, nishaanth nishaant...@gmail.com wrote: please describe the tree...give an elaborate explanation to your input On Sun, Jan 9, 2011 at 8:02 PM, juver++ avpostni...@gmail.com wrote: x = 2, z = 3, y = 1. Does your algo give correct answer for this? node 1 cannot be reached while DFS from node 2 https://lh3.googleusercontent.com/_qdJSDBXyZKE/TSi5XyCrEzI/ARg/PB7anNiPA2c/graph.png -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- S.Nishaanth, Computer Science and engineering, IIT Madras. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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 Intrerview
Will this work ? Find the node x, then the node y within the sub tree rooted at x and then z within the sub tree rooted at y since they must within a unique path If any of those searches fails there are no such nodes On Sun, Jan 9, 2011 at 6:02 AM, Gene gene.ress...@gmail.com wrote: The problem never says that the tree is rooted. So LCA is not very relevant. The path between two nodes in any tree is unique. (Otherwise it has a cycle and is not a tree.) So all that's needed is to search for z starting at x (DFS or BFS will work fine). When you find the unique path, see if it contains y. This is O(n) where n is the number of nodes. The problem is more interesting if you are allowed to pre-process the tree one time in order to build a data structure to support many queries. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: FINDSR in spoj
Brute force :
Have 2 pointers one pointing to last character and other pointing to the
first occurrence of last character. compare the chars at the corresponding
positions and decrement both pointers. when the latter hits -1 increment the
counter and reset it to its original value. if the comparison fails at any
point reset the counter to 1 and find the position of next occurrence of
the last char in the input string and repeat the process until both the
index reduce to 0.
@Bharath
you need to read a list of input strings terminated by * before processing
the strings.
testcase : aaabbbcccddaaabbbcccd
On Tue, Dec 7, 2010 at 12:18 PM, bharath kannan bharathgo...@gmail.comwrote:
I tried solving that prob..here's my code
#includeiostream
#includestring
using namespace std;
main()
{
string s;
cins;
while(1)
{
if(s.size()==1 s[0]=='*')
break;
int length=1,curr=0,start=0,count=1;
for(int i=1;is.size();i++)
{
if(s[i]!=s[curr] s[i]!=s[start])
{
curr=0;
count=1;
length=i+1;
}
else if(s[i]!=s[start] s[i]==s[curr])
{
curr++;
}
else if(s[i]==s[start] s[i]!=s[curr])
{
length=i;
curr=0;
count=1;
i=i-1;
}
else if(s[i]==s[start] s[i]==s[curr])
{
if(i%length==0)
{
count++;
curr++;
}
else
curr++;
}
}
if(s[s.size()-1]==s[length-1])
coutcount\n;
else
cout1\n;
cins;
}
}
I am getting WA..anyone pls tel a testcase where the above code
fails..pls..
Thanks in advance..
On Mon, Dec 6, 2010 at 5:44 PM, alexsolo asp...@gmail.com wrote:
http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: Max Heap + Binary Search Tree
To insert a node into a tree with such a property: First insert the node into the tree using the rules of Binary Search tree based on Value i . Now compare Node-j and Node-Parent-j. Depending upon the result of comparison perform left rotation or right rotation so that the Heap property is also maintained. Repeat this process until you fully restore the Heap property. On Wed, Dec 15, 2010 at 2:54 PM, Prims topcode...@gmail.com wrote: Lets assume that the tree node has two keys K1 and K2. K1 satisfies the BST property K2 satisfies the Max Heap Property. Our problem is to build a binary tree which satisfies both the properties. For a maximal heap the root node must be the maximum. So we find the node which has the K2 max. And make it as the root node. Among the remaining nodes, The nodes to the left of the tree will be those whose K1 value is less than that of the Root nodes K1. And rest will be on the right side of the root. Now again repeat the procedure for finding the next left node of root and right node of root using the same logic above On Dec 15, 2:07 pm, snehal jain learner@gmail.com wrote: A rooted binary tree with keys in its nodes has the binary search tree property (BST property) if, for every node, the keys in its left subtree are smaller than its own key, and the keys in its right subtree are larger than its own key. It has the heap property if, for every node, the keys of its children are all smaller than its own key. You are given a set of n binary tree nodes that each contain an integer i and an integer j. No two i values are equal and no two j values are equal. We must assemble the nodes into a single binary tree where the i values obey the BST property and the j values obey the heap property. If you pay attention only to the second key in each node, the tree looks like a heap, and if you pay attention only to the first key in each node, it looks like a binary search tree.Describe a recursive algorithm for assembling such a tree -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: Maximum subarray whose sum is zero
I believe the space complexity should be O(n) since you need to store the cumulative sum corresponding to each of the elements from the input starting from the first element. On Wed, Dec 1, 2010 at 12:04 AM, Prims topcode...@gmail.com wrote: I got the solution to use a hash table storing partial sums a[0], a[0]+a[1], a[0]+a[1]+a[2], etc. in a hash table, along with i Whenever a collision happens, then it is the sub array from i to the last summand. This involves O(N) Time complexity but i what is the space complexity in this case? On Nov 30, 10:19 pm, Prims topcode...@gmail.com wrote: There is an unsorted array of positive and negative integers. I need to find out maximum sub array whose sum is zero efficiently. I can able to provide an answer in O(N^2) time complexity with O(N) Space Complexity Can anyone know better 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Dynamic prog.
thats right ! DP must be the best approach to solve it ! On Tue, Nov 30, 2010 at 10:40 PM, Akash Agrawal akash.agrawa...@gmail.comwrote: In addition to these assumptions, you have also assumed that numbers are greater than 1 else * will lower the result. Regards, Akash Agrawal http://tech-queries.blogspot.com/ On Thu, Nov 25, 2010 at 11:18 AM, Algoose chase harishp...@gmail.comwrote: For this specific case since only 2 operators are used : + , * and we know that * is the operator that maximizes the value(provided both the operands are not equal to one / none of the operand is zero and also given that operands are +ve ). Doing * operation as late as possible should suffice right ? For Eg: Do all additions in the first pass and do all multiplications in 2nd pass. is there be any case where the above mentioned logic fails ? On Wed, Nov 24, 2010 at 4:07 PM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: you can use an algorithm similar to matrix chain multiplication i.e. if dp[i][j] is the maximum value that you can get with the numbers v_i to v_j and in order to maximize it find k that maximizes ( dp[i][k] op_k dp[k][j] ) v_i is the ith value and op_k is the kth operator obviously if i==j : dp[i][j] = v_i -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] sorting variant
I am not sure if this what you are looking for. Assuming that the arrays are sorted in ascending order. Choose one of the 2 arrays as a Reference Array. for each element element in reference array, do a binary search to find all elements that are less than the current element in reference and include them in the result array(and mark the index of the largest among them so that you dont have to consider them in subsequent searches reducing the range of binary search) before including the current element from reference. If there is no element less than the current element in the other array , then include that current element and move to the next element in reference array. On Sun, Nov 7, 2010 at 3:21 AM, lichenga2404 lichenga2...@gmail.com wrote: Suppose we'd like to implement a sorting variant where every element is compared only a small number of times. a) devise a divide and conquer algorithm to merge 2 sorted arrays of length n , which guarantees that every element is included in at most O(log n ) comparisons. b) using this modified merge , prove that Merge-Sort will include element in at most O( (log n)^2) comparisons. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: Addition Of numbers in SLL
The Solution is pretty straight forward when you long number is represented
in reverse order in linked list.
If the number is not in reverse order, We need an Explicit stack or we must
Use Recursion .
Other way around this is to construct another parallel linked list along
with Sum(linked list) for maintaining the carry information and use multiple
passes until the Carry linked list completely vanishes.
Whenever you find the sum digit , Use sum-digit = (list1-digit +
list2-digit + Carry-next-digit) % 10
Carry-digit =
(list1-digit + list2-digit + Carry-digit) / 10
On Mon, Aug 16, 2010 at 8:03 AM, Ashish Goel ashg...@gmail.com wrote:
int add(struct node* pL1, struct node * pl2,int gap/*no of digits in l1
-no of digits in l2*/)
{ //assumption, # of nodes in L1 is # of nodes in L2, make sure this
before calling this, counting nodes is less costlier than reversal
if (!(pl1) || !(pl2)) return 0;
if (gap0)
{
carry = add(pL1-next, pL2, gap-1);
carry = (pl1-data+carry)/10;
pl1-data =(pl1-data+carry) %10;
return carry;
}
else
{
carry = add(pL1-next, pl2-next, gap -1);
carry = (pl1-data+pl2-data+carry)/10;
pl1-data =(pl1-data+pl2-data+carry) %10;
return carry;
}
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, Aug 15, 2010 at 12:19 PM, Manjunath Manohar
manjunath.n...@gmail.com wrote:
@Dave..Can u provide a small snippet for ur explanation pls..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] minimum window containing charecters
@ Anand, No , It doesnt Try with String2 = LH String1 = HELLO. I think LCS solves a different problem from the one being asked here. I think we must generate all possible combination of strings and for each combination , check if all chars from str2 is present in it. On Sun, Aug 1, 2010 at 11:54 PM, Anand anandut2...@gmail.com wrote: Even if they are not in the same order still it works http://codepad.org/jpCUqwpA http://codepad.org/jpCUqwpA On Sun, Aug 1, 2010 at 10:52 AM, srikanth sg srikanthini...@gmail.comwrote: dude they dont need to be in the same order .. how are taking care of that On Sun, Aug 1, 2010 at 10:47 AM, Anand anandut2...@gmail.com wrote: Using Dynamic programing(Longest common subsequence logic) we can solve this problem in O(nm) where n is the length of the first string and m is the length of second string. Last element of matrix which the length of the string that matches. http://codepad.org/cyiKEMSF http://codepad.org/cyiKEMSF On Sun, Aug 1, 2010 at 8:13 AM, srikanth sg srikanthini...@gmail.comwrote: plz .. if any one knows dp solution then tell ... On Sun, Aug 1, 2010 at 7:31 AM, Ashim Kapoor ashimkap...@gmail.comwrote: I am not sure, but can I do this using a suffix trie ? any comments ? On Sun, Aug 1, 2010 at 2:29 PM, Ashish Goel ashg...@gmail.com wrote: solution could be to find the charcter position from both sides for each char of s2 then from the 2*n array, find the smallest index from left and largest from right, within these two indexes all chars would be there one case where one of the chars can be missing can be found if a row in this 2-d array remains unmodified Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sat, Jul 31, 2010 at 10:22 PM, Nikhil Jindal fundoon...@yahoo.co.in wrote: At the moment, I can only think of an O(n^3) algo. Maybe if you can find a hash function which computes the hash value depending on the unique characters the string contains, you can reduce it to O(n^2). On Sat, Jul 31, 2010 at 7:09 PM, srikanth sg srikanthini...@gmail.com wrote: given two string , find the minimum width in string 1 containing the all characters of string 2 , they may present in different order string 1-HELLO string 2- LE answer-2 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com algogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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
Re: [algogeeks] algorithm
Add Each number from the stream to a Doubly linked list in sorted fashion
i = 1;
j = 1;
while( stream not empty)
{
if( i == 1 j == 1)
{
Median = Cur ; /*Create New list with ist Number*/
}
Add_Node_In_Sorted_Order(Cur);
If( If new node is added after median )
i++; /*if the current median is 3rd node and new
node is added @ 5th position*/
bAddedBeforeMedian = False;
else
j++;
bAddedBeforeMedian = true;
if( i %2 == 1 !bAddedBeforeMedian)
Median = median -next;
else if (j%2==1 bAddedBeforeMeidan)
Median = Median-prev
}
return Median-Data;
At any given point in time Median will point to the median among the numbers
seen so far
-
On Sat, Jul 24, 2010 at 8:02 PM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
You are given a stream of numbers which can be positive or negative. You
are required to provide an operation FIND MEDIAN..which when invoked should
be able return the median of the numbers in stream (in sorted order) in O(1)
time.
Eg: 0 1 2 3 4
Right FIND MEDIAN returns 2 as median
Now input is -2 -4
So Stream = 0 1 2 3 -2 -2 -4
Sorted Stream would be -4 -2 0 1 2 3 4 and FIND MEDIAN returns 1
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] You have 2 arrays of integer. You have to write a function, which take an integer as input and returns bool. Example array 1 has {1,5,10} array 2 has {2,5,9}. Func(3) should return t
@jalaj
TRY
A:16, 12, 10, 6 ,2
B:11, 10,7, 2, 1
num: 26
On Sat, Jul 24, 2010 at 5:13 AM, jalaj jaiswal jalaj.jaiswa...@gmail.comwrote:
Take two pointers both at the start of each array...
i=0,j=0
let the size of sorted arrays be m and n
int func(int num,int m,int n){
int i=0,j=0;
while (imjn){
if((num=a[i])||(num=a[j])||num(a[i]+b[j]))
return 0;
if(num==(a[i]+b[j]))
return 1;
if(numa[i]+b[j]){
if(a[i]b[j]) j++;
else i++;
}
}
return 0;
}
O(m+n) complexity
Ps. i'm returning true if the number equals a[i]+b[j] and not just when it
equals a single element in any array
On Fri, Jul 23, 2010 at 9:22 AM, Shafi Ahmad shafi.ah...@gmail.comwrote:
Let argument of function Func is k.
Case 1: If at least on of the array is sorted (say array1) then.
For each number in array2, do
1. binary search for (k - array1[i]) in array1
2. if found
return true.
else
return false
case 2: Arrays are not sorted then
1. Sort one array and apply algo for case 1.
Time complexity will be sizeof(unsortedarray)log (sizeofsortedarray).
Regards,
Shafi
On Fri, Jul 23, 2010 at 12:01 AM, vijay auvija...@gmail.com wrote:
You have 2 arrays of integer. You have to write a function, which take
an integer as input and returns bool. Example array 1 has {1,5,10}
array 2 has {2,5,9}. Func(3) should return true, since 1 (from array
1) +2 (from array 2) =3 ( i.e summation of 2 numbers (1 from each
array) is equal to 3). Func(13) should 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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Regards,
Shafi Ahmad
The difficult we do immediately, the impossible takes a little
longerUS Army
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Boxes!!!
can we sort the boxes based on their volume in descending order and start highest volume box to lowest volume box (outer loop) -Inner loop start from lowest volume box to highest volume box upto the box considered in outer loop. Running time : O(n^2) On Tue, Jul 20, 2010 at 8:28 PM, Ashish Goel ashg...@gmail.com wrote: kindly give an example Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Tue, Jul 20, 2010 at 8:04 AM, siddharth shankar siddharth.shanka...@gmail.com wrote: step : 1. Sorting LBH in decreasing order first on L than on B and than on H . 2. Now find longest decreasing sub-sequence of array of structures(LBH) . correct me if I m wrong !!! On Sun, Jul 18, 2010 at 11:44 PM, amit amitjaspal...@gmail.com wrote: Given a lot of cuboid boxes with different length, breadth and height. We need to find the maximum subset which can fit into each other. For example: If Box 1 has LBH as 7 8 9 If Box 2 has LBH as 5 6 8 If Box 3 has LBH as 5 8 7 If Box 4 has LBH as 4 4 4 then answer is 1,2,4 A box can fit into another only and only if all dimensions of that is less than the bigger box.Rotation of boxes is not possible. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- siddharth shankar -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: center of a tree
Given the collection of nodes that constitute the diameter of the tree, The node with Max height among them i.e the node thats closest to the root(top level node) need not necessarily have children with equal height. For Instance: If the the top_level_node-left-height top_level_node-right-height , then find p such that p = top_level_node-right-height - top_level_node-left-height - 1; now traverse down p levels to the right along the path that constitutes the diameter. this node will be the center of the tree. @gene : you mentioned within brackets (though not necessarily the overall maximum).Did you mean the same as i do ? On Sun, Jul 4, 2010 at 2:19 AM, Gene gene.ress...@gmail.com wrote: On Jul 3, 10:14 am, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: give an algo to find center of a tree conter of a tree is midpoint of diameter which is the largest distance b/w any two nodes You can traverse the tree once in O(n) to label each node N with its height H(N), which is the maximum distance to any descendent leaf. Then traverse it again looking for a node C with H(C-left) = H(C- right) and the maximum value of D(C) = 1 + H(C-left) + H(C-right). The first condition puts C in the middle of some maximal length path (though not necessarily the overall maximum). The second picks the center IF there is only one center. A tree can also have 2 centers. For example in the tree 1 -- 2 -- 3 \ -- 4 both 1 and 2 are centers because their radius is 1 in both cases. Working out how to handle this case is not hard. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] sum to 0
@ Amir: I think you cannot find two numbers in B and C such that their sum is -A[k] in O(n) in all cases with the logic that you mentioned. for instance you can try with : A : 2 7 8 10 B :-2, 0, 1, 9 C: -7 -2 1 3 On Wed, Jun 16, 2010 at 5:56 AM, Amir hossein Shahriari amir.hossein.shahri...@gmail.com wrote: sort all arrays for each number in A , A[k] find two numbers in B and C such that their sum is -A[k] this can be done in O(n) time: set i at the beginning of B and j at the end of C while in or j=0 if ( B[i] + C[j] == -A[k] ) return true if ( B[i] + C[j] -A[k] ) increase i else decrease j we have to do this for each element of A so the overall complexity is: O(n2) time O(1) space correct me if I'm wrong On 6/15/10, sharad kumar sharad20073...@gmail.com wrote: plzzz comment on this question -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] isomorphic trees
The Definition of isomorphic trees given in the first post is incomplete
We say two rooted unordered trees are isomorphic if
1. a tree with a single node (the root) is only isomorphic to a tree with a
single node;
2. two trees with roots A and B, none of which is a single-node tree, are
isomorphic if and only if there is a 1-1 correspondence between the subtrees
of A and the subtrees of B such that corresponding subtrees are isomorphic.
Lets say each node has an additional field that says the number of children
it has.
bool IsIsomorphic(Node* T1,Node* T2)
{
if( T1 == null T2 == null ) return true;
if( T1-numChilderen == T2-numChilderen)
{
if(IsIsomorphic(( T1-left,T2-left)
IsIsoMorphic(T1-right,T2-right)) || (IsIsoMorphic(T1-right,T2-left)
IsIsomorphic(T1-left,T2-Right));
}
else return false;
}
Correct me if needed !
On Wed, Jun 9, 2010 at 8:29 PM, divya jain sweetdivya@gmail.com wrote:
@vadivel and anand
{ 1,2,3 } is *isomorphic* to { 1,3,2 }
{ 1,2,3,4,5,6,7 } is *isomorphic* to { 1,3,2,7,6,4,5 }
{ 1,2,3,4,5,6,7 } is NOT *isomorphic* to { 1,3,2,4,5,6,7 }
so its nt necessary that right and left will interchange. it may or may
not. if all right and left are interchanged then it is mirror tree. i think
ur code is for mirror tree and not isomorphic tree..
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Single ordered list
For multiple ordered lists you can build a single Max heap out of elements from all this list and Process as its done in heapsort On Wed, Jun 9, 2010 at 9:14 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: I had answered this question(of multiple lists) 2 or three days back. Go into the archive if u wanna see :P -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 On Wed, Jun 9, 2010 at 6:52 PM, Raj N rajn...@gmail.com wrote: But what if the same same problem is extended for multiple lists. As the individual lists have already been sorted, is there any efficient way or any other sorting algo which exploits this fact. On Tue, Jun 8, 2010 at 10:56 PM, divya jain sweetdivya@gmail.comwrote: merging as in merge sort. On 8 June 2010 19:59, Raj N rajn...@gmail.com wrote: What is the most efficient way of combining 2 separate ordered list into a single ordered list ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Removing extra parentheses in an infix string
Hi , To add to your logic, I hope we must also be checking at the precedence of the first operator that appears after the closing parenthesis ')' before we can decided if the parenthesis can be removed or not . On Thu, Jun 3, 2010 at 11:37 PM, Antony Vincent Pandian.S. sant...@gmail.com wrote: If the base logic follows the below rule, it should work. If any operator within parenthesis is of less precedence to the operator before the opening parenthesis, the parenthesis can not be removed. For cases of equal precedence of operators before parenthesis and within parenthesis, transitivity condition should be checked. If transitive, parenthesis can be removed else should be retained. Eg: parenthesis cannot be removed for division operator while can be removed for multiplicative or addition or subtraction operator. On 6/3/10, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: So there is a prob algoose A*(B*C) and a*(b*c+d) i hope you understood -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Sent from my mobile device Luv, S.Antony Vincent Pandian -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Removing extra parentheses in an infix string
Will this work ?
consider A+(B*C)
have an operator stack to hold the operators. As we scan elements from left
to right,push the operators in operator stack.
when you encounter a '(' , then scan to find the first operator that comes
after '(' (in this case *).
If this operator has a higher precedence than the operator @ top of stack
(in this case +). Then we can safely remove the parenthesis. Else we cant
remove the brackets
On Thu, Jun 3, 2010 at 1:05 PM, divya jain sweetdivya@gmail.com wrote:
1.calculte the postfix of given expression.
2.now remove a particular parenthesis from expression and check if the
postfix of this expression is equal to the postfix of original expression.
if yes then the parenthesis we have removed were extra. if no then the
parenthesis were not exta.
3 now remove other parenthesis as step 2 and repeat till u have done this
for all parenthesis
On 1 June 2010 20:12, Raj N rajn...@gmail.com wrote:
How to remove extra parentheses in an infix string. For example if it
is A+(B*C) parentheses for * is not required as it has higher
precedence. Can someone suggest a good routine for this?
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Removing extra parentheses in an infix string
Thats right !!! On Thu, Jun 3, 2010 at 6:08 PM, Rohit Saraf rohit.kumar.sa...@gmail.comwrote: So there is a prob algoose A*(B*C) and a*(b*c+d) i hope you understood -- -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14http://www.cse.iitb.ac.in/%7Erohitfeb14 -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Convert a Binary tree into spike.
Hi , We can do Breadth first search but without any additional Memory like Queue. Since we connect the siblings we can traverse through siblings. Going from Top to bottom, Each Internal node(non-leaf) must connect its children. If that internal node has a right sibling then connect the right most node of internal node with the left most child node of the sibling. Continue until the sibling node is null. As you towards right remove the links to its parent. Also save the left most node at each level to traverse down to next level. On Thu, May 13, 2010 at 6:57 PM, Jitendra Kushwaha jitendra.th...@gmail.com wrote: This can be done with level order traversal of the tree Algorithm count = count2 = 0 1. Push the root in the queue. 2. keep count at each level for root count =1 3. while(queue not empty) 4. push all childs of node at the top of queue in queue 5. count2 += (number of childs of node at the top) 6. print the top node of queue and dequeue it 7. count -= 1 8. if (count == 0) 9.print newline 10. count = count2 11. count2 = 0 any comments are welcomed... -- Regards Jitendra Kushwaha Undergradute Student Computer Science Eng. MNNIT, Allahabad -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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 google question
Hi
will this work ?
since we need Set S with n pairs of largest values , any such pair within
the set would (always) contain A[0] or B[0] because they maximize the value
of the pair.
so
// code snippet
typedef std::vectorint,int Pairs;
Pairs.push(A[0],B[0])
int i = 1; // index for ListA
int j = 1; // index for list B
count = 1;
while( count = n)
{
if( A[0] + B[j] B[0] + A[i] )
{
Pairs.push(A[0],B[j])
j++;
}
else
{
Pairs.Add(A[i],B[0])
i++;
}
count++;
}
since there are n items in both the lists, j and i wont go beyond n in the
while loop
On Sun, May 2, 2010 at 3:44 PM, Shishir Mittal 1987.shis...@gmail.comwrote:
This problem has been discussed before @
http://groups.google.co.in/group/algogeeks/browse_thread/thread/9c1e1aa8cf1ed437/d451cd9468d985f7
I believe, the problem can't be solved in O(n) but only in O(nlog n).
@Divya: Are you sure the interviewer explicitly asked for an O(n) time
algorithm?
On Sun, May 2, 2010 at 1:48 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:
@divya You're rite. Post a solution if you have one.
--
Regards,
Vignesh
On 2 May 2010 13:14, divya jain sweetdivya@gmail.com wrote:
@Mohit
according to ur algo if a[1], b[0] has sum greater than a[0],b[1]
then i is incremented i is now 2 so for next iteration u ll compare
a[2] b[0] and a[1] b1]. but what about a[0] b[1] this pair s lost forever.
think for ths case also.
On 2 May 2010 11:22, mohit ranjan shoonya.mo...@gmail.com wrote:
@Algoose Chase
point taken
Thanks
Mohit Ranjan
Samsung India Software Operations.
On Sat, May 1, 2010 at 8:43 PM, Algoose Chase harishp...@gmail.comwrote:
@mohit
The idea of DP is fine.
When you find the Max i dont think you need to include A[i+1]+B[j+1]
because it can never be greater than both A[i+1]+B[j] and A[i]+B[j+1]
since
both the lists are sorted in decreasing order.
On Fri, Apr 30, 2010 at 8:47 PM, mohit ranjan shoonya.mo...@gmail.com
wrote:
oops
Sorry didn't read properly
last algo was for array sorted in ascending order
for this case, just reverse the process
A[n] and B[n] are two array
loop=n, i=0, j=0;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of first index from both array will
be max
foo = MAX ( A[i+1]+B[j], A[i+1]+B[j+1], A[i]+B[j+1] ) // using
DP, moving forward
if foo==A[i+1]+B[j]; i++ // only increment A
if foo==A[i+1]+B[j+1]; i++; j++ // increment both A and B
if foo==A[i]+B[j+1]; j++ // increment only B
}
Mohit Ranjan
Samsung India Software Operations.
On Fri, Apr 30, 2010 at 8:40 PM, mohit ranjan
shoonya.mo...@gmail.com wrote:
Hi Divya,
A[n] and B[n] are two array
loop=n, i=n-1, j=n-1;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of last index from both array will
be max
foo = MAX ( A[i-1]+B[j], A[i-1]+B[j-1], A[i]+B[j-1] ) // using
DP moving backward
if foo=A[i-1]+B[j]; i-- // only reduce A
if foo=A[i-1]+B[j-1]; i--; j-- // reduce both A and B
if foo=A[i]+B[j-1]; j-- // reduce only B
}
Time: O(n)
Mohit Ranjan
On Fri, Apr 30, 2010 at 5:35 PM, divya sweetdivya@gmail.comwrote:
Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G,
let's
say they are decreasingly sorted), we define a set S = {(a,b) | a
\in
A
and b \in B}. Obviously there are n^2 elements in S. The value of
such
a pair is defined as Val(a,b) = a + b. Now we want to get the n
pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks
Re: [algogeeks] a google question
OOPs.. sorry
this doesnt work !
On Sun, May 2, 2010 at 6:11 PM, Algoose Chase harishp...@gmail.com wrote:
Hi
will this work ?
since we need Set S with n pairs of largest values , any such pair within
the set would (always) contain A[0] or B[0] because they maximize the value
of the pair.
so
// code snippet
typedef std::vectorint,int Pairs;
Pairs.push(A[0],B[0])
int i = 1; // index for ListA
int j = 1; // index for list B
count = 1;
while( count = n)
{
if( A[0] + B[j] B[0] + A[i] )
{
Pairs.push(A[0],B[j])
j++;
}
else
{
Pairs.Add(A[i],B[0])
i++;
}
count++;
}
since there are n items in both the lists, j and i wont go beyond n in the
while loop
On Sun, May 2, 2010 at 3:44 PM, Shishir Mittal 1987.shis...@gmail.comwrote:
This problem has been discussed before @
http://groups.google.co.in/group/algogeeks/browse_thread/thread/9c1e1aa8cf1ed437/d451cd9468d985f7
I believe, the problem can't be solved in O(n) but only in O(nlog n).
@Divya: Are you sure the interviewer explicitly asked for an O(n) time
algorithm?
On Sun, May 2, 2010 at 1:48 PM, vignesh radhakrishnan
rvignesh1...@gmail.com wrote:
@divya You're rite. Post a solution if you have one.
--
Regards,
Vignesh
On 2 May 2010 13:14, divya jain sweetdivya@gmail.com wrote:
@Mohit
according to ur algo if a[1], b[0] has sum greater than a[0],b[1]
then i is incremented i is now 2 so for next iteration u ll compare
a[2] b[0] and a[1] b1]. but what about a[0] b[1] this pair s lost forever.
think for ths case also.
On 2 May 2010 11:22, mohit ranjan shoonya.mo...@gmail.com wrote:
@Algoose Chase
point taken
Thanks
Mohit Ranjan
Samsung India Software Operations.
On Sat, May 1, 2010 at 8:43 PM, Algoose Chase harishp...@gmail.comwrote:
@mohit
The idea of DP is fine.
When you find the Max i dont think you need to include A[i+1]+B[j+1]
because it can never be greater than both A[i+1]+B[j] and A[i]+B[j+1]
since
both the lists are sorted in decreasing order.
On Fri, Apr 30, 2010 at 8:47 PM, mohit ranjan
shoonya.mo...@gmail.com wrote:
oops
Sorry didn't read properly
last algo was for array sorted in ascending order
for this case, just reverse the process
A[n] and B[n] are two array
loop=n, i=0, j=0;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of first index from both array
will be max
foo = MAX ( A[i+1]+B[j], A[i+1]+B[j+1], A[i]+B[j+1] ) // using
DP, moving forward
if foo==A[i+1]+B[j]; i++ // only increment A
if foo==A[i+1]+B[j+1]; i++; j++ // increment both A and B
if foo==A[i]+B[j+1]; j++ // increment only B
}
Mohit Ranjan
Samsung India Software Operations.
On Fri, Apr 30, 2010 at 8:40 PM, mohit ranjan
shoonya.mo...@gmail.com wrote:
Hi Divya,
A[n] and B[n] are two array
loop=n, i=n-1, j=n-1;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of last index from both array
will be max
foo = MAX ( A[i-1]+B[j], A[i-1]+B[j-1], A[i]+B[j-1] ) // using
DP moving backward
if foo=A[i-1]+B[j]; i-- // only reduce A
if foo=A[i-1]+B[j-1]; i--; j-- // reduce both A and B
if foo=A[i]+B[j-1]; j-- // reduce only B
}
Time: O(n)
Mohit Ranjan
On Fri, Apr 30, 2010 at 5:35 PM, divya sweetdivya@gmail.comwrote:
Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G,
let's
say they are decreasingly sorted), we define a set S = {(a,b) | a
\in
A
and b \in B}. Obviously there are n^2 elements in S. The value of
such
a pair is defined as Val(a,b) = a + b. Now we want to get the n
pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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
Re: [algogeeks] a google question
@mohit
The idea of DP is fine.
When you find the Max i dont think you need to include A[i+1]+B[j+1] because
it can never be greater than both A[i+1]+B[j] and A[i]+B[j+1] since both the
lists are sorted in decreasing order.
On Fri, Apr 30, 2010 at 8:47 PM, mohit ranjan shoonya.mo...@gmail.comwrote:
oops
Sorry didn't read properly
last algo was for array sorted in ascending order
for this case, just reverse the process
A[n] and B[n] are two array
loop=n, i=0, j=0;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of first index from both array will be
max
foo = MAX ( A[i+1]+B[j], A[i+1]+B[j+1], A[i]+B[j+1] ) // using DP,
moving forward
if foo==A[i+1]+B[j]; i++ // only increment A
if foo==A[i+1]+B[j+1]; i++; j++ // increment both A and B
if foo==A[i]+B[j+1]; j++ // increment only B
}
Mohit Ranjan
Samsung India Software Operations.
On Fri, Apr 30, 2010 at 8:40 PM, mohit ranjan shoonya.mo...@gmail.comwrote:
Hi Divya,
A[n] and B[n] are two array
loop=n, i=n-1, j=n-1;
while(loop0) // for n largest pairs
{
print A[i]+B[j]; // sum of last index from both array will be
max
foo = MAX ( A[i-1]+B[j], A[i-1]+B[j-1], A[i]+B[j-1] ) // using DP
moving backward
if foo=A[i-1]+B[j]; i-- // only reduce A
if foo=A[i-1]+B[j-1]; i--; j-- // reduce both A and B
if foo=A[i]+B[j-1]; j-- // reduce only B
}
Time: O(n)
Mohit Ranjan
On Fri, Apr 30, 2010 at 5:35 PM, divya sweetdivya@gmail.com wrote:
Given two sorted postive integer arrays A(n) and B(n) (W.L.O.G, let's
say they are decreasingly sorted), we define a set S = {(a,b) | a \in
A
and b \in B}. Obviously there are n^2 elements in S. The value of such
a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs
from S with largest values. The tricky part is that we need an O(n)
algorithm.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Build BST from binary tree without extra space
Hi, How do you define without extra space ? Doing any order traversal either using recursion or using iteration is going to take extra space . If you are given a binary tree represented by pointers that points to children nodes is it possible to do a heap sort without an array ? On Thu, Apr 29, 2010 at 6:59 AM, sharad kumar aryansmit3...@gmail.comwrote: my choice is build a min heap .sort the array with heap sort.then find the median of the sorted array and build tree On Wed, Apr 28, 2010 at 10:16 PM, Vivek S s.vivek.ra...@gmail.com wrote: @Rajesh Patidar I think we should do in Post order traversal alone. If we go by Preorder/Inorder we might lose track of children node that is currently being inserted into the BST. - correct me if im wrong :) On 28 April 2010 15:30, Rajesh Patidar patidarc...@gmail.com wrote: pickup node in any order no matter(pre,post,inorder) and just one by one. start adding the node into bst no need to use extra space u have to just ditach the node from binary tree and attach it in bst. On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com wrote: How to build BST from binary tree in place i.e without extra space ?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- BL/\CK_D!AMOND -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Reduce, Reuse and Recycle Regards, Vivek.S -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com . For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- yezhu malai vaasa venkataramana Govinda Govinda -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Build BST from binary tree without extra space
If you mean to convert the binary tree to binary search tree directly , then
BinarytoBST(Node* root)
{
if( root == nulll) return;
BinarytoBST(root-left);
BinarytoBST(root-right);
if( root-left )
Node* NodeL = MAX(root-left);
if ( root-right )
Node* NodeR = MIN(root-right);
if( NodeL-Data root-data)
{
// swap values.
temp = NodeL-data;
NodeL-data = root-data;
root-data = temp;
BinarytoBST(NodeL);
}
if( NodeR-Data = root-data)
{
// swap values.
temp = NodeR-data;
NodeR-data = root-data;
root-data = temp;
BinarytoBST(NodeR);
}
On Thu, Apr 29, 2010 at 11:23 AM, Algoose Chase harishp...@gmail.comwrote:
Hi,
How do you define without extra space ?
Doing any order traversal either using recursion or using iteration is
going to take extra space .
If you are given a binary tree represented by pointers that points to
children nodes is it possible to do a heap sort without an array ?
On Thu, Apr 29, 2010 at 6:59 AM, sharad kumar aryansmit3...@gmail.comwrote:
my choice is build a min heap .sort the array with heap sort.then find
the median of the sorted array and build tree
On Wed, Apr 28, 2010 at 10:16 PM, Vivek S s.vivek.ra...@gmail.comwrote:
@Rajesh Patidar
I think we should do in Post order traversal alone. If we go by
Preorder/Inorder we might lose track of children node that is currently
being inserted into the BST. - correct me if im wrong :)
On 28 April 2010 15:30, Rajesh Patidar patidarc...@gmail.com wrote:
pickup node in any order no matter(pre,post,inorder) and just one by
one. start adding the node into bst no need to use extra space u have
to just ditach the node from binary tree and attach it in bst.
On Wed, Apr 28, 2010 at 1:18 AM, Ashish Mishra amishra@gmail.com
wrote:
How to build BST from binary tree in place i.e without extra space ??
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
BL/\CK_D!AMOND
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Reduce, Reuse and Recycle
Regards,
Vivek.S
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
yezhu malai vaasa venkataramana Govinda Govinda
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] The Mystery Spiral
I have a logical question about the solution pasted. The Problem says given N*N numbers filled in a matrix , print the numbers in spiral . What the code does is it fills the N*N numbers in spiral in decreasing order and then prints the matrix contents left to right , top to bottom. Will the two produce the same results ? Or I understood the problem incorrectly ? On Sat, Apr 17, 2010 at 6:53 PM, Chinmay S cvs...@gmail.com wrote: *Problem statement:* Given a integer N, print N*N numbers in a N x N spiral. *Detailed problem description:* http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral/ *Solution:* Recently posted the following code. http://2600hertz.wordpress.com/2010/03/20/the-mystery-spiral-part2/ (managed to compress it into as few as 99 lines) Please comment on *further optimisations*(if any)... (any optimisations will do, either size OR performance) [image: spiralcode.jpg] -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: Largest span of Increasing Pair in an array
Hi all,
How about this ?
set K to the first element i.e Array[0] and set j to the last element i.e
Array[size-1].
Decrement the index j until you find Array[j] Array[j+1] and increment the
index k until you find Array[k] Array[k-1] and do this until you find the
conditions met.
Does it solve the original problem ?
Or is it the largest Non decreasing sequence thats been asked in original
problem .
On Wed, Mar 24, 2010 at 1:08 PM, saurabh gupta sgup...@gmail.com wrote:
Hi Achala,
This fails for:
0 1 2000 3 4 5 6
prog's output:
arr[j]=2000,arr[k]=0,j=2,k=0
correct output should be:
arr[j]=6,arr[k]=0,j=6,k=0
you seem to be relying on the difference in the 'values' (contents) instead
of the index span.
On Mon, Mar 22, 2010 at 11:10 PM, achala sharma 3.ach...@gmail.comwrote:
One Solution for Largest span in array,I have checked it on many
inputs,according to me its working fine
void Large_Span(int * arr,int num_elem)
{
int j=1,k=0,i,prev_k=0;
for(i=1;inum_elem;i++)
{
if(arr[i]arr[i-1])
{
if((arr[j]-arr[k])(arr[i]-arr[i-1]))
{
if(jarr[i] k=arr[i-1])
{
j=i;
}
else if((jarr[i] karr[i-1])||(jarr[i] karr[i-1]))
{
j=i;
k=i-1;
}
}
else if(arr[k]arr[i-1])
{
if(kj)
{
prev_k=k;
k=i-1;
}
}
else if(arr[j]arr[i])
j=i;
}
else
{
if(arr[k]arr[i])
{
if(ij)
{
prev_k=k;
k=i;
}
else
k=i;
}
}
}
if(kj)
{
k=prev_k;
}
printf(arr[j]=%d,arr[k]=%d,j=%d,k=%d,arr[j],arr[k],j,k);
}
On Mon, Mar 22, 2010 at 8:28 AM, Manish mannishmaheshw...@gmail.comwrote:
This does not look like a solution for the posted problem.
This fails the test case {2, 7, 6, 0, 100}, where the answer should
have been 4, for k=0 and j=4.
Manish
On Mar 20, 1:49 pm, saurabh gupta sgup...@gmail.com wrote:
This may not be the optimal solution to
Given an array of integers A[N], find the maximum value of (j-k) such
that A[k] = A[j] jk.
I am looking for a solution with time complexity better than O(N^2).
this was in response to
how u can solve it in o(n)
and
how to solve this in the claimed O(N) time.
On Sat, Mar 20, 2010 at 9:14 PM, Ralph Boland rpbol...@gmail.com
wrote:
On Mar 15, 10:07 am, saurabh gupta sgup...@gmail.com wrote:
while you scan the array
maintain four indices plus two lengths
two indices and a length mark one sub-array - start,end, length
each such sub-array indicates a non-decreasing sequence,
call them S1 and S2.
while one scans, S2 keeps track of incoming elements (curr
sequence)
S1 keeps track of the maximum length (along with indices) so far
(prev
sequence)
as one encounters an element which is less than the previous
element,
this marks the end of S2,
S1 replaces S2 if len S2 len S1 else S2 starts afresh from this
new
element.
In the end if len S2 len S1 answer = S2
else answer = S1.
PS: In the beginning and till one encounters a smaller element
than the
prev one for the first time, S1 = S2
I agree that this is a nice algorthithm that solves the
largest non decreasing sequence problem.
However, I don't agree that this solves the problem
originally posted.
Regards,
Ralph Boland
--
You received this message because you are subscribed to the Google
Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and
cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up.
Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@googlegroups.com
.
For
Re: [algogeeks] Re: Merge two BST in O(n) time with O(1)
Hi, @Asish meena and Arun : I dont think you can simply append a whole tree( BST2) at some position just because the root of the BST2 is at its correct position.For instance , Lets say you append BST2's Root anywhere within the left subtree of BST1's Root. But if the right most leaf node of BST2 is greater than the root of BST1, then the merged tree is no longer a binary search tree. Hence your approach will not work in all cases. On Wed, Feb 10, 2010 at 5:12 PM, r_arun rathakrishnana...@gmail.com wrote: Your algorithm is correct. But 3. Remove the children from this place and store them as BST3 and BST4. This is not required , because trying to merge BST2 with BST1,which is equivalent to finding a place to insert a pointer to root of BST2 in BST1. Whenever you need a place for a new node, you take a place of a existing leaf in BST1 for that new node. So we need not worry about children. Also in a BST there is no configuration for which a new element can not be inserted. So we can just link the pointers and get a merged tree. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] string ques
void FindPattern(string inputstring)
{
int length = inputstring.length()
int currentEnd = 1; //end position of the first substring to be searched
int currentBeg = 0; //begining position of the first substring
int Result = 0;
char* Pattern= null;
while( currentEnd length-3) // we look for a pattern only until the 3rd
last char
{
Pattern = inputstring.substr(currentBeg,CurrentEnd);
// Search for the pattern within the input string from Next charecter of
CurrentEnd.
Result = inputstring.find(Pattern, CurrentEnd+1) ;
// If Pattern Not found , Increase CurrentBeg by 1 char and start search
for next pair of chars
if( Result = -1 )
{
CurrentBeg++;
CurrentEnd = CurrentBeg + 1;
Continue;
}
// If Pattern is Found . Print it! and Increase the Current End by 1 so
that now you search for a bigger pattern starting with same //first
charecter.
Printf(%s\n,Pattern.c_str());
CurrentEnd++;
}
}
On Wed, Feb 3, 2010 at 1:30 AM, ankit mahendru ankit.mahend...@gmail.comwrote:
Rephrasing the question again :
Q. Find all the patterns which are present in the character array given. A
pattern is a sub-array containing 2 or more chars and is having a frequency
of more than one.
Example:
i/p: aabcdadabc
o/p: ab, abc, bc, da
basically what we have to search is those sub-string(s) of length 2 or more
which repeats itself(not necessarily twice, but 'n' number of times). In the
above example 'ab' has been highlighted with red in order to make it
clear.
Another example:
i/p : fghjerhjfgjefgh
o/p: fg, je , hj, fgh
I hope its clear now.
Thanks
Ankit Mahendru
On Tue, Feb 2, 2010 at 8:31 PM, vivek bijlwan viv...@gmail.com wrote:
explain the question a little further please
On Tue, Feb 2, 2010 at 11:03 AM, Algoose Chase harishp...@gmail.comwrote:
Hope you meant a pattern is sub-array containing 2 or more UNIQUE chars.
hope based on dfn, abcd is also a pattern in the input you have given.
On Tue, Feb 2, 2010 at 1:11 AM, ankit mahendru
ankit.mahend...@gmail.com wrote:
Q. Find all the patterns once which are present in the character array
given. A pattern is a sub-array containing 2 or more chars.
Example:
i/p: aabcdadabc
o/p: ab, abc, bc, da
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] string ques
Hope you meant a pattern is sub-array containing 2 or more UNIQUE chars. hope based on dfn, abcd is also a pattern in the input you have given. On Tue, Feb 2, 2010 at 1:11 AM, ankit mahendru ankit.mahend...@gmail.comwrote: Q. Find all the patterns once which are present in the character array given. A pattern is a sub-array containing 2 or more chars. Example: i/p: aabcdadabc o/p: ab, abc, bc, da -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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] Add 2 long integers with digits represented by linked lists
@saurabh :
so you scanned to find out that both lists are same : O(n) (agreed)
prepare list 3 in time O(n) (agreed)
process list 3 in time O(n) (*HOW ??*)
can you run through your method and show how you process list 3 in O(n)
using the below lists as input:
5-5-5-5-5-5-5-5-5-5 and
4-4-4-4-4-4-4-4-4-5
hope you know the constraints : you cant reverse original list. and you cant
use recursion. and you need to traverse the list LEFT TO RIGHT to satisfy
the first 2 conditions.
Yes , I agree these lists takes O(n) time: list 1 = 4-7-8-1-6
list 2 = 2-3-4
but not in all cases.
I agree that for most cases(except the wild ones) the running time must be
O(n) only but you certainly need multiple passes depending upon the input.
Hope I am clear !
On Mon, Feb 1, 2010 at 11:39 PM, saurabh gupta sgup...@gmail.com wrote:
the key observation is that your requirement for no space is nullified by
using the space in the resultant list.
so you scanned to find out that both lists are same : O(n)
prepare list 3 in time O(n)
process list 3 in time O(n)
current list 3 is the answer as list 4 is empty
total time O(n) as k is small
On Mon, Feb 1, 2010 at 11:19 PM, saurabh gupta sgup...@gmail.com wrote:
nope,
if both lists are of same length list 4 is not required and you save time
to deal with list 4
so, you have list 3 only
time reqd is O(3n)
3 passes approximately
On Mon, Feb 1, 2010 at 11:24 AM, Algoose Chase harishp...@gmail.comwrote:
Thats true ! , The purpose is to add very long integers such that we
cant use premative data types to represent them.
The point I was trying to prove is : you would need to go through
multiple passes through the list(essentially to propagate carry) when you
have conditions like No Reversing the original lists and no recursion and no
to any extra memory usage.
@ saurabh: Hope you have not considered the worst case before
generalizing the running time to 2n+m .
lets assume the 2 lists are of same size so n = m.This eliminates the
need to find out m or to create list 4
and lets assume the linked list are 5-5-5-5-5-5-5-5-5-5 and
4-4-4-4-4-4-4-4-4-5
Only thing is you need to create list 3 (as u have mentioned) . Now its
not possible to add the 2 lists through a single pass from left to right .
This would need n passes on a linked list of size n making the running time
n^2.
On Thu, Jan 28, 2010 at 5:51 AM, saurabh gupta sgup...@gmail.comwrote:
this defeats the purpose,
they are stored in linked list because they cannot be stored in a given
type.
On Thu, Jan 28, 2010 at 3:25 AM, Deva R r.deva...@gmail.com wrote:
i faced this qn in * interview.
best soln i could give was:
- traverse each list and derive both the numbers.. something like below
node = list-head;
i=1; value =0;
while (node)
{ value = (node-data)*i +value;
i*=10;
node = node-next;
}
- add both the numbers. u can either return the number or form a new
list and return.
i gave the code.. and its o(m+n), for lists of size m,n.
-Deva
On Wed, Jan 27, 2010 at 10:02 PM, saurabh gupta sgup...@gmail.comwrote:
step 1 is n not m
which makes it O(3n)
On Wed, Jan 27, 2010 at 9:54 PM, saurabh gupta sgup...@gmail.comwrote:
its not exponential
time to find out m = m
time to create list 3 = m
time to create list 4 = n-m
time to come up with proper added list (list 3 modification) = m
time to merge list 3 and list 4 = n-m
total time = 2n+m
except step 1 all are reversals with approximately same constant and
constant for step 1 is smaller
so one can say
O(2n+m)
On Wed, Jan 27, 2010 at 5:26 PM, Anurag Bhatia
abhati...@gmail.comwrote:
If that is the representation, then the lists have to be reversed.
Otherwise the time goes up exponentially.
On Wed, Jan 27, 2010 at 5:19 PM, Algoose Chase
harishp...@gmail.com wrote:
Condition:
Can we do it keeping the original lists intact ? ie without
reversing it.
I mean , No recursion no Reversing ... is it possible ?
@kumar :
15234 is represented as 1-5-2-3-4
On Wed, Jan 27, 2010 at 4:09 PM, saurabh gupta sgup...@gmail.com
wrote:
perhaps you mean,
reverse each link list O(n+m).
then sum each node with carryover maintained.
On Wed, Jan 27, 2010 at 11:07 AM, Anurag Bhatia
abhati...@gmail.com
wrote:
Let us take an example -
Num 1 = 123456
Num 2= 1234
Link-1-Link-2-Link-3-Link-4-Link5-Link6
Link-1-Link-2-Link-3-Link-4
Add nodes into linkedlist 1 till either one of the list is not
null.
Make sure you process the carry in each iteration.
--AB
On Tue, Jan 26, 2010 at 9:47 PM, Algoose Chase
harishp...@gmail.com
wrote:
conditions:
NO extra memory (@ stack or Heap) at all. No recursion.
Any body has got any hint about how to get this done ?
--
You received this message because you are subscribed to the
Google
Groups
[algogeeks] Add 2 long integers with digits represented by linked lists
conditions: NO extra memory (@ stack or Heap) at all. No recursion. Any body has got any hint about how to get this done ? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algoge...@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] Algorithm for vector problem
void PrintFamilyTree(const short generation)
{
printf(Name : %s Generation = %d\n, m_Name.c_str(),generation);
vectorHuman*::iterator it;
for (it = this.begin(); it this.end() ;it++)
{
it-PrintFamilyTree(generation+1);
}
}
On Tue, Nov 24, 2009 at 9:20 PM, Aditya Shankar
iitm.adityashan...@gmail.com wrote:
Hi,
On Tue, Nov 24, 2009 at 6:38 PM, Ankur ankuraror...@gmail.com wrote:
What would be the best algorithm for the undermentioned problem.
Implement method PrintFamilyTree() that prints out the Name and
Generation of the tree
Output should resemble
Name: Jan Generation:0
Name: Mike Generation:1
Name: Greg Generation:2
Name: Carol: Generation: 2
Name: Peter Generation: 3
Name: Marcia Generation: 3
Name: Bobby Generation: 1
The order you have mentioned is preorder traversal of the tree.
Regards
Aditya Shankar
class Human : public std::vectorHuman *
{
public:
Human(const std::string name) : m_Name(name) {};
virtual void PrintFamilyTree(const short generation = 0) const;
protected:
std::string m_Name;
};
class Male: public Human
{
public:
Male(const std::string name) : Human(name) {};
};
class Female: public Human
{
public:
Female(const std::string name) : Human(name) {};
};
void main()
{
Male m1(Mike), m2(Greg), m3(Peter), m4(Bobby);
Female f1(Carol), f2(Marcia), f3(Jan);
m1.push_back(m2);
f1.push_back(m3);
f1.push_back(f2);
m1.push_back(f1);
f3.push_back(m1);
f3.push_back(m4);
f3.PrintFamilyTree();
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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: Print binary tree in spiral
I posted this long b4 but dint see this error : Delivery to the following
recipient failed permanently: algogeeks@googlegroups.com
re-posting:
BST_Spiral(struct node* root)
{
ht = Height(root);
for( i = 0; i= ht; i++)
{
PrintSpiral(root, i, i%2 /*flip 1 and 0 alternately on each
iteration*/);
}
void PrintSpiral(struct node* root, int level, bool bRTL/* Right-To-Left */)
{
if ( root == NULL) return;
if( level == 0 )
{
printf(%d, root-data)
return;
}
if( bRTL )
{
PrintSpiral(root-right,level-
1,bRTL)
PrintSpiral(root-left,level-1,bRTL)
}
else
{
PrintSpiral(root-left,level-1,bRTL)
PrintSpiral(root-right,level-1,bRTL)
}
}
On Tue, Nov 24, 2009 at 11:12 AM, Rohit Saraf
rohit.kumar.sa...@gmail.comwrote:
And it cannot be made more efficient.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.comalgogeeks%2bunsubscr...@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 algoge...@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.
