Follow up on Catalon Nubmer...
On Fri, Jul 30, 2010 at 10:44 AM, Amit Jaspal wrote:
> n is clearly a number lets say 3 then BST's with 1,2,3 values as key are to
> be calculated
>
>
> On Fri, Jul 30, 2010 at 9:08 AM, Apoorve Mohan wrote:
>
>> @AMIT: what does "n" represents?
>>
>>
>> On Fri, Jul
A simple queue implementation will do.
-Regards
Amit Agarwal
blog.amitagrwal.com
On Fri, Jul 30, 2010 at 9:22 AM, Priyanka Chatterjee wrote:
>
>
> On 30 July 2010 02:59, Priyanka Chatterjee wrote:
>
>> Algo: 1. find height of tree
>> 2. do level order traversal
>> i> at e
n is clearly a number lets say 3 then BST's with 1,2,3 values as key are to
be calculated
On Fri, Jul 30, 2010 at 9:08 AM, Apoorve Mohan wrote:
> @AMIT: what does "n" represents?
>
>
> On Fri, Jul 30, 2010 at 5:46 AM, sharad kumar wrote:
>
>> @amit is it BST or binary tree??cos BST is unique rite
There few errors in your code rest is fine.I have updated in line
On Fri, Jul 30, 2010 at 9:22 AM, Priyanka Chatterjee wrote:
>
>
> On 30 July 2010 02:59, Priyanka Chatterjee wrote:
>
>> Algo: 1. find height of tree
>> 2. do level order traversal
>> i> at each level store th
On 30 July 2010 02:59, Priyanka Chatterjee wrote:
> Algo: 1. find height of tree
> 2. do level order traversal
> i> at each level store the address of each tree node in the
> data part of a linked node and form linked list of the nodes
> ii> store the header of
@AMIT: what does "n" represents?
On Fri, Jul 30, 2010 at 5:46 AM, sharad kumar wrote:
> @amit is it BST or binary tree??cos BST is unique rite???binary tree meas
> use catalan numbers 2nCn/(n+1)!
>
>
>
> On Thu, Jul 29, 2010 at 9:56 PM, amit wrote:
>
>> Given the numbers from 1 to n, write an al
If space is not a restriction-
Build a B-tree.
1. Have a dummy root.
2. At level one- Numbers divisible by 1. ie. (1-9).
3. At level 2- numbers made after adding a digit to numbers at level 1. e.g.
number 7 at level will have children- (70,72,74,76,78). and so on..
4. Do the same at each level. Le
I have formulated a solution, not strictly of O(n), but I guess it's close.
===
1. for(int k=0;k wrote:
> I guess your solution would also be proved incorrect with the following,
>
> Numbers in bold are the two arrays.
>
> 125122 120 110 104 103 102 101
> 100
@amit is it BST or binary tree??cos BST is unique rite???binary tree meas
use catalan numbers 2nCn/(n+1)!
On Thu, Jul 29, 2010 at 9:56 PM, amit wrote:
> Given the numbers from 1 to n, write an algorithm to find how many
> distinct binary search trees can be formed.. eg n=4, no of distinct
> bs
@ srikant , trhe structure of binary tree have to be modified for this
solution right..as nodes may have 3 links
On Fri, Jul 30, 2010 at 12:03 AM, ashish agarwal <
ashish.cooldude...@gmail.com> wrote:
> I think use bfs ...
>
> On Thu, Jul 29, 2010 at 11:26 AM, irfan naseef wrote:
>
>>
>>
>> On Th
Yeah use BFS, push the nodes on a stack and make them point to each
other.
How they point depends on the question, which needs clarification.
Should they ALL be connected to each other as in A to B and A to C and
B to C or
just A to B and B to C. Either way, the above approach should work
fine.
-
Algo: 1. find height of tree
2. do level order traversal
i> at each level store the address of each tree node in the
data part of a linked node and form linked list of the nodes
ii> store the header of a linked list at a certain level in an
array
3. retur
Use a recursive functionthis below function will add up all nodes at the
same level.
void Traverse(Node n,int level, LinkedList list){
if(n==null) return;
if(n>list.size())
list.add(n.value);
else
list.set(list.get(level)+n.value);
Traverse(n.left,level+1,list);
An algorithm to print all the 10-digit nos such that first 1 digit is
divisible by 1, first 2 digits by 2, first 3 digits by 3 and so
on...first 9 digits by 9. I think the tenth digit can be anything from
0 to 9.
--
You received this message because you are subscribed to the Google Groups
"Algor
BFS
On Thu, Jul 29, 2010 at 11:56 PM, irfan naseef wrote:
>
>
> On Thu, Jul 29, 2010 at 11:35 PM, ashish agarwal <
> ashish.cooldude...@gmail.com> wrote:
>
>> please explain q ..i didnt understand
>>
>>
>> On Thu, Jul 29, 2010 at 11:01 AM, irfan wrote:
>>
>>> I attended Amazon placement test tod
Given the numbers from 1 to n, write an algorithm to find how many
distinct binary search trees can be formed.. eg n=4, no of distinct
bst's are 14. ??
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algog
are the nodes having an extra pointer for sibling??
--
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...@googlegr
Yeah, you can do it either way. You can even add a dummy element
instead of checking for empty and popping each time.
But basically yeah, that's how I'd do it.
Manjunath put it in a nice concise way.
On Jul 29, 3:42 am, Sathaiah Dontula wrote:
> @Minotauraus
>
> I feel Queue gives more picture.
Use suffix trie.
On 30 July 2010 00:50, Sony Jose wrote:
> hi Minotauruas,
>
>
> "For each node in the tree query the hash table. If there is a
> collision (value exists) get point to that node from the table
> and traverse the subtree, until you reach leaf nodes or find that the
> subtrees are
hi Minotauruas,
"For each node in the tree query the hash table. If there is a
collision (value exists) get point to that node from the table
and traverse the subtree, until you reach leaf nodes or find that the
subtrees are not the same."
can you explain this above statement in an bit more clear
I think use bfs ...
On Thu, Jul 29, 2010 at 11:26 AM, irfan naseef wrote:
>
>
> On Thu, Jul 29, 2010 at 11:35 PM, ashish agarwal <
> ashish.cooldude...@gmail.com> wrote:
>
>> please explain q ..i didnt understand
>>
>>
>> On Thu, Jul 29, 2010 at 11:01 AM, irfan wrote:
>>
>>> I attended Amazon pl
solution is straight forward
identifying nodes at different levels
and making connection between them using a FLAG node
On Thu, Jul 29, 2010 at 11:26 AM, irfan naseef wrote:
>
>
> On Thu, Jul 29, 2010 at 11:35 PM, ashish agarwal <
> ashish.cooldude...@gmail.com> wrote:
>
>> please explain q ..i d
On Thu, Jul 29, 2010 at 11:35 PM, ashish agarwal <
ashish.cooldude...@gmail.com> wrote:
> please explain q ..i didnt understand
>
>
> On Thu, Jul 29, 2010 at 11:01 AM, irfan wrote:
>
>> I attended Amazon placement test today . There was a question where i
>> got confused.It is as follows.
>>
>> G
please explain q ..i didnt understand
On Thu, Jul 29, 2010 at 11:01 AM, irfan wrote:
> I attended Amazon placement test today . There was a question where i
> got confused.It is as follows.
>
> Give an algorithm to connect all nodes in one level of a binary tree .
>
> 5
> 5
>
I attended Amazon placement test today . There was a question where i
got confused.It is as follows.
Give an algorithm to connect all nodes in one level of a binary tree .
5
5
/
\ / \
8 2 ---
void levelordertraversal(struct node* root,height)
{
int i=0;
for(i=1;i<=height(root);i++
printlevel(root,i);
}
void printlevel(struct node *root, level)
{
if(root == null)
return;
else if(level==1)
printf("%d",root->data);
else if(level>1)
do the level order traversal of the binary tree and keep the count of the
stack...thats the width of the tree..
--
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 fr
we can find the sum of all elements i.e, n(n+1)/2.
and then compute the sum of all squares of elements..i.e (n(n+1)(2n+1))/6
now u have two equations..u can now compute both the missing element and the
duplicate..
--
You received this message because you are subscribed to the Google Groups
"Algo
Can use a map to read the array and do map[arr[i]]=1. If there's a 1
already present print arr[i]. This method solves the problem in O(n)
time and O(n) space complexity.
On Jul 29, 2:56 am, Minotauraus wrote:
> If numbers are consecutive you can do better. Calculate (n-1)(n-2)/2 -
> sum of all el
@above: but this may lead to overflow of the integer as you don't know what
is "n".
if the value of n is large then you can;t do this
On Thu, Jul 29, 2010 at 3:26 AM, Minotauraus wrote:
> If numbers are consecutive you can do better. Calculate (n-1)(n-2)/2 -
> sum of all ele
@Minotauraus
I feel Queue gives more picture.
Thanks,
Sathaiah Dontula
On Thu, Jul 29, 2010 at 3:53 AM, Minotauraus wrote:
> Width of a Tree = maximum number of nodes at the same level.
> Example:
>a
> bc
> d e
#include
int main()
{
int a[] = { 10,5,6,8,1,10,8,7,9,9}; /* Assuming a[i] is in {i=1,N} */
int N = 10,index,j;
int i;
for (i = 0; i < N; i++) {
index = a[i] % N;
if (a[index] > N) {
printf("Duplicate number is %d\n",a[i]%N);
I think we can assume a perfect hashing to exist. [Please correct me if I am
wrong]
Implementing one, is a different issue. :))
Other than hashing, we can use BST or Heap. ~ O(klog(n))
On Thu, Jul 29, 2010 at 1:07 PM, sourav wrote:
> @Shiv
>
> Collision is itself a wel known issue in hashing
> printf("%d\n",printf("%d\n",printf("%d",i))); return 0;
12--3
remove the new line '\n' character from 2nd printf it will print 111 because
printf function returns number of character displayed. New line is
considered as one chracter.
In original questions 2nd
printf returns the number of character it prints so output is ok
it is 111
see this o/p you will understand
#includeint main(){int
i=1;printf("%d\n",printf("%d\n",printf("%d",i))); return 0;}
http://codepad.org/gLGMDdoU
--
You received this message because you are subscribed to the Google Group
every printf statement wll return how many number of parameter/variable
print r printed so 2nd nested wll print number 1 n remaing two printf
statement wll print number of parameters are printed so total three 1's
.:)
-- Prashant Kulkarni
|| Lokaha Samastaha Sukhino Bhavanthu ||
|| Sarve Jana
@Shiv
Collision is itself a wel known issue in hashing and much need to be
done to avoid collision. When you say your appraoch is hash the
numbers, how do u make sure without knowing the nature of the numbers
that you can hash them without bringing ing collision of inequal items
of the array?
On
If numbers are consecutive you can do better. Calculate (n-1)(n-2)/2 -
sum of all elements in the array.
That'll require one less loop compared to XORing twice.
-Minotauraus.
On Jul 28, 8:51 am, Apoorve Mohan wrote:
> Solution :
>
> 1. Find Xor of numbers from 1 to n-1.
>
> 2. Find Xor of the n
Hi tarak,
output is right, because every printf print 1 so there is 3 printf call...so
111 is right
On Thu, Jul 29, 2010 at 2:16 PM, tarak mehta wrote:
> #include
> int main()
> {
> int i=1;
> printf("%d\n",printf("%d",printf("%d",i))); return 0;
> }
>
>
> output is 111..i was expecting it to be
I'd say use a hash table to store node/pointer for quick lookup
instead.
For each node in the tree query the hash table. If there is a
collision (value exists) get point to that node from the table
and traverse the subtree, until you reach leaf nodes or find that the
subtrees are not the same.
For
Width of a Tree = maximum number of nodes at the same level.
Example:
a
bc
d e f g
h i j
Here, the max. width is 4 at level 3->d, e, f, g
Algo to find width:
1. Push node on stack1
Good approach Shiv.I think thats the best way to do so.The question does not
strictly say we have consecutive n-1 distinct numbers.So,its not worth
considering that particular case.
On Thu, Jul 29, 2010 at 12:08 AM, Shiv ... wrote:
> What if the number are not consecutive?
>
> My approach-
> Put
printf("%d\n",printf("%d",printf("%d",i)));
<- 1 --> This will print 1
and printf returns 1
< 2 --> This will print the
return value of printf <1> and it will return 1.
<--- 3
#include
int main()
{
int i=1;
printf("%d\n",printf("%d",printf("%d",i))); return 0;
}
output is 111..i was expecting it to be 11..plz explain??
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@
44 matches
Mail list logo
