Re: [algogeeks] Re: Largest even length palindrome in a string!!
but actually we need something better as per prob, cannot be done in O(n). so we need to think of something like O(n lg n) or O( n ^ 3/2) :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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.
[algogeeks] Best Data Structure for this?
Google has many visitors to its site. And it tracks what pages the customers visited, etc and other stuff. Lets say you store the data of customer id and the page id as a record in a log-file. Now assuming that you have created one log file for each day with that above data- format. Give me the way to find all the customers who made a visit on day1 and day2 and visited atleast two different pages. Say a customer visited two different pages on day1 and then comes back on day2 and visited some other page on day2 he should be listed. Lets say the logfile1 has contents like: c1 p1 c2 p2 c1 p3 c3 p4 c5 p6 And logfile2 has contents: c10 c7 c4 p4 c3 p4 c5 p1 c1 p2 c2 p1 Then the customers you print out are c1, c2, c5. -- 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] array question
@sharad while storing each element in hash by your approach u ll check if its already there in hash. so the complexity here will be O(n2). correct me if i m wrong. isnt there ny better algo..? On 6 June 2010 06:28, sharad kumar aryansmit3...@gmail.com wrote: @dhivya:keep storing the first occurance element index in hash map and then start insertin eleement based on index position On Sun, Jun 6, 2010 at 12:31 AM, divya sweetdivya@gmail.com wrote: Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. So cant use a dictionary. -- 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] array question
No it will be O(n). -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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] array question
#includeiostream
#includemap
#includeiterator
using namespace std;
int main()
{
int arr[5]={12,3,4,3,3};
mapint,intmp;
int i=0;
for(i=0;i5;++i)
{
if(!(mp[arr[i]]))
mp[arr[i]]=i;
else
continue;
}
mapint,int::iterator it;
for(it=mp.begin();it!=mp.end();++it)
coutit-secondendl;
cin.sync();
cin.get();
return 0;
}
On Sun, Jun 6, 2010 at 3:14 PM, divya jain sweetdivya@gmail.com wrote:
@sharad
while storing each element in hash by your approach u ll check if its
already there in hash. so the complexity here will be O(n2). correct me if i
m wrong. isnt there ny better algo..?
On 6 June 2010 06:28, sharad kumar aryansmit3...@gmail.com wrote:
@dhivya:keep storing the first occurance element index in hash map and
then start insertin eleement based on index position
On Sun, Jun 6, 2010 at 12:31 AM, divya sweetdivya@gmail.com wrote:
Given an array with some repeating numbers. Like 12,6,5,12,6
output: 12,12,6,6,5
12 shud come before 6 since it is earlier in list. So cant use a
dictionary.
--
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.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.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: array question
@sharad: Your code seems will seem to give output 12,3,4 and not
12,3,3,3,4. It semes from the original description of the problem that
you also need to keep count of frequency of occurance of items in the
map.
Secondly, you have iterated through the map and got the elemenst in
same order as you had inserted. This is specific to the map in
programing language and may not be a feature available in all
languages. Conceptually map is a dictionary of name,value pair which
enables O(1) insertion, deletion and O(1) access. Traversal in the
order of insertion may not be always available. Let me know what you
feel.
Sain
On Jun 6, 4:39 pm, sharad kumar aryansmit3...@gmail.com wrote:
#includeiostream
#includemap
#includeiterator
using namespace std;
int main()
{
int arr[5]={12,3,4,3,3};
mapint,intmp;
int i=0;
for(i=0;i5;++i)
{
if(!(mp[arr[i]]))
mp[arr[i]]=i;
else
continue;
}
mapint,int::iterator it;
for(it=mp.begin();it!=mp.end();++it)
coutit-secondendl;
cin.sync();
cin.get();
return 0;
}
On Sun, Jun 6, 2010 at 3:14 PM, divya jain sweetdivya@gmail.com wrote:
@sharad
while storing each element in hash by your approach u ll check if its
already there in hash. so the complexity here will be O(n2). correct me if i
m wrong. isnt there ny better algo..?
On 6 June 2010 06:28, sharad kumar aryansmit3...@gmail.com wrote:
@dhivya:keep storing the first occurance element index in hash map and
then start insertin eleement based on index position
On Sun, Jun 6, 2010 at 12:31 AM, divya sweetdivya@gmail.com wrote:
Given an array with some repeating numbers. Like 12,6,5,12,6
output: 12,12,6,6,5
12 shud come before 6 since it is earlier in list. So cant use a
dictionary.
--
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.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- Hide quoted text -
- Show quoted text -
--
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.
[algogeeks] String Mathching and RegEx [Good Old Days]
Hi All Here is a problem for us to solve: Write a function which takes as parameters one regular expression(only ? and * are the special characters to consider) and a string and returns whether the string matched the regular expression. -- 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 even length palindrome in a string!!
Suffix tree is obviously there but 1. It requires more lots of space. Just draw a suffix tree and you will know. 2. Pre-processing takes time. We cant ignore this time because its proportional to N. There is one linear solution described here: http://www.akalin.cx/2007/11/28/finding-the-longest-palindromic-substring-in-linear-time/ Still trying to understand O(N) algo.. On Sun, Jun 6, 2010 at 2:15 PM, jalaj jaiswal jalaj.jaiswa...@gmail.com wrote: i think it can be done in O(n) using suffix trees. but making suffix tree also requires O(n) space and O(n) time... attached is the ppt (it has the same example)... On Sun, Jun 6, 2010 at 1:51 PM, Rohit Saraf rohit.kumar.sa...@gmail.com wrote: but actually we need something better as per prob, cannot be done in O(n). so we need to think of something like O(n lg n) or O( n ^ 3/2) :) -- Rohit Saraf Second Year Undergraduate, Dept. of Computer Science and Engineering IIT Bombay http://www.cse.iitb.ac.in/~rohitfeb14 -- 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. -- 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.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] Best Data Structure for this?
Use hash table with customer ID as key. There can be three components in value: 1. num_days 2. pages 3. flag For each line, calculate hash, find value for given key. Increment appropriate values (i.e. pages or num_days). If num_days 1 pages 1, add this customer to result array, mark this customer's flag and don't process that customer further. On Sun, Jun 6, 2010 at 2:52 PM, amit amitjaspal...@gmail.com wrote: Google has many visitors to its site. And it tracks what pages the customers visited, etc and other stuff. Lets say you store the data of customer id and the page id as a record in a log-file. Now assuming that you have created one log file for each day with that above data- format. Give me the way to find all the customers who made a visit on day1 and day2 and visited atleast two different pages. Say a customer visited two different pages on day1 and then comes back on day2 and visited some other page on day2 he should be listed. Lets say the logfile1 has contents like: c1 p1 c2 p2 c1 p3 c3 p4 c5 p6 And logfile2 has contents: c10 c7 c4 p4 c3 p4 c5 p1 c1 p2 c2 p1 Then the customers you print out are c1, c2, c5. -- 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. -- 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 Mathching and RegEx [Good Old Days]
lets say u entered a*.nw aab is i/p string then recursivley substitute a and check for it.or use a table for storing the augmented grammer On Sun, Jun 6, 2010 at 6:02 PM, Veer Sharma thisisv...@rediffmail.comwrote: Hi All Here is a problem for us to solve: Write a function which takes as parameters one regular expression(only ? and * are the special characters to consider) and a string and returns whether the string matched the regular expression. -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Puzzle
A square Island surrounded by bigger square, and in between there is infinite depth water. The distance between them is L. The wooden blocks of L are given. The L length block can't be placed in between to cross it, as it will fall in water (just fitting). How would you cross using these L length blocks. -- 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.
[algogeeks] Puzzle
There are N nuts and N bolts, all unique pairs od Nut and Bolt You cant compare Nut with Nut. You cant compare Bolt with Bolt You CAN compare Nut with Bolt Now how would you figure out matching pairs of nut and bolt from the given N nut and Bolt. The basic soln is O(N^2). Give O(NlogN soln) -- 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.
[algogeeks] ds
Convert in O(n) time: a1a2a3a4.aNb1b2b3b4.bN to a1b2a2b2a3b3a4b4..aNbN -- 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] ds
in o(n) take a separate array of size 2n and for iteration a[i] and a[i+1] should have ai and bi elelemnt On Sun, Jun 6, 2010 at 7:39 PM, sharad sharad20073...@gmail.com wrote: Convert in O(n) time: a1a2a3a4.aNb1b2b3b4.bN to a1b2a2b2a3b3a4b4..aNbN -- 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Find Max Number of Elephants
I am sorry for the link if it caused any confusion. It was just a part of the signature. Kindly disregard the link in this context. Anurag Sharma On Sun, Jun 6, 2010 at 7:55 AM, Minotauraus anike...@gmail.com wrote: I think you can do this in O(n) time. Feel free to correct me where I'm wrong. Create a 2D array with years on one side and elephant's time alive on the other. example: 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 E1 1 1 1 11 1 1 1 1 E2 1 11 1 1 1 1 11 E3 1 1 1 1 Now for every years add vertical indices example 2006 = 3, 2007 = 3, 2008 = 3 and so on. This will give you the year with max elephant population. The array can be init with 0 or a static array can be used. @Anurag: How will you approach this problem by using LCA algorithm that your link leads to? On Jun 5, 6:16 am, amit amitjaspal...@gmail.com wrote: Maximum number of elephants alive Hello guyz, Every elephant has a birth_time and a death_time. Given N Elephants with birth times and death times.. How can we find 1) the maximum number of elephants that can be alive at any given point of time. 2) what is the year in which you can have maximum number of elephants alive. ex: E1 - 2000-2008 E2-2004-2012 E3-2006-2009 So in 2006 you have 3 elephants alive (maximum) PS: ignore months and all stuff .. if a elephants live in a year consider it lives that complete year I have O(year_max-year_min) solution and O(n^2) solution , where n=number of elephants . Can we do better ?? thanks -- 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] ds
this is ques by adobe and they want inplace soln.. -- 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: array question
output willl be 12 12 5 6 6 On 6 June 2010 18:27, souravsain souravs...@gmail.com wrote: @divya: Does your problem require the output to be sorted also? What will be the output required if inout is 12,5,6,12,6? Will it be 12,12,6,6,5 or 12,12,5,6,6,? Sain On Jun 6, 12:01 am, divya sweetdivya@gmail.com wrote: Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. So cant use a dictionary -- 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: Find Max Number of Elephants
1. have an array of N years. starting with first year and ending at last year. O(N) space here. initialise all elements to zero. 2. Take array of E and birthyear first. Whenever you encounter new birthyear, do array[year]++. 3. Take array of E and deathyear now. Whenever you encounter new deathyear, do array[year]--. 4. Parse this array of year. sum_for_given_year += array[year] To me, it looks like O(N). Correct me if I am wrong. On Sun, Jun 6, 2010 at 7:56 PM, Anurag Sharma anuragvic...@gmail.com wrote: I am sorry for the link if it caused any confusion. It was just a part of the signature. Kindly disregard the link in this context. Anurag Sharma On Sun, Jun 6, 2010 at 7:55 AM, Minotauraus anike...@gmail.com wrote: I think you can do this in O(n) time. Feel free to correct me where I'm wrong. Create a 2D array with years on one side and elephant's time alive on the other. example: 2000 2001 2002 2003 2004 2005 2006 2007 2008 2009 2010 2011 2012 E1 1 1 1 1 1 1 1 1 1 E2 1 1 1 1 1 1 1 1 1 E3 1 1 1 1 Now for every years add vertical indices example 2006 = 3, 2007 = 3, 2008 = 3 and so on. This will give you the year with max elephant population. The array can be init with 0 or a static array can be used. @Anurag: How will you approach this problem by using LCA algorithm that your link leads to? On Jun 5, 6:16 am, amit amitjaspal...@gmail.com wrote: Maximum number of elephants alive Hello guyz, Every elephant has a birth_time and a death_time. Given N Elephants with birth times and death times.. How can we find 1) the maximum number of elephants that can be alive at any given point of time. 2) what is the year in which you can have maximum number of elephants alive. ex: E1 - 2000-2008 E2-2004-2012 E3-2006-2009 So in 2006 you have 3 elephants alive (maximum) PS: ignore months and all stuff .. if a elephants live in a year consider it lives that complete year I have O(year_max-year_min) solution and O(n^2) solution , where n=number of elephants . Can we do better ?? thanks -- 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. -- 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. -- 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] Puzzle
place the L block diagonally... --Sundeep. On Sun, Jun 6, 2010 at 7:29 PM, sharad sharad20073...@gmail.com wrote: A square Island surrounded by bigger square, and in between there is infinite depth water. The distance between them is L. The wooden blocks of L are given. The L length block can't be placed in between to cross it, as it will fall in water (just fitting). How would you cross using these L length blocks. -- 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.
[algogeeks] ds
Given an array of size n wherein elements keep on increasing monotically upto a certain location after which they keep on decreasing monotically, then again keep on increasing, then decreasing again and so on. Sort the array in place (ie. using only O(1) extra memory). -- 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.
[algogeeks] Re: ds
In order to make it inplace, time complexity has gone to n^2.
Rearrange(array,int N) //So array size is 2N
{
int i = 1;//points to index array[1] which has a2 since a1 is already
at the correct place;
int j = N;//array[0] to array[N-1] is a1 to aN. so j is index of b1
//it is assumed that N is
for(;j 2N;j++)
{
int bValue = array[j];
//right shift all elements from j to i (moving right to left)
for(int k = j; ki ; k--)
{
array[k]=array[k-1];
}
//k now is equal to i but a2 has shifted to array[2] from
array[1];
array[k] = bValue;
i = i+2;//No need to consider array[i+1] as that element (a2 in
first iteration is at its proper place
}
}
Space Complexity: Inplace
Time Complexity:
to move b1 : a2 to aN i.e., N-1 right shifts
to move b2 : a3 to aN i.e., N-2 right shifts
...
to move b(N-1): aN moved right: 1 right shift
so total shifts=1+2+3+.N-1
hence time complexity = n^2
Let me know if you have comments or improvements.
Sain
On Jun 6, 7:28 pm, sharad kumar sharad20073...@gmail.com wrote:
this is ques by adobe and they want inplace soln..
--
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.
[algogeeks] Re: array question
@divya:go through the elements and keep inserting them in a BST. While inserting if elements already exists in BST, increase its frequency (Node of BST has element a nd frequency). Also if elemengs is newly inserted then also place it in a seperate array. So this array (say Array M) will become something like 12,5,6. This array will give order of first occurance of numbers. This whole process will take nlogn (BST creation assuming worst case that all elements are uinque in the input array). Once done, scan through each element in array M, find its corrosponding element in BST (logn) which will give the frequency. Fill those many indexes in input array with array M[i]. If all elements are uinque, this will also take nlogn. Else if input array has m distince elements, which will require us to look into BST for m times. hence entire process has time compelxity: O(nlogn + nlogn)= O(2nlogn) Space complexity: O(2n) [1 for BST and 1 for array M, worst case when all elements are unique in inpur array). Let me know your comments if any or any better appraoch as this once may have improvements. On Jun 6, 7:47 pm, divya jain sweetdivya@gmail.com wrote: output willl be 12 12 5 6 6 On 6 June 2010 18:27, souravsain souravs...@gmail.com wrote: @divya: Does your problem require the output to be sorted also? What will be the output required if inout is 12,5,6,12,6? Will it be 12,12,6,6,5 or 12,12,5,6,6,? Sain On Jun 6, 12:01 am, divya sweetdivya@gmail.com wrote: Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. So cant use a dictionary -- 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.- Hide quoted text - - Show quoted text - -- 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.
[algogeeks] Modified Tower of Hanoi
Here is a modified version tower of hanoi. Along with usual tower of hanoi conditions there ia also a condition that a disk cannot rest over another disk that is more than one size larger. For eg disk 2 may rest on disk 3 but not on disk 4. How to make changes to the existing algo to incorporate this condition? -- 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.
[algogeeks] Re: Puzzle
Take a Nut, try putting it to all bolts (this is Comparing Nut with Bolt). If Nut goes not go and fit into bolt, keep the bolt on left, if Nut fits loose, keep the bolt on right and keep the bolt and nut which match, at centre. This is pivot of quicksort. All bolts to left of this central Nut+bolt are smaller and all towards right are large than central Nut + bolt. This will take N comparision. Then take second Nut. try fitting to central bolt. It will not fit. But we will be able to make a decision weather to move left or right. if this Nut is tight on bolt, try smaller bolts on left, else try larger bolts on right. This will take n/2 comparisions and we will find exact bolt fitting this 2nd nut. This process will again divide either left or right bolts into 2 part. and go on. This shold take NlogN time to complete the whole matching process as in case of quick sort. let me know your comments or improvements. Sain On Jun 6, 7:05 pm, sharad sharad20073...@gmail.com wrote: There are N nuts and N bolts, all unique pairs od Nut and Bolt You cant compare Nut with Nut. You cant compare Bolt with Bolt You CAN compare Nut with Bolt Now how would you figure out matching pairs of nut and bolt from the given N nut and Bolt. The basic soln is O(N^2). Give O(NlogN soln) -- 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.
[algogeeks] Can you count?
How do you count the number of ways a number can be expressed as a sum of 2 or more numbers? For eg. if the number is 5 , count=3 i.e 1+1+1+1+1, 4+1, 3+2 note 2+3 is same as 3+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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: sorted 2-d array
I meant O(n) considering there are n elements and not n rows/ columns. :-) so my n = nrows x ncolumns. Since we talk of input size in terms of number of elements I thought it'd be n instead of nrowsXncolumns. On Jun 6, 4:26 am, Senthilnathan Maadasamy senthilnathan.maadas...@gmail.com wrote: @Minotauraus Since the input is an n*n array I think you meant O(n*n), Right? -- 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.
[algogeeks] Re: divisible by 3
@Anand: Thanks for the code. I knew you could do it by bit shifting. :-) On Jun 5, 10:21 pm, Anand anandut2...@gmail.com wrote: Here is a code for it.http://codepad.org/umkh3pjf On Sat, Jun 5, 2010 at 7:14 PM, Minotauraus anike...@gmail.com wrote: Subtract 3 from the number until either you get 0 or a negative number. If you get 0, its divisible, else not. You can probably do this by bit shifting too. On Jun 5, 11:45 am, divya sweetdivya@gmail.com wrote: Find if a number is divisible my 3, without using %,/ or *. You can use atoi(). -- 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] ds
Here is my approach is o(n). http://codepad.org/YAFfZpxO http://codepad.org/YAFfZpxO On Sun, Jun 6, 2010 at 7:28 AM, sharad kumar sharad20073...@gmail.comwrote: this is ques by adobe and they want inplace soln.. -- 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: array question
Here is my approch which runs in O(n). http://codepad.org/d3pzYQtW http://codepad.org/d3pzYQtW On Sun, Jun 6, 2010 at 7:47 AM, divya jain sweetdivya@gmail.com wrote: output willl be 12 12 5 6 6 On 6 June 2010 18:27, souravsain souravs...@gmail.com wrote: @divya: Does your problem require the output to be sorted also? What will be the output required if inout is 12,5,6,12,6? Will it be 12,12,6,6,5 or 12,12,5,6,6,? Sain On Jun 6, 12:01 am, divya sweetdivya@gmail.com wrote: Given an array with some repeating numbers. Like 12,6,5,12,6 output: 12,12,6,6,5 12 shud come before 6 since it is earlier in list. So cant use a dictionary -- 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.
[algogeeks] Re: Can you count?
In number theory, a partition of a positive integer n is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a composition. The number of partitions of n is given by the partition function p(n). You can compute p(n) recursively. See http://en.wikipedia.org/wiki/Partition_(number_theory). Dave On Jun 6, 2:05 pm, Raj N rajn...@gmail.com wrote: How do you count the number of ways a number can be expressed as a sum of 2 or more numbers? For eg. if the number is 5 , count=3 i.e 1+1+1+1+1, 4+1, 3+2 note 2+3 is same as 3+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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
