Re: [algogeeks] Re: MS interview
i would suggest using tires data structure, basically a n-nary tree to store the dictionary. Entire algo is as follows: 1) Create a trie http://en.wikipedia.org/wiki/Trie representing the dictionary. 2) create a aux array for the search key. as count [ key[i] ] ++; 3) Start a recursion from the root of the trie and pick a path if (count [ path ] 0 ) 3rd step ensures that we traverse only those valid paths (ie valid words, this would reduce n! checking of all combinations). On Thu, Aug 23, 2012 at 8:23 PM, Ashish Goel ashg...@gmail.com wrote: yes, that is correct. O(mn) to form multimap and then O(m) to tell all anagram groups Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Thu, Aug 23, 2012 at 5:11 PM, kings dns.bhar...@gmail.com wrote: Dear GC, The efficient data structure in my opinion is Hash Table. 1. For a given word in the dictionary we need to form an anagram dictionary i.e. take a given word sort it which forms the key for the hashtable , then start forming the different anagrams for that word and insert it into the hash table with the corresponding key. 2. Once the hash table is ready for the given word sort it find the key and print all the anagarams i.e. values associated to that key. we will get all the anagrams for a given word. Coming to time complexity... sorting of a word can be done in a O(nlogn). building of anagram will take O(n). hash complexity O(n) worst case. so total time complexity is O(nlogn) for whole execrcise. Thanks Bhargava On Wednesday, 22 August 2012 23:39:02 UTC+5:30, GC wrote: Ques.. Given a m-word dictionary ... and a n-sized word... .. now suggest DS for dictionary such that you can find out all the anagrams of the given word present in dictionary... -- Regards, G C -- 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/-/ySPUSvS0Sh0J. 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.
Re: [algogeeks] Re: Equal probability between 1-7
On Sat, Jul 28, 2012 at 6:58 PM, Megha megha14.2...@gmail.com wrote:
@deepika- can you please explain the approach for this solution ?
--
Sent from my Android phone with K-9 Mail. Please excuse my brevity.
@megha 'rejection sampling' is going to be your search key
deepikaanand swinyanand...@gmail.com wrote:
int rand7()
{
int x = 5*rand5() + rand5(); //enlarge the range from (0 to 5 )to 0
to 24 by multiplying with 5
if(x 20)
return rand7() ;//recursive call
else
return x%7;//this will result in uniform distribution of number
between 0-6
}
--
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.
Re: [algogeeks] Directi Interview Ques
pls discuss about prilims, online coding round too !! regards, Karthikeyan.M On 7/11/12, arumuga abinesh arumugaabin...@gmail.com wrote: http://www.geeksforgeeks.org/archives/17743 Using the above problem we get all possible merges , at each possible merge, we can calculate the sum. On 7/11/12, Mr.B sravanreddy...@gmail.com wrote: I think you missed the question: Its a stable merge. (order of elements in each array should be same) Sorting will destroy the original order. Thanks, Mr.B [Please include complexities and pseudo-code] On Tuesday, 10 July 2012 16:18:04 UTC-4, Akshat wrote: Here you have to first sort both the arrays A and B and merge both the arrays to form the sorted array C -- Akshat Sapra Under Graduation(B.Tech) IIIT-Allahabad(Amethi Campus) *--* sapraaks...@gmail.com akshatsapr...@gmail.com rit20009008@ rit20009...@gmail.comiiita.ac.in -- 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/-/uCRLEzDBWAAJ. 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.
Re: [algogeeks] [Directi] Two most distant element in tree
the path we are looking for is surely between two leaf nodes. start from the root and go to the deepest leaf node.. (dfs/bfs) from that node traverse the entire tree to find the longest path that exists (dfs/bfs) u can keep track of the last node u visit in two variables for every path and update new variables with the optimal path's last visited node .. this way u get the two required nodes On Sun, Mar 25, 2012 at 3:40 PM, Navin Kumar navin.nit...@gmail.com wrote: How to find the two most distant nodes in a binary tree. Its not about calculating the diameter of tree, but the two end nodes in the diameter of the tree. Optimal algorithm expected .. -- 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/-/8pDy6hcBPOUJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] [ DirectI ] Interview question
if i'm not wrong .. we are to repeat this process till no more such pair is found.. rite?? this condition will come only if the given array gets sorted in ascending order .. so the solution is to sort the array O(nlogn).. On Sat, Mar 24, 2012 at 7:31 PM, Navin Kumar navin.nit...@gmail.com wrote: Given an array of integers, for each index i, you have to swap the value at i with the first value smaller than A[ i ] that comes after index i. An efficient solution expected. -- 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/-/an6YzWV-2xsJ. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Floyd Warshall
consider the loop as rep(k,n) rep(i,n) rep(j,n) if(dp[i][k] dp[k][j])dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]) here we take one node (first for loop) and check if the cost of moving from i-j gets reduced on choosing k as intermediate node. On Sat, Mar 3, 2012 at 6:26 PM, saurabh singh saurab...@gmail.com wrote: Its quite trivial..it just if there's a shorter way to reach from index j and k by using any of the nodes as intermediate Saurabh Singh B.Tech (Computer Science) MNNIT blog:geekinessthecoolway.blogspot.com On Sat, Mar 3, 2012 at 5:59 PM, shady sinv...@gmail.com wrote: Can someone explain Flyod Warshall algorithm, i am unable to understand how it works ? even a good link will suffice, i am not getting the intuition behind it. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To post to this group, send email to algogeeks@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: Divisibility by five
@dave
int no=10;
char ans[100];
sprintf(ans,%d,no);
coutans;
On Fri, Jan 20, 2012 at 10:29 PM, Arun Vishwanathan
aaron.nar...@gmail.comwrote:
@dave or anyone: can u pls explain the logic of n3 in dave's solution?
why is it subtracted from n(which is divided by 4 using 2) and what does
n 3 indicate?
On Sat, May 7, 2011 at 9:38 AM, Dave dave_and_da...@juno.com wrote:
@Umer: Do you suppose that you can convert an int into a string
without using division or mod, either directly or indirectly?
Dave
On May 4, 1:12 am, Umer Farooq the.um...@gmail.com wrote:
I'm surprised to see that why are you guys making this problem so
complex.
This problem can be solved in two steps only.
1- Convert the given int into string
2- Check if the last character is 0 or 5. // it yes, then return true
else
return false
for e.g.
125 (last character is 5 ... therefore it is divisible by 5)
120 (last character is 0 ... therefore it is divisible by 5)
111 (last character is 1 ... therefore it is not divisible by 5)
The pseudo-code has been written in my above email.
On Wed, May 4, 2011 at 1:49 AM, Dave dave_and_da...@juno.com wrote:
@anshu: Spoiler alert... I was thinking of something more along the
line
int DivisibleBy5 (int n)
{
n = n 0 ? n : -n;
while( n 0 )
n = (n 2) - (n 3);
return (n == 0);
}
To see that it works, write n as n = 4*a + b, where 0 = b = 3. Then
the iteration replaces n by a - b. Consider (4*a + b) + (a - b), the
sum of two consecutive values of n. This simplifies to 5*a, which is a
multiple of 5. Thus, n is a multiple of 5 before an iteration if and
only if it also is a multiple of 5 afterwards,
It is clearly log n because n is replaced by a number no greater than
n/4 on each iteration.
Examples:
n = 125. The sequence of iterates is 30, 5, 0. Ergo, 125 is a multiple
of 5.
n = 84. The sequence of iterates is 21, 4, -1. Ergo, 84 is not a
multiple of 5.
Dave
On May 3, 3:13 am, anshu anshumishra6...@gmail.com wrote:
algorithm:
if any number(a) is divisible by 5 it can be wriiten as 4*b + b --
this cleary shows the last two bit of a b will be same.
lets understand by an example (35)10 = (100011)2
xx1100
+ xx11
-
100011
now this clearly shows we can calculate the unknowns(x) by
traversing
right to left
code:
int main()
{
int n, m;
cin n;
m = n;
int a, b;
int i=2;
a = (m3)2;
b = (m3);
m = 2;
bool rem = 0,s,r;
while (m3)
{
r = a(1i);
s = r^(m1)^rem;
b = b|(si);
a = a|(s(i+2));
rem = (rs)|(srem)|(rrem) ;
i++;
m = 1;
}
if (a+b == n) cout yes\n;
else cout no\n;
return 0;
}- 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 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.
--
Umer- 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 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.
--
People often say that motivation doesn't last. Well, neither does
bathing - that's why we recommend it daily.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send email to algogeeks@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
Re: [algogeeks] Re: A graph problem
find the size of smallest cycle in the given graph ... tarjan should do the trick.. dfs basically ... :) On Thu, Jan 5, 2012 at 7:02 PM, WgpShashank shashank7andr...@gmail.comwrote: @Saurabh DFS Should Work Here, Start from any room i , visit next room connected to it .. then to this room so on , once you back track you will back to the starting node ,this way you can find out .min.umber of room he need to visit will be 2 times of traversal isn't it ? posting the soln in hurry :), i know may have some bugs , will discuss after some time. Thanks Shashank -- 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/-/El6uttSxuA0J. 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.
