It cannot obviously be better than O(N + k log k).(This is the case when
there is infinite memory to use).
So with space constraint i guess O(N log k) is not bad. (which means I
cannot think of anything better :P)
--
Rohit Saraf
Second Year Undergrad
It would be highly appreciated if you could share this announcement
with your colleagues, students and individuals whose research is in
theoretical computing, complexity theory, algorithms, computational
science and related areas.
Call for papers: TMFCS-10, USA, July 2010
The 2010 International C
I would make two routines,
first which would give me substrings of string ( similar to strtok )
Then I would either use finite state automata while searching reverse
way , that should work ?
About window solution , I am getting few ideas but not sure how would
I differentiate for 'eo' to get corre
I dont think greedy or dp should be the way to approach the problem since it
does not show optimal sub-structure property.
On Mon, May 17, 2010 at 10:22 PM, Rohit Saraf
wrote:
> I was really not able to digest the greedy thing
> Great example!!
>
> On 5/17/10, Amir hossein Shahriari
> wrote:
Hello,
There exists differnet google groups for OS related queries. Could you
please move out your discussion there.
Thanks
Pramod Negi
On Thu, May 6, 2010 at 5:34 AM, Yalla Sridhar wrote:
> yea if your processor has multiple cores or is Hyper Threading support then
> it can execute more
One (space-intensive) idea:
Re-represent each string as a set of pairs (character, position of
character). Then sort each set of pairs by character. Then find
corresponding sequences in the sorted lists of pairs, where the
character and the difference between position is the same from pair to
pa
Oops, build() is a member of base_avl_tree, not the iter member class.
On May 14, 5:23 pm, W Karas wrote:
> See the definition of:
>
> template
> bool build(fwd_iter p, size num_nodes)
>
> Within the iter subclass, within the base_avl_tree template in:
>
> http://wkaras.webs.com/gen_cpp/a
I was really not able to digest the greedy thing
Great example!!
On 5/17/10, Amir hossein Shahriari wrote:
> @divya : it's a greedy approach and again it's WRONG!
> your answer for {110,100,90,70,60,10 } would be:
> A = { 110, 70, 60 }
> B = { 100, 90 , 10 }
> the difference is 40
> the corre
oops!
Anurag Sharma
On Mon, May 17, 2010 at 5:00 PM, Navin Naidu wrote:
> @anurag:
>
> -99 -2 -1 3 +99
>
> The min sum (=0) for value pair (-99, 99)
>
> Now skip, +99 and -99, so -1 will be selected: (99, -99, -1) = -1
>
> Actual result: -2, -1, 3 : 0
>
>
>
>
>
> On Mon, May 17, 2010 at 8:48 AM
On May 17, 5:36 pm, Rohit Saraf wrote:
> @divya : descending order sorting works. BRILLIANT !!
Not really.
Try this input: 8 6 5 5 5 1
The best partition is [8 6 1] [5 5 5] but Divya's algorithm gives [8
5 1] [6 5 5].
-Jagadish
http://www.cse.iitb.ac.in/~jagadish
> On 5/17/10, divya
@divya : it's a greedy approach and again it's WRONG!
your answer for {110,100,90,70,60,10 } would be:
A = { 110, 70, 60 }
B = { 100, 90 , 10 }
the difference is 40
the correct ans:
A = { 110, 100 , 10 }
B = { 90 , 70 , 60 }
the difference is 0
i don't believe a greedy algorithm would work for thi
The best algorithm I can think of is to maintain a heap of k elements.
Takes O(n log k) time.
Is anything told about the values of the keys? If the keys have values
less than N, then it is possible to do
what you say, i.e sort them in place.
-Jagadish
http://www.cse.iitb.ac.in/~jagadish
On May
@Jalaj
if u consider only Space complexity then it can be done in O(n^2) time
and constant space
here i assume string u taken only hv a-z character nothing else
try this
for(i=0;i='a' && st[i]<='z') )
continue;
count=1;
for(j=i+1;j wrote:
> Hi Friends
>
> Ha
How about:
void part(const int a[], int n_a, int g1[], int g2[])
{
int i, j, k;
/* diff = sum(g1) - sum(g2) */
int diff;
sort(a, n_a);
diff = 0;
for (i = 0, j = n_a - 1, k = 0; i < j; ++k, ++i, --j)
{
if ((a[i] > a[j]) == (diff > 0))
{
@divya : descending order sorting works. BRILLIANT !!
On 5/17/10, divya jain wrote:
> my algo on the array 1 200 500 2000
> sort the array therefore we have now 2000 500 200 1
> 1st array will have largest element
> A= {2000}
> and B={500}
> sumA=2000
> sumB=500
> now abs((2000+200)-500)>abs((20
Try this .. i think it will work.. correct me if wrong
sort(&x[0],&x[n]);
ysum=y[0]=x[n-1];
ysum=z[0]=x[n-2];
j=0;
k=n-3;
l=n/2;
for(i=1;i wrote:
> my algo on the array 1 200 500 2000
> sort the array therefore we have now 2000 500 200 1
Sharing link for Morris Inorder
http://www.scss.tcd.ie/disciplines/software_systems/fmg/fmg_web/IFMSIG/winter2000/HughGibbonsSlides.pdf
Courtesy Rohit
On Mon, May 17, 2010 at 3:42 PM, kaushik sur wrote:
> @Manish
>
> Does not a recursive solution [inorder traversal] takes an implicit stack
> spa
@anurag:
-99 -2 -1 3 +99
The min sum (=0) for value pair (-99, 99)
Now skip, +99 and -99, so -1 will be selected: (99, -99, -1) = -1
Actual result: -2, -1, 3 : 0
On Mon, May 17, 2010 at 8:48 AM, Anurag Sharma wrote:
> @Navin : Let me work out the case you gave me array={-99,0,2,-1,99}
>
>
the output shd be epo..
hint to the problem : PROBLEM DO NOT READ IF U WANT TO SOLVE THE URSELF
it involves the concept of finding window
u hv to 1st search for the window which contains all characters of string.
then u have to alter window so as to get minmum length window..
On 17 May 2010 16:
my algo on the array 1 200 500 2000
sort the array therefore we have now 2000 500 200 1
1st array will have largest element
A= {2000}
and B={500}
sumA=2000
sumB=500
now abs((2000+200)-500)>abs((2000)-(500+200))
so we ll put 200 in array B. now since B has n/2 elements rest of the
element goes to ar
@kaushik where are you creating explicit stack ? It has to be outside
inorder(Root) , right ?
If yes , then you can use only a count and that should work . Make
kth bit of count = 1 , rest all 0.
Just before printing in Inorder , right shift count and when it
becomes ZERO , that's the value you a
@Divya
BigS =" Hellepo What's up"
SmallS = 'eo'
o/p should be ? "ellepo" OR "epo" ?
if its "ellepo" DP would work fine . If its "eo" probably need some
modification in DP.
-Manish
On May 16, 8:36 pm, Navin Naidu wrote:
> @Sharad: yup
>
> On Sun, May 16, 2010 at 8:36 PM, Rohit Saraf
> wrote:
@Manish
Does not a recursive solution [inorder traversal] takes an implicit stack
space ?
Please correct me if I am wrong ?
@Rahul
Can you please send us the *morris inorder pdf* link that u have shared once
?
Best Regards
Kaushik
--
You received this message because you are subscribed to the
@Navin : Let me work out the case you gave me array={-99,0,2,-1,99}
1. Sort the array in nlogn time: array={-99,-1,0,2,99}
2. consider all possible pairs of numbers and keep track of the sum closest
2 zero:
-99+-1=-100, |-100|=100
-99+0=-99,|-99|=99
-99+2=-97,|-97|=97
-99+99=0,|0|=0 <--- th
Hi Friends
Hash Map takes 2byte [in Java] for holding a character
So in Amazon -
It takes A - 1
M - 1
Z - 1
O - 1
N - 1
But it's time effective!
Yes it takes additional space for intergers, for each key 4 byte for an
integer!!! :-(
***
public void checkTheFrequency() {
25 matches
Mail list logo
