[algogeeks] Re: Matrix Searching
For a large list of words, At each location, look for the character before/after that character in the word on opposite sides of the initial location, and continue from there Is it like: frequency count of 'a' is smallest 'a' is in 2 words available and alpha shall we check for 'v' near 'a'; if found then look for the complete word OR look for 'v' and 'i' on both sides of 'a'; if found then search for remaining characters in both directions OR look for 'l' and 'b' on both sides of 'a'; if found then search for remaining characters in both directions OR look for 'l' 'a'; if found then search for remaining characters in that direction OR look for 'h' 'a'; if found then search for remaining characters in that direction Is this what we should be doing? On Saturday, 15 September 2012 01:43:14 UTC+5:30, Don wrote: I had to do something like this with a large list of words to search for. If you're just looking for one word, look for the first letter, and when you find it, look at adjacent locations for the second letter. If found, continue in that direction matching letters until you either match the whole word or don't. But for a big list of words to search for, it was faster to do something like this: Build a frequency count for each character, along with a list of ordered pairs indicating where that character is located. Then, to look for a word, find the character with the smallest frequency count and step through the list for that character. At each location, look for the character before/after that character in the word on opposite sides of the initial location, and continue from there. Don On Sep 14, 2:47 pm, Arun Kindra reserve4placem...@gmail.com wrote: *You have given any n*n matrix in which characters are stored and you have to search that a given word is present or not.(words can be horizontally, vertically, diagonally)* -- 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/-/tKJcCEYJsjAJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] help to give DP solution
we can assign minimum possible value, like negative infinity to the diagonal elements. Then they would not be considered for maximizing the sum. -- 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/-/iQtl7QGJBFwJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] array problem
@srikanth
we can use segment trees to get sum of an interval
but there is another condition of sum of distinct numbers only. how can we
take that into account in a segment tree?
On Thursday, 6 September 2012 17:35:59 UTC+5:30, srikanth reddy malipatel
wrote:
post the logic not the code!
BTW this problem can be done using segment trees.
http://community.topcoder.com/tc?module=Staticd1=tutorialsd2=lowestCommonAncestor
On Thu, Sep 6, 2012 at 4:51 PM, bharat b bagana.bh...@gmail.comjavascript:
wrote:
Its better to write an O(n) solution for this problem as the # test cases
are very high and #elements are also very huge..
use visited array for distinct numbers ... space--O(n).. time--O(n)
On Sat, Aug 25, 2012 at 2:39 AM, michael miller
wentworth@gmail.comjavascript:
wrote:
Hi,
You are given N numbers. You have to perform two kinds of operations:
U x y - x-th number becomes equal to y.
Q x y - calculate the sum of distinct numbers from x-th to y-th. It
means that the sum for the set {1, 2, 3, 2, 7} will be equal to 13
(1+2+3+7).
1=N=5 and
t is the number of test cases where 1=t=10
all numbers fit in the 32 bit integer range...
suggest some solution..
here is my solution
but it is giving wrong answer fo some unknown test case...plz suggest me
the test case where i am getting wrong answer
#includestdio.h
#includemath.h
int main()
{
int list[5],i,n,j,sum,k,l;char c;long t;
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,n);
for(i=0;in;i++)
{
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d,list[i]);
}
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%ld,t);
t=2*t;
while(t)
{
sum=0;
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%c,c);
fflush(stdin);
scanf
http://www.opengroup.org/onlinepubs/009695399/functions/scanf.html(%d
%d,k,l);
if(c=='Q')
{
for(i=k-1;il-1;i++)
{
for(j=i+1;jl;j++)
{
if(list[i]==list[j])
break;
else if((j==l-1) (list[i]!=list[j]))
{
sum=sum+list[i];
}
}
}
printf
http://www.opengroup.org/onlinepubs/009695399/functions/printf.html(%d\n,sum+list[l-1]);
}
if(c=='U')
{
list[k-1]=l;
}
t--;
}
return 0;
}
--
You received this message because you are subscribed to the Google
Groups Algorithm Geeks group.
To post to this group, send email to algo...@googlegroups.comjavascript:
.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
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 algo...@googlegroups.comjavascript:
.
To unsubscribe from this group, send email to
algogeeks+...@googlegroups.com javascript:.
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 view this discussion on the web visit
https://groups.google.com/d/msg/algogeeks/-/tBX6PSU32EkJ.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] help to give DP solution
@tushar :- correct... On Sun, Sep 16, 2012 at 12:59 PM, Tushar tushicom...@gmail.com wrote: we can assign minimum possible value, like negative infinity to the diagonal elements. Then they would not be considered for maximizing the sum. -- 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/-/iQtl7QGJBFwJ. 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] celebrity problem
http://www.geeksforgeeks.org/archives/19622 Plz tell what is size 4 in this case -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Pivot postion of quick sort
for a pivot picked randomly, even the same input array would have different time complexity going through quicksort thousands of thousands of times. the worst case could happen too(but the probability is very small), so random-pivot-set has statistically on average O(logN), we are talking about average on thousands of run, not individual one. On Saturday, September 15, 2012 2:27:50 PM UTC-4, atul007 wrote: typo error :- we can make it *independent** of this input format On Sat, Sep 15, 2012 at 11:56 PM, atul anand atul.8...@gmail.comjavascript: wrote: pivot position plays important role in determining the time complexity of the algorithm. suppose array is already sorted then if you go by obvious means by selecting pivot element as the 1st element of the input array,then recurrence will be :- T(n)=T(n-1)+theta(n) hence complexity of the algo will be O(n^2). actually if you form a recurrence tree you will see that it form like a skewed tree , so at every stage you are not dividing the problem into 2 parts. if we are lucky we will have pivot element arnd the center of the array,now this will divided the problem into T(n/2)+theta(n) = nlogn. so suppose you are competing in sorting challenge and me as your opponent will give you sorted input so that i can get a plus point over your algo. so how can we avoid this ?? now as we know by now that time complexity is dependent on the input format(inc/dec order or nearly sorted).we can make it interdependent of this input format by randomizing the input sequence OR we select random pivot instead of selecting 1st element as pivot. This is know as randomized quick sort.now quicksort will no longer dependent on the input sequence but worst case complexity still remain O(n^2) , because if your random generator function given input as sorted sequence complexity still be O(n^2). On Sat, Sep 15, 2012 at 7:43 PM, sulekha metta metta@gmail.comjavascript: wrote: hi every one!! how does pivot position effect the efficiency in quick sort algorithm thanks in advance -- 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.comjavascript: . To unsubscribe from this group, send email to algogeeks+...@googlegroups.com javascript:. 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 view this discussion on the web visit https://groups.google.com/d/msg/algogeeks/-/nDf15aeA4j8J. 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: infibeam placement procedure
Violating the rules of the group...!! Itz a place to discuss about algorithms.. not to ask wat wil b coming in ur xams..! LOL..!! rather to discuss about interview questions , go for GeeksForGeekshttp://www.geeksforgeeks.org/forum/view/company-interview, Hope it is useful , All d best :) On Sunday, 16 September 2012 03:09:18 UTC+5:30, saket wrote: some one with infibeam visited their college please tell their proceure and also give some questions asked in written and interviews . -- 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/-/3gE5JSqKDfUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] help to give DP solution
@atul: in Hungarian Algorithms works for minimization of cost where the terminating condition is based on zeros.. in my problem what value i will have to consider as base/terminating values because there may not be same values in coloumn and rows.. second thing you use subtraction there, here will i have to use addition..?? please clarify.. i have seen following link: http://s-mat-pcs.oulu.fi/~mpa/matreng/eem1_2-1.htm if you have link which explains maximization problem.. please post here.. On Sun, Sep 16, 2012 at 12:44 AM, atul anand atul.87fri...@gmail.comwrote: correct me if i am wrong , it seems similar to Hungarian algorithm. here each column can be considered as persons P(p0,p1,p2,..pn) and each as cost of job say X(x0,x1,x2,x3,x4xn). Hungarian algorithm tells how to find minimal but here its maximal...so i guess changes in the algo will give the outputl On Sat, Sep 15, 2012 at 9:10 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: A 2D array of order A[N][N] is given, considering entry A[i][i] as invalid you have to select one element from each row such that 1. Selected elements does not belong to same column. 2. Sum of selected element has maximal. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.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. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.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.
Re: [algogeeks] help to give DP solution
make all mat[i][j] to -ve sign and make mat[i][j]=INT_MAX now i guess same algo will work..no changes required. On Sun, Sep 16, 2012 at 4:42 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @atul: in Hungarian Algorithms works for minimization of cost where the terminating condition is based on zeros.. in my problem what value i will have to consider as base/terminating values because there may not be same values in coloumn and rows.. second thing you use subtraction there, here will i have to use addition..?? please clarify.. i have seen following link: http://s-mat-pcs.oulu.fi/~mpa/matreng/eem1_2-1.htm if you have link which explains maximization problem.. please post here.. On Sun, Sep 16, 2012 at 12:44 AM, atul anand atul.87fri...@gmail.comwrote: correct me if i am wrong , it seems similar to Hungarian algorithm. here each column can be considered as persons P(p0,p1,p2,..pn) and each as cost of job say X(x0,x1,x2,x3,x4xn). Hungarian algorithm tells how to find minimal but here its maximal...so i guess changes in the algo will give the outputl On Sat, Sep 15, 2012 at 9:10 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: A 2D array of order A[N][N] is given, considering entry A[i][i] as invalid you have to select one element from each row such that 1. Selected elements does not belong to same column. 2. Sum of selected element has maximal. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.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. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.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.
Re: [algogeeks] help to give DP solution
typo error :- mat[ i ] [ j ] to -ve sign and make mat[ i ][ i ]=INT_MAX On Mon, Sep 17, 2012 at 9:43 AM, atul anand atul.87fri...@gmail.com wrote: make all mat[i][j] to -ve sign and make mat[i][j]=INT_MAX now i guess same algo will work..no changes required. On Sun, Sep 16, 2012 at 4:42 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: @atul: in Hungarian Algorithms works for minimization of cost where the terminating condition is based on zeros.. in my problem what value i will have to consider as base/terminating values because there may not be same values in coloumn and rows.. second thing you use subtraction there, here will i have to use addition..?? please clarify.. i have seen following link: http://s-mat-pcs.oulu.fi/~mpa/matreng/eem1_2-1.htm if you have link which explains maximization problem.. please post here.. On Sun, Sep 16, 2012 at 12:44 AM, atul anand atul.87fri...@gmail.comwrote: correct me if i am wrong , it seems similar to Hungarian algorithm. here each column can be considered as persons P(p0,p1,p2,..pn) and each as cost of job say X(x0,x1,x2,x3,x4xn). Hungarian algorithm tells how to find minimal but here its maximal...so i guess changes in the algo will give the outputl On Sat, Sep 15, 2012 at 9:10 PM, Rahul Kumar Patle patlerahulku...@gmail.com wrote: A 2D array of order A[N][N] is given, considering entry A[i][i] as invalid you have to select one element from each row such that 1. Selected elements does not belong to same column. 2. Sum of selected element has maximal. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.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. -- Thanks and Regards: Rahul Kumar Patlehttp://www.linkedin.com/profile/view?id=106245716trk=tab_pro M.Tech, School of Information Technology Indian Institute of Technology, Kharagpur-721302, Indiahttp://www.iitkgp.ac.in/ Mobile No: +91-8798049298, +91-9424738542 Alternate Email: rahulkumarpa...@hotmail.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.
