So finally what will be the solution?
Harshal's solution doesn't print the characters in the order of
appearance in the orignal array as nishant righly pointed out.
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
anonymous see this http://ideone.com/TuNbS
Can anyone tell me why gcc complier giving this warning
prog.c:8: warning: implicit declaration of function ‘strlen’
On 6/26/11, anonymous procrastination opamp1...@gmail.com wrote:
So finally what will be the solution?
Harshal's solution doesn't print
use
#includestring.h instead of #includestrings.h
--
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
this will need two passes
first pass creates the hash map of char and count
second pass walk over the the string again, refer hash map to print that
many chars, remove this char from hash once printed and move on untill the
complete string is covered or hashmap size is 0
Best Regards
Ashish
Harshal's solution can be modified to make it worth with just 1 pass
over the input string.
What we need is an additional link pointer for each entry in the
auxillary array.
Additionally, we need current and start pointers which will be
null to start with.
Now, for every character in the input
ya i needed the same thing!
On Wed, Jun 22, 2011 at 3:04 PM, saurabh singh saurab...@gmail.com wrote:
Without the ascii count table as harshal has used above,is it possible to
do the problem in o(n) time?
On Wed, Jun 22, 2011 at 2:57 PM, Harshal hc4...@gmail.com wrote:
@ross: ya,
oh...an array of constant length signify's constant memorywhy dint i see
that...thanks guys!!!
regards
---sriji!!
On Thu, Jun 23, 2011 at 6:35 PM, Sriganesh Krishnan 2448...@gmail.comwrote:
ya i needed the same thing!
On Wed, Jun 22, 2011 at 3:04 PM, saurabh singh
sorry .. didnt see the question properly ...
and yes binary tree will not be a good option...
On Thu, Jun 23, 2011 at 6:39 PM, Sriganesh Krishnan 2448...@gmail.comwrote:
oh...an array of constant length signify's constant memorywhy dint i
see that...thanks guys!!!
regards
---sriji!!
@Harshal,
Even if you use a buffer of size 256 it is still O(1), because 256 is
a constant invariant of n...
Ur solution is correct!
On Jun 22, 10:24 am, Harshal hc4...@gmail.com wrote:
ignore above solution. My bad, did'nt see O(1) space constraint!!
On Wed, Jun 22, 2011 at 10:53 AM,
@ross: ya, don't know what i was thinking.!!
On Wed, Jun 22, 2011 at 2:33 PM, ross jagadish1...@gmail.com wrote:
@Harshal,
Even if you use a buffer of size 256 it is still O(1), because 256 is
a constant invariant of n...
Ur solution is correct!
On Jun 22, 10:24 am, Harshal
Without the ascii count table as harshal has used above,is it possible to do
the problem in o(n) time?
On Wed, Jun 22, 2011 at 2:57 PM, Harshal hc4...@gmail.com wrote:
@ross: ya, don't know what i was thinking.!!
On Wed, Jun 22, 2011 at 2:33 PM, ross jagadish1...@gmail.com wrote:
@Harshal,
No. This is equivalent to a sort with comparisons based on index of first
occurrence in the input string. Any comparative algorithm is O(n log n) and a
non comparative algorithm can be O(n) only by using counting or radix sorting
etc.
--
DK
http://twitter.com/divyekapoor
http://www.divye.in
No. This is equivalent to a sort with comparisons based on index of first
occurrence in the input string. Any comparative algorithm is O(n log n) and a
non comparative algorithm can be O(n) only by using counting or radix sorting
etc.
--
DK
http://twitter.com/divyekapoor
http://www.divye.in
what if we create a binary tree with root as the first element of the string
and if the next character is equal then place it to left else place it to
right. Similar comparison will be done while inserting all the other nodes
too .
after that if InOrder traversal is performed.. it would give us
No, it will not work. We don't have to print all the characters in sorted
order.
On Thu, Jun 23, 2011 at 12:19 AM, snehi jain snehijai...@gmail.com wrote:
what if we create a binary tree with root as the first element of the
string and if the next character is equal then place it to left else
how come its printing in sorted ... i didn't get it...
On Thu, Jun 23, 2011 at 12:27 AM, oppilas . jatka.oppimi...@gmail.comwrote:
No, it will not work. We don't have to print all the characters in sorted
order.
On Thu, Jun 23, 2011 at 12:19 AM, snehi jain snehijai...@gmail.comwrote:
what
May be I didn't understood your logic.
According to original question for
I/P kapilra
O/P --kaapilr..
Now,
-what if we create a binary tree with root as the first element of the
string and if the next character is equal then place it to left else place
it to right. Similar comparison will be
the binary tree for the above example will be
k(1)
\
a(2)
/ \
(7) a p(3)
\
i(4)
\
l(5)
\
@snehi .. your solution does not come upto the O(n) as for n elements of
string it will take O(lg n) for each , so a total of O ( n * lg n )
Otherwise a better variation to Solution is taking a count member in each
node and incrementing it when another occurrence is made of that character.
@Harshal: I think ur code will print the input string in a sorted order.
@Snehi: Ur tree will never be balanced. and in worst case scenario there
will be only right child.so in that case generation of binary tree may go
upto O(n*n).
P.S.: correct me if i am wrong.
On Wed, Jun 22, 2011 at 1:50 PM,
@ sunny agrawal : I misinterpreted the question .. but im not clear about
how you define interleaving of two strings .. Should the two strings be
mixed up at constant intervals or they can be mixed up anywhere .. and
should the ordering of the characters in the original strings be preserved
while
two strings can be mixed up anywhere .. and yes the ordering of the
characters in the original strings must be preserved while constructing the
third string ??
On Fri, May 27, 2011 at 1:04 PM, Senthil S senthil2...@gmail.com wrote:
@ sunny agrawal : I misinterpreted the question .. but im not
Can be solved in this way also :
#include iostream
#include cstring
using namespace std;
string a, b, c;
int memo[51][51][51];
int interleave(int ai, int bi, int ci)
{
int r1, r2;
r1 = r2 = 0;
if ( ai == a.size() bi == b.size() ci == c.size() ) {
return 1;
Can it be done this way ..Take count of each alphabet for all the three
strings and store separately.. Then for each alphabet in the third string,
check if its count is equal to the sum of the counts of the corresponding
alphabet in the first two strings .. If the counts match for all alphabets
@senthil
nopes, it will not work
eg.
S3 = cba
S1 = a
S2 = bc
count matches but not interleaved
On Thu, May 26, 2011 at 2:43 PM, Senthil S senthil2...@gmail.com wrote:
Can it be done this way ..Take count of each alphabet for all the three
strings and store separately.. Then for each alphabet
Gys, this problem can b esolved using dynamic programming in o n^2.l
recursive/iterative approach wont work.
Regards
Saurabh
On Thu, May 26, 2011 at 4:41 PM, sunny agrawal sunny816.i...@gmail.comwrote:
@senthil
nopes, it will not work
eg.
S3 = cba
S1 = a
S2 = bc
count matches but not
But checking the count is a good first step. If the count doesn't
match the result is false. If the count does match, you need to check
further. I found that my test set ran 10x faster if I checked the
count first.
Don
On May 26, 6:11 am, sunny agrawal sunny816.i...@gmail.com wrote:
@senthil
This is the same algorithm as my previous solution. Both produce the
correct result, but this one does not have tail recursion, so it will
run faster.
bool interleaved2(char *s1, char *s2, char *s3)
{
while(1)
{
if (!s1[0] !s2[0] !s3[0]) return true;
if (s1[0] == s3[0])
{
A Recursive solution:
int interleaved(char *s1, char *s2, char *s3) {
if (s1 == null s2== null s3==null) return 1;
if (s3==null) return 0;
if (s1 != null *s1 == *s3) return interleaved(s1+1,s2,s3+1);
else if (s2 != null *s2 == *s3) return interleaved(s1, s2+1,s3+1);
There are some things which could be done to make the program run
faster in some cases.
For example, either version of my solution above will take a very long
time to determine that these inputs are not interleaved:
s1 = aa
s2 =
Your iterative solution does not work in cases where both s1 and s2
have the next character in s3, but only choosing the s2 character next
will result in correct interleaving.
s1 = ab
s2 = axb
s3 = axabb
Your iterative solution will say that these are not interleaved, but
they really are.
Don
Even my recursive solution will not work. :). Nice catch.!!.
int interleaved(char *s1, char *s2, char *s3) {
if (s1 == null s2== null s3==null) return 1;
if (s3==null) return 0;
if (s1 != null *s1 == *s3 s2 != null *s2 == *s3) return
interleaved(s1+1,s2,s3+1) || return
bool interleaved(char *s1, char *s2, char *s3)
{
return (!*s1 !*s2 !*s3) || // Base case, all strings are
empty
(*s1 (*s1 == *s3) interleaved(s1+1,s2,s3+1)) || // First
character of s1 is next in s3
(*s2 (*s2 == *s3) interleaved(s1,s2+1,s3+1));// First
character of s2 is next in
bool interleaved(char *s1, char *s2, char *s3)
{
// Base case, all strings are empty
return (!s1[0] !s2[0] !s3[0]) ||
// First character of s1 is next in s3
(s1[0] (s1[0] == s3[0]) interleaved(s1+1,s2,s3+1)) ||
// First character of s2 is next in s3
(s2[0] (s2[0] == s3[0])
http://tech-queries.blogspot.com/2010/12/finding-minimum-window-in-array-which.html
just use words in place of chars...
Regards,
Akash Agrawal
http://tech-queries.blogspot.com/
On Fri, Dec 31, 2010 at 11:00 AM, Davin dkthar...@googlemail.com wrote:
Find the area with less distance between
Find the area with less distance between words. Distance is measured
words count in between two words.
On Dec 30, 4:08 pm, 周翔 csepark...@gmail.com wrote:
Distance is measured on number of words. what is your meaning ? can you
explain it?
2010/12/29 Davin dkthar...@googlemail.com
try it by longest common sequence.
then interchange values .
then delete and insert or watever..
--
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,
cost = min (E(i-1, j ) ,E(i , j-i) , E(i-1,j-1) + diff(i,j))
where diff(i,j) = 0 if( a[i] == b[j])
= 1 otherwise
and E(0, i) = i and E(j,0) = j
On Tue, Jul 20, 2010 at 2:10 PM, Ashutosh Shukla 04aashut...@gmail.comwrote:
try it by longest common sequence.
then
http://codepad.org/QSaNaQlH
On Mon, Jul 19, 2010 at 10:29 PM, Anand anandut2...@gmail.com wrote:
Given two text strings A of length n and B of length m, you want to
transform A into B with a minimum number of operations of the following
types: delete a character from A, insert a character
39 matches
Mail list logo
