[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

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

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

[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

[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

[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

[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

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(in

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

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

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\

[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; arr1SU

[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 i

[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 o

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) correc

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

[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

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

[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

[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.

[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

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(

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...

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 ar

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

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];