Q1) Given a newspaper and a set of ‘l’ words, give an efficient algorithm
to find the ‘l’ words in the newspaper.
Q2) Find the next higher number in set of permutations of a given number.
Q3) Given preorder of a BST, find if each non-leaf node has just one child
or not. To be done in linear
you can use flag[256];
now you just need to check
loop:
flag[str[i]]==0)
{
//swap()
//permute function call
//swap()
flag[str[i]=1;
}
done
On 7/3/12, Nishant Pandey nishant.bits.me...@gmail.com wrote:
1) Find all permutations of a string.
2) Improve it so that
you can use flag[256];
now you just need to check
loop:
if (flag[str[i]]==0)
{
//swap()
//permute function call
//swap()
flag[str[i]=1;
}
done
On 7/4/12, atul anand atul.87fri...@gmail.com wrote:
you can use flag[256];
now you just need to check
loop:
u need inoder traversal as well
On Wed, Jul 4, 2012 at 11:22 AM, Navin Kumar algorithm.i...@gmail.comwrote:
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the web visit
@Vindhya: BST can be reconstructed only by preorder traversal. In case of
binary tree we need two traversal inorder and pre/post order
On Wed, Jul 4, 2012 at 1:07 PM, vindhya chhabra vindhyachha...@gmail.comwrote:
u need inoder traversal as well
On Wed, Jul 4, 2012 at 11:22 AM, Navin Kumar
Serialisation meaning? Numbering the nodes. Any specific order, or as
in level order??
On 7/4/12, Ashish Goel ashg...@gmail.com wrote:
a] How would you serialize a binary tree in a file(improve it)
b] serialization that you have chosen, write a code to reconstruct the tree
Best Regards
Ashish
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
4. One problem: consider
...
a b...
c d...
...
if ab is a prefix, can aba be another prefix, i would assume so. But if
that is true, i am not sure if this program will come to an
Q5 is sorting problem
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 4:13 PM, Ashish Goel ashg...@gmail.com wrote:
1. inverted hasp map
2. not clear
3. VLR, how do you identify end of L and start of R, question incomplete
Q4
vectorString prefix;
prefix[0]=NULL;
prefixCount =1;
for (int i=0;in;i++)
for (int j=0;jn;j++)
for (int k=0; kprefixCount;k++)
{
if (visited[i][j]) continue;
visited[i][j] = true;
String s=prefix[k]+a[i][j];
if (isWord(s) { printWord(s);
my understanding is to either write the level order traversal noting
parent, child relation or write the adjacency list into a file where we
store the edges
Best Regards
Ashish Goel
Think positive and find fuel in failure
+919985813081
+919966006652
On Wed, Jul 4, 2012 at 3:58 PM, adarsh kumar
Consider trees:
1 3
2 3 2
1
pre order traversal is same still (1 , 2 ,3) even though ist tree doesn't
satisfy the criteria . So I don't think it can be
1. For first question trie of given word will be best option.
Space complexity O(total length of words) (worst case)
Time complexity O(T) . T length of input text (Newspaper)
2. consider it to be a 4 digit number ABCD . Find maximum Most
significant digit say it is C , and out of these
we can serialize the binary tree using preorder traversal and marking NULL
pointer as '#'.
source:
http://www.leetcode.com/2010/09/serializationdeserialization-of-binary.html
On Wed, Jul 4, 2012 at 4:21 PM, Ashish Goel ashg...@gmail.com wrote:
my understanding is to either write the level
For question 5.
Even this doesn't seems right
Consider this scenario
Match b/w Winner
a vs b a
a vs c c
b vs c b
What will be order ?? acb or bca
On Wed, Jul 4, 2012 at 5:38 PM, Bhupendra Dubey
Vindhya - Navin is right because in case of BST, if you sort the preorder
array you will get inorder array. This means you already have information
about the inorder, if you given preorder/postorder/levelorder.
--
You received this message because you are subscribed to the Google Groups
bool checkTree(Tree node)
{
if(node[right]==NULLnode[left]==NULL)
return true;
if(node[right]==NULLnode[left]!=NULL||node[left]==NULLnode[right]!=NULL)
return false;
else
return checkTree(node[right])checkTree(node[left]);
}
i think this algo can solve problem just traverse the node and keep eye
int treeMaxHeight(int index)
{
if(tree[index]==NULL)
return 0;
else
{
return 1+max(treeHeight(2*index),treeHeight(2*index+1));
}
}
int treeMinHeight(int index)
{
if(tree[index]==NULL)
return 0;
else
{
return 1+min(treeHeight(2*index),treeHeight(2*index+1));
}
}
1
2 3 is not a BST and its pre-order traversal is 1 2 3, pre
order of other is 3 2 1 .
On Wed, Jul 4, 2012 at 5:17 PM, Bhupendra Dubey bhupendra@gmail.comwrote:
Consider trees:
1 3
2 3
the code works fine only in case of duplicates , but if we consider
string to be non duplicates like say :abc then all permutation cant be
obtainned .
On Wed, Jul 4, 2012 at 12:31 PM, atul anand atul.87fri...@gmail.com wrote:
you can use flag[256];
now you just need to check
loop:
if
^ Thank you! Mind discussing the algorithm please?
On Wed, Jul 4, 2012 at 7:06 PM, deepikaanand swinyanand...@gmail.comwrote:
code :-
http://ideone.com/O5yuo
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To post to this group, send
http://stackoverflow.com/questions/1900197/generating-variations-without-repetitions-permutations-in-java/
On Wed, Jul 4, 2012 at 8:16 PM, Nishant Pandey nishant.bits.me...@gmail.com
wrote:
the code works fine only in case of duplicates , but if we consider
string to be non duplicates like
Any efficient algorithm to find intersection of two linked lists.Example:
Linked List 1) 1 - 2 - 3 - 4 - 5 - 6
Linked List 2) 3 - 4 - 5
Intersection 4 - 5 - 6
--
You received this message because you are subscribed to the Google Groups
Algorithm Geeks group.
To view this discussion on the
Suppose a file.txt contains : 50 40 30 # # 5 # 10 # #
i want to fetch only integers. How should i fetch it. I tried with fgetc
and fscanf but it was too complicated.
My approach: fetched one word at a time and put it into separate string and
then i converted that string to integer(if each
Fetch a character.
if isdigit( current_character )
flag =1
else if current_character is any character except space
while current_char is not space
current_char_position ++
On Wed, Jul 4, 2012 at 10:44 PM, Navin Kumar algorithm.i...@gmail.comwrote:
Suppose a file.txt contains
Please ignore the last post
Fetch a character.
if isdigit( current_character )
add it to temp string
flag =1
else if current_character is any character except space
flag = 0
while current_char is not space
current_char_position ++
else if current_char is space
it was 4 - 5, not 4 - 5 - 6
On Wed, Jul 4, 2012 at 10:41 PM, Abhi abhi120...@gmail.com wrote:
Any efficient algorithm to find intersection of two linked lists.Example:
Linked List 1) 1 - 2 - 3 - 4 - 5 - 6
Linked List 2) 3 - 4 - 5
Intersection 4 - 5 - 6
--
You received this message
3 - 4 - 5, sorry for that silly mistakes
On Wed, Jul 4, 2012 at 10:54 PM, Abhishek Sharma abhi120...@gmail.comwrote:
it was 4 - 5, not 4 - 5 - 6
On Wed, Jul 4, 2012 at 10:41 PM, Abhi abhi120...@gmail.com wrote:
Any efficient algorithm to find intersection of two linked lists.Example:
reading from a file is bottle neck so better to read number of line into a
buffer then read it char by char or word by word depend on algo...
On Wed, Jul 4, 2012 at 10:44 PM, Navin Kumar algorithm.i...@gmail.comwrote:
Suppose a file.txt contains : 50 40 30 # # 5 # 10 # #
i want to fetch only
Sorry i typed wrongly
tree is
2
1 3
preorder traversal is 123 and same for other tree as well. Please check !
On Wed, Jul 4, 2012 at 5:24 PM, a g ag20071...@gmail.com wrote:
1
2 3 is not a BST and its pre-order traversal is 1 2 3, pre
order of
thanks all
On Wed, Jul 4, 2012 at 10:57 PM, Navin Gupta navin.nit...@gmail.com wrote:
Given a pre-order traversal, we can sort it to get the inorde traversal.
Sorting the preorder is O( NLogN ).
Now as we know the ordering of elements is
Preorder - Root - Left Child - Right Child
@Navin
I dont think der is any need to sort the preorder traversal
given ...it will cost u more
as sorting take O(n log n ) and recursion alone will take O(n^2)
{mentioned in step 4 }
sO the overall complexity will be the sum of two..+ space of O(n) //to
store inorder traversal
--
You received
get the size of both the linked list say d1,d2 ;
get their diff like df=abs(d1-d2);
now take 2 pointers both poiting to the start of both the linked list .
go to bigger list now move this pointer until both the distance becomes
equal .
at this point we have one pointer from smaller list pointing
32 matches
Mail list logo
