[algogeeks] Re: Minimal number of swaps
oh, nevermind, sorry ;P you want the 1's at the beginning, not the end... //friday On Friday, April 22, 2016 at 4:07:53 PM UTC-4, icy` wrote: > > Hi, > I'm not sure I understand the second example. Shouldn't the second one > also produce an answer of 1 (swap the one in index 1 with the zero in the > last index) > 0 *1* 0 1 1 1 *0* > > icy` > > On Tuesday, March 29, 2016 at 10:00:21 AM UTC-4, Régis Bacra wrote: >> >> This puzzle comes from a contribution on codingame.com (link to the >> puzzle <https://www.codingame.com/games/community/?puzzleId=103>). Any >> idea to solve it efficiently? >> >> Given a list of 1 and 0, you must regroup all the 1 at the begin of the >> list in a minimum number of steps. A step is the interchange of two >> elements located at different positions. >> The expected result is the minimum number of steps required to obtain a >> sorted list. >> >> Examples: >> 1 0 1 0 1 -> 1 >> 0 1 0 1 1 1 0 -> 2 >> > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Minimal number of swaps
Hi, I'm not sure I understand the second example. Shouldn't the second one also produce an answer of 1 (swap the one in index 1 with the zero in the last index) 0 *1* 0 1 1 1 *0* icy` On Tuesday, March 29, 2016 at 10:00:21 AM UTC-4, Régis Bacra wrote: > > This puzzle comes from a contribution on codingame.com (link to the puzzle > <https://www.codingame.com/games/community/?puzzleId=103>). Any idea to > solve it efficiently? > > Given a list of 1 and 0, you must regroup all the 1 at the begin of the > list in a minimum number of steps. A step is the interchange of two > elements located at different positions. > The expected result is the minimum number of steps required to obtain a > sorted list. > > Examples: > 1 0 1 0 1 -> 1 > 0 1 0 1 1 1 0 -> 2 > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com.
[algogeeks] Re: Facebook question!
At first I found this tricky, as the number of strings in the array is unknown, and it can be hard to iterate over unknown items of unknown length. Since repeated combinations are included, we know the total number of combinations (lengths of all strings multiplied). In my Ruby example below, I used strings abcde, 123, and YZ . My method was to set up a resulting array of empty strings of length 30 (5*3*2).Then I examined the kind of combinations we will make: a1Y a1Z a2Y a2Z a3Y a3Z , b1Y etc. Notice if we generate combinations in this order, a will repeat six times in a row, and this is because the remaining elements are three and two letters long (3*2). Similarly, the numbers in 123 will be repeated twice in a row, because the remaining (last) word has only two characters. This amount of repetition is assigned to variable *repeats* below. And each element of YZ repeats once in a row since there are no more elements after. If there is more room in the total combinations, then the word will repeat again from the beginning; e.g. for 123 the middle characters of the answers will be 1,1, 2,2,3,3,1,1,2,2,3,3 until 30 is reached. The strings of the res array are slowly built in this way. Ruby helps deal with some of the other minor issues. Pic below. icy` [image: Inline image 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. image.png
[algogeeks] Re: Missing Number Problem
By missing I assume that the numbers are consecutive and we are at least provided with a range. Suppose for the sake of example, the range is 100,000 to 400,000 with 203,148 being the missing number. They come to us shuffled up, and let us suppose we are taking them from the hard drive instead of an array, one by one. Now if the range is known, there is an interesting property of XOR that you can use. A variable initialized to 0 can be XOR'd with every element in the range, and then XOR'd with all the provided numbers. It will then become the missing number. Ruby example (again, assume numbers coming from hard drive or other source, one at a time, and not array in memory): [image: Inline image 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. image.png
Re: [algogeeks] finding element in array with minimum of comparing
nice solution, Dave!
@Umer -- if the sought ele is first, then Dave's code has it sitting in the
variable temp for a little while. Loop will stop when size is 0, since
arr[0]==elem. Now he throws temp back into arr[0], which will return index
0 from the last compare line.
On Wednesday, October 3, 2012 2:08:56 AM UTC-4, Umer Farooq wrote:
@Dave Thanks for pointing that out.
But I still can't get what if elem is on first element or it is not
present in the array? How is your code going to handle that situation?
@Atul, Well yes, In the given question, the number of iterations were 2n.
Which I have reduced to n+n/2.
On Tue, Oct 2, 2012 at 11:13 PM, atul anand atul.8...@gmail.comjavascript:
wrote:
@umer : how no. of comparison are reduced to half by moving both
sidesyou have 2 if condition inside, so you are making 2
comparisons at each iteration + n/2 comparison for while loop so
number of comparisons are n+n/2
On 10/2/12, Umer Farooq the@gmail.com javascript: wrote:
why don't we try it from both ends ... something like this:
int i = 0; j = size-1;
while (i != j)
{
if (arr[i] == elem)
return arr[i];
if (arr[j] == elem)
return arr[j];
}
this way, we have eliminated half of the comparisons in for loop? What
do
you guys say?
On Tue, Oct 2, 2012 at 12:18 PM, rafi rafiw...@gmail.com javascript:
wrote:
Vikas is right!
while (n) is equal to (while n!=0)
you have 2n compares!
בתאריך יום שני, 1 באוקטובר 2012 12:12:21 UTC+2, מאת vikas:
still there is no improvement, compiler will generate the code to
compare
with zero here. what you have accomplished is , hide it from human
eyes
On Monday, 1 October 2012 15:25:09 UTC+5:30, Navin Kumar wrote:
@atul:
still it won't compare 0 th element. Slight modification in your
code:
n=*sizeof(arr)*;
do
{
if(elem==arr[*--n*])
print found;
}while(n);
On Mon, Oct 1, 2012 at 9:50 AM, atul anand atul.8...@gmail.com
wrote:
yes, but there no need of checking outside the loop
n=sizeof(arr)-1;
do
{
if(elem==arr[n])
print found;
n--;
}while(n);
On Mon, Oct 1, 2012 at 9:33 AM, Navin Kumar
algorit...@gmail.comwrote:
@atul: keep one more checking outside loop for element at 0 th
index.
Because when n = 0 the your loop come out from the loop without
comparing
it.
On Mon, Oct 1, 2012 at 8:55 AM, atul anand
atul.8...@gmail.comwrote:
n=sizeof(arr);
n--;
while(n)
{
if(elem=arr[n])
print found;
n--;
}
On Sun, Sep 30, 2012 at 2:56 PM, רפי וינר rafiw...@gmail.com
wrote:
Hi
i was in an interview and was given a simple function
int arrExsits(int* arr,int size,int elem){
for (int i=0;isize;++i)
if(elem==arr[i])
return i;
return -1;
}
this function does 2n compares
n- the if statment
n-check that i is smaller then size
i was suppose to give an optimal (less compares) solution so i
gave
int arrExsits(int* arr,int size,int elem){
if (arr[size-1]==elem)
return size-1;
arr[size-1]=elem]
for (int i=0;;++i)
if(elem==arr[i]){
if (i!=size-1)
return i;
return -1;
}
this solution works and it has n+2 compares the first one
another n
and the second inner if.
they told me it's good (and I've passed) but they told just for
my
knowledge that there is a better N compare solution.
I've searched the web but couldn't find it.
anybody knows?
Thanks
--
You received this message because you are subscribed to the
Google
Groups Algorithm Geeks group.
To post to this group, send email to algo...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com**.
For more options, visit this group at
http://groups.google.com/**
group/algogeeks?hl=en
http://groups.google.com/group/algogeeks?hl=en
.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algo...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com**.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en
http://groups.google.com/group/algogeeks?hl=en
.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algo...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com**.
For more options, visit this group at http://groups.google.com/**
group/algogeeks?hl=en
http://groups.google.com/group/algogeeks?hl=en
.
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algo...@googlegroups.com.
To unsubscribe from
Re: [algogeeks] spoj problem EASYMATH
why not just brute force this? one little array contains [a, (a+d), (a+2d), (a+3d), (a+4d) ], which is then filtered so that none of those are multiples of another. Then set a count variable to m-n+1. Check all numbers in range against your little array, decrementing count and breaking out if a divisible num is found. In Ruby, screenshot so that syntax highlighting remains. (comments start with # ) [image: Inline image 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. image.png
[algogeeks] Re: Puzzle
hm, very strange set of numbers. If the first number was 38 I *might*
see the hints of a pattern, but since it is just 3, I have no idea.
[if the first number was ] 38(now +1, or 1 squared)
39 , 41, 43, 45(+4, or 2 squared)
49, 51, 53, 55(+9, or 3 squared)
64, __ __ __ (I would then guess 66, 68, 70, and 86)
icy`
On Feb 28, 7:44 am, srikanth reddy malipatel srikk...@gmail.com
wrote:
{39,41,43,45} incremented by 2
{49,51,53,55} incremented by 2
{64,?,?,?}
first number in each set is considered as base number.
3 is for the number of numbers in each set other than base number.
so in final set base number is 64 and other 3 numbers are incremented by 2.
On Tue, Feb 28, 2012 at 1:48 PM, payal gupta gpt.pa...@gmail.com wrote:
one option cud be reverse the digits...i.e
(bt the first n d last do not satisfy d pattern howeva)
93 , 14,34,54,94,15,35,35,55
an increment is applied to the last 4th no each tme...
not very sure if its crckt...
Regards,
PAYAL GUPTA
On Tue, Feb 28, 2012 at 12:48 PM, Kartik Sachan kartik.sac...@gmail.com
wrote:
I think logic is the difference is
2 2 4 2 2 2 8 so next will be 2 2 2 2 2 16
so ans will be 66 68 70
but first number 3 making some problem
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
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.
--
Srikanth Reddy M
(M.Sc Tech.) Information Systems
BITS-PILANI
--
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.
[algogeeks] Re: Programming Question
I dont know Pascal too well, but to me it looks like nested if statements. If xy , all the rest of it happens Since x is not greater than y, nothing happens. So x and y should remain the same (10,20) On Nov 17, 6:09 am, Vijay Khandar vijaykhand...@gmail.com wrote: In the following Pascal Program segment what is the value of X after the execution of the program segment? X:=10; Y:=20; If XY,then if X0 then X:=abs(X) else X:=2*X; Plz anyone explain -- 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.
[algogeeks] Re: Minimize bins
yea, i'd go with greedy also. Fill bin with biggest size s1 as much as possible (and same for other bins), then try to squeeze in next biggest size s2, etc. On Oct 29, 7:17 am, teja bala pawanjalsa.t...@gmail.com wrote: Greedy knapsack algorithm will work fine in this case as in each bin n1s1+n2s2+..nrsr=C gives the optimal solution... On Sat, Oct 29, 2011 at 4:34 AM, SAMMM somnath.nit...@gmail.com wrote: Suppose u have n1 items of size s1, n2 items of size s2 and n3 items of size s3. You'd like to pack all of these items into bins each of capacity C, such that the total number of bins used is minimized. -- 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.
[algogeeks] Re: Intersection of arrays
you didnt mention if duplicate elements should appear in the intersection or not. If no duplicates necessary, then your language may already have intersection between arrays built in. Or you should write an intersection operator/method between arrays (in ruby it is just the operator). My example output: arrays: 6 elements in each array: 20 range: 1 to 5 array #1: [4, 5, 5, 1, 4, 3, 4, 3, 2, 5, 2, 5, 1, 3, 3, 1, 2, 3, 1, 5] array #2: [2, 2, 3, 5, 2, 5, 1, 1, 2, 3, 1, 1, 2, 5, 3, 2, 3, 3, 2, 2] array #3: [1, 3, 2, 5, 4, 3, 1, 1, 2, 1, 5, 4, 4, 4, 2, 2, 5, 1, 2, 2] array #4: [3, 5, 4, 5, 1, 2, 3, 4, 3, 2, 1, 1, 2, 2, 4, 1, 2, 3, 2, 3] array #5: [2, 1, 5, 2, 1, 4, 3, 2, 3, 1, 2, 4, 4, 2, 4, 5, 5, 3, 5, 5] array #6: [4, 4, 2, 5, 3, 2, 5, 3, 5, 3, 2, 4, 4, 2, 5, 5, 4, 3, 1, 1] intersection: [2, 1, 3] my intersection here is simply ar1 ar2 ar3 ar4 ar5 ar6 , no duplicates show up. On Oct 28, 3:09 am, kumar raja rajkumar.cs...@gmail.com wrote: How is it possible to create a hash map using elements as keys and their counts as values .If we give some key the value is automatically computed by hash function .If u are given an element/key its index/value is calculated by hash function.am i corrct?? On 27 October 2011 22:36, Nitin Garg nitin.garg.i...@gmail.com wrote: The hashing solution is similar to the 1st answer herehttp://stackoverflow.com/questions/2932979/find-a-common-element-with... A sorting solution will take O(k.n.logn) time On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage ghat...@gmail.com wrote: Don, As you said, the intersection set, won't really be in sorted order as it depends on the elements of the second array, which are unsorted. Still, sorting them wouldn't be much different as it'd be worst case O(n logn).. [ Array 2 == Array 1 ] But sorting the First Array has already cost O(n logn) So I guess the worse case complexity has to be O(n logn) anyway.. On Thu, Oct 27, 2011 at 10:54 PM, Dan dant...@aol.com wrote: Hashing all of the K arrays seems like a bit much. How about this? You have K seperate arrays to start with, each array having N elements (is that correct?). 1) Sort the first array. 2) Step through the 2nd array, 1 element at a time say Array(2).element(i) Check to see if the value of Array(2).element(i) is in the first sorted array. If it is, add this numeric value to your list of intersection elements. As you pass through all elements of the 2nd array, the values found which are intersecting need to be saved ( maybe in the 1st arrays space to save memory). Ideally, these should be saved in sorted order as they are found. ( how you store the sorted array will affect speed of this check of course. I'd keep it simple on the 1st round, then optimize the code once everything appears to be working well, ie with buckets or pointers or whatever. How you determine if an element in array 2 intersects with an element of array 1 will depend on how you store your sorted array. You might do a linear search or a binary search or a bucket search of some sort ). 3) Now... step through the 3rd array, 1 element at a time, looking to see if each value is in the just created list of intersection elements 4) Do the save thing now with each of the remaining original K arrays. Dan :-) On Oct 24, 10:17 pm, kumar raja rajkumar.cs...@gmail.com wrote: Find intersection of K unsorted array of N elements each. Intersection consists of elements that appear in all the K arrays. what data structure is useful here?? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anup Ghatage -- 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. -- 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. -- Regards Kumar Raja
[algogeeks] Re: Intersection of arrays
sorry, i made a slight coding mistake in my last post (invisible 7th array) , but the logic remains the same...corrected sample output: arrays: 6 elements in each array: 20 range: 1 to 5 array #1: [3, 4, 3, 4, 5, 3, 2, 2, 1, 4, 2, 3, 4, 4, 3, 1, 3, 2, 4, 4] array #2: [1, 4, 5, 2, 1, 5, 1, 4, 3, 1, 3, 2, 5, 4, 4, 1, 3, 4, 5, 3] array #3: [4, 3, 4, 3, 3, 5, 2, 5, 4, 5, 2, 2, 1, 5, 5, 4, 4, 1, 2, 2] array #4: [4, 2, 5, 1, 1, 1, 1, 1, 5, 5, 1, 3, 4, 1, 5, 4, 3, 5, 2, 5] array #5: [3, 4, 2, 5, 1, 4, 1, 5, 5, 5, 3, 5, 2, 1, 4, 1, 1, 5, 2, 5] array #6: [5, 5, 2, 4, 3, 5, 5, 4, 1, 4, 2, 3, 1, 1, 5, 2, 5, 1, 3, 4] intersection: [3, 4, 5, 2, 1] On Oct 28, 3:09 am, kumar raja rajkumar.cs...@gmail.com wrote: How is it possible to create a hash map using elements as keys and their counts as values .If we give some key the value is automatically computed by hash function .If u are given an element/key its index/value is calculated by hash function.am i corrct?? On 27 October 2011 22:36, Nitin Garg nitin.garg.i...@gmail.com wrote: The hashing solution is similar to the 1st answer herehttp://stackoverflow.com/questions/2932979/find-a-common-element-with... A sorting solution will take O(k.n.logn) time On Fri, Oct 28, 2011 at 9:51 AM, Anup Ghatage ghat...@gmail.com wrote: Don, As you said, the intersection set, won't really be in sorted order as it depends on the elements of the second array, which are unsorted. Still, sorting them wouldn't be much different as it'd be worst case O(n logn).. [ Array 2 == Array 1 ] But sorting the First Array has already cost O(n logn) So I guess the worse case complexity has to be O(n logn) anyway.. On Thu, Oct 27, 2011 at 10:54 PM, Dan dant...@aol.com wrote: Hashing all of the K arrays seems like a bit much. How about this? You have K seperate arrays to start with, each array having N elements (is that correct?). 1) Sort the first array. 2) Step through the 2nd array, 1 element at a time say Array(2).element(i) Check to see if the value of Array(2).element(i) is in the first sorted array. If it is, add this numeric value to your list of intersection elements. As you pass through all elements of the 2nd array, the values found which are intersecting need to be saved ( maybe in the 1st arrays space to save memory). Ideally, these should be saved in sorted order as they are found. ( how you store the sorted array will affect speed of this check of course. I'd keep it simple on the 1st round, then optimize the code once everything appears to be working well, ie with buckets or pointers or whatever. How you determine if an element in array 2 intersects with an element of array 1 will depend on how you store your sorted array. You might do a linear search or a binary search or a bucket search of some sort ). 3) Now... step through the 3rd array, 1 element at a time, looking to see if each value is in the just created list of intersection elements 4) Do the save thing now with each of the remaining original K arrays. Dan :-) On Oct 24, 10:17 pm, kumar raja rajkumar.cs...@gmail.com wrote: Find intersection of K unsorted array of N elements each. Intersection consists of elements that appear in all the K arrays. what data structure is useful here?? -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- Anup Ghatage -- 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. -- 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. -- Regards Kumar Raja M.Tech(SIT) IIT Kharagpur, 10it60...@iitkgp.ac.in -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to
[algogeeks] FACEBOOK ONLINE CODING ROUND
small typo.. in part 2) it should say 13-(1+4+6)=2. Basically when the position becomes smaller than the element, you stop subtracting. -- 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.
[algogeeks] Re: FACEBOOK ONLINE CODING ROUND
is this contest still going? if so, where ? i have a solution that does (100, 1267650600228229401496703205376 )(just one hundred 1's) in 0.03 seconds in an older ruby on an older pc I'd like to submit ;P On Oct 21, 10:48 pm, sunny agrawal sunny816.i...@gmail.com wrote: yea i know 1st Approach is much better and is Only O(N^2) for precomputing all the values for nck and then O(k) for finding no of bits set in The Kth number and another loop of O(k) to find the required number i posted 2nd approach in the context to vandana's tree approach of sorting 2^N numbers, rather simply sort the numbers in the array... and this approach is O(N*2^N) On 10/21/11, sravanreddy001 sravanreddy...@gmail.com wrote: @Sunny.. why do we need an O(2^N) complexity? for a value of N=40-50, the solution is not useful.. but, your 1st approach is lot better and i have got it too.. 1. O(N) complexity to search the k. (k bits in the numbers) x- (sigma 1-k (n C i)) 2. again, keep substracting (k-i) for i= 0-k-1 so.. O(k) here and recursively performing step 2. (worst case complexity is O(T)) where T = nCk O(N) + O(T) == O(T) as it dominates the given number. unless it doesn't fall in the range.. or equivalently -- max( O(T), O(N) ) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/NJR9l-UB7c8J. 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. V 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.
[algogeeks] i cannot solve this written test question
one possible ruby solution/pic attached -- 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. attachment: digsum_output.png
[algogeeks] i cannot solve this written test question
one possible solution in ruby (sry if this is double-posted -- i did not see it come up the first time) [image: digsum_output.png] -- 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. digsum_output.png
[algogeeks] Re: remove duplicate words from a string
a) 1. could split the string using a regexp (into an array) in which you define a word -- is hi. the same as hi, and hi ? 2. then perform a unique operation on the array (some languages have this built in) to remove duplicates 3. recombine array elements into string by joining with a space, for example, depending on how you split it in the first step b) Perhaps another way, in-place, could be to check the string, one word (again define this) at a time, storing each word in a hash. If the hash already contains the word, replace this occurrence with spaces or null bytes. Finally compact the string (remove all null bytes, or turn all extra spaces into one space, etc). icy` On Oct 10, 3:08 pm, sunny agrawal sunny816.i...@gmail.com wrote: Trie will take too much space.. Balanced Binary tree can be Better ...?? On Tue, Oct 11, 2011 at 12:16 AM, Ankur Garg ankurga...@gmail.com wrote: I think this can be done through tries Any better solution ? On Mon, Oct 10, 2011 at 10:59 PM, sachin goyal monugoya...@gmail.comwrote: remove duplicate words from a string with min. complexityy. -- 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. -- Sunny Aggrawal B.Tech. V 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.
[algogeeks] Re: character count in array
Just use a hash to count frequency of something; e.g. in ruby:
ar= %w(a a b c a b b c d e a d e f)
freq=Hash.new(0)
ar.each {|c| freq[c]+=1}
p freq
#output
#{a=4, b=3, c=2, d=2, e=2, f=1}
you could only do it in place in O(1) only if your input array is
already 2*(number of all possible characters) size, but you didnt
mention size of input array. For example, what if input was just
[a,b,c,d,e] ? The size is 5.You cant just convert the input
into [a,1,b,1,c,1,d,1,e,1] without increasing the size to 10. So
hash is the better method.
On Sep 3, 11:04 am, Ankuj Gupta ankuj2...@gmail.com wrote:
if for all inputs you array remains of same size we can take it as
constant space
On Sep 3, 7:49 pm, rajul jain rajuljain...@gmail.com wrote:
@ankuj just want to clarify that in hashing method we require array of
fixed size let say arr[26] , so is it considered as constant space or not?
On Sat, Sep 3, 2011 at 8:02 PM, siddharam suresh
siddharam@gmail.comwrote:
sol already posted please search old thread
Thank you,
Sid.
On Sat, Sep 3, 2011 at 8:01 PM, Ankuj Gupta ankuj2...@gmail.com wrote:
If we take our input to be characters a-z ans A-Z then we require
fixed space which can be treated as O(1).
On Sep 3, 7:10 pm, teja bala pawanjalsa.t...@gmail.com wrote:
this 'll work if u i/p the string in dis manner
aaabbcc(consecutive same)
a3b2c2
#includestdio.h
#includeconio.h
main()
{
int x=1,i=0;
char a[100];
gets(a);
while(a[i]!='\0')
{
while(a[i]==a[i+1])
{
x++;
i++;
}
printf(%c%d,a[i],x);
x=1;
i++;
}
getchar();
}
--
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.
[algogeeks] Find the Max from each sub-array of size k Options
comparison/benchmarks of the 1) naive method, which just calls max with every new index, up to size of array - k 2) my method , which only makes a call to max if the old max is out of range or the newest/very rightmost element is greater than max ruby code: [image: max_subarray_text.png] benchmark output: [image: max_subarray_output.png] To test this, I had shuffled an array of size 1000 with k=25.I also called each method 1000 times, which shows 5x improvement over naive method icy` -- 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. max_subarray_output.pngmax_subarray_text.png
[algogeeks] Re: Find the Max from each sub-array of size k Options
I apologize to the group; i meant to post as reply to Find the Max from each sub-array of size k but I accidentally selected the word Options as well. Sorry. On Sep 2, 3:42 pm, icy` vipe...@gmail.com wrote: comparison/benchmarks of the 1) naive method, which just calls max with every new index, up to size of array - k 2) my method , which only makes a call to max if the old max is out of range or the newest/very rightmost element is greater than max ruby code: [image: max_subarray_text.png] benchmark output: [image: max_subarray_output.png] To test this, I had shuffled an array of size 1000 with k=25. I also called each method 1000 times, which shows 5x improvement over naive method icy` max_subarray_output.png 3KViewDownload max_subarray_text.png 26KViewDownload -- 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.
[algogeeks] Re: Fwd: 8 queens problem
interesting because just the other day I wrote something to get all 92
solutions for 8x8 n queens problem in a little under 3 sec. I
also used to play chess seriously, and my coach once gave me this
exercise to find a few working configurations.
I would advise against blindly placing all queens and then checking if
secure -- way too many combinations to go through. Your problem
here might be that it is possible to place 7 queens, and the 8th one
might have no place to go. At this point in your algorithm, doesnt
count become 8 anyway, and tries to return true?
I went with the algorithm to place the rooks on the board, 8!
permutations, one on each row, and then check all diagonals. This can
be limited to even fewer iterations, but it was fast enough for me.
hope this helps,
icy`
On Sep 1, 3:30 pm, mc2 verma qlearn...@gmail.com wrote:
hey guys ,
I am trying to solve 8-queens problem using backtracking. Here is my algo.
Could someone please tell me what is wrong in this code??
bool queen(int p,int count , int position[][])
{
if(count == 8) return true;
for(int i=p,i8;i++)
for(int j=0;j8;j++)
if(marked(i,j) == false ) // finding secure position on board
{
markboard(i,j); // if found any secure position then
mark all board positions which are in range of queen.
position[count][count]={i,j}; //save position for final answer
count++;
if(queen(p+1,count,position[][]) == true)
return true;
}
}
--
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.
[algogeeks] Re: Find Max Sum Value Pairs
actually this makes me think about the question requirements a bit..
in math, arent sets supposed to have *unique* elements?
so if A= [ 1 2 3 4] , B= [ 1 2 3 4], then shouldnt
S = { (4,4) (4,3) (4,2) (4,1) (3,3) (3,2) (3,1) (2,2) (2,1)
(1,1) } ??
since A is equal to B, the size of S is (4 choose 2) plus the four
mirror pairs, so 6+4 = 10
and the question implies mathematical sets with that notation, so why
are there necessarily n squared elements in S ...?
On Sep 1, 2:01 pm, rajul jain rajuljain...@gmail.com wrote:
@bharat I think pair of your example would be (4,4) , (4,3) ,(3,4),
(3,3)
correct me if am wrong..
On Thu, Sep 1, 2011 at 4:55 PM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
@Mac: It gives us the first largest pair but need not all n pairs ..
ex:
A=1 1 3 4
B=1 2 3 4
pairs : (4,4),(4,3),(3,3),(2,4) .
On Thu, Sep 1, 2011 at 4:57 AM, MAC macatad...@gmail.com wrote:
since its sorted , cant we just take last (largest if assedning) elements
of each and return o(1) .. (since +ve we can do so i guess)
On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta navneetn...@gmail.comwrote:
Given two sorted positive integer arrays A(n) and B(n), we define a
set S = {(a,b) | a in A and b in B}. Obviously there are n2 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. need an O(n)
algorithm.
--
Regards,
Navneet
--
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.
--
thanks
--mac
--
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.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
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.
[algogeeks] Re: Find Max Sum Value Pairs
i kinda just ate my own words there ;P if a set has unique
elements, {4,4} isnt possible.. it would just be {4}
i'm not sure how to deal with ( ) instead of { }
On Sep 1, 5:12 pm, icy` vipe...@gmail.com wrote:
actually this makes me think about the question requirements a bit..
in math, arent sets supposed to have *unique* elements?
so if A= [ 1 2 3 4] , B= [ 1 2 3 4], then shouldnt
S = { (4,4) (4,3) (4,2) (4,1) (3,3) (3,2) (3,1) (2,2) (2,1)
(1,1) } ??
since A is equal to B, the size of S is (4 choose 2) plus the four
mirror pairs, so 6+4 = 10
and the question implies mathematical sets with that notation, so why
are there necessarily n squared elements in S ...?
On Sep 1, 2:01 pm, rajul jain rajuljain...@gmail.com wrote:
@bharat I think pair of your example would be (4,4) , (4,3) ,(3,4),
(3,3)
correct me if am wrong..
On Thu, Sep 1, 2011 at 4:55 PM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
@Mac: It gives us the first largest pair but need not all n pairs ..
ex:
A=1 1 3 4
B=1 2 3 4
pairs : (4,4),(4,3),(3,3),(2,4) .
On Thu, Sep 1, 2011 at 4:57 AM, MAC macatad...@gmail.com wrote:
since its sorted , cant we just take last (largest if assedning) elements
of each and return o(1) .. (since +ve we can do so i guess)
On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta
navneetn...@gmail.comwrote:
Given two sorted positive integer arrays A(n) and B(n), we define a
set S = {(a,b) | a in A and b in B}. Obviously there are n2 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. need an O(n)
algorithm.
--
Regards,
Navneet
--
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.
--
thanks
--mac
--
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.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
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.
[algogeeks] Re: Find Max Sum Value Pairs
@Dave thanks for clarifying that (4,3) is different from (3,4)
But let's suppose, for example, n is 3
so A is of size n, and B is of size n, as required
e.g. A = [1 1 2] , B = [1 2 2]
S = { (1,1) (1,2) (1,2) (1,1) (1,2) (1,2) (2,1) (2,2) (2,2) }
but now you see there are repeated points that are also in the same
order. These are duplicates and should be removed, if S is truly a
set. Pruned version:
S = { (1,1) (1,2) (2,1) (2,2) }
size of set is not n^2, or 9, but rather
(size of unique(A) ) * (size of unique(B) ) = 4
With this in mind, I would first eliminate or ignore duplicates as you
are iterating through A, B
On Sep 1, 5:50 pm, Dave dave_and_da...@juno.com wrote:
@Icy: You left off the pairs (3,4), (2,4), (2,3), (1,4), (1,3), and
(1,2). These are different than the pairs you listed, because they are
ordered: the first element is from set A and the second element is
from set B. This was masked because of your choice of A = B. But you
wouldn't have made that mistake if you had chosen A = [1 2 3 4] and B
= [5 6 7 8].
There is no restriction in the original problem statement that the
numbers in each array are distinct. One application I have seen of
this problem is with the travel reservation web sites, where they will
show you some number of the cheapest round trip flight combinations.
In that case, there is more to the data items than just the price,
including at least airline and flight time. Several different flights
might have the same price, so arrays like A = [1 1 2 3 3 3 3] and B =
[1 2 2 2 3 3 4 4 4 4] (with duplicate prices) are possible. In that
case, the first 2 (cheapest) round trips will have score 2. Then
follows 7 round trips with score 3. Etc.
Dave
On Sep 1, 4:12 pm, icy` vipe...@gmail.com wrote:
actually this makes me think about the question requirements a bit..
in math, arent sets supposed to have *unique* elements?
so if A= [ 1 2 3 4] , B= [ 1 2 3 4], then shouldnt
S = { (4,4) (4,3) (4,2) (4,1) (3,3) (3,2) (3,1) (2,2) (2,1)
(1,1) } ??
since A is equal to B, the size of S is (4 choose 2) plus the four
mirror pairs, so 6+4 = 10
and the question implies mathematical sets with that notation, so why
are there necessarily n squared elements in S ...?
On Sep 1, 2:01 pm, rajul jain rajuljain...@gmail.com wrote:
@bharat I think pair of your example would be (4,4) , (4,3) ,(3,4),
(3,3)
correct me if am wrong..
On Thu, Sep 1, 2011 at 4:55 PM, bharatkumar bagana
bagana.bharatku...@gmail.com wrote:
@Mac: It gives us the first largest pair but need not all n pairs ..
ex:
A=1 1 3 4
B=1 2 3 4
pairs : (4,4),(4,3),(3,3),(2,4) .
On Thu, Sep 1, 2011 at 4:57 AM, MAC macatad...@gmail.com wrote:
since its sorted , cant we just take last (largest if assedning)
elements
of each and return o(1) .. (since +ve we can do so i guess)
On Thu, Sep 1, 2011 at 2:15 PM, Navneet Gupta
navneetn...@gmail.comwrote:
Given two sorted positive integer arrays A(n) and B(n), we define a
set S = {(a,b) | a in A and b in B}. Obviously there are n2 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. need an O(n)
algorithm.
--
Regards,
Navneet
--
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.
--
thanks
--mac
--
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.
--
**Please do not print this e-mail until urgent requirement. Go Green!!
Save Papers = Save Trees
*BharatKumar Bagana*
**http://www.google.com/profiles/bagana.bharatkumarhttp://www.google.com/profiles/bagana.bharatkumar
*
Mobile +91 8056127652*
bagana.bharatku...@gmail.com
--
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.-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
[algogeeks] Re: microsoft interview
Dave has a nice idea but I cant get it to work =/ [[1, 0, 0, 1], [0, 0, 1, 0], [0, 0, 0, 0]] original matrix [[1, 0, 1, 1], [1, 1, 1, 1], [0, 0, 1, 1]] dave's [[1, 1, 1, 1], [1, 1, 1, 1], [1, 0, 1, 1]] expected Maybe I converted it wrong. My method was basically the same as Anup's -- 1st pass fill rows and convert 1's to 2's. 2nd pass check for 2's and fill those columns. But complexity seems to be n*m*m + n*m*n = nm^2 + mn^2 which is about O(n^2 m^2) ?=/ I would like to get Dave's to work =P On Aug 31, 1:47 pm, siva viknesh sivavikne...@gmail.com wrote: @dave...additionally u ve to do this...checking the 1st row nd 1st column... if(a[0][0]) set both first row and first column; else for(i=1;in;i++) if(a[0][i]) set first row; else set first column; On Aug 31, 10:34 pm, siva viknesh sivavikne...@gmail.com wrote: dave s algo is nice :) On Aug 31, 10:09 pm, Dave dave_and_da...@juno.com wrote: @Ashima: Scan all but the first row and the first column. If there is a 1 in a row, set the first element of that row to 1. If there is a 1 in a column, set the first element of that column to zero. Now, set any element in all but the first row and the first column of the matrix that has a 1 it the first element of its row or a 1 in its first element of its colunn to 1. Dave On Aug 31, 12:02 pm, Ashima . ashima.b...@gmail.com wrote: @dave wats d logic behind ur code Ashima M.Sc.(Tech)Information Systems 4th year BITS Pilani Rajasthan On Wed, Aug 31, 2011 at 9:05 AM, Dave dave_and_da...@juno.com wrote: @Manish: for( i = 1 ; i n ; ++i ) for( j = 1 ; j m ; ++j ) if( a[i][j] != 0 ) a[i][0] = a[0][j] = 1; for( i = 1 ; i n ; ++i ) for( j = 1 ; j m ; ++j ) if( a[i][0] + a[0][j] != 0 ) a[i][j] = 1; Dave On Aug 31, 8:40 am, manish kapur manishkapur.n...@gmail.com wrote: Input is a matrix of size n x m of 0s and 1s. eg: 1 0 0 1 0 0 1 0 0 0 0 0 If a location has 1; make all the elements of that row and column = 1. eg 1 1 1 1 1 1 1 1 1 0 1 1 Solution should be with Time complexity = O(n*m) and O(1) 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.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.-Hidequotedtext - - 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 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.
[algogeeks] Re: APTITUDE QUESTIONS
1. b2. c 3. a I think ;P I tried to do all by hand with some shortcuts, but i got 2 for the third one, so it' s a bit of a guess On Aug 30, 10:27 am, abhishek abhishek.ma...@gmail.com wrote: 1. Teacher asked the students to find the cube root of a natural number but she did not mention the base. Students assumed the base found the cube root. Each student got an integer. Find the sum of digits of that number. A. 0 B. 1 C. 6 D. 7 E. 8 2. What is the difference of last two digits of N where N=7^2010 a.1 b.3 c.5 d.7 e.9 3.Find the first non Zero digit in 67!(Factorial) a.3 b.4 c.5 d.6 e.7 -- 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.
[algogeeks] Re: APTITUDE QUESTIONS
For the third one by hand, I was just trying to keep track of 1-2 of the first digits for each section. I broke into sections as follows (^ to mean power here): 9! = (I just did this by hand, 1728x210=362880) , so we take 36. 10! to 19! = approx 1^10 = 1 20! to 29! = approx 2^10 = 1024 = 10 30! to 39! = approx 3^10 = 3, 6, 9, 27, 81, 243, 72.., 216.., 63..., 189.. = 1 40! to 49! = 4^10 = 4, 16, 64, 25.., 10.., 4.. = this looked like a pattern, the tenth one should be 1.. again = 1 50! to 59! = 5^10 = 5, 25, 125, 60.. , 30.., 150.., 75.., 37.., 18.., 90 = 9 60! to 67! = 6^8 = 6, 36, 216, 126.. , 72..., 43.., 25.., 15.. = 1 so actually to correct what I had above, I was really looking to do 9*36 , (not 9*3=27), which gives about 324, or 3 for the first digit. This is just an approximation but it seems to work. On Aug 30, 4:06 pm, kartik sachan kartik.sac...@gmail.com wrote: for 1st question ans will be a,b,e as (125)^1/3 is 5 sum is 8 for 2nd question we see pattern in 7 power i.e 7,9,3,1 and this pattern reapeats for inerval of 4 and second term of of any power of 7=2 is 4 so diff is 5 ans will be 5 how to find the ans of third question?? -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: solving a simple equation
well if the answer is more than 3, I would be surprised. There are probably some integer rules to justify really small limits, but here is how I justified it to myself: I. Treat every variable like it is a.2a^2 = 4a , or a^2 = 2a . This only works for a=1, a=2. So likely a cannot be more than 2. a) suppose a=1 and treat d as a c. b+c^2 = 1+b+2c c^2 = 1+2c c^2 - 2c - 1 = 0 c^2 - 2c +1 = 2 (c-1)^2 = 2 c = 1+- sqrt(2) hmm.. so c doesnt even reach 3 b) suppose a=2 and treat d as a c. 2b + c^2 = 2 + b + 2c b = -c^2 - 2c + 2 with values of c=3 , the right side is negative. II. conclusions? a is at most 2, and c is at most 2. So yea, basically what Don said. 1, 1, 2, 3 1, 2, 2, 3 2, 2, 2, 2 On Aug 30, 5:05 pm, Don dondod...@gmail.com wrote: There are three solutions, with d never exceeding 3. Don On Aug 30, 3:08 pm, him himanshuarora.1...@gmail.com wrote: finding number of integral solution of the equation ab+cd=a+d+b+c (1=a=b=c=d) (any efficient method ) -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: convert a string into another in minimum number of steps
Yea, I hope the intermediate words are dictionary words; it's more fun that way. I played such a game before, where you and a friend try to convert some 4-letter word into another, using legal words. BIKE - LAZY BIKE BAKE RAKE RAZE LAZE LAZY On Aug 30, 2:25 am, kARTHIK R k4rth...@gmail.com wrote: So the intermediate words need not be dictionary words? Karthik R, RD Engineer, Tejas Networks. On Tue, Aug 30, 2011 at 11:50 AM, PRATEEK VERMA prateek...@gmail.comwrote: edit distance algorithm -- 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.
[algogeeks] Re: puzzle
I hope you dont mind that I respond to the original question about the 6x6 matrix. As I understand it, all elements have to be either 1 or -1, and product of *every* row and *every* column is 1 = how many arrangements? Now a bunch of you seem to think(nxn) = 2^((n-1)^2) gives the answer, so I'm trying to give it a chance, but already I'm kinda skeptical that the answer is over 33million . I wrote a brute force which I'm trying to test for small case 3x3. Using the formula you guys gave, 2^(2^2) == 2^(4) == 16. My program outputs, for n=3: [[-1, -1, nil], [-1, -1, nil], [nil, nil, nil]] [[-1, nil, -1], [-1, nil, -1], [nil, nil, nil]] [[nil, -1, -1], [nil, -1, -1], [nil, nil, nil]] [[-1, -1, nil], [nil, nil, nil], [-1, -1, nil]] [[-1, nil, -1], [nil, nil, nil], [-1, nil, -1]] [[nil, -1, -1], [nil, nil, nil], [nil, -1, -1]] [[nil, nil, nil], [-1, -1, nil], [-1, -1, nil]] [[nil, nil, nil], [-1, nil, -1], [-1, nil, -1]] [[nil, nil, nil], [nil, -1, -1], [nil, -1, -1]] 10 The nil is just a null value; imagine it is the 1 in the problem. The program gives 9 cases, and implied is the empty set case, which would be all nil's, or in our case, contains no -1's, but instead has all 1's. So together it gives 10. I even drew up the cases so that it would be easier to see -- http://i56.tinypic.com/24b5kiq.png So first I will ask, where are the missing 6 cases? For each row, we choose 0, 2, 4, ...n-1's to fill it with. If we fill, for example, matrix[0][0] and matrix[0][1] with -1 , to satisfy the first row requirement, this actually determines the columns, do not forget.If we use this example for the simple 3x3 case, it is clearly seen that the first two columns must have *exactly* one more -1 to fulfill the even requirement (my output shows this in case #1 and case #4). I think the formula does not cut enough of these intersections off. I'm getting 962 for n=6 , so lol icy` On Aug 26, 10:34 am, Naren s sweetna...@gmail.com wrote: varun: can u explain it little further.. On Wed, Aug 10, 2011 at 7:49 PM, varun pahwa varunpahwa2...@gmail.comwrote: make two ropes 50m and 100 meter. make a loop kind of thing with that now you have two 50 mtr ropes so get down to 100 mtr point and tie loop rope in downward now cut the loop at 100 mtr you have 100 mtr rope then move down with the help of that. i hope i am clear. On Mon, Aug 8, 2011 at 1:52 PM, Shachindra A C sachindr...@gmail.comwrote: tie the rope to the peg and hold the rope at a little less than 100m point. Then jump. On Mon, Aug 8, 2011 at 1:19 PM, Himanshu Srivastava himanshusri...@gmail.com wrote: @Dave oh i thought some logical concept willl be applied in that case...it is ok!!! thanks:) On Fri, Aug 5, 2011 at 1:47 AM, Dave dave_and_da...@juno.com wrote: @Himanshu: That is easy for any boy scout. :-) Tie the rope at the top of the tower. Then tie a sheepshank knot of a comfortable length in the rope and cut the middle strand inside the knot. Climb down the rope to the peg and tie the other end of the rope onto the peg. Then, while standing on or hanging from the peg, shake the upper rope to release the sheepshank knot. The upper end will fall down and you can climb the rest of the way down. Dave On Aug 4, 1:50 pm, Himanshu Srivastava himanshusri...@gmail.com wrote: suppose u tie the rope at 200mt height and now climb down to 100m heightthen u tie the rope at that point then how will you open the rope at point above 200mt where u have tied it earlier On Thu, Aug 4, 2011 at 11:15 PM, mohit verma mohit89m...@gmail.com wrote: can't we tie the rope where we are standing (at height of 200 meter)? On Thu, Aug 4, 2011 at 10:26 PM, neeraja marathe neeraja.marath...@gmail.com wrote: this was the puzzle asked to me in NVIDIA interview: you are standing on top of a tower of ht 200 mt. .At 100 mt. ht . from bottom of tower there is a peg where u can tie a rope. You have a rope of length 150 mt. with you and using this rope you have to get down the tower. you can not jump or there is nobody to help you. how will u get down the tower?? -- 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. -- *MOHIT VERMA* -- 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
[algogeeks] Re: puzzle
Other than making little loops and risking the fall on the first trip down, I dont think the rope question has an answer. NVIDIA just wanted to see if you were suicidal =D On Aug 26, 3:36 pm, Piyush Grover piyush4u.iit...@gmail.com wrote: Cut the rope in 50mtrs and 100mtrs length. Make a small loop(of negligible length at one end of the 50 mtrs rope) Tie the other end of the rope at the top and from the loop end side pass the 100mtrs rope such that you have both the ends of 100mtrs rope in your end. now get down at 100mtrs peg point(~50 + 50 = 100 mtrs). Pull the 100 mtrs rope and tie it at the peg at 100mtrs height. Get down to the bottom. On Fri, Aug 26, 2011 at 7:29 PM, Himanshu Srivastava himanshusri...@gmail.com wrote: lol :P On Wed, Aug 10, 2011 at 11:35 PM, $hr! k@nth srithb...@gmail.com wrote: Tie the rope at the top of the tower Climb down with the help of the rope up to 100 mt peg possItion Tie the rope to that peg, Climb up to the top of the tower with that rope. Now release the rope at the top and hold it. It ll take you down.:P On Wed, Aug 10, 2011 at 7:49 PM, varun pahwa varunpahwa2...@gmail.comwrote: make two ropes 50m and 100 meter. make a loop kind of thing with that now you have two 50 mtr ropes so get down to 100 mtr point and tie loop rope in downward now cut the loop at 100 mtr you have 100 mtr rope then move down with the help of that. i hope i am clear. On Mon, Aug 8, 2011 at 1:52 PM, Shachindra A C sachindr...@gmail.comwrote: tie the rope to the peg and hold the rope at a little less than 100m point. Then jump. On Mon, Aug 8, 2011 at 1:19 PM, Himanshu Srivastava himanshusri...@gmail.com wrote: @Dave oh i thought some logical concept willl be applied in that case...it is ok!!! thanks:) On Fri, Aug 5, 2011 at 1:47 AM, Dave dave_and_da...@juno.com wrote: @Himanshu: That is easy for any boy scout. :-) Tie the rope at the top of the tower. Then tie a sheepshank knot of a comfortable length in the rope and cut the middle strand inside the knot. Climb down the rope to the peg and tie the other end of the rope onto the peg. Then, while standing on or hanging from the peg, shake the upper rope to release the sheepshank knot. The upper end will fall down and you can climb the rest of the way down. Dave On Aug 4, 1:50 pm, Himanshu Srivastava himanshusri...@gmail.com wrote: suppose u tie the rope at 200mt height and now climb down to 100m heightthen u tie the rope at that point then how will you open the rope at point above 200mt where u have tied it earlier On Thu, Aug 4, 2011 at 11:15 PM, mohit verma mohit89m...@gmail.com wrote: can't we tie the rope where we are standing (at height of 200 meter)? On Thu, Aug 4, 2011 at 10:26 PM, neeraja marathe neeraja.marath...@gmail.com wrote: this was the puzzle asked to me in NVIDIA interview: you are standing on top of a tower of ht 200 mt. .At 100 mt. ht . from bottom of tower there is a peg where u can tie a rope. You have a rope of length 150 mt. with you and using this rope you have to get down the tower. you can not jump or there is nobody to help you. how will u get down the tower?? -- 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. -- *MOHIT VERMA* -- 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.-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 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, Shachindra A C -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this
[algogeeks] Re: Find the non-duplicate element in sorted array in O(n) time
my binary search method in Ruby is similar to Don's. I tested with
array [1,1,2,2,2,2,3,3,9,14,14] , to which the answer should be 9,
and now added what I call fluff (meaningless numbers) to either:
the left (300_000 zeroes at the head) , making it difficult for direct
approach; the middle (150_000 of each of the 3's and 14's around
the 9 ); or the right (300_000 18's added to the end). I also had
it run each method 100 times. I just hope the following formats
decently...
user system totalreal
fluff on left
direct 16.75 0.00 16.75 ( 16.753000)
binary0.00 0.00 0.00 ( 0.002000)
fluff in middle
direct8.344000 0.00 8.344000 ( 8.335000)
binary6.844000 0.00 6.844000 ( 6.846000)
fluff on right
direct0.00 0.00 0.00 ( 0.001000)
binary0.00 0.00 0.00 ( 0.003000)
As expected, the direct approach sucks when it hits a large n and the
singleton is near the end. It actually does fairly well otherwise.
By the way, Don, I took pairs to mean it divides 2 evenly, and the
asker even gave an example with four 2's. (Assuming his result should
be 4, not 5, typo ;P). So your line about decreasing the midpoint
just once is not enough, and actually to increase binary performance,
a check should be made if ar[mid]==ar[left] , also check if
ar[mid]==ar[right], and if it does, like in my fluff examples , you
can save loads of time on useless checks.
@surender -- good question; I would think no, but binary search would
still return 3. Direct approach would fail with default checks. I
got the impression we were searching for a single[ton].
On Aug 25, 6:32 am, surender sanke surend...@gmail.com wrote:
{ 1,1,2,2,2,2,3,3,3,4,4,5,5}, here 3 is missing its pair, does this also
comes under this problem?
surender
On Thu, Aug 25, 2011 at 8:12 AM, Dave dave_and_da...@juno.com wrote:
@Shailesh: Sir, your response is unresponsive, because the original
poster specifically asked for a solution that was O(n). Please don't
waste our time giving answers that so obviously do not meet the
problem statement.
Dave
On Aug 24, 6:33 pm, smb shaileshbir...@gmail.com wrote:
XOR all the elements, the answer is the number you want.
On Aug 24, 5:11 pm, Don dondod...@gmail.com wrote:
I assume that elements in pairs means that each value occurs exactly
twice except for the one single.
This algorithm is O(log n) and is nonrecursive. Writing it recursively
would make it a couple of lines shorter, but because it is purely tail
recursion, that is not necessary.
// Given an array a of size elements in which all elements occur in
pairs except for one single item,
// find the single item and return its value.
int findSingle(int *a, int size)
{
while(1)
{
// For an array of size 1, the only element is the single.
if (size == 1) return a[0];
// The logic below won't work for size three, but it is simple to
find the single.
else if (size == 3) return (a[0] == a[1]) ? a[2] : a[0];
else
{
// Pick the midpoint of the array
int midpoint = size/2;
// If we are looking at the second element of a pair, move back
to the first element
if (a[midpoint] == a[midpoint-1]) --midpoint;
// If midpoint is not a pair, that is the single.
else if (a[midpoint] != a[midpoint+1]) return a[midpoint];
// If midpoint is odd, look at left half of the array
if (midpoint % 2) size = midpoint;
else // If midpoint is even, look at the right half of the array
{
a += midpoint;
size -= midpoint;
}
}
}
}
On Aug 24, 4:49 am, atul purohit gonewiththe...@gmail.com wrote:
Hi,
A* sorted *integer array contains elements in pairs. All the pairs
are
complete except one element whose pair is missing. Find that element.
Ex. { 1,1,2,2,2,2,3,3,4,5,5}
result = 5
There is a standard solution which returns an XOR of all the
elements. But
this needs O(n) time complexity. The person who asked me this
question said
that this can be done in O(n). Maybe we can eliminate some
elements.
Anyone knows how to do this?
Cheers,
Atul- 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 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
[algogeeks] Re: Reverse dutch flag problem
not enough information, imo. Tell me more about the given string... is the string made up of consecutive integers/characters ? Are there always the same number of each character type? And the goal is to braid , like the hairstyle, as much as possible (if the previous answer is no, all braids cannot be the same)? On Aug 25, 1:50 pm, sachin sabbarwal algowithsac...@gmail.com wrote: one solution might be: to traverse whole list counting no of zeros and 1's. and then make another string(or overwrite the same) with the required pattern,append any other characters(suppose all 0's exhausted and some 1's and 2's were left) left at the end. is there any better solution?? On Sat, Aug 20, 2011 at 4:20 PM, sukran dhawan sukrandha...@gmail.comwrote: i that .ink the soln for this problem is given in geeksforgeeks.com On Sat, Aug 20, 2011 at 3:27 PM, Sanjay Rajpal srn...@gmail.com wrote: Suppose we are given a string . Make it 012012012012 in O(n) time and O(1) space. Sanju :) -- 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.
[algogeeks] Re: find the complexity
isnt this logarithmic?regular loop 1..n runs in n/(1 step each time) - O(n) this loop n/(k + k^2 each time) - ln(n)/ ( ln(k) + k ln(2) ) - ln(n-k) - O(ln(n)) or something like that ;P I was going from memory. Please confirm, but I feel like it approaches logarithmic speed. On Aug 25, 1:46 pm, sachin sabbarwal algowithsac...@gmail.com wrote: what will be the time complexity?? sum=1 for(k=0; kn; k = k+2^k) sum=sum+sum; end print(sum); -- 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.
[algogeeks] Re: Apti
nice prakash. Algorithm is definitely better than brute force. But
here is brute force anyway, just go from 2 to square root of n ;P
I initially misread it and thought you were asking for ANY {c,d} set
in which c,d are factors of n (but not necessarily c*d = n) . That
wouldve been all of the factors (12) , choose 2, unless I am
mistaken. 12 nCr 2 = 66.
#!/usr/bin/ruby -w
#how many unique sets {a,b} can be formed if a,b are factors of N and
axb=N
# N = 24*33
n=792
#factors = [2,2,2,3,3,11]
#results
res=['1x792']
2.upto(Math.sqrt(n)) {|c|
next unless (c1).zero? || c%3==0 || c%11==0
resc.to_s+'x'+(n/c).to_s if n%c==0
}
p res, res.size
# output $ ./set_factors.rb
#[1x792, 2x396, 3x264, 4x198, 6x132, 8x99, 9x88,
11x72, 12x66, 18x44, 22x36, 24x33]
#12
On Aug 23, 2:39 pm, Nikhil Gupta nikgp...@iitr.ernet.in wrote:
sorry I wrote them in different order:
if (a,b) and (b,a) are considered same then answer is 12
and if they are considered different it is 24.
--
Nikhil Gupta
Indian Institute of Technology Roorkee,
Roorkee, Uttarakhand,
India , 247667
Phone: +91 9634990161
email: nikgp...@iitr.ernet.in
nikhilg.8...@gmail.com
--
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.
[algogeeks] Re: Longest palindrome
brute force...http://codepad.org/D07BNo91 There are some checks to help reduce O(n^2), so I want to say.. O(1.5n) ?=) #output for str = 'abaccddccefe' #ccddcc 6 #for str = 'abraxyzarba' #a 1 On Aug 22, 1:09 pm, uma umai...@gmail.com wrote: can yo tell exactly , how the suffix tree is used for finding palindromes? On Aug 22, 3:58 am, WgpShashank shashank7andr...@gmail.com wrote: Hey Geeks I think question can be solved by many ways . some of the algorithms are i have implemented aware of are - 1st. Algo Generate all palindromes (even odd length ) of given string while keep tracking of their length in last just compare max (evenlength_palindrome , oddlength_palindrome) . Time Complexity O(N^2) where N is length of String 2nd . Algo. For Those Who are just saying Use DP :) Find The LCS(Longest Common Sub-sequence of String (say s1) reverse of String (say s2) ) It Involves DP to solve efficiently but guaranteed optimal solution Time Complexity O(N^2) where N is length of String Space Complexity O(N^2) for table 3rd. Use Suffix Tree ( Need to Work On It) basic idea is to build the suffix tree of string reverse string check no every node where suffix belongs to , the deepest common node will us longest palindrome in given string. Correct me if i missed something ? Thanks Shashank Mani Computer Science Birla Institute of Technology ,Mesra -- 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.
[algogeeks] Re: Longest palindrome
sorry, I meant to joke about (0.5 * n^2) ;P On Aug 22, 4:46 pm, icy` vipe...@gmail.com wrote: brute force... http://codepad.org/D07BNo91 There are some checks to help reduce O(n^2), so I want to say.. O(1.5n) ? =) #output for str = 'abaccddccefe' #ccddcc 6 #for str = 'abraxyzarba' #a 1 On Aug 22, 1:09 pm, uma umai...@gmail.com wrote: can yo tell exactly , how the suffix tree is used for finding palindromes? On Aug 22, 3:58 am, WgpShashank shashank7andr...@gmail.com wrote: Hey Geeks I think question can be solved by many ways . some of the algorithms are i have implemented aware of are - 1st. Algo Generate all palindromes (even odd length ) of given string while keep tracking of their length in last just compare max (evenlength_palindrome , oddlength_palindrome) . Time Complexity O(N^2) where N is length of String 2nd . Algo. For Those Who are just saying Use DP :) Find The LCS(Longest Common Sub-sequence of String (say s1) reverse of String (say s2) ) It Involves DP to solve efficiently but guaranteed optimal solution Time Complexity O(N^2) where N is length of String Space Complexity O(N^2) for table 3rd. Use Suffix Tree ( Need to Work On It) basic idea is to build the suffix tree of string reverse string check no every node where suffix belongs to , the deepest common node will us longest palindrome in given string. Correct me if i missed something ? Thanks Shashank Mani Computer Science Birla Institute of Technology ,Mesra -- 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.
[algogeeks] crossing a bridge; running away from zombies (logic puzzle)
Hey everyone, I recently joined this group, so I thought I'd add a short interview/ logic puzzle that I remember hearing. Hopefully it wasnt already said. Part of the fun is the story, so here it goes... Four people have been running away from a pack of zombies, and are now injured in varying degrees. It is already nighttime, and they have come upon a bridge. They must cross the bridge as fast as possible before the pack of zombies comes upon them, but the bridge is very dark, slippery, and cannot support much weight. There is one flashlight. Rules: * the bridge must be crossed with the flashlight, only two people at most. A return trip must be made (the flashlight cannot be thrown back, etc) * the four people cross the bridge at different speeds: 1minute, 2 minutes, 5 min, and 10min. A trip time is determined by the slowest person. So if the 1min crosses together with the 5min, the trip time is 5min. *if a person falls off the bridge, he/she goes to /dev/null;P So what is the fastest way for everyone to cross the bridge, and how long does that take? ~icy -- 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.
[algogeeks] Re: MS BRAINTEASR
hmm... interesting logic, but what about, for example, 8 people and 3 hats. Why can't one of the five without hats also be unsure and try to go swimming on one of the nights? I was thinking, if they somehow know how many hats there are (writing numbers in the sand or other cheating methods), it would be n choose c days at most, if they try a combination every night. But this can further be simplified to just n at most, if exactly one new person goes by himself at night. One cheating method: one man is a leader. The leader chooses all men he sees with hats and says let's go swimming at midnight. If that does not work, the next night the same people (but without the leader) go swimming at midnight. Two nights. So... I'm thinking n days, since the men do not know how many hats there are. And if cheating is allowed, 1-2 days. Remember, the question did say the men cannot *tell* each other...=P On Aug 18, 7:15 am, DheerajSharma dheerajsharma1...@gmail.com wrote: Case 1: when one person is wearing hat.The person wearing hat will see that no other is wearing hat.hence he must be wearing it.So she will take it off.hence one day Case 2: when two persons are wearing,first will think..that only second one is wearing..while second will think only first one is wearing.hence no one will go on first day. on the second day..when both will see the same thing..they will come to know..that they are also wearing hat..and making the second one confused ;) hence..they both will go and take off hat on second day. Case 3: first person sees hat on two others.(same for other two). no one will go on first day. On second day..same situation..bt this time the person is still unsure..wether she is wearing hat or not..bcoz case 2 can happen.. on third day..when same situation arises...they will come to know..that they are also wearing hat..hence..they will take it off on day 3. so on.. so on.. For C hats...C dayz... On Aug 18, 4:06 pm, DheerajSharma dheerajsharma1...@gmail.com wrote: it would take c days to take off all the hats On Aug 18, 3:51 pm, pg@manit gpt.pa...@gmail.com wrote: A bunch of men are on an island. A genie comes down and gathers everyone together and places a magical hat on some people’s heads (i.e., at least one person has a hat). The hat is magical: it can be seen by other people, but not by the wearer of the hat himself. To remove the hat, those (and only those who have a hat) must dunk themselves underwater at exactly midnight. If there are n people and c hats, how long does it take the men to remove the hats? The men cannot tell each other (in any way) that they have a hat. FOLLOW UP Prove that your solution is correct. -- 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.
[algogeeks] Re: Question from Google interview
Well no, I would think it would match Balls for him, since it is greedy -- it would try to match as much as possible that works/is in dict. So I have to agree with Aditya here, but I would go from the back/right to the left. So I would first get round, then hopefully are round and finally Balls are round. Now it gets tricky if the remaining left section cannot be broken into words. Then we'd have to backtrack once and take the next less-greedy match, and try again. If that fails, take even less greedier match , or backtrack yet again. On Aug 18, 1:05 pm, Dave dave_and_da...@juno.com wrote: @Aditya: You probably have to be a bit more careful than that. You can't add the space until both the first part is a word in the dictionary and the rest of the string can also be broken into words in the dictionary. Consider Ballsareround. Your algorithm seems to put a space after the second l, but then no initial part of sareround may be in your dictionary. In that case, you have to reject that space and continue until you get to a division point such that both the first part is in the dictionary and the second part can be broken into words. Sounds like a good place for recursion. Dave On Aug 18, 10:52 am, aditya kumar aditya.kumar130...@gmail.com wrote: not sure abt the algo but we can think in terms of tokeninzing . ie go for greedy method . greedy looks for maximum match . extract the token and match with the dictionary word . if match found then add the additional space else look for next token . On Thu, Aug 18, 2011 at 9:10 PM, Navneet Gupta navneetn...@gmail.comwrote: Given a string containing multiple words such that spaces between words is missing. Also, you have a dictionary containing valid words. Ex. Thatwouldbefantastic Output a string with proper spaces inserted. Output - That would be fantastic The case of words like bandwidth present can be discounted. -- Regards, Navneet -- 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.
[algogeeks] Re: Amazon question
#!/usr/bin/ruby -w
#array of unsorted positive integers
# find the [only] one that is duplicated
arr= [97,2,54,26,67,12,1,19,44,4,29,36,67,14,93,22,39,89]
h = Hash.new(0)
arr.each {|n|
h[n]+=1
(puts n; break) if h[n]==2
}
#output
#67
I hope this meets the requirements ;P
On Aug 18, 3:15 pm, *$* gopi.komand...@gmail.com wrote:
How to find duplicate element (only one element is repeated) from an array
of unsorted positive integers..
time complexity .. O(n)
space .. o(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.
