Re: [algogeeks] importance of heaps
From interview perspective i think min-max heaps are enough. You should be able to identify situations where you can apply them. I do not think other heaps are of any use. On Tue, Jun 5, 2012 at 11:40 AM, Abhishek Sharma abhi120...@gmail.comwrote: can anyone please tell me how important are heaps as compared to other data structures (from interview's point of view). i am not talking about simple min/max heaps, but advanced ones like fibonacci heaps and binomial heaps -- 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, Jeevitesh Shekhar Singh.* -- 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] LINKED LIST QUESTION
This is possible only if Linked List is sorted then we can apply Merge Sort for Linked List which would be in place. Otherwise the time complexity would be O(n logn). On Mon, Jun 4, 2012 at 3:00 PM, VIHARRI viharri@gmail.com wrote: Hi we need find a node in linked list in O(logn). You can change the list as u like. -- 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/-/vSoEXlaRTEIJ. 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, Jeevitesh Shekhar Singh.* -- 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] Re: amazon interview questions
i have not implemented it but i can you an idea how to approach it.
Go to Each suffix in suffix or suffix array(I would prefer suffix array as
it is easier) traverse the each suffix till you encounter the first letter
of the suffix you are traversing and check to see this suppose i is the
index you found out the starting letter then check
s.substring(0,i)==s.substring(i,2i).
I hope you get the idea.
On Mon, Jun 4, 2012 at 9:14 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@jeevitesh :- yes i am also thinking of suffix tree,
but i am facing problem in implementing it. did you implement it ??
On Mon, Jun 4, 2012 at 9:11 AM, utsav sharma utsav.sharm...@gmail.comwrote:
@hassan :- it will not work for many strings as you are checking from the
mid of strings. try out ababcdef,aabc.
@atul :- it should be done in O(n).
On Sun, Jun 3, 2012 at 11:54 PM, Hassan Monfared hmonfa...@gmail.comwrote:
yes it's not valid
On Sun, Jun 3, 2012 at 5:36 PM, anugrah anugrah.agra...@gmail.comwrote:
So any string with two same characters is not valid??
for example :
GEEK has E followed by E.
So GEEK is also invalid?
On Jun 3, 1:49 pm, Hassan Monfared hmonfa...@gmail.com wrote:
bool IsValid(string s)
{
for(int len=0;lens.len/2;len++)
{
int start1=0,start2=len+1;
while(start2s.size())
{
for(int i=0;ilen start2+is.size()
s[start1+i]=s[start2+i];i++);
if(i==len)
return false; //not valid
start1++;
start2++;
}
}
return true; // valid
}
On Sun, Jun 3, 2012 at 12:52 PM, atul anand atul.87fri...@gmail.com
wrote:
can be done with O(n^2) time complexity..
can it be done with O(n) complexity ???
On 6/3/12, utsav sharma utsav.sharm...@gmail.com wrote:
given a string tell wether it is valid or not.
string is valid if there is no substring which have the same
substring
following it.
these strings are not valid:- stringstring,geek123123rt,
abcadabcad,strngstingstrngsting
--
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.
--
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.
--
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,
Jeevitesh Shekhar Singh.*
--
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] Tree/Graph implementation
We can use the following data structure for Graphs:- - Adjacency Lists(More generally used) - Adjacency Matrix(Takes a lot of space but good for dense graph) For Trees:- We can model a node such that it has two pointers one of which points to its first child while the other points to the next peer or sibling. On Tue, May 29, 2012 at 4:03 PM, Hassan Monfared hmonfa...@gmail.comwrote: you can use adjacency matrices for spare graphs and two dimensional array for non-spare graphs On Tue, May 29, 2012 at 2:47 PM, prakash y yprakash@gmail.com wrote: How to implement complex data structures like trees (with unknown no.of subtrees) and graphs efficiently in C/Java? I have implemented binary trees in Java as it always contains two nodes. But I don't know about graphs. I am not able to solve these problems in coding contests because of this. Can anyone please suggest me? Thanks in advance. ~Prakash. -- 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, Jeevitesh Shekhar Singh.* -- 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] Print longest string duplicated M times
You can use Suffix Arrays or Suffix Trees.
On Mon, May 21, 2012 at 8:17 AM, Ashish Goel ashg...@gmail.com wrote:
soln pls
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Sun, May 20, 2012 at 5:49 PM, jalaj jaiswal
jalaj.jaiswa...@gmail.comwrote:
I can give you a dynamic programming approach in O(n^2) and O(n) space .
On Tue, May 15, 2012 at 12:22 PM, Ashish Goel ashg...@gmail.com wrote:
I am unclear about the answer provided by Programming Pearls on the
question. What this does is to find longest string whose beginning is
separated by exactly M chars.
The original question is to find the longest string duplicated M times. Any
ideas on the approach for this? I could think of having a suffix tree with
each node keeping a count to keep track of while insertion how many times
this node was passed while going down
#include stdlib.h
#include string.h
#include stdio.h
int pstrcmp(char **p, char **q)
{ return strcmp(*p, *q); }
int comlen(char *p, char *q)
{ int i = 0;
while (*p (*p++ == *q++))
i++;
return i;
}
#define M 1
#define MAXN 500
char c[MAXN], *a[MAXN];
int main()
{ int i, ch, n = 0, maxi, maxlen = -1;
while ((ch = getchar()) != EOF) {
a[n] = c[n];
c[n++] = ch;
}
c[n] = 0;
qsort(a, n, sizeof(char *), pstrcmp);
for (i = 0; i n-M; i++)
if (comlen(a[i], a[i+M]) maxlen) {
maxlen = comlen(a[i], a[i+M]);
maxi = i;
}
printf(%.*s\n, maxlen, a[maxi]);
return 0;
}
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
--
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.
--
Regards,
Jalaj Jaiswal
Software Developer,
Adobe Systems
+91-9019947895
*
*
FACEBOOK http://www.facebook.com/jalaj.jaiswal89
LINKEDINhttp://www.linkedin.com/profile/view?id=34803280trk=tab_pro
--
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,
Jeevitesh Shekhar Singh.*
--
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] finding anagrams in a list of words
Yup i agree with Atul's solution. Just explaining the same thing a little better. Have a HashMap with the following structure:- HashMapString, ArrayListString; now scan through the List of words Sort the word and check whether it is already there on the hashmap if it is just add this word to the list for this corresponding word else just add this sorted form of this word to the HashMap . So if you give me any word i will sort it check it in hashmap and get the list of all its corresponding anagrams. On Sat, May 12, 2012 at 1:57 PM, atul anand atul.87fri...@gmail.com wrote: given the list of words... what you can do is the following :- now take first word from the list.. sort this word in alphabetical order...for eg str=bcda --- sort , we get str=abcd now considering this sorted word as a key(abcd) , insert original word (bcda as value) into the hash table ( hash table with chaining ) similarly do it for other words. now given a word , you just need to sort this given word and use it as a key to fetch all anagram. On Fri, May 11, 2012 at 5:24 PM, mayur mayursa...@gmail.com wrote: Hi all, I am stuck with a question for a long time...can someone provide the best algorithm for this.. Question).. find all the anagrams in a list of words. The algorithm should be efficient as the list can be very large. -- 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/-/c4cSIMcBYLEJ. 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, Jeevitesh Shekhar Singh.* -- 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] Sorting in O(n)
Hi all, I am new to this group. My last post was deleted i do not know the reason behind it. I will explain my logic here:- as the range is 1 to n^2 we have a input array like input[n^2]. We can take a auxillary array of size n^2 like aux[n^2]. Scan the input array. For each input input[i] increment by one corresponding aux[input[i]]. After this just iterate through the aux array printing the index aux[i] times. This way we can sort it in O(n) time. On Sat, May 5, 2012 at 2:02 PM, saurabh singh saurab...@gmail.com wrote: After giving some thought,I think even radix sort may not be sufficient. Complexity of radix sort is O(k*n) where k is the number of buckets required to sort the given range. The number of buckets is proportional to the number of bits required to represent the *maximum number in the given range.*For our case the maximum number is O(n^2).Hence *the number of buckets required would be proportional to log(n^2) in the worst case.* Hence the worst case complexity for the given constraints using radix sort would be *O(n*(log n^2)) = O(n*logn).* This is no better than comparision sort.A slight optimization that we can make is to use a higher base which would reduce the number of buckets required but would add the cost of converting each number into the higher base. Somehow I am getting convinced worst case O(n) algorithm may not be possible.Working on the mathematical proof. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sat, May 5, 2012 at 8:37 AM, saurabh singh saurab...@gmail.com wrote: @cegprakash They are n numbers lying in the range 1 to n^2.Not necessarily sorted. eg 3 4 1 2 5 8 (6 numbers satisfying the conditions given in the problem) Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sat, May 5, 2012 at 5:17 AM, Prakash D cegprak...@gmail.com wrote: The range 1 to n^2 is already sorted On Sat, May 5, 2012 at 12:17 AM, Algobiz deepak.arulkan...@gmail.com wrote: How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas? -- 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/-/PGgMdaIbGIsJ. 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. -- 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, Jeevitesh Shekhar Singh.* -- 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] Re: Sorting in O(n)
Hi Shiva. You are right we will be wasting a lot of memory. But still it depends like if we have lot of numbers in the range of 1, n^2 present in the input array then this trade off is not bad. The issue here is we cannot otherwise sort it in O(n) time unless and until we have extra space. So we will have to live with it in this case as i do not think it would be possible in O(n) time otherwise. On Sat, May 5, 2012 at 2:33 PM, shiv narayan narayan.shiv...@gmail.comwrote: @jeevitesh yeah that may be right but it requires extra space as lot of space will be wasted... On May 5, 1:44 pm, Jeevitesh jeeviteshshekha...@gmail.com wrote: Hi all, I am new to this group. My last post was deleted i do not know the reason behind it. I will explain my logic here:- as the range is 1 to n^2 we have a input array like input[n^2]. We can take a auxillary array of size n^2 like aux[n^2]. Scan the input array. For each input input[i] increment by one corresponding aux[input[i]]. After this just iterate through the aux array printing the index aux[i] times. This way we can sort it in O(n) time. On Sat, May 5, 2012 at 2:02 PM, saurabh singh saurab...@gmail.com wrote: After giving some thought,I think even radix sort may not be sufficient. Complexity of radix sort is O(k*n) where k is the number of buckets required to sort the given range. The number of buckets is proportional to the number of bits required to represent the *maximum number in the given range.*For our case the maximum number is O(n^2).Hence *the number of buckets required would be proportional to log(n^2) in the worst case.* Hence the worst case complexity for the given constraints using radix sort would be *O(n*(log n^2)) = O(n*logn).* This is no better than comparision sort.A slight optimization that we can make is to use a higher base which would reduce the number of buckets required but would add the cost of converting each number into the higher base. Somehow I am getting convinced worst case O(n) algorithm may not be possible.Working on the mathematical proof. Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sat, May 5, 2012 at 8:37 AM, saurabh singh saurab...@gmail.com wrote: @cegprakash They are n numbers lying in the range 1 to n^2.Not necessarily sorted. eg 3 4 1 2 5 8 (6 numbers satisfying the conditions given in the problem) Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sat, May 5, 2012 at 5:17 AM, Prakash D cegprak...@gmail.com wrote: The range 1 to n^2 is already sorted On Sat, May 5, 2012 at 12:17 AM, Algobiz deepak.arulkan...@gmail.com wrote: How to sort n numbers in the range of 1 to n^2 in O(n).. Any ideas? -- 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/-/PGgMdaIbGIsJ. 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. -- 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, Jeevitesh Shekhar Singh.* -- 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.
