[algogeeks] Re:
use suffix trie. On Aug 16, 9:36 pm, ashita dadlani wrote: > You have a string say "foobarfoo" in which "fo" and "oo" aree repeated > twice.You have to find all such repeated pairs in O(n) time,The string can > only have alphanumeric elements in it. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Permutation of Array.
@srinivas reddy i suppose u took my algo wrongly.. consider ur eg: 2,242 first digits== 2,2(same) 2nd digits== 2,4(here 2 remains as it is as there is no futher digit for no 2) now arrange==> 2242(output)... my algo works correctly here too.. correct me if am wrong.. On Sun, Aug 22, 2010 at 10:41 AM, srinivas reddy wrote: > @aravind prasad > > ho can u arrange the numbers > 2,202 > > suppose if u arrange 202 2 > ok u wiil get the least value > > now 2,242 > if u arrange in same manner as above u will get 242 2 > which is not smallest one... > > so better luck next time. > > On Sun, Aug 22, 2010 at 8:41 AM, Aravind Prasad wrote: >> >> for the method of comparison in insertion sort,, consider >> >> 1)compare the first digit of all nos and sort them >> >> 2)if they are same, go for next digit... >> >> >> correct me if am wrong... >> >> >> On Aug 21, 7:00 pm, Chonku wrote: >> > Treat each number as string and make a trie out of it. For the first >> > input >> > [55,31,312,33], it would look like the following >> > . >> > / \ >> > 3/ 5\ >> > 1/ 3\ 5\ >> > 31/ 2\ 33\ \55 >> > 312\ >> > Once we have a trie, just print it out by based on the smallest number >> > first. In this case, the print would go as follows. >> > >> > 313123355 >> > >> > On Sat, Aug 21, 2010 at 12:53 PM, Nikhil Agarwal >> > wrote: >> > >> > >> > >> > > Suppose the test is like: >> > >> > > 21 71 217 >> > > after sorting and msb appending we get: 217 712 217 >> > > sort: 217 217 712 >> > >> > > here we have 2 same elements 217 and 217 so we remove the 7 from the >> > > following logic: >> > >> > > 1.if msb > lsb we delete from the 2nd 217.else >> > > 2.we delete 7 from 1st one. >> > >> > > so this gives 2121771 >> > >> > > if it wud have been 41 200 412->412 200 412->200 412 412 >> > > here we will remove 2 from last one.giving 20041241 instead of >> > > 20041412 . >> > >> > > On Sat, Aug 21, 2010 at 12:26 PM, BALARUKESH SIVARAMAN < >> > > sbalarukesh1...@gmail.com> wrote: >> > >> > >> @Nikhil >> > >> I am clear with your first 2 algos but not with the change u >> > >> introduced >> > >> ie., adding a check. please give a working example >> > >> > >> -- >> > >> 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> > >> .com> >> > >> . >> > >> For more options, visit this group at >> > >>http://groups.google.com/group/algogeeks?hl=en. >> > >> > > -- >> > > Thanks & Regards >> > > Nikhil Agarwal >> > > Senior Undergraduate >> > > Computer Science & Engineering, >> > > National Institute Of Technology, Durgapur,India >> > >http://tech-nikk.blogspot.com >> > >http://beta.freshersworld.com/communities/nitd >> > >> > > -- >> > > 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> > > .com> >> > > . >> > > For more options, visit this group at >> > >http://groups.google.com/group/algogeeks?hl=en. >> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to algoge...@googlegroups.com. >> To unsubscribe from this group, send email to >> algogeeks+unsubscr...@googlegroups.com. >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com. > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- thanks and regards aravind prasad -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Permutation of Array.
@aravind prasad ho can u arrange the numbers 2,202 suppose if u arrange 202 2 ok u wiil get the least value now 2,242 if u arrange in same manner as above u will get 242 2 which is not smallest one... so better luck next time. On Sun, Aug 22, 2010 at 8:41 AM, Aravind Prasad wrote: > for the method of comparison in insertion sort,, consider > > 1)compare the first digit of all nos and sort them > > 2)if they are same, go for next digit... > > > correct me if am wrong... > > > On Aug 21, 7:00 pm, Chonku wrote: > > Treat each number as string and make a trie out of it. For the first > input > > [55,31,312,33], it would look like the following > > . > > /\ > > 3/ 5\ > >1/ 3\5\ > > 31/ 2\ 33\ \55 > >312\ > > Once we have a trie, just print it out by based on the smallest number > > first. In this case, the print would go as follows. > > > > 313123355 > > > > On Sat, Aug 21, 2010 at 12:53 PM, Nikhil Agarwal > > wrote: > > > > > > > > > Suppose the test is like: > > > > > 21 71 217 > > > after sorting and msb appending we get: 217 712 217 > > > sort: 217 217 712 > > > > > here we have 2 same elements 217 and 217 so we remove the 7 from the > > > following logic: > > > > > 1.if msb > lsb we delete from the 2nd 217.else > > > 2.we delete 7 from 1st one. > > > > > so this gives 2121771 > > > > > if it wud have been 41 200 412->412 200 412->200 412 412 > > > here we will remove 2 from last one.giving 20041241 instead of 20041412 > . > > > > > On Sat, Aug 21, 2010 at 12:26 PM, BALARUKESH SIVARAMAN < > > > sbalarukesh1...@gmail.com> wrote: > > > > >> @Nikhil > > >> I am clear with your first 2 algos but not with the change u > introduced > > >> ie., adding a check. please give a working example > > > > >> -- > > >> 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 & Regards > > > Nikhil Agarwal > > > Senior Undergraduate > > > Computer Science & Engineering, > > > National Institute Of Technology, Durgapur,India > > >http://tech-nikk.blogspot.com > > >http://beta.freshersworld.com/communities/nitd > > > > > -- > > > You received this message because you are subscribed to the Google > Groups > > > "Algorithm Geeks" group. > > > To post to this group, send email to algoge...@googlegroups.com. > > > To unsubscribe from this group, send email to > > > algogeeks+unsubscr...@googlegroups.com > > > > . > > > For more options, visit this group at > > >http://groups.google.com/group/algogeeks?hl=en. > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Adobe Questions
to traverse the tree in a spiral manner...
1. Insert the root into stack.
2. then in a loop check not both stack and queue are empty
3. {
while(stack not empty)
{
node =pop(stack);
coutleft);
insertintoqueue(node->right);
}
while(queue not empty)
{
node = dequeue(queue);
coutleft);
push(node->right);
}
}
On Aug 22, 6:41 am, Aravind Prasad wrote:
> can anyone provide the correct and full logic for printing BST
> spirally ..
>
> consider a tree
>
> a
> / \
> b c
> / \ / \
> d e f g
>
> output==>> abcgfeh
>
> here my doubt is ==>>
>
> how to find the level at wihich we are present (considering we are
> using a stack for even levels and queue for odd levels)
>
> On Aug 21, 9:50 am, Stanley Cai wrote:
>
> > this one is not very right...
>
> > public void solution(String str) {
>
> > int t = Integer.parseInt(str, 2);
>
> > System.out.printf(Integer.toBinaryString((int)((1l<<32) - t)));
>
> > }
>
> > Still for this issue, it could be hard if the string is very long, length is
> > more than 32
>
> > On Fri, Aug 20, 2010 at 6:46 PM, GOBIND KUMAR wrote:
> > > This is the code for question no-4
>
> > > #include
> > > #include
> > > using namespace std;
> > > int main(){
> > > char str[20];
> > > char *sp=str;
> > > int n=0;
> > > int count=0;int carry=1;
> > > gets(str);
> > > //cout<<"\n"< > > while(*sp!='\0'){
> > > *sp=(*sp=='1')?'0':'1';
> > > sp++;
> > > count++;
> > > }
> > > //cout<<"\n"< > > sp--;
> > > if(*sp=='1'){
> > > *sp='0';
> > > carry=1;
> > > }
> > > else {
> > > *sp='1';
> > > cout<<"\n"< > > getch();
> > > return 0;
> > > }
> > > sp--;
> > > while(count && carry){
> > > if(*sp=='1'){
> > > *sp='0';
> > > carry=1;
> > > }
> > > else{
> > > *sp='1';
> > > carry=0;
> > > }
> > > sp--;
> > > count--;
> > > }
> > > cout<<"\n"< > > getch();
> > > 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 algoge...@googlegroups.com.
> > > To unsubscribe from this group, send email to
> > > algogeeks+unsubscr...@googlegroups.com > > .com>
> > > .
> > > For more options, visit this group at
> > >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: 0's and 1's yet again!!!
if the intention of the problem is to do it in O(n)..
then we can do 2 passses.. one to find the no of 0 and 1..
then in 2nd pass,, put 0 in even and 1 in odd and leave the rest of
the array as such..
O(n)+O(n)=O(n).
On Aug 20, 5:40 pm, Ashutosh Tamhankar wrote:
> Here is a C++ version of the algorithm to solve this problem.
>
> #include
> #define TRUE 1
> #define FALSE 0
> typedef struct Binarr{
> int iNumber;
>
> };
>
> class binaryarr{
> Binarr * arr;
>
> public:
> int iHead;
> int iSize;
> int iZeroes;
> int iOnes;
> int iTail;
> binaryarr(void);
> ~binaryarr(void);
> bool Rearrange(void);
> bool IsOdd(int iNumber);
> bool IsZero(int iNumber);
> bool SwapElements(int iUnexpected, int iCurrTail, int iExpected);
> bool ZeroOneBalanced(void);
> void Display(void);
>
> };
>
> void binaryarr:: Display(void){
> std::cout << std::endl << "Contents of the arr are";
> for(int j=0; j std::cout << std::endl<< arr[j].iNumber;
>
> }
>
> bool binaryarr:: ZeroOneBalanced(void){
> int iTotal = -1;
> iTotal = iOnes + iZeroes;
> if (iTotal == iSize && iOnes != iZeroes){
> std::cout << std::endl<<"Number of Ones =
> "< std::cin >> iSize;
>
> if(iSize != 0){
> if ((iSize % 2) == 0)
> {
> std::cout << std::endl<<"Enter each zero or one and press
> enter"< arr = (Binarr *) malloc(iSize-1);
> for (iIndex = 0 ; iIndex < iSize ; iIndex ++ )
> std::cin >> arr[iIndex].iNumber;
> iHead = 0;
> iTail = iSize-1;
> iZeroes = 0;
> iOnes = 0;
> }
> else
> {
> std::cout << "The size of the arr cant fit equal number of zeros
> and ones\n";
> iHead = -1;
> }
> }
> else
> {
> std::cout << "The size of the arr cant fit equal number of zeros
> and ones\n";
> iHead = -1;
> }
>
> }
>
> // Free the memory
> binaryarr::~binaryarr(void){
> /*if (iHead != -1)
> free(arr);*/
>
> }
>
> // is the given number odd or even
> bool binaryarr::IsOdd(int iNumber){
> if ( (iNumber == 0 ) )
> return TRUE;
> else
> if (( (iNumber % 2) == 0 ) && (iNumber!=1) )
> return TRUE;
> else
> return FALSE;
>
> }
>
> // is the given number zero or one
> bool binaryarr::IsZero(int iNumber){
>
> if (arr[iNumber].iNumber == 0){
> iZeroes = iZeroes + 1;
> return TRUE;
> }
> else
> {
> iOnes = iOnes + 1;
> return FALSE;
> }
>
> }
>
> bool binaryarr:: SwapElements(int iUnexpected, int iCurrTail, int
> iExpected){
> int iTemp = -1;
> int iFound = -1;
> /*while !((IsZero(iUnexpected)) && iExpected){
> iCurrTail = iCurrTail - 1;
> iFound = 1;
> }*/
> for (int iDecr = iCurrTail; iDecr >= iUnexpected; iDecr--)
> {
> if((IsZero(iDecr)) && (iExpected == 0) || (!(IsZero(iDecr))) &&
> (iExpected == 1))
> {
> iFound = 1;
> iTail = iDecr; // Reposition current tail.
> iTemp = arr[iUnexpected].iNumber;
> arr[iUnexpected].iNumber = arr[iDecr].iNumber;
> arr[iDecr].iNumber = iTemp;
> return TRUE;
> }
> }
> //
>
> if ((iFound == -1) || (iOnes != iZeroes))
> {
> std::cout << std::endl << "binaryarr:: SwapElements: Mismatch or
> mismatch in num of zeros : ones. Expected = "< "< return FALSE;
> }
>
> }
>
> // sort the input arr such that every odd position has a 1 and even position
> a zero.
> bool binaryarr::Rearrange(void){
>
> for (iHead = 0; iHead < iTail; iHead++) {
> if (IsOdd(iHead)) // Determine if the position on the arr is ODD
> {
> if (IsZero(iHead)) // Position is odd; but a zero encountered
> {
> /*if (iTail == iHead)
> iTail = iTail +1;*/
> // Expected is 1.
> if (!(SwapElements(iHead,iTail, 1))) {
> std::cout << std::endl <<"No matching element found for
> element @:"< return FALSE;
> }
> else
> std::cout << std::endl <<"Successfully swapped between
> "< }
> // arr head is 1
> }
> else // position is even
> {
> if (!(IsZero(iHead)))
> {
> if (!(SwapElements(iHead,iTail, 0))) {
> std::cout << std::endl <<"No matching element found for
> element @:"< return FALSE;
> }
> else
> std::cout << std::endl <<"Successfully swapped between
> "< }
> // arr head is 0
> }
>
> }
> Display();
> if (!(ZeroOneBalanced()))
> return FALSE;
> return TRUE;
>
> }
>
>
[algogeeks] Re: Permutation of Array.
for the method of comparison in insertion sort,, consider 1)compare the first digit of all nos and sort them 2)if they are same, go for next digit... correct me if am wrong... On Aug 21, 7:00 pm, Chonku wrote: > Treat each number as string and make a trie out of it. For the first input > [55,31,312,33], it would look like the following > . > / \ > 3/ 5\ > 1/ 3\ 5\ > 31/ 2\ 33\ \55 > 312\ > Once we have a trie, just print it out by based on the smallest number > first. In this case, the print would go as follows. > > 313123355 > > On Sat, Aug 21, 2010 at 12:53 PM, Nikhil Agarwal > wrote: > > > > > Suppose the test is like: > > > 21 71 217 > > after sorting and msb appending we get: 217 712 217 > > sort: 217 217 712 > > > here we have 2 same elements 217 and 217 so we remove the 7 from the > > following logic: > > > 1.if msb > lsb we delete from the 2nd 217.else > > 2.we delete 7 from 1st one. > > > so this gives 2121771 > > > if it wud have been 41 200 412->412 200 412->200 412 412 > > here we will remove 2 from last one.giving 20041241 instead of 20041412 . > > > On Sat, Aug 21, 2010 at 12:26 PM, BALARUKESH SIVARAMAN < > > sbalarukesh1...@gmail.com> wrote: > > >> @Nikhil > >> I am clear with your first 2 algos but not with the change u introduced > >> ie., adding a check. please give a working example > > >> -- > >> 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 >> .com> > >> . > >> For more options, visit this group at > >>http://groups.google.com/group/algogeeks?hl=en. > > > -- > > Thanks & Regards > > Nikhil Agarwal > > Senior Undergraduate > > Computer Science & Engineering, > > National Institute Of Technology, Durgapur,India > >http://tech-nikk.blogspot.com > >http://beta.freshersworld.com/communities/nitd > > > -- > > 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 > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
@Nikhil : I considered the array to be a linked list. xoring the
indexes helps when you don't know how many elements you have.
Marius.
On Aug 22, 5:04 am, Nikhil Agarwal wrote:
> @marius Why are you xorring the indexes along with nos.?any special reason?
>
>
>
>
>
>
>
>
>
> On Sun, Aug 22, 2010 at 7:19 AM, UMarius wrote:
> > @Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1}
> > the output is correct.
> > Maybe I didn't explain the steps correctly. This is the code:
>
> > for(int i = 0 ; i < arr1.Length ; i++)
> > {
> > arr1XOR ^= arr1[i];
> > arr1XOR ^= i;
>
> > arr1SUM += arr1[i];
> > arr1MUL *= arr1[i];
> > }
>
> > for (int i = 0; i < arr2.Length; i++)
> > {
> > arr2XOR ^= arr2[i];
> > arr2XOR ^= i;
>
> > arr2SUM += arr2[i];
> > arr2MUL *= arr2[i];
> > }
>
> > if(arr1XOR == arr2XOR && arr1SUM == arr2SUM && arr1MUL ==
> > arr2MUL)
> > {
> > //SAME VALUES - IDENTICAL ARRAYS
> > }
> > else
> > {
> > //NOT IDENTICAL
> > }
>
> > Please correct me if I'm wrong.
>
> > Marius.
>
> > On Aug 22, 3:45 am, Dave wrote:
> > > @UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the
> > > original problem, you see that the question is not whether the arrays
> > > are identical (which is easily determined by simply comparing them
> > > element-by-element in O(n)), but whether they contain the same values,
> > > possibly in a different order.
>
> > > Dave
>
> > > On Aug 21, 11:01 am, UMarius wrote:
>
> > > > What about this?
>
> > > > 1. xor all elements of each array and their corresponding indexes &
> > > > sum all the elements of each array & mul all elements of each array
> > > > 2. if all results are the same then the arrays are identical
>
> > > > Nice to "meet" you all, I just joined and this is my first post :) ...
>
> > > > > Given two arrays of numbers, find if each of the two arrays have the
> > > > > same set of integers ? Suggest an algo which can run faster than
> > NlogN
> > > > > without extra space?- Hide quoted text -
>
> > > > - Show quoted text -
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
>
> --
> Thanks & Regards
> Nikhil Agarwal
> Senior Undergraduate
> Computer Science & Engineering,
> National Institute Of Technology,
> Durgapur,Indiahttp://tech-nikk.blogspot.comhttp://beta.freshersworld.com/communities/nitd
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
@marius Why are you xorring the indexes along with nos.?any special reason?
On Sun, Aug 22, 2010 at 7:19 AM, UMarius wrote:
> @Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1}
> the output is correct.
> Maybe I didn't explain the steps correctly. This is the code:
>
> for(int i = 0 ; i < arr1.Length ; i++)
>{
>arr1XOR ^= arr1[i];
>arr1XOR ^= i;
>
>arr1SUM += arr1[i];
>arr1MUL *= arr1[i];
>}
>
>for (int i = 0; i < arr2.Length; i++)
>{
>arr2XOR ^= arr2[i];
>arr2XOR ^= i;
>
>arr2SUM += arr2[i];
>arr2MUL *= arr2[i];
>}
>
>if(arr1XOR == arr2XOR && arr1SUM == arr2SUM && arr1MUL ==
> arr2MUL)
>{
>//SAME VALUES - IDENTICAL ARRAYS
>}
>else
>{
>//NOT IDENTICAL
>}
>
> Please correct me if I'm wrong.
>
>
> Marius.
>
>
> On Aug 22, 3:45 am, Dave wrote:
> > @UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the
> > original problem, you see that the question is not whether the arrays
> > are identical (which is easily determined by simply comparing them
> > element-by-element in O(n)), but whether they contain the same values,
> > possibly in a different order.
> >
> > Dave
> >
> > On Aug 21, 11:01 am, UMarius wrote:
> >
> >
> >
> >
> >
> >
> >
> > > What about this?
> >
> > > 1. xor all elements of each array and their corresponding indexes &
> > > sum all the elements of each array & mul all elements of each array
> > > 2. if all results are the same then the arrays are identical
> >
> > > Nice to "meet" you all, I just joined and this is my first post :) ...
> >
> > > > Given two arrays of numbers, find if each of the two arrays have the
> > > > same set of integers ? Suggest an algo which can run faster than
> NlogN
> > > > without extra space?- Hide quoted text -
> >
> > > - Show quoted text -
>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
Thanks & Regards
Nikhil Agarwal
Senior Undergraduate
Computer Science & Engineering,
National Institute Of Technology, Durgapur,India
http://tech-nikk.blogspot.com
http://beta.freshersworld.com/communities/nitd
--
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] kth smallest element in a heap < x
sure, but the implementation is confusing. My question is does not the 2nd count overwrite the 1st value of count in side the function? Thank you. On Sun, Aug 22, 2010 at 1:04 AM, Harshal ..Bet oN iT!! wrote: > if it is a min heap,, then traversing down from the root node, it takes > O(k) time to reach the kth smallest element. so, i think its just that > straight!!! plz correct me if 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. > 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] Re: Longest Palindromic Substring
You use a trie when you want to model a number of strings. Suffix Tree is used only when you have one string in your model. Suffix Tree is a type of trie, but the difference lies in the intent. On Sat, Aug 21, 2010 at 7:22 PM, Chi wrote: > Isn't that by definition a compressed trie, i.e patricia-tree, crit- > bit tree (suffix-tree)? Or what is the difference? > > On Aug 20, 5:17 pm, Nikhil Jindal wrote: > > @chonku > > As i understand, a trie is used when we have a lot of strings (such as a > > dictionary). > > Here we just have a single string. The resultant trie will be: > > > > a > > \ > > b > >\ > > c > > \ > > l > >\ > > e > > \ > > v > >\ > > e > > \ > > l > >\ > > a > > \ > > b > >\ > > c > > > > We get a similar trie for the reverse string. > > > > So why are you using a trie here? I cant see any advantage of it here. > > > > > > > > > > > > On Fri, Aug 20, 2010 at 8:36 AM, Chonku wrote: > > > Can we use a trie here. > > > Make first pass from left to right and construct the trie. > > > Make second pass from right to left and look for the trie branch with > > > maximum nodes that match the characters. > > > > > On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal >wrote: > > > > >> Hi All, > > > > >> Givan a string, you have to find the longest palindromic substring. > > >> For ex: Longest Palindromic substring for abclevelabc is level. > > > > >> What is the most optimised solution possible? > > > > >> Please access the attached hyperlink for an important electronic > communications disclaimer: > http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php > > > > >> -- > > > > >> You received this message because you are subscribed to the Google > Groups "Algorithm Geeks" group. > > > > >> To post to this group, send email toalgoge...@googlegroups.com. > > > > >> To unsubscribe from this group, send email > toalgogeeks+unsubscr...@googlegroups.com > > >. > > > > >> For more options, visit this group athttp:// > 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 > toalgoge...@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 access the attached hyperlink for an important electronic > communications disclaimer: > http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php > > -- > 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] Permutation of Array.
Treat each number as string and make a trie out of it. For the first input [55,31,312,33], it would look like the following . /\ 3/ 5\ 1/ 3\5\ 31/ 2\ 33\ \55 312\ Once we have a trie, just print it out by based on the smallest number first. In this case, the print would go as follows. 313123355 On Sat, Aug 21, 2010 at 12:53 PM, Nikhil Agarwal wrote: > Suppose the test is like: > > 21 71 217 > after sorting and msb appending we get: 217 712 217 > sort: 217 217 712 > > here we have 2 same elements 217 and 217 so we remove the 7 from the > following logic: > > 1.if msb > lsb we delete from the 2nd 217.else > 2.we delete 7 from 1st one. > > so this gives 2121771 > > if it wud have been 41 200 412->412 200 412->200 412 412 > here we will remove 2 from last one.giving 20041241 instead of 20041412 . > > On Sat, Aug 21, 2010 at 12:26 PM, BALARUKESH SIVARAMAN < > sbalarukesh1...@gmail.com> wrote: > >> @Nikhil >> I am clear with your first 2 algos but not with the change u introduced >> ie., adding a check. please give a working example >> >> -- >> 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 & Regards > Nikhil Agarwal > Senior Undergraduate > Computer Science & Engineering, > National Institute Of Technology, Durgapur,India > http://tech-nikk.blogspot.com > http://beta.freshersworld.com/communities/nitd > > > -- > 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.
[algogeeks] Re: Array Problem
@Dave: I read the question correctly and for A = { 1 , 2} B = { 2 , 1}
the output is correct.
Maybe I didn't explain the steps correctly. This is the code:
for(int i = 0 ; i < arr1.Length ; i++)
{
arr1XOR ^= arr1[i];
arr1XOR ^= i;
arr1SUM += arr1[i];
arr1MUL *= arr1[i];
}
for (int i = 0; i < arr2.Length; i++)
{
arr2XOR ^= arr2[i];
arr2XOR ^= i;
arr2SUM += arr2[i];
arr2MUL *= arr2[i];
}
if(arr1XOR == arr2XOR && arr1SUM == arr2SUM && arr1MUL ==
arr2MUL)
{
//SAME VALUES - IDENTICAL ARRAYS
}
else
{
//NOT IDENTICAL
}
Please correct me if I'm wrong.
Marius.
On Aug 22, 3:45 am, Dave wrote:
> @UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the
> original problem, you see that the question is not whether the arrays
> are identical (which is easily determined by simply comparing them
> element-by-element in O(n)), but whether they contain the same values,
> possibly in a different order.
>
> Dave
>
> On Aug 21, 11:01 am, UMarius wrote:
>
>
>
>
>
>
>
> > What about this?
>
> > 1. xor all elements of each array and their corresponding indexes &
> > sum all the elements of each array & mul all elements of each array
> > 2. if all results are the same then the arrays are identical
>
> > Nice to "meet" you all, I just joined and this is my first post :) ...
>
> > > Given two arrays of numbers, find if each of the two arrays have the
> > > same set of integers ? Suggest an algo which can run faster than NlogN
> > > without extra space?- Hide quoted text -
>
> > - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Adobe Questions
can anyone provide the correct and full logic for printing BST
spirally ..
consider a tree
a
/ \
bc
/ \ / \
d e f g
output==>> abcgfeh
here my doubt is ==>>
how to find the level at wihich we are present (considering we are
using a stack for even levels and queue for odd levels)
On Aug 21, 9:50 am, Stanley Cai wrote:
> this one is not very right...
>
> public void solution(String str) {
>
> int t = Integer.parseInt(str, 2);
>
> System.out.printf(Integer.toBinaryString((int)((1l<<32) - t)));
>
> }
>
> Still for this issue, it could be hard if the string is very long, length is
> more than 32
>
>
>
> On Fri, Aug 20, 2010 at 6:46 PM, GOBIND KUMAR wrote:
> > This is the code for question no-4
>
> > #include
> > #include
> > using namespace std;
> > int main(){
> > char str[20];
> > char *sp=str;
> > int n=0;
> > int count=0;int carry=1;
> > gets(str);
> > //cout<<"\n"< > while(*sp!='\0'){
> > *sp=(*sp=='1')?'0':'1';
> > sp++;
> > count++;
> > }
> > //cout<<"\n"< > sp--;
> > if(*sp=='1'){
> > *sp='0';
> > carry=1;
> > }
> > else {
> > *sp='1';
> > cout<<"\n"< > getch();
> > return 0;
> > }
> > sp--;
> > while(count && carry){
> > if(*sp=='1'){
> > *sp='0';
> > carry=1;
> > }
> > else{
> > *sp='1';
> > carry=0;
> > }
> > sp--;
> > count--;
> > }
> > cout<<"\n"< > getch();
> > 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 algoge...@googlegroups.com.
> > To unsubscribe from this group, send email to
> > algogeeks+unsubscr...@googlegroups.com > .com>
> > .
> > For more options, visit this group at
> >http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
@UMarius: A = {1,2}, B = {2,1} fails your test. If you reread the
original problem, you see that the question is not whether the arrays
are identical (which is easily determined by simply comparing them
element-by-element in O(n)), but whether they contain the same values,
possibly in a different order.
Dave
On Aug 21, 11:01 am, UMarius wrote:
> What about this?
>
> 1. xor all elements of each array and their corresponding indexes &
> sum all the elements of each array & mul all elements of each array
> 2. if all results are the same then the arrays are identical
>
> Nice to "meet" you all, I just joined and this is my first post :) ...
>
>
>
> > Given two arrays of numbers, find if each of the two arrays have the
> > same set of integers ? Suggest an algo which can run faster than NlogN
> > without extra space?- Hide quoted text -
>
> - Show quoted text -
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Longest Palindromic Substring
1)maintain 2 pointers.. one from left and other from right..
2)run two nested loops to compre each element from right with the element in
left..
3)if they are same pass the subset(the characters in between) to function
that checks if it is a palindrome or not.
complexity==> O(n^2)+O(n)
correct me if am wrong
On Sun, Aug 22, 2010 at 5:48 AM, venkatesan B wrote:
> use stack
> push one by one element before compare to top 2 element in stack
> {
> if same then pop element and compare next char of string with top char in
> stack
> if same continue otherwise clear stack
> }
> else
> {push element to stack}
>
> if wrong correct me
>
>
>
>
> --- On *Sat, 21/8/10, nipun batra * wrote:
>
>
> From: nipun batra
> Subject: Re: [algogeeks] Longest Palindromic Substring
> To: algogeeks@googlegroups.com
> Date: Saturday, 21 August, 2010, 4:18 PM
>
>
> An O(n^3) solution.Wanna know if it's possible to optimize without using
> trees.
>
> #include
> #include
> using namespace std;
> char* substring(char*s,int start,int finish)
> {
> int ctr=0;
> char str[1000];
> while(start<=finish)
> {
> str[ctr]=s[start];
> start+=1;
> ctr+=1;
> }
> str[ctr]='\0';
> return str;
> }
> bool isPalindrome(char *s)
> {
> int size=strlen(s);
> int j=size-1;
> int i=0;
> while((s[i]==s[j])&&(i {
> i+=1;
> j-=1;
> }
> if (i>=j)
> return true;
> else
> return false;
> }
> int main()
> {
>
> int i,j;
> char s[100];
> cin>>s;
>
> int size=strlen(s);
> int tempMax=size-1;
> while(tempMax>1)
> {
> for(i=0;i+tempMax {
> if(isPalindrome(substring(s,i,i+tempMax)))//O(n)
> {
> puts(substring(s,i,i+tempMax));
> cout<<" of size "< break;
> }
> }
> tempMax-=1;
> }
>
>
> return 0;
> }
>
>
>
>
> On Sat, Aug 21, 2010 at 12:12 PM, Chonku
> http://mc/compose?to=cho...@gmail.com>
> > wrote:
>
> I definitely meant a suffix Tree and not a trie. Apologize for that. :)
>
> On Fri, Aug 20, 2010 at 8:47 PM, Nikhil Jindal
> http://mc/compose?to=fundoon...@yahoo.co.in>
> > wrote:
>
> @chonku
> As i understand, a trie is used when we have a lot of strings (such as a
> dictionary).
> Here we just have a single string. The resultant trie will be:
>
> a
> \
> b
>\
> c
> \
> l
>\
> e
> \
> v
>\
> e
> \
> l
>\
> a
> \
> b
>\
> c
>
> We get a similar trie for the reverse string.
>
> So why are you using a trie here? I cant see any advantage of it here.
>
> On Fri, Aug 20, 2010 at 8:36 AM, Chonku
> http://mc/compose?to=cho...@gmail.com>
> > wrote:
>
> Can we use a trie here.
> Make first pass from left to right and construct the trie.
> Make second pass from right to left and look for the trie branch with
> maximum nodes that match the characters.
>
> On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal
> http://mc/compose?to=fundoon...@yahoo.co.in>
> > wrote:
>
> Hi All,
>
> Givan a string, you have to find the longest palindromic substring.
> For ex: Longest Palindromic substring for abclevelabc is level.
>
> What is the most optimised solution possible?
>
> Please access the attached hyperlink for an important electronic
> communications disclaimer:
> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
>
>
>
>
>
>
> --
>
> 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.
>
>
> Please access the attached hyperlink for an important electronic
> communications disclaimer:
> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
>
>
>
> --
>
> You received this message because
Re: [algogeeks] Longest Palindromic Substring
use stackpush one by one element before compare to top 2 element in stack {if
same then pop element and compare next char of string with top char in stackif
same continue otherwise clear stack}else{push element to stack}
if wrong correct me
--- On Sat, 21/8/10, nipun batra wrote:
From: nipun batra
Subject: Re: [algogeeks] Longest Palindromic Substring
To: algogeeks@googlegroups.com
Date: Saturday, 21 August, 2010, 4:18 PM
An O(n^3) solution.Wanna know if it's possible to optimize without using trees.
#include#includeusing namespace std;char*
substring(char*s,int start,int finish)
{ int ctr=0; char str[1000]; while(start<=finish)
{ str[ctr]=s[start]; start+=1;
ctr+=1; } str[ctr]='\0'; return str;
}bool isPalindrome(char *s) { int size=strlen(s);
int j=size-1; int i=0; while((s[i]==s[j])&&(i=j)
return true; else return false; }int main() {
int i,j; char s[100]; cin>>s;
int size=strlen(s); int tempMax=size-1;
while(tempMax>1) { for(i=0;i+tempMax wrote:
I definitely meant a suffix Tree and not a trie. Apologize for that. :)
On Fri, Aug 20, 2010 at 8:47 PM, Nikhil Jindal wrote:
@chonkuAs i understand, a trie is used when we have a lot of strings (such as a
dictionary).
Here we just have a single string. The resultant trie will be:
a
\
b
\
c
\
l
\
e
\
v
\
e
\
l
\
a
\
b
\
c
We get a similar trie for the reverse string.
So why are you using a trie here? I cant see any advantage of it here.
On Fri, Aug 20, 2010 at 8:36 AM, Chonku wrote:
Can we use a trie here.
Make first pass from left to right and construct the trie.
Make second pass from right to left and look for the trie branch with maximum
nodes that match the characters.
On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal wrote:
Hi All,
Givan a string, you have to find the longest palindromic substring.
For ex: Longest Palindromic substring for abclevelabc is level.
What is the most optimised solution possible?Please access the attached
hyperlink for an important electronic communications disclaimer:
http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
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.
Please access the attached hyperlink for an important electronic communications
disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
@UMarius: I'm sounding like a broken record. Rather than challenging everyone to keep coming up with counterexamples, please provide a rationale as to why an algorithm such as this should work. It looks as if you have two equations in 2N unknowns and are trying to assert that the only solution is A_1 = B_1, A_2 = B_2, etc. (where I have assumed that each array is sorted). Usually, it takes 2N equations to determine 2N unknowns, although other information about the solutions can lessen that number in certain circumstances. At least if you are going to propose something, do so only after you have tested it on all of the combinations of up to four numbers between -5 and 5. Dave On Aug 21, 11:01 am, UMarius wrote: > What about this? > > 1. xor all elements of each array and their corresponding indexes & > sum all the elements of each array & mul all elements of each array > 2. if all results are the same then the arrays are identical > > Nice to "meet" you all, I just joined and this is my first post :) ... > > > > > Given two arrays of numbers, find if each of the two arrays have the > > same set of integers ? Suggest an algo which can run faster than NlogN > > without extra space?- Hide quoted text - > > - Show quoted text - -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] kth smallest element in a heap < x
if it is a min heap,, then traversing down from the root node, it takes O(k) time to reach the kth smallest element. so, i think its just that straight!!! plz correct me if 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. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Array Problem
What about this? 1. xor all elements of each array and their corresponding indexes & sum all the elements of each array & mul all elements of each array 2. if all results are the same then the arrays are identical Nice to "meet" you all, I just joined and this is my first post :) ... > Given two arrays of numbers, find if each of the two arrays have the > same set of integers ? Suggest an algo which can run faster than NlogN > without 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Re: Longest Palindromic Substring
Isn't that by definition a compressed trie, i.e patricia-tree, crit- bit tree (suffix-tree)? Or what is the difference? On Aug 20, 5:17 pm, Nikhil Jindal wrote: > @chonku > As i understand, a trie is used when we have a lot of strings (such as a > dictionary). > Here we just have a single string. The resultant trie will be: > > a > \ > b > \ > c > \ > l > \ > e > \ > v > \ > e > \ > l > \ > a > \ > b > \ > c > > We get a similar trie for the reverse string. > > So why are you using a trie here? I cant see any advantage of it here. > > > > > > On Fri, Aug 20, 2010 at 8:36 AM, Chonku wrote: > > Can we use a trie here. > > Make first pass from left to right and construct the trie. > > Make second pass from right to left and look for the trie branch with > > maximum nodes that match the characters. > > > On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal > > wrote: > > >> Hi All, > > >> Givan a string, you have to find the longest palindromic substring. > >> For ex: Longest Palindromic substring for abclevelabc is level. > > >> What is the most optimised solution possible? > > >> Please access the attached hyperlink for an important electronic > >> communications > >> disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php > > >> -- > > >> You received this message because you are subscribed to the Google Groups > >> "Algorithm Geeks" group. > > >> To post to this group, send email toalgoge...@googlegroups.com. > > >> To unsubscribe from this group, send email > >> toalgogeeks+unsubscr...@googlegroups.com. > > >> For more options, visit this group > >> athttp://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 > > toalgoge...@googlegroups.com. > > To unsubscribe from this group, send email > > to>algogeeks+unsubscr...@googlegroups.com > .com> > > . > > For more options, visit this group at > >http://groups.google.com/group/algogeeks?hl=en. > > Please access the attached hyperlink for an important electronic > communications > disclaimer:http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
[algogeeks] Discussion on unique-elements-in-an-array
i think this could be done if we use binary search tree for finding the duplicates. 1. take first element in the array as the root. 2. for the next input element(say x) there can be 3 cases: 2.1 x==root : since this is a duplicate we discard this element and move to next no. in the list. 2.2 xhttp://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Longest Palindromic Substring
@Nipun: The soln is correct. It is O(n^3) and no extra memory is required.
One soln I can think of is:
Find longest common substring in the given string and its reverse. It will
be a palindrome.
This will be O(n^2) but uses extra space.
On Sat, Aug 21, 2010 at 4:18 PM, nipun batra wrote:
> An O(n^3) solution.Wanna know if it's possible to optimize without using
> trees.
>
> #include
> #include
> using namespace std;
> char* substring(char*s,int start,int finish)
> {
> int ctr=0;
> char str[1000];
> while(start<=finish)
> {
> str[ctr]=s[start];
> start+=1;
> ctr+=1;
> }
> str[ctr]='\0';
> return str;
> }
> bool isPalindrome(char *s)
> {
> int size=strlen(s);
> int j=size-1;
> int i=0;
> while((s[i]==s[j])&&(i {
> i+=1;
> j-=1;
> }
> if (i>=j)
> return true;
> else
> return false;
> }
> int main()
> {
>
> int i,j;
> char s[100];
> cin>>s;
>
> int size=strlen(s);
> int tempMax=size-1;
> while(tempMax>1)
> {
> for(i=0;i+tempMax {
> if(isPalindrome(substring(s,i,i+tempMax)))//O(n)
> {
> puts(substring(s,i,i+tempMax));
> cout<<" of size "< break;
> }
> }
> tempMax-=1;
> }
>
>
> return 0;
> }
>
>
>
>
> On Sat, Aug 21, 2010 at 12:12 PM, Chonku wrote:
>
>> I definitely meant a suffix Tree and not a trie. Apologize for that. :)
>>
>> On Fri, Aug 20, 2010 at 8:47 PM, Nikhil Jindal wrote:
>>
>>> @chonku
>>> As i understand, a trie is used when we have a lot of strings (such as a
>>> dictionary).
>>> Here we just have a single string. The resultant trie will be:
>>>
>>> a
>>> \
>>> b
>>>\
>>> c
>>> \
>>> l
>>>\
>>> e
>>> \
>>> v
>>>\
>>> e
>>> \
>>> l
>>>\
>>> a
>>> \
>>> b
>>>\
>>> c
>>>
>>> We get a similar trie for the reverse string.
>>>
>>> So why are you using a trie here? I cant see any advantage of it here.
>>>
>>> On Fri, Aug 20, 2010 at 8:36 AM, Chonku wrote:
>>>
Can we use a trie here.
Make first pass from left to right and construct the trie.
Make second pass from right to left and look for the trie branch with
maximum nodes that match the characters.
On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal <
fundoon...@yahoo.co.in> wrote:
> Hi All,
>
> Givan a string, you have to find the longest palindromic substring.
> For ex: Longest Palindromic substring for abclevelabc is level.
>
> What is the most optimised solution possible?
>
> Please access the attached hyperlink for an important electronic
> communications disclaimer:
> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
>
>
>
>
>
>
> --
>
> 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.
>>>
>>> Please access the attached hyperlink for an important electronic
>>> communications disclaimer:
>>> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
>>>
>>>
>>>
>>> --
>>>
>>> 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:
Re: [algogeeks] Re: Longest Common Subsequence
"longest common substring in the given string". If i get it right. You need two strings to find a common subsequence. We use DP for it. 2010/8/18 ♪ ѕяiηivαѕαη ♪ <21.sr...@gmail.com> > Example: > If my sequence is ABC..the longest common subsequence is > AC,BC,AB. > It is a very common problem... > > > On Wed, Aug 18, 2010 at 11:58 AM, vinodh kumar wrote: > >> heh could u explain the question with a example..??!! >> >> On Aug 18, 8:47 pm, ♪ ѕяiηivαѕαη ♪ <21.sr...@gmail.com> wrote: >> > Hi.. >> > Can anyone here explain me /provide me with an algorithm/source code in >> C >> > which efficiently finds out the *longest common substring in the given >> > string??* >> >> -- >> 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. > Please access the attached hyperlink for an important electronic communications disclaimer: http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Array Problem
@Nikhil Agarwal: You cannot take extra memory and neither the range of
numbers is specified.
Counting will not be a viable option.
On Fri, Aug 20, 2010 at 9:38 AM, Nikhil Agarwal
wrote:
> Check this new algo: plz provide counter eg.(if any)
>
> step 1 : count the no. of elements,0s,1s,2s,3s in arr1 and arry2.if yes
> proceed to step 2 else print fail
> step2: if(sum of the elements and product of the non zero elements are
> same in both arrays ) print arrays are same else print fail.
>
>
> On Fri, Aug 20, 2010 at 4:26 AM, Dave wrote:
>
>> @Saikat: Rather than challenging everyone to keep coming up with
>> counterexamples, please provide a rationale as to why an algorithm
>> such as this should work. It looks as if you have two equations in 2N
>> unknowns and are trying to assert that the only solution is A_1 =
>> B_1,
>> A_2 = B_2, etc. (where I have assumed that each array is sorted).
>> Usually, it takes 2N equations to determine 2N unknowns, although
>> other information about the solutions can lessen that number in
>> certain circumstances.
>>
>> At least if you are going to propose something, do so only after you
>> have tested it on all of the combinations of up to four numbers
>> between -5 and 5.
>>
>> Dave
>>
>> On Aug 19, 11:52 am, Saikat Debnath wrote:
>> > 1. Add sum of squares of all numbers in respective groups, if equal
>> > goto step 2.
>> > 2. XOR all elements of both groups, (if==0) elements are same.
>> >
>> > On Aug 19, 9:21 pm, Dave wrote:
>> >
>> >
>> >
>> > > @Nikhil Jindal: What you say is true for 2 numbers, but not for more
>> > > than 2.
>> > > 1 + 6 + 6 = 2 + 2 + 9 = 13, and 1 * 6 * 6 = 2 * 2 * 9 = 36.
>> >
>> > > Dave
>> >
>> > > On Aug 19, 6:00 am, Nikhil Jindal wrote:
>> >
>> > > > Nikhil's algo is correct if the following is always true:
>> >
>> > > > Given: x + y = S, x * y = M
>> > > > and x' + y' = S', x' * y' = M'
>> >
>> > > > If: S' = S and M' = M, then x = x' and y = y'
>> > > > i.e for given sum and product, the elements are unique.
>> >
>> > > > On Thu, Aug 19, 2010 at 12:54 PM, Nikhil Agarwal
>> > > > wrote:
>> >
>> > > > > @Dave : my algo won't fail for {0,1,-1} and {0,2,-2} .
>> >
>> > > > > S1=0;S2=0;
>> > > > > M1=-1 and M2 =-4 (excluding 0 multiplication which i had
>> corrected)
>> > > > > M1!=M2 there fore it is correct.
>> >
>> > > > > Code:
>> >
>> > > > > bool check_arrays(vector v1,vector v2){
>> > > > > if(v1.size()!=v2.size())
>> > > > > return 0;
>> > > > > if(v1.size()==0&&v2.size()==0)
>> > > > > return 1;
>> > > > > int sum,product1,product2;
>> > > > > sum=0;product1=1;product2=1;
>> > > > > for(int i=0;i> > > > > sum+=v1[i];
>> > > > > sum-=v2[i];
>> > > > > if(v1[i]!=0)
>> > > > > product1*=v1[i];
>> > > > > if(v2[i]!=0)
>> > > > > product2*=v2[i];
>> > > > > }
>> > > > > if(sum==0&&(product1==product2))
>> > > > > return 1;
>> > > > > return 0;
>> > > > > }
>> > > > > On Thu, Aug 19, 2010 at 11:26 AM, Dave
>> wrote:
>> >
>> > > > >> @Srinivas, Make that: Your algorithm seems to fail on A =
>> {0,1,-2), B
>> > > > >> =
>> > > > >> (0,2,-3). I was thinking ones-complement arithmetic instead of
>> twos-
>> > > > >> complement.
>> >
>> > > > >> Dave
>> >
>> > > > >> On Aug 18, 11:59 pm, Dave wrote:
>> > > > >> > @Srinivas, Your algorithm seems to fail on A = {0,1,-1), B =
>> > > > >> > (0,2,-2).
>> >
>> > > > >> > Dave
>> >
>> > > > >> > On Aug 18, 10:53 pm, srinivas reddy
>> wrote:
>> >
>> > > > >> > > add one more thing to the solution suggested by nikhil
>> i.e;count the
>> > > > >> number
>> > > > >> > > of elements in array 1 and number of elements in array2 if
>> these two
>> > > > >> values
>> > > > >> > > are equal then after follow the algo proposed by nikhil
>> agarwal..
>> >
>> > > > >> > > On Wed, Aug 18, 2010 at 8:50 PM, Rais Khan <
>> raiskhan.i...@gmail.com>
>> > > > >> wrote:
>> > > > >> > > > @Chonku: Your algo seems to fail with following input.
>> > > > >> > > > Arr1[]= {1,6}
>> > > > >> > > > Arr2[]={7}
>> >
>> > > > >> > > > On Wed, Aug 18, 2010 at 8:42 PM, Rais Khan <
>> raiskhan.i...@gmail.com
>> > > > >> >wrote:
>> >
>> > > > >> > > >> @Nikhil: Your algo seems to fail with following input.
>> What do you
>> > > > >> say?
>> > > > >> > > >> Arr1[]= {1,2,3}
>> > > > >> > > >> Arr2[]={6}
>> >
>> > > > >> > > >> On Wed, Aug 18, 2010 at 7:17 AM, Nikhil Agarwal <
>> > > > >> > > >> nikhil.bhoja...@gmail.com> wrote:
>> >
>> > > > >> > > >>> Sum all the elements of both the arrays..let it be s1 and
>> s2
>> > > > >> > > >>> Multiply the elements and call as m1 and m2
>> > > > >> > > >>> if(s1==s2) &&(m1==m2)
>> > > > >> > > >>> return 1;else
>> > > > >> > > >>> return 0;
>> >
>> > > > >> > > >>> O(n)
>> >
>> > > > >> > > >>> On Tue, Aug 17, 2010 at 11:33 PM, amit <
>> amitjaspal...@gmail.com>
>> > > > >> wrote:
>> >
>> > > > >> > > Given two arrays of numbers, find if each of the two
>> arrays have
>> > > > >> the
>> > > > >> > > same set of integers ? Suggest an algo which can run
>> faster than
>> > > > >
Re: [algogeeks] Permutation of Array.
Suppose the test is like: 21 71 217 after sorting and msb appending we get: 217 712 217 sort: 217 217 712 here we have 2 same elements 217 and 217 so we remove the 7 from the following logic: 1.if msb > lsb we delete from the 2nd 217.else 2.we delete 7 from 1st one. so this gives 2121771 if it wud have been 41 200 412->412 200 412->200 412 412 here we will remove 2 from last one.giving 20041241 instead of 20041412 . On Sat, Aug 21, 2010 at 12:26 PM, BALARUKESH SIVARAMAN < sbalarukesh1...@gmail.com> wrote: > @Nikhil > I am clear with your first 2 algos but not with the change u introduced > ie., adding a check. please give a working example > > -- > 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 & Regards Nikhil Agarwal Senior Undergraduate Computer Science & Engineering, National Institute Of Technology, Durgapur,India http://tech-nikk.blogspot.com http://beta.freshersworld.com/communities/nitd -- 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] Longest Palindromic Substring
An O(n^3) solution.Wanna know if it's possible to optimize without using
trees.
#include
#include
using namespace std;
char* substring(char*s,int start,int finish)
{
int ctr=0;
char str[1000];
while(start<=finish)
{
str[ctr]=s[start];
start+=1;
ctr+=1;
}
str[ctr]='\0';
return str;
}
bool isPalindrome(char *s)
{
int size=strlen(s);
int j=size-1;
int i=0;
while((s[i]==s[j])&&(i=j)
return true;
else
return false;
}
int main()
{
int i,j;
char s[100];
cin>>s;
int size=strlen(s);
int tempMax=size-1;
while(tempMax>1)
{
for(i=0;i+tempMax wrote:
> I definitely meant a suffix Tree and not a trie. Apologize for that. :)
>
> On Fri, Aug 20, 2010 at 8:47 PM, Nikhil Jindal wrote:
>
>> @chonku
>> As i understand, a trie is used when we have a lot of strings (such as a
>> dictionary).
>> Here we just have a single string. The resultant trie will be:
>>
>> a
>> \
>> b
>>\
>> c
>> \
>> l
>>\
>> e
>> \
>> v
>>\
>> e
>> \
>> l
>>\
>> a
>> \
>> b
>>\
>> c
>>
>> We get a similar trie for the reverse string.
>>
>> So why are you using a trie here? I cant see any advantage of it here.
>>
>> On Fri, Aug 20, 2010 at 8:36 AM, Chonku wrote:
>>
>>> Can we use a trie here.
>>> Make first pass from left to right and construct the trie.
>>> Make second pass from right to left and look for the trie branch with
>>> maximum nodes that match the characters.
>>>
>>> On Thu, Aug 19, 2010 at 7:46 PM, Nikhil Jindal >> > wrote:
>>>
Hi All,
Givan a string, you have to find the longest palindromic substring.
For ex: Longest Palindromic substring for abclevelabc is level.
What is the most optimised solution possible?
Please access the attached hyperlink for an important electronic
communications disclaimer:
http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
--
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.
>>>
>>
>> Please access the attached hyperlink for an important electronic
>> communications disclaimer:
>> http://dce.edu/web/Sections/Standalone/Email_Disclaimer.php
>>
>>
>>
>> --
>>
>> You received this message because you are subscribed to the Google Groups
>> "Algorithm Geeks" group.
>>
>> To post to this group, send email to algoge...@googlegroups.com.
>>
>> To unsubscribe from this group, send email to
>> algogeeks+unsubscr...@googlegroups.com
>> .
>>
>>
>> For more options, visit this group at
>> http://groups.google.com/group/algogeeks?hl=en.
>>
>>
>>
> --
> You received this message because you are subscribed to the Google Groups
> "Algorithm Geeks" group.
> To post to this group, send email to algoge...@googlegroups.com.
> To unsubscribe from this group, send email to
> algogeeks+unsubscr...@googlegroups.com
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
