Re: [algogeeks] Can you guys help me how to approach this problem !!!
You guy check this solution. It is expected to be run in O(n lg n) for random permutation in average time. For worst case, I think we can improve it for that. Let's do an example firstly. 7 3 4 1 2 6 5 8 For *1*, it self is a block. Let's count the blocks containing *1* firstly. If a block with size more than 1 contains *1*, it will contains *2*. Now check *2*, it is not beside *1*, so no block with size=2 contains *1*. Let's check *3*', the minimum position for (1,2,3) is 1 (with 0 based index), and maximum position for (1,2,3) is 4. Because 4-1+1 = 4>3, no block with sizeo=3 contains *1*. Let's check *4*, the minimum position for (1,2,3,4) is 1, and maximum position is 4. The window size is 4-1+1 = 4. We find a block with size=4 and it contains *1*. By continuing this process, we will get the number of blocks containing number *1* and more important is the time we need is linear time: O(n). Now, we have checked all blocks including number *1*. So from now on, we do not need number *1* anymore. It means we can split the list into two [7 3 4] and [2 6 5 8] and repeat the above process again & again. If the permutation is really random, the above process is very similar as the QuickSort process and then we know the whole process cost O(n lg n) time. However, for worst case like [1 2 3 4 ... n], it performs very bad. The time complexity is linear with the number of blocks and so it is not good in worst case. I.e. the above algorithm need O(n^2) time for such worst case. Hope other guys can solve the worst case in O(n lg n) time. Thanks On Tue, Dec 1, 2009 at 2:33 PM, Vinoth Kumar wrote: > Given an array A which holds a permutation of 1,2,...,n. A sub-block A > [i..j] of an array A > is called a valid block if all the numbers appearing in A[i..j] are > consecutive numbers (may not be in order. > > Given an array A= [ 7 3 4 1 2 6 5 8] > the valid blocks are [3 4], [1,2], [6,5], [3 4 1 2], [3 4 1 2 6 5], [7 > 3 4 1 2 6 5], [7 3 4 1 2 6 5 8] > > Give an O( n log n) algorithm to count the number of valid blocks. > > > -- Vinod > > -- > > 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] how can i find size of an object in java
java normally pre-alloc much memory and so you have no way to get the actual heap usage with simple method. normally for a given jvm, the size of an object can be calculated statically. what you need is to read source code of jvm, :) anyway, you can simple estimate size of an object as the summation of its properties, plus some additional header fields. NOTE that reference only occupy a pointer size unit. This is quite different from c++. On Wed, Nov 25, 2009 at 5:20 PM, Abhijeet Kumar wrote: > > how do i measure the JVM memory ??? > can u specify a command or class to use?? > > On Wed, Nov 25, 2009 at 8:12 AM, Chakravarthi Muppalla > wrote: >> >> measure jvm memory usage before/after creating ur object; but it is not >> assured to give the correct size(gc). >> or u can use a premain agent. >> >> On Wed, Nov 25, 2009 at 12:37 AM, Abhijeet Kumar >> wrote: >>> >>> How can i find size of an object in java >>> plsss answer asap >>> >>> -- >>> >>> 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. >> >> >> >> -- >> Thanks, >> Chakravarthi. >> >> -- >> >> 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. > > > > -- > Cheers.. > Abhijeet Kumar > > -- > > 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] Horse race
firstly 5 races are required, because if even one horse is not used, this horse maybe the fastest and so the result will not be correct. with the following steps, 7 races are enough and so the question becomes "will 6 races or even 5 races enough?" 1. group the horses 5 by 5, and suppose the result is a1 < a2 < ... < a5 b1 < b2 < ... < b5 ... e1 < e2 < .. < e5 (here < means slower than) 2. group a5,b5,..,e5 into a race, suppose the result is a5 < b5 < c5 < d5 < e5 3. now the only candidates are e5 (the fastest), e4, e3, d5, d4, c5 4. group e4, e3, d5, d4, c5 into a race and pick the fastest two horse, support they are x, y 5. then the fastest 3 horses will be e5, x, y On Thu, Nov 5, 2009 at 6:05 PM, eSKay wrote: > There are 25 horses and you need to figure out the three fastest > horses by placing them into races. Assume there is no tie in the > speed. There are five tracks so for each race, you can place five > horses and figure out the relative rank among those five horses but > you don't have the exact finishing time, i.e. there is no direct > comparison between results from two different races. What's the > minimum number of races you need to arrange in order to figure out the > three fastest horses? > > -- > > 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. > 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] interview question
I guess this is just a *program* problem, not even including any algorithm problem. Even from viewer of c++ programmer, I think you should refer any classic c++ tutorial for it, instead of asking it online. It is an interview problem, and it can be find on any c++ book. Just use some time to find it. On Wed, Nov 4, 2009 at 7:08 PM, yash wrote: > write a program for "catlog " catlog contain subcatlog or product . > we can futher expand catlog/subcatalog. product is leaf of catalog > [like composite pattern] > > 1. write a c++ program to display the product on basis of product id. > write a copy constucter and assingement operator for catalog class > > > > example > Business > / \ > Compurter Cloths > / \ \ > monitor(product) sell shirt(prodcut > > > [business,computer,cloths,sell are catalog] > [monitor and shits are product] > > -- > > 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. > 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: aai + bj + ck =0
your algorithm need O(n^2) preprocess time and so the total time is still O(n^2). I guess the author asks a really O(n lg n) time algo On Tue, Nov 3, 2009 at 6:19 PM, anilkumarmyla wrote: > I propose another solution with O(N LogN) Time Complexity and O(N^2) Space > complexity (not sure if it would count towards space or time) > > Space > 1) Generate all possible combinations of A[i] + B[j] and maintain them in an > array D (N^2 array) ---> O(N^2) > 2) Build a min or max heap out of D array using bottom up building ---> > O(N^2) > > Now D contains all possible sums of A[i] and B[j] in heap formation and the > maximum height of the heap is O( Log N^2) = O(Log N) > > Time > 1) For each C[k] search for -C[k] in the D heap. Search takes time atmost > the height of the heap ---> O(N Log N) > > Please correct me if I'm wrong. > > -- > > 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. > 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: aai + bj + ck =0
ck will be changed every time for your example
there will be at most N ck, and so the inner loop will be executed for
at most O(N) time.
when there is no available ck, the inner loop will exit
On Tue, Nov 3, 2009 at 12:45 PM, dinesh bansal wrote:
> I think this algorithm is O(N^3) because in a worst case when condition
> "if(ai + bj + ck > 0)" fail for all the elements in C, the inner loop will
> run for N^3 times since we have not incremented j yet.
>
> lets take a very rough example , A = {1,2,3,4,5}, B = {2,3,4,5,6}, C =
> {7,6,5,4,3}, the condition check "if(ai + bj + ck == 0)" will execute for
> 5^3 times.
>
> Thanks,
>
> On Sun, Nov 1, 2009 at 2:04 PM, daizi sheng wrote:
>>
>> In the inner loop, either ck get decreased, or bj get increased,
>> but you know there are at moast n possible ck and n possible bj, so
>> the complexity
>> of the inner loop is at most O(n), plus the outer loop, the whole
>> complexity
>> is O(n^2)
>>
>> On Sun, Nov 1, 2009 at 4:32 PM, Arun wrote:
>> > This is O(n^3) because of the goto statement (effectively you have
>> > replaced
>> > a loop with goto :) I think.
>> > Instead of neightbor in C, you can do a binary search.
>> > This is what I could think of but it doesnt meet the problem's
>> > requiremen -
>> > O(nlgn):
>> > 1) O(n^2logn) with O(1) space:)
>> > Sort all 3 arrays. For each pair of a[i],b[j], binary search for
>> > (0-(a[i]+b[j])) in C to see if its present.
>> > 2) O(n^2) with O(n) space
>> > Same as above, but instead of binary search of 0-(a[1]+b[j]) on C, you
>> > put
>> > all elements of C in a hash.
>> > There must be some variation of merge sort to do it in nlgn, but Im not
>> > able
>> > to see it :)
>> > On Sun, Nov 1, 2009 at 12:39 AM, daizi sheng
>> > wrote:
>> >>
>> >> with all arrays sorted firstly, if you enumerate ai, bj in ascedning
>> >> order,
>> >> ck will be sure in descending order.
>> >>
>> >> foreach(ai in A)
>> >> ck = largest element in C
>> >> foreach(bj in B)
>> >> AGAIN:
>> >> if(ai + bj + ck == 0) algorithm over
>> >> if(ai + bj + ck > 0) ck change to its neighbor in C and goto AGAIN
>> >> if(ai + bj + ck < 0) continue checking next bj
>> >>
>> >>
>> >> On Sun, Nov 1, 2009 at 3:10 PM, anilkumarmyla
>> >> wrote:
>> >> > No matter whatever i could think of, I am unable to do better than
>> >> > N^3
>> >> >
>> >> > @daizi sheng
>> >> > I don't get your algorithm
>> >> > "2. enumerate ai, bj both in ascending order,"
>> >> > Will that really help ? In what way ?
>> >> >
>> >> > --
>> >> >
>> >> > 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.
>> >> > 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.
>> >> 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.
>> > 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.
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>
>
>
> --
> Dinesh Bansal
> The Law of Win says, "Let's not do it your way or my way; let's do it the
> best way."
>
> --
>
> 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.
> 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.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: aai + bj + ck =0
In the inner loop, either ck get decreased, or bj get increased, but you know there are at moast n possible ck and n possible bj, so the complexity of the inner loop is at most O(n), plus the outer loop, the whole complexity is O(n^2) On Sun, Nov 1, 2009 at 4:32 PM, Arun wrote: > This is O(n^3) because of the goto statement (effectively you have replaced > a loop with goto :) I think. > Instead of neightbor in C, you can do a binary search. > This is what I could think of but it doesnt meet the problem's requiremen - > O(nlgn): > 1) O(n^2logn) with O(1) space:) > Sort all 3 arrays. For each pair of a[i],b[j], binary search for > (0-(a[i]+b[j])) in C to see if its present. > 2) O(n^2) with O(n) space > Same as above, but instead of binary search of 0-(a[1]+b[j]) on C, you put > all elements of C in a hash. > There must be some variation of merge sort to do it in nlgn, but Im not able > to see it :) > On Sun, Nov 1, 2009 at 12:39 AM, daizi sheng wrote: >> >> with all arrays sorted firstly, if you enumerate ai, bj in ascedning >> order, >> ck will be sure in descending order. >> >> foreach(ai in A) >> ck = largest element in C >> foreach(bj in B) >> AGAIN: >> if(ai + bj + ck == 0) algorithm over >> if(ai + bj + ck > 0) ck change to its neighbor in C and goto AGAIN >> if(ai + bj + ck < 0) continue checking next bj >> >> >> On Sun, Nov 1, 2009 at 3:10 PM, anilkumarmyla >> wrote: >> > No matter whatever i could think of, I am unable to do better than N^3 >> > >> > @daizi sheng >> > I don't get your algorithm >> > "2. enumerate ai, bj both in ascending order," >> > Will that really help ? In what way ? >> > >> > -- >> > >> > 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. >> > 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. >> 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. > 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: aai + bj + ck =0
with all arrays sorted firstly, if you enumerate ai, bj in ascedning order, ck will be sure in descending order. foreach(ai in A) ck = largest element in C foreach(bj in B) AGAIN: if(ai + bj + ck == 0) algorithm over if(ai + bj + ck > 0) ck change to its neighbor in C and goto AGAIN if(ai + bj + ck < 0) continue checking next bj On Sun, Nov 1, 2009 at 3:10 PM, anilkumarmyla wrote: > No matter whatever i could think of, I am unable to do better than N^3 > > @daizi sheng > I don't get your algorithm > "2. enumerate ai, bj both in ascending order," > Will that really help ? In what way ? > > -- > > 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. > 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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Identify The f(x) :you are given a series of numbers(asked by MICROSOFT )?
first n number can not define the full function and so you need to guess. I think you just need a simple enough f(x) to represent the full list, e.g. a closed formula, but you have to define *simple* firstly. I guess Knuth's Concrete Mathematics should help you for more insight. On Thu, Oct 29, 2009 at 8:19 PM, Pawandeep wrote: > > hello everyone , > you are given a series of numbers like > > 2,4,6,8,10,12this is simple though > > nd u hve to identify that f(x) = x+ 2 for this series .. > > now can you write a program to identify the f(x) for any series of > numbers.. > > // i know it is tough but don't say its not possible > > > > --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to 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 -~--~~~~--~~--~--~---
[algogeeks] Re: aai + bj + ck =0
n^2 algo should be obvious, e.g. 1. sort them 2. enumerate ai, bj both in ascending order, then you just need to test ck in descending order instead of enumerating it or you can even make a hash table for C array and then enumerate the first two arrays. On Fri, Oct 30, 2009 at 7:53 PM, ankur aggarwal wrote: > Given 3 randomly filled array of size N ( say A , B and > C ).give Algorithm to verify if there exists a triplet such that > ai + bj + ck =0 where > 0 space complexity of > you’re algorithm .O(N^2) algorithm will get partial credit. > > > --~--~-~--~~~---~--~~ 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 -~--~~~~--~~--~--~---
[algogeeks] Re: find the output
there is no expected output of this program because it is obviously
implement dependent. if you really want to know the results, try to
run it. if you want to know why, dump the assemble code to check it
manually.
anyway, I do not think this topic is related to this group.
On Tue, Jan 6, 2009 at 5:18 AM, tania hamid wrote:
>
>
> Plz indicate the output of the following code and explain why is it so..
>
>
> char *modify (char *s)
> {
> #define MAX 15
> char buffer[MAX];
> strcpy (buffer, s);
>
> buffer[0] = 'H';
> return buffer;
> }
>
> int
> main ()
> {
> printf ("hello!!!");
> printf ("%s ", modify ("hello!!!"));
> }
>
> >
>
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: Lucky numbers
check this perl program, hope it explains the algorithm itself
>>START OF algo.pl
use warnings;
use strict;
sub is_lucky_number
{
my ($cur, $n, $last_n, $next_n, $old_n);
$cur = 1; # to remove numbers at $cur, $cur*2, ...
$n = shift @_; # current index of the input number before removing
$old_n = $n;
die unless $n > 0;
$last_n = -1; # index of the input number when after removing
every $cur-1 number
while($last_n != $n)
{
$cur++;
$next_n = $n - int($n / $cur);
if($n % $cur == 0)
{
#print "$old_n is removed at $cur-th step\n";
return 0; # input number is not lucky because it will be
removed at $cur-th step
}
$last_n = $n;
$n = $next_n;
}
return 1;
}
foreach my $input (1..100)
{
print "$input is lucky\n" if &is_lucky_number($input);
}
print "Press return to exit\n";
<>;
On Sun, Jan 4, 2009 at 2:08 AM, kannan wrote:
>
> All the numbers from 1 to infinity are written in sequence:
>
> 1,2,3,4,5,6,7,8,9,10,11,12,13,14.
> in the first iteration, every second number is removed, leaving:
> 1,3,5,7,9,11,13
> in the second iteration, every third number in the above sequence is
> removed, thus leaving: 1,3,7,9,13
> in the third iteration, every fourth number is removed, leaving:
> 1,3,7,13
> like this the process goes on indefinitely.
> the numbers which are, thus, left are called lucky numbers.
>
> Given a number n(can be as big as 18 digits) you must tell if n is a
> lucky number or not.. how do i proceed?? all that i can think of is a
> naive implementation which obviously wont work because n can be as big
> as 18 digits...
> could you help me or give suggestions on how to proceed
> (This question was asked in a practice contest which is over now)
>
> >
>
--~--~-~--~~~---~--~~
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
-~--~~~~--~~--~--~---
[algogeeks] Re: String and Array Performance Issue
An alternative method is splitting the big string into pieces and storing such pieces into another data structure like hash table (js object can be used as hash table). Only when you need the big string, concate them again. You may not need the whole string very often, I guess. On Wed, Nov 5, 2008 at 5:25 PM, Adrian Godong <[EMAIL PROTECTED]> wrote: > Hum, I may be able to use that replace function. Let me check on it. > > The problem now is that I have more than 1000 value on the string, it's very > slow on the iteration (not on the memory). I presume concatenating strings > are slow as usual. > > On Wed, Nov 5, 2008 at 5:19 PM, daizi sheng <[EMAIL PROTECTED]> wrote: >> >> I do not think you method will get problems unless the string is too long. >> But will you use too long string in JavaScript? >> >> Anyway, if you really want to get this done more effeciently, I >> suggest you to use predefined *replace* functions of String object. >> >> >> On Wed, Nov 5, 2008 at 3:56 PM, Adrian Godong <[EMAIL PROTECTED]> >> wrote: >> > Hi, >> > >> > The following question may be simple for you guys, but I do really need >> > help. >> > >> > I have the following application, all the code is Javascript (so you'll >> > miss >> > all those powerful library features and server-class computing power). >> > >> > I need an algorithm improvement for the following scenario: >> > >> > 1. I have a string of pipe delimited values, e.g. value1|value2|value3 >> > 2. I will need to find one value, and remove it from the string. For >> > instance, I will need to find value2 and remove it from the string so >> > the >> > end result would be something like value1|value3 >> > 3. My current approach is very direct, yet inefficient; split the string >> > into array, iterate the array, for each item, I will reconstruct the >> > string >> > using string concatenation (e.g. newvalue += currentvalue), if >> > currentvalue >> > is equal to the one being removed, I will skip this value and continue >> > with >> > the next items. >> > >> > The problem is, this algorithm is very slow because whatever you remove, >> > it >> > will need to iterate the whole array (O(n)). Even worse, if I remove >> > more >> > than one value at once, it will iterate the whole array as many times as >> > the >> > item being removed. >> > >> > Anyone have insight about certain algorithm I can use to improve this >> > scenario? Keep in mind it's in Javascript. >> > >> > -- >> > Adrian Godong >> > [EMAIL PROTECTED] >> > Microsoft MVP >> > https://mvp.support.microsoft.com/profile/Adrian >> > >> > > >> > >> >> > > > > -- > Adrian Godong > [EMAIL PROTECTED] > Microsoft MVP > https://mvp.support.microsoft.com/profile/Adrian > > > > --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: String and Array Performance Issue
I do not think you method will get problems unless the string is too long. But will you use too long string in JavaScript? Anyway, if you really want to get this done more effeciently, I suggest you to use predefined *replace* functions of String object. On Wed, Nov 5, 2008 at 3:56 PM, Adrian Godong <[EMAIL PROTECTED]> wrote: > Hi, > > The following question may be simple for you guys, but I do really need > help. > > I have the following application, all the code is Javascript (so you'll miss > all those powerful library features and server-class computing power). > > I need an algorithm improvement for the following scenario: > > 1. I have a string of pipe delimited values, e.g. value1|value2|value3 > 2. I will need to find one value, and remove it from the string. For > instance, I will need to find value2 and remove it from the string so the > end result would be something like value1|value3 > 3. My current approach is very direct, yet inefficient; split the string > into array, iterate the array, for each item, I will reconstruct the string > using string concatenation (e.g. newvalue += currentvalue), if currentvalue > is equal to the one being removed, I will skip this value and continue with > the next items. > > The problem is, this algorithm is very slow because whatever you remove, it > will need to iterate the whole array (O(n)). Even worse, if I remove more > than one value at once, it will iterate the whole array as many times as the > item being removed. > > Anyone have insight about certain algorithm I can use to improve this > scenario? Keep in mind it's in Javascript. > > -- > Adrian Godong > [EMAIL PROTECTED] > Microsoft MVP > https://mvp.support.microsoft.com/profile/Adrian > > > > --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Making money from google is hard
I did that hope you all do that,:) 2007/9/20, Dhyanesh (ધયાનેશ) <[EMAIL PROTECTED]>: > > > Go to google groups, go to "View Profile" for that person and then > click "Report Profile". There you can report the person as Spam. If > enough people do it then such people would be banned. > > -Dhyanesh > > On 9/17/07, Dhruva Sagar <[EMAIL PROTECTED]> wrote: > > On 9/17/07, daizi sheng <[EMAIL PROTECTED]> wrote: > > > anyone who can block such ad-guys? > > > > That would be good...anyone? please? > > > > > > > > 2007/9/17, austin <[EMAIL PROTECTED]>: > > > > > > > > > > > Making money from google is hard > > > > http://www.goodtolove.com has solved this problem .They re sharing > > > > their 60% adsense revenue with you.Just start sharing > > > > videos,webpages,images and start making friends.Guaranteed you will > be > > > > making a lot of money from google using this website. > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > > -- > > Thanks & Regards, > > Dhruva Sagar. > > > > > > > > > > > > > --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: need an algorithm for inserting tags....
yes I also think linearly searching is enough, :) even you have > 1M words, you can use something like hash for testing if it occur at the current position just post what you think the problem it (because you said "linearly searching through the paragraph for words and tagging them would not work obviously", but I can not see why) 2007/9/18, adak <[EMAIL PROTECTED]>: > > > Linearly searching through the text (including the tags) WILL work > just fine, gomsi. > > Post up a troublesome example, and I believe I can show you. > > > > > > --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: alorithm for shortest paths
2007/9/18, Raj <[EMAIL PROTECTED]>:
>
>
> Hey Thanks,
>
> I need algo of complexity same as BFS i.e O(m+n).
> I think we need to use BFS with some twiks.
> and it is undirected graph.
oh you do not got my idea
I mean the complexity of the algo is same with shortest path algorithm
and in unweighted graph, it is same with bfs,:) i.e. O(m+n)
Raj
>
> On Sep 16, 7:54 pm, "daizi sheng" <[EMAIL PROTECTED]> wrote:
> > you mean the number of shortest paths in G from give vertexes A & B ( A
> to
> > B)
> > let me formulate the number as this
> >
> > f(A,B,len)
> >
> > where A is the src, B is the dst and len is the length of the shortest
> path
> >
> > it is easily to be derived out that
> > f(A,B,len) = \sum_{C is A's neighbor} f(C,B,len-1)
> >
> > also the base is f(B,B,0) = 1
> >
> > then the complexity of this algorithm is?
> >
> > there are only at most n*n states for all possible A,B,len (because if
> we
> > know A & B we should have already known len)
> >
> > and to caculate f(A,B,len) we need to check all neighbors for A, that's
> d(A)
> > also we at most check len times (so at most n times)
> >
> > then we totally check (sun of all d(a)) * n = 2mn (m is the number of
> edges)
> >
> > and so the algorithm is O(n^3 * m)
> >
> > but this is not the best algorithm, we can even get an algorithm with
> same
> > bound of shortest path algorithm
> >
> > firstly, perform a shortest path algorithm to get all dis(C,B) where B
> is
> > the dest and C is any vertex (including A)
> > we construct a direct graph like this
> >
> > an edge connect X to Y iff dis(X,B) = dis(Y,B) + 1
> >
> > you can prove that this graph is a direct acyclic graph and every path
> from
> > A to B in this graph is shortest path in the original graph
> > and any shortest path from A to B in the original graph is a path in
> this
> > graph
> >
> > now what you need to do is calculate the number of shortest path from A
> to B
> > in this new graph.
> >
> > but this is a direct acyclic graph, so very easy,:)
> >
> > hope this can help you
> >
> > 2007/9/17, Raj <[EMAIL PROTECTED]>:
> >
> >
> >
> >
> >
> > > what is the algo for finding the number of shortest paths in Graph G.
> > > It is unweighted graph.- 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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Making money from google is hard
anyone who can block such ad-guys? 2007/9/17, austin <[EMAIL PROTECTED]>: > > > Making money from google is hard > http://www.goodtolove.com has solved this problem .They re sharing > their 60% adsense revenue with you.Just start sharing > videos,webpages,images and start making friends.Guaranteed you will be > making a lot of money from google using this website. > > > > > --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: alorithm for shortest paths
you mean the number of shortest paths in G from give vertexes A & B ( A to
B)
let me formulate the number as this
f(A,B,len)
where A is the src, B is the dst and len is the length of the shortest path
it is easily to be derived out that
f(A,B,len) = \sum_{C is A's neighbor} f(C,B,len-1)
also the base is f(B,B,0) = 1
then the complexity of this algorithm is?
there are only at most n*n states for all possible A,B,len (because if we
know A & B we should have already known len)
and to caculate f(A,B,len) we need to check all neighbors for A, that's d(A)
also we at most check len times (so at most n times)
then we totally check (sun of all d(a)) * n = 2mn (m is the number of edges)
and so the algorithm is O(n^3 * m)
but this is not the best algorithm, we can even get an algorithm with same
bound of shortest path algorithm
firstly, perform a shortest path algorithm to get all dis(C,B) where B is
the dest and C is any vertex (including A)
we construct a direct graph like this
an edge connect X to Y iff dis(X,B) = dis(Y,B) + 1
you can prove that this graph is a direct acyclic graph and every path from
A to B in this graph is shortest path in the original graph
and any shortest path from A to B in the original graph is a path in this
graph
now what you need to do is calculate the number of shortest path from A to B
in this new graph.
but this is a direct acyclic graph, so very easy,:)
hope this can help you
2007/9/17, Raj <[EMAIL PROTECTED]>:
>
>
> what is the algo for finding the number of shortest paths in Graph G.
> It is unweighted graph.
>
>
> >
>
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] rectangle question
I have some rectangles A,B,C,D,... I wan to place them in a bigger rectangle Z, how to minimize area of Z? where I say place I mean make Z cover A,cover B & cover all others, but A,B,.. should not overlap. also the position of A,B,C...is not important & u can even rotate the rectangles to get smaller Z I guess there may be a theorem saying that rotating on a rangle a (which is not 0,90,180,270, ...) is not neccessary to get the minimum Z, but have not found it on Google, also have not proved or disproved it --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Hackers' Handbook - Hacker Publications !!!
yes yes agree with you if he again put such rubbishes, we will make our bot to click his f*cking ads. 2007/4/25, Arun <[EMAIL PROTECTED]>: > dude, > ENOUGH! Please. > I will goto ur blog and click the Google Ads, happy? > > > On 4/24/07, candra < [EMAIL PROTECTED] > wrote: > > > > Hacker Publications !!! Part 1 > > > > 1.1 Computer Incident Advisory Capability (CIAC) > > 1.2 Call and Response Telephone Compilations (CRTC) > > 1.3 Forbidden Knowledge > > 1.4 Keen Veracity > > 1.5 Lexxicor > > 1.6 Midnight Hackers Private Club > > > > > > Hacker Publications !!! Part 2 > > > > 2.1 Phrack > > 2.2 Risks Forum Digest > > > > > > Hacker Publications !!! Part 3 > > > > 3.1 Tricks of the Trade > > 3.2 Underground Periodical > > > > > > For more information, you can visit our website at : > http://www.ilmuhacker.com > > > > Best regards, > > > > ilmuhacker.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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Hackers' Handbook - Hacker Publications !!!
I think ur information is just rubish u just want to put AD for your site you will be banned 2007/4/25, candra <[EMAIL PROTECTED]>: > > Hacker Publications !!! Part 1 > > 1.1 Computer Incident Advisory Capability (CIAC) > 1.2 Call and Response Telephone Compilations (CRTC) > 1.3 Forbidden Knowledge > 1.4 Keen Veracity > 1.5 Lexxicor > 1.6 Midnight Hackers Private Club > > > Hacker Publications !!! Part 2 > > 2.1 Phrack > 2.2 Risks Forum Digest > > > Hacker Publications !!! Part 3 > > 3.1 Tricks of the Trade > 3.2 Underground Periodical > > > For more information, you can visit our website at : http://www.ilmuhacker.com > > Best regards, > > ilmuhacker.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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Professional Hacker Training
I think it is not suitable for this group 2007/4/25, candra <[EMAIL PROTECTED]>: > > "Professional Hacker Training Plus Thousands of Security Tools And > Hacking Information Files" > "Hackers EnCyclopedia" contains the very latest hacking and security > tools, the very latest security advisories on the latest products, and > tons of new articles on hacking and phreaking from the perpetrators > themselves. > > When you realize what a danger hackers and those with the skills > present, you will realize how much "Hackers EnCyclopedia" > > Hacking - Windows 95/98/NT/2000/Me/XP, Linux, BSD, Irix, HP-UX, AIX, > SCO Unix, and many other platform! Information, advisories, exploits, > plus hundreds of security and auditing tools! How will you know your > system is safe from hackers unless you get this DVD? > > Phone Phreaking - The very latest on that black art that the phone > companies still can't shut down, dozens of years and billions of > dollars later! With state of the art information on cellular phones, > voice mail, pagers, Caller ID, Test numbers, and much more! > > Hacker Publications - The most up to date information from hackers > themselves! > > Viruses - Learn how malicious code propagates, how to detect and > remove it! Many detection and eradication utilities are included! > > Internet - Vulnerabilities in web servers, clients, email, news, FTP, > and even the very backbone protocols! > > Hackers and The Law - What the news media isn't telling you about > those high-profile hacker cases! Plus legal pitfalls to avoid falling > into yourself! > > Wetware Hacking - Find out how hackers, advertising agencies, and the > government are "hacking" right into your mind every day! And how to > recognize and stop it. And much more... > > For more information, you can visit our website at : http://www.ilmuhacker.com > > Best regards, > > ilmuhacker.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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Interesting problem
is DP ok? 2006/6/30, Arunachalam <[EMAIL PROTECTED]>: > > Hi, >I am thinking a solution to this question for long time. But could > not make it. Can anyone try and give some idea about this problem? > > http://acm.mipt.ru/judge/problems.pl?problem=014 > > -- > === > want to know more about me > http"//ww.livejournal.com/users/arunachalam > > > -- myblog: http://gnor.net/daizisheng/blog/ --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: A problem related to palindromes
a not very simple solution is here: suppose reverse of x is y denote z = x . y (conta...) e.g. x = 123 y = 321 z = 123321 now the problem can be transform to the following one: let f(i) be the length of longest common prefix of the i-th prefix of z and z as whole now to calculate the maximum f(i) over all i's there are more general algorithms to calculate the f(i,j): longest common prefix of the i-th and the j-th prefix in O(1) time so... 2006/5/2, aj <[EMAIL PROTECTED]>: > > Given a binary string x of length n, find the longest prefix of x in > linear time which is a palindrome. > > thx > aj > > > > > -- myblog: http://gnor.net/daizisheng/blog/ --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Comparing different sets of data:
if there are many Sets, I think this problem is very similar to the algorithms in general search engine! so, maybe inverted table may be a good solution! anyone knows any better ones? I am very interested to hearing that! 2006/5/1, Glenn <[EMAIL PROTECTED]>: > > I assume that this problem was solved before. Help is very much > appreciated. > > Comparing different sets of data: > > Initial Situation: I do have a number of elements which can be fully or > partially included in different sets of data. > > I would like to find out the set of data which has the biggist > similarity to my search data set. > > Example: > > Elements: A,B,C,D,E,F > > Search Data Set: (B,C,D) > > Data Set I:(A,E,F) > Data Set II:(C,D,E) > Data Set III:(A,D,E,F) > > What algorithm finds out that Data Set II is most similar to the Search > Data set? > > cheers Glenn > > > > > -- myblog: http://gnor.net/daizisheng/blog/ --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Find the nth item from the end of a linked list in a single pass.
u r right I think 2006/5/1, Manu <[EMAIL PROTECTED]>: > > i think we should take two pointers and then move the second pointer to > n-1 places from the first and then move both the pointers > simultaneously when the second pointer becomes null we get the first > pointer as the final answer... > > but the confusion is whether to count the movement of the second > pointer n-1 places ahead as being counted in the pass or not... > > > correct me if i m wrong plzzz. > > > > > -- myblog: http://gnor.net/daizisheng/blog/ --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Finding the k largest/smallest elements in the array !
another soure to find the solution,:) "introduction to algorithms" 2006/4/25, BiGYaN <[EMAIL PROTECTED]>: > > It is rather easy of you want an n(log n) algo. > But linear I don't thaink so. > > > > > -- myblog: http://gnor.net/daizisheng/blog/ --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: frequent substring
if ur chars are just alphabet! the equation 26 ^ 3 = 17576 will show u the answer 2006/4/25, iwgmsft <[EMAIL PROTECTED]>: > > Write a function that determines the most frequent 3 character strings > in an otherwise random string of one million characters. > > > > > -- myblog: http://gnor.net/daizisheng/blog/ --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: find pair in O(N)
n = size of num
i = 0
j = n-1
while(i < j) {
c = num[i] + num[j]
if(c < given number) i++
else if(c > given number) j--
else show and j--
}
2006/4/21, iwgmsft <[EMAIL PROTECTED]>:
>
> one of microsoft interview questionif anybody interested
>
> in given array int num[10]={1,-5,6,7,9,9,20,25,31,45} it is a sorted
> array.
> write a function void findsum(int [],int x)
> int [] is array and x is number.
> function should print all possible pair of elements in array that can
> make a sum equal to x.
> for example if value of x is 26
> then function should print
> 1,25
> 25,1
>-5,31
> 31,-5
> Function should be implemented using O(N) or O(2N) approach try to
> avoid using O(N 2) approach(Means avoid nested loop).
>
>
> >
>
--
myblog: http://gnor.net/daizisheng/blog/
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: why this happen in c?
2006/3/13, ajay mall <[EMAIL PROTECTED]>:
> Hi,
>
> Can u tell what would be output of following code and what is reson behind
> this?
>
> void main()
> {
>float a=4;
>int i=2;
> printf("%f..%d",i/a,i/a);
first, printf is very stupid. so does any function who use the
variable argument list. the reason is that they do not know what's the
type of its real arguments.
for this example, the format string is "%f...%d",
so, *printf* this his arguments to be one *double* and then one *int*. why?
if u read the C standard, u should note that the type conversion rule
applied here is:
convert real arguments with type *float*,*double* into double
convert real arguments with type *char*,*short*,*int* into int
so the real arguments printf receive is two doubles with value 0.5 and 0.5
but what he want is one double and then one integer? what will happened?
the compiler will push two double (8 bytes in X86 arch.. each) into
the stack. then printf will pop out a double (this is right), and then
an integer( he will simply extract the first 4 bytes of the second
double to be this integer). so what is the value of this integer ? it
depends on which arch.. u r on! also depends how ur machine express an
integer and a double.
maybe this will help u. if any problem, plz let me know!
> printf("%d..%f",i/a,i/a);
> }
>
> --
> " Talent hits a target no one else can hit
> Genius hits a target no one else can see ."
>
> FROM- AJAY BAHADUR MALL
> #N-405,DSK BLOCK,MMM HALL,
> IIT KHARAGPUR(WEST BENGAL)-721302
> Mail-id:[EMAIL PROTECTED]
> MOBILE NO: +919932978592
>
>
--
myblog: http://gnor.net/daizisheng/blog/
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Free Anti Virus Softwares
ban him plz, it is absolutely a ROBOT 2006/3/13, srid <[EMAIL PROTECTED]>: > > Stop posting such irrelevant messages to this group. Please try to keep > it pristine and help me keep my mind not to wander off to ban you. > > -admin > > -- > Sridhar Ratna | http://www.24dot1.com/ > > > > -- myblog: http://gnor.net/daizisheng/blog/ --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] oh no, some rubish now. kick it out, plz
-- myblog: http://gnor.net/daizisheng/blog/ --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: Anyone interested in being paid to find a solution to a commercial problem?
I think it exactly is KP, :) so maybe they do not need to pay any cash now,:) 2006/3/1, Dhyanesh <[EMAIL PROTECTED]>: > Isnt this exactly the same as the 0-1 Knapsack problem ? > > -Dhyanesh > > On 2/28/06, josh <[EMAIL PROTECTED]> wrote: > > > > We are software developers for the vacation rental business. We need > > to code an availability search (in Microsoft SQL Server) to find the > > cheapest combination of properties that will accommodate a given > > capacity. Testing all possible combinations is not an option as forty > > properties will yield roughly a trillion combinations. We have got to > > the point where we take each property in turn, starting with the > > cheapest in terms of cost per head, and then adding the next cheapest > > and so on, until greater than or equal to the required capacity is > > reached. If that capacity is reached EXACTLY, we then have a solution. > > So far so good. But if we have gone over the required capacity, there > > is a possibility that a different mix with a lower capacity will be > > cheaper, even if the cost per head of capacity is higher, as a result > > of the spare capacity in going over what is required rather than > > matching it exactly. > > > > We also need to be able to implement a solution WITHIN SQL Server as it > > > > > -- myblog: http://gnor.net/daizisheng/blog/ --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: largest Number Smaller Than Given Number
how about this shorter solution,:)
int go(unsigned int n)
{
int c[10] = {0},i,d,cur;
for(cur = 1;cur <= n;cur *= 10) {
d = n / cur % 10;
c[d]++;
for(i = d - 1;i >= 0;i--) if(c[i]) {
d = n / (cur * 10);
d = d * 10 + i;
c[i]--;
for(i = 9;i >= 0;i--) {
while(c[i]--) d = d * 10 + i;
}
return d;
}
}
return -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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: largest Number Smaller Than Given Number
2006/2/26, ajay mishra <[EMAIL PROTECTED]>: > @Dont Know, > plz check the examples which u gave > 1) 321 should aswer be 231 or 312 e.g. 321 keep 3 not been changed, so change 21 only 2 could be descrease to 1 so the answer is 312 > 2) 5342 should the answer be 5432( it si greater than 5342) so it shld be > 5324. keep 53 not been changed, so change 42 only so the answer is 5324 > > plz check what i say , am i correct. > > > On 2/26/06, daizi sheng <[EMAIL PROTECTED]> wrote: > > > > give u some ideas: > > > > for 11261 > > > > 1st try: keep prefix 112 without beening changed > > the remaining number is 61 > > can we descrease the first digit (it is 6) ? > > yes > > so decrease it to the largest possible digit (that is 1) > > so change 61 -> 16 > > so the answer is 11216 > > > > if we fail in the 1st try, we can try shorter prefix such as 11, 1 > > > > if any question, plz let me know. > > > > 2006/2/26, Dont Know < [EMAIL PROTECTED]>: > > > > > > Sorry Sorry in the above given examples in the third example the output > > > should be 11216. > > > > > > > > > > > > > > > > > > -- > > myblog: > > > > > > -- > > Ajay kr. Mishra > > www.ajay.mishra19.googlepages.com > > IIT KGP > > > > > -- myblog: http://gnor.net/daizisheng/blog/ --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: largest Number Smaller Than Given Number
give u some ideas: for 11261 1st try: keep prefix 112 without beening changed the remaining number is 61 can we descrease the first digit (it is 6) ? yes so decrease it to the largest possible digit (that is 1) so change 61 -> 16 so the answer is 11216 if we fail in the 1st try, we can try shorter prefix such as 11, 1 if any question, plz let me know. 2006/2/26, Dont Know <[EMAIL PROTECTED]>: > > Sorry Sorry in the above given examples in the third example the output > should be 11216. > > > > -- myblog: http://gnor.net/daizisheng/blog/ --~--~-~--~~~---~--~~ 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 [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~--~~~~--~~--~--~---
[algogeeks] Re: test if more than half of numbers are equal
if there is an element occurring more than n/2 times in Q, we can find
it as following.
if x \in Q and y \in Q and x != y, we can just drop both of them and
do not change the
answer. so the algo. is like:
c = 0
for i = 1 to n {
if(c == 0) {
c = 1
x = Q_i
}else{
if(Q_i != x) c--
else c++
}
}
then we claim x is the answer.
then we can count the occurrence of x in Q to give to final answer!
2006/2/21, kool_guy <[EMAIL PROTECTED]>:
>
> Given a set Q of n numbers, and you want to test if more than n/2
> numbers are equal. You are only allowed to compare two numbers
> directly. Give an algorithm that uses O(n log n) comparisons.
>
>
>
>
--
myblog: http://gnor.net/daizisheng/blog/
--~--~-~--~~~---~--~~
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 [EMAIL PROTECTED]
For more options, visit this group at http://groups.google.com/group/algogeeks
-~--~~~~--~~--~--~---
[algogeeks] Re: Donald E. Knuth - The Art of Computer Programming, Volumn 4 released
musing 2006/1/6, Abhi <[EMAIL PROTECTED]>: > > Donald E. Knuth - > The Art of Computer Programming, Volumn 4 released > > http://www.cs.utsa.edu/~wagner/knuth/ > > -- myblog: http://gnor.net/daizisheng/blog/
[algogeeks] Re: The File Writing Problem
1. I think the *C* functions will be faster than *C++*'s, e.g. printf vs cout U can use fwrite to write ur array into a file 2. To compare ur two methods, I think the first one will not be more slow. Because of the *system buffer*, it is not true that there is a disk write when there is a element outout! 2005/12/16, [EMAIL PROTECTED] <[EMAIL PROTECTED]>: > > Hello, > > I need to store an array in a file. The array length is 1000. I want > the fastest disk writing method to work. I know reading/writing a big > block from the hard disk is faster because it involves only 1 seek. I > seem to have 2 optons : > > Option 1) for(i=1 to 1000) > fll< > Option 2) Store the array contents into a single string str and then > fll< > where fll is the file pointer. Which would be faster. I am concerened > about the performance because I need to write numerical data in a file > of size around 4 Gb. It may be possible to optimize the seek time if I > some how know how much block size could it write in one go. > > Regards > Anirudh Koul > http://cs.dal.ca/~koul/ > > -- myblog: http://gnor.net/daizisheng/blog/
