[algogeeks] string
Given a string A, and a string B, and a dictionary, how would you convert A to B in the minimum no of operations, given that: i) All the intermediate words must be from the dictionary ii) An ‘operation’ is defined as: a) Delete any character from a string ex dog → do b) Insert any character into a string ex cat → cart c) Replace any character in the string with another ex cat → cot -- 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: graph
can be done in O(n^2) also
below is a rough pseudocode
initialize visited[v]=0
for every vertex v{
call dfs(v)
check if al visited are 1 or not
if all visited break;
else do visited[v]=0 again.
}
correcf me if i'm missing anything
On Fri, Jul 16, 2010 at 5:38 AM, Gene gene.ress...@gmail.com wrote:
Construct the transitive closure of the graph. You can use Warshall's
algorithm, which is O(v^3) in run time. If any row of the adjacency
matrix is all 1's, the corresponding vertex can reach all others. You
can ignore the diagonal element if you don't care whether vertices are
reachable from themselves (i.e. whether they are contained in a
cycle).
On Jul 12, 1:06 pm, Love-143 lovekesh6mn...@gmail.com wrote:
1.Give an efficient algorithm which takes as input a directed graph G =
(V,E), and determines whether or not there is a vertex s is in V from
which
all other vertices are reachable.?
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
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] a google question
question please...
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Fri, Jul 16, 2010 at 4:43 PM, manish bhatia mb_mani...@yahoo.com wrote:
It doesn't work
A =
92 87 81 72 70 61 53 22 18 17
B =
79 78 74 68 64 62 57 34 29 24
C (GOLD) =
171 170 166 166 165 161 160 160 159 156
D (TEST) =
171 170 166 166 165 159 155 155 146 145
Result: FAILED!
manish...
--
*From:* Jitendra Kushwaha jitendra.th...@gmail.com
*To:* algogeeks@googlegroups.com
*Sent:* Sun, 2 May, 2010 9:13:14 PM
*Subject:* Re: [algogeeks] a google question
Here is a solution of O(n) , taking 4 pointers 2 for each array
#include cstdio
#includeiostream
using namespace std;
#define N 10
int main(void)
{
int arr1[N] = {8,7,4,3,2,1,1,1,1,1};
int arr2[N] = {34,23,21,19,15,13,11,8,4,2};
int *p11,*p12,*p21,*p22;
p11 = p12 = arr1;
p21 = p22 = arr2;
int f1;
f1 = 0;
for(int i=0;iN;i++) {
int ans=0;
int a,b,c,d;
a = *p11 + *p21;
b = *p11 + *p22;
c = *p21 + *p12;
d = *(p11+1) + *(p21+1);
//printf(a=%d b=%d c=%d d=%d\n,a,b,c,d); //debug
if(f1==0)ans = a ,p12++ , p22++ , f1=1;
else if(b = c b = d )ans = b , p22++ ;
else if(c = b c = d )ans = c , p12++ ;
elseans = d , p11++ , p21++ ,printf(4 );
printf(%d\n,ans);
}
}
Regards
Jitendra Kushwaha
Undergradute Student
Computer Science Eng.
MNNIT, Allahabad
--
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.comalgogeeks%2bunsubscr...@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.comalgogeeks%2bunsubscr...@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] string
http://en.wikipedia.org/wiki/Levenshtein_distance Best Regards Ashish Goel Think positive and find fuel in failure +919985813081 +919966006652 On Sun, Jul 18, 2010 at 6:08 PM, Ratnesh Thakur ratneshthaku...@gmail.comwrote: Given a string A, and a string B, and a dictionary, how would you convert A to B in the minimum no of operations, given that: i) All the intermediate words must be from the dictionary ii) An ‘operation’ is defined as: a) Delete any character from a string ex dog → do b) Insert any character into a string ex cat → cart c) Replace any character in the string with another ex cat → cot -- 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.comalgogeeks%2bunsubscr...@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: graph
@jalaj..he has asked for a linear algo
On Sat, Jul 17, 2010 at 12:47 AM, jalaj jaiswal
jalaj.jaiswa...@gmail.comwrote:
can be done in O(n^2) also
below is a rough pseudocode
initialize visited[v]=0
for every vertex v{
call dfs(v)
check if al visited are 1 or not
if all visited break;
else do visited[v]=0 again.
}
correcf me if i'm missing anything
On Fri, Jul 16, 2010 at 5:38 AM, Gene gene.ress...@gmail.com wrote:
Construct the transitive closure of the graph. You can use Warshall's
algorithm, which is O(v^3) in run time. If any row of the adjacency
matrix is all 1's, the corresponding vertex can reach all others. You
can ignore the diagonal element if you don't care whether vertices are
reachable from themselves (i.e. whether they are contained in a
cycle).
On Jul 12, 1:06 pm, Love-143 lovekesh6mn...@gmail.com wrote:
1.Give an efficient algorithm which takes as input a directed graph G =
(V,E), and determines whether or not there is a vertex s is in V from
which
all other vertices are reachable.?
--
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.comalgogeeks%2bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
With Regards,
Jalaj Jaiswal
+919026283397
B.TECH IT
IIIT ALLAHABAD
--
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.comalgogeeks%2bunsubscr...@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: GIven 2 dates, print out the lines in the file between these 2 dates. Also optimize solution because the file may be huge and so dont go line by line.
At the time of logging, the timestamp can be added to a B-tree, with the nodes having the line number(i.e., number of bytes to be skipped from the beginning). At the time of searching, simple logarithmic time search will directly return the line address. On Jul 17, 11:27 pm, vijay auvija...@gmail.com wrote: a file contains lot of log information in the form of DD:MM:YY HOURS: MINUTES:SECOND: random length text GIven 2 dates, print out the lines in the file between these 2 dates. Also optimize solution because the file may be huge and so dont go line by line. -- 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] Adobe Puzzle
Puzzle, A square Island surrounded by bigger square, and in between there is infinite depth water. The distance between them is L. The wooden blocks of L are given. The L length block can't be placed in between to cross it, as it will fall in water (just fitting). How would you cross using these L length blocks. -- 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] Boxes!!!
Given a lot of cuboid boxes with different length, breadth and height. We need to find the maximum subset which can fit into each other. For example: If Box 1 has LBH as 7 8 9 If Box 2 has LBH as 5 6 8 If Box 3 has LBH as 5 8 7 If Box 4 has LBH as 4 4 4 then answer is 1,2,4 A box can fit into another only and only if all dimensions of that is less than the bigger box.Rotation of boxes is not possible. -- 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] Dynamic Programming Problem on Strings
@ashish: AAA is the prefix of the string and it is valid as a prefix and it's only used for strings with length = 6 (where it is a valid prefix) actually only dp[i][j] where i==j counts the number of such strings and otherwise there is no string where i!=j and it that case dp[i][j] counts the number of valid prefixes for string dp[0][0]=1 does satisfy both properties because 0=0 so the number of As Bs are the same the logic behind n/2 is that if the length of the string is n this means that it has n/2 As and n/2 Bs (n must be even) the dp for n=4 doesn't look like that! this is how it looks (i just compiled the code and checked values of dp): 1 0 0 1 1 0 1 2 2 so dp[2][2]=2 which means the number of strings with 2 As and 2 Bs is 2 -- 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] Adobe Puzzle
Use the block of size L, use the diagonal of the block (diagonal would be definitely L ) to fit in between two square islands. Thanks, On Sun, Jul 18, 2010 at 11:38 PM, amit amitjaspal...@gmail.com wrote: Puzzle, A square Island surrounded by bigger square, and in between there is infinite depth water. The distance between them is L. The wooden blocks of L are given. The L length block can't be placed in between to cross it, as it will fall in water (just fitting). How would you cross using these L length blocks. -- 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.comalgogeeks%2bunsubscr...@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] a google question
@Kushwaha
Your programe is wrong.
Try this input:
a[ ] = {30,25,19,16,14};
b[ ] = {20,18,12,10,8};
the right answer should be 50 48 45 43 42
but the program output is 50 48 45 43 37。
2010/5/2 Jitendra Kushwaha jitendra.th...@gmail.com
Here is a solution of O(n) , taking 4 pointers 2 for each array
#include cstdio
#includeiostream
using namespace std;
#define N 10
int main(void)
{
int arr1[N] = {8,7,4,3,2,1,1,1,1,1};
int arr2[N] = {34,23,21,19,15,13,11,8,4,2};
int *p11,*p12,*p21,*p22;
p11 = p12 = arr1;
p21 = p22 = arr2;
int f1;
f1 = 0;
for(int i=0;iN;i++) {
int ans=0;
int a,b,c,d;
a = *p11 + *p21;
b = *p11 + *p22;
c = *p21 + *p12;
d = *(p11+1) + *(p21+1);
//printf(a=%d b=%d c=%d d=%d\n,a,b,c,d); //debug
if(f1==0)ans = a ,p12++ , p22++ , f1=1;
else if(b = c b = d )ans = b , p22++ ;
else if(c = b c = d )ans = c , p12++ ;
elseans = d , p11++ , p21++ ,printf(4 );
printf(%d\n,ans);
}
}
Regards
Jitendra Kushwaha
Undergradute Student
Computer Science Eng.
MNNIT, Allahabad
--
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.comalgogeeks%2bunsubscr...@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.
