Re: [algogeeks] MS interview question
1. Make a trie of all dictionary words. 2.then run a loop for all characters of string 3.suppose start from I ,as I is a word in dictionary,word found then increment counter 4.Now counter comes to X,no word found 5.Now it comes to A,two word could start from A(A and AM) now run this loop till end of string or till you didn't find M if find M,then word is AM ,otherwise it's A.then increment counter for outer loop 6.counter comes to F,no word found 7.G,M,J so on(No word found) 8.then A, again inner loop would run till the end of string length or till u didn't find M. In this way I think we could find all valid words in dictionary time complexity would be O(n^3) n for outer loop,n for inner loop and n for searching in trie On Sun, Apr 14, 2013 at 12:41 PM, rahul sharma rahul23111...@gmail.comwrote: Suppose you are given a string IAMABOY and a dictionary then divide it into I AM A BOY if it is possible to break form as many dictionary words from a string giveM able to solve it..but how if we are given a string like IXAFGMJAHBDSOXDY. how can we form I AM A BOY..will be done in Opower(2,n)..for every character we consider it and not and form 2 ways...plz anyone shre the code for this approach...if the word is not a cotiguous subarray.. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out. -- You received this message because you are subscribed to the Google Groups Algorithm Geeks group. To unsubscribe from this group and stop receiving emails from it, send an email to algogeeks+unsubscr...@googlegroups.com. For more options, visit https://groups.google.com/groups/opt_out.
Re: [algogeeks] Question asked in Amazon Online Test
I think no need to reverse the string,following program is giving me
correct o/p.Although right now this program will work only for binary
operator,for unary add extra condition
main()
{
char str[100];
int i=0;
int digit;
scanf(%s,str);
while(str[i])
{
if(isdigit(str[i]))
{
printf(%c,str[i]);
if(isdigit(str[i+1]))
{
printf(%c,str[i+1]);
digit=popstack();
printf(%c,digit);
i++;
}
}
else if(str[i]=33 str[i]=47)
{
pushstack(str[i]);
}
i++;
}
while(top!=0)
{
digit=popstack();
printf(%c,digit);
}
}
On Sat, Jun 30, 2012 at 11:50 AM, himanshu kansal
himanshukansal...@gmail.com wrote:
i think this algo will do...
reverse the given prefix expression
while(!nd of input)
{ if it is operand
push in a stack
if its an operator
{ op1=pop(stack);
op2=pop(stack);
push (op1 op2 operator) on to stack;
}
}
On Sat, Jun 30, 2012 at 1:56 AM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
example
-+53+2/36
step 1: 63/2+35+-
step 2: 36/2+53+-
On Sat, Jun 30, 2012 at 1:55 AM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
reverse the prefix notation and then reverse each continuous occurence
of operands
On Sat, Jun 30, 2012 at 12:50 AM, Abhishek Sharma
abhi120...@gmail.comwrote:
convert prefix to infix,then convert infix to postfix.Now, to convert
prefix to infix, push numbers in one stack and operators in other.Then use
thishttp://www.velocityreviews.com/forums/t445633-prefix-to-infix-conversion.html
algo
to perform this.Then do the same for infix to postfix.It works with simple
operators,but difficult to implement with parenthesis.
On Sat, Jun 30, 2012 at 12:21 AM, rahul ranjan
rahul.ranjan...@gmail.com wrote:
oh bhai mere. kewal preorder use karke kaise tree bana dega???
On Fri, Jun 29, 2012 at 11:23 PM, amrit harry dabbcomput...@gmail.com
wrote:
@bhaskar ur algo fails on this case (5+3)-(2+(3/6))
-+53+2/36
63/2+35-+
showing that 6/3 but actually it is 3/6
so i think it could be done by folowing algo
make a binary tree of given expression in O(n) then do postorder
traversal take O(n) so problem can be solved in O(n). and take O(2*n+1)
space
On Fri, Jun 29, 2012 at 9:13 PM, Bhaskar Kushwaha
bhaskar.kushwaha2...@gmail.com wrote:
I think just reversing the prefix notation converts it to postfix
notation
On Fri, Jun 29, 2012 at 7:46 PM, Gobind Kumar Hembram
gobind@gmail.com wrote:
Given an integer expression in a prefix format (i.e. the operator
precedes the number it is operating on) , print the expression in
the
post fix format .
Example: If the integer expression is in the prefix format is
*+56-78,
the postfix format expression is 56+78-*. Both of these
correspond to the expression (5+6)*(7-8).
--
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,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
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 Regards
Amritpal 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.
--
Abhishek Sharma
Under-Graduate Student,
PEC University of Technology
--
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,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
regards,
Bhaskar Kushwaha
Student
Final year
CSE
M.N.N.I.T. Allahabad
--
You received this message
Re: [algogeeks] Re: Directi question-centre of the tree
I think this algorithm is used for calculating poset in graph. On Sat, Jun 16, 2012 at 3:04 AM, Hemesh Singh hemesh.mn...@gmail.comwrote: + 1 for DK's solution. Is that a standard algorithm coz I feel like I have heard it somewhere ?? On Mon, Aug 8, 2011 at 1:37 AM, DK divyekap...@gmail.com wrote: @KK: DFS and BFS are O(N) and Floyd Warshall is O(N^3). Could you please state how you can use the traversals directly to get the center? (And prove your correctness too?) The solution given by Wladimir ( expanded upon by me) is O(N) and uses (somewhat) the inverse of a BFS as a traversal. -- DK http://twitter.com/divyekapoor http://gplus.to/divyekapoor http://www.divye.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/-/HnMOZtOrkqwJ. 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. -- Hemesh 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.
Re: [algogeeks] Re: Largest span of Increasing Pair in an array
One Solution for Largest span in array,I have checked it on many
inputs,according to me its working fine
void Large_Span(int * arr,int num_elem)
{
int j=1,k=0,i,prev_k=0;
for(i=1;inum_elem;i++)
{
if(arr[i]arr[i-1])
{
if((arr[j]-arr[k])(arr[i]-arr[i-1]))
{
if(jarr[i] k=arr[i-1])
{
j=i;
}
else if((jarr[i] karr[i-1])||(jarr[i] karr[i-1]))
{
j=i;
k=i-1;
}
}
else if(arr[k]arr[i-1])
{
if(kj)
{
prev_k=k;
k=i-1;
}
}
else if(arr[j]arr[i])
j=i;
}
else
{
if(arr[k]arr[i])
{
if(ij)
{
prev_k=k;
k=i;
}
else
k=i;
}
}
}
if(kj)
{
k=prev_k;
}
printf(arr[j]=%d,arr[k]=%d,j=%d,k=%d,arr[j],arr[k],j,k);
}
On Mon, Mar 22, 2010 at 8:28 AM, Manish mannishmaheshw...@gmail.com wrote:
This does not look like a solution for the posted problem.
This fails the test case {2, 7, 6, 0, 100}, where the answer should
have been 4, for k=0 and j=4.
Manish
On Mar 20, 1:49 pm, saurabh gupta sgup...@gmail.com wrote:
This may not be the optimal solution to
Given an array of integers A[N], find the maximum value of (j-k) such
that A[k] = A[j] jk.
I am looking for a solution with time complexity better than O(N^2).
this was in response to
how u can solve it in o(n)
and
how to solve this in the claimed O(N) time.
On Sat, Mar 20, 2010 at 9:14 PM, Ralph Boland rpbol...@gmail.com
wrote:
On Mar 15, 10:07 am, saurabh gupta sgup...@gmail.com wrote:
while you scan the array
maintain four indices plus two lengths
two indices and a length mark one sub-array - start,end, length
each such sub-array indicates a non-decreasing sequence,
call them S1 and S2.
while one scans, S2 keeps track of incoming elements (curr sequence)
S1 keeps track of the maximum length (along with indices) so far
(prev
sequence)
as one encounters an element which is less than the previous element,
this marks the end of S2,
S1 replaces S2 if len S2 len S1 else S2 starts afresh from this new
element.
In the end if len S2 len S1 answer = S2
else answer = S1.
PS: In the beginning and till one encounters a smaller element than
the
prev one for the first time, S1 = S2
I agree that this is a nice algorthithm that solves the
largest non decreasing sequence problem.
However, I don't agree that this solves the problem
originally posted.
Regards,
Ralph Boland
--
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
algogeeks%2bunsubscr...@googlegroups.comalgogeeks%252bunsubscr...@googlegroups.com
.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
--
Man goes to doctor. Says he's depressed. Says life seems harsh and cruel.
Says he feels all alone in a threatening world where what lies ahead is
vague and uncertain. Doctor says Treatment is simple. Great clown
Pagliacci is in town tonight. Go and see him. That should pick you up.
Man
bursts into tears. Says But, doctor...I am Pagliacci.
--
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.
