[lnkForumImage]
TotalShareware - Download Free Software
Confronta i prezzi di migliaia di prodotti.
Asp Forum
 Home | Login | Register | Search 


 

Forums >

comp.lang.c++

design a tree structure which generates dynamic substrees

dongfei

11/29/2008 4:19:00 AM

There is an interview question I am asked in Microsoft. Write a
function to build a word tree from a dictionary ?

Input: a dictionary file
Function: void build(filename);
the sample.
Root--a----t
| |__
|___ bout
by

At first, I design it using a trie tree that every tier contains 26
letters.
struct trienode
{
trienode* subtree[26];
char* ch;
};

But the interviewer said it wastes a lot space. I only need to insert
the nodes if necessary. How to design the data structure to support
the dynamic allocated nodes?
4 Answers

red floyd

11/29/2008 4:27:00 AM

0

dongfei wrote:
> There is an interview question I am asked in Microsoft. Write a
> function to build a word tree from a dictionary ?
>
> Input: a dictionary file
> Function: void build(filename);
> the sample.
> Root--a----t
> | |__
> |___ bout
> by
>
> At first, I design it using a trie tree that every tier contains 26
> letters.
> struct trienode
> {
> trienode* subtree[26];
> char* ch;
> };
>
> But the interviewer said it wastes a lot space. I only need to insert
> the nodes if necessary. How to design the data structure to support
> the dynamic allocated nodes?
You should learn about the associative containers in the Standard Library.

Kai-Uwe Bux

11/29/2008 4:52:00 AM

0

dongfei wrote:

> There is an interview question I am asked in Microsoft. Write a
> function to build a word tree from a dictionary ?
>
> Input: a dictionary file
> Function: void build(filename);
> the sample.
> Root--a----t
> | |__
> |___ bout
> by
>
> At first, I design it using a trie tree that every tier contains 26
> letters.
> struct trienode
> {
> trienode* subtree[26];
> char* ch;
> };
>
> But the interviewer said it wastes a lot space. I only need to insert
> the nodes if necessary. How to design the data structure to support
> the dynamic allocated nodes?

See Knuth: TAOCP, Vol 3, 6.3 (digital searching).

The main idea is a space-time tradeoff. You can do

struct trienode {
char* str;
trienode* next;
trienode* down;
};

and use a linked list for the siblings of a node.


Best

Kai-Uwe Bux

dongfei

11/29/2008 8:43:00 AM

0

On Nov 29, 12:52 pm, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
> dongfei wrote:
> > There is an interview question I am asked in Microsoft. Write a
> > function to build a word tree from a dictionary ?
>
> > Input: a dictionary file
> > Function: void build(filename);
> > the sample.
> > Root--a----t
> >    |      |__
> >    |___     bout
> >          by
>
> > At first, I design it using a trie tree that every tier contains 26
> > letters.
> > struct trienode
> > {
> > trienode* subtree[26];
> > char* ch;
> > };
>
> > But the interviewer said it wastes a lot space. I only need to insert
> > the nodes if necessary.  How to design the data structure to support
> > the dynamic allocated nodes?
>
> See Knuth: TAOCP, Vol 3, 6.3 (digital searching).
>
> The main idea is a space-time tradeoff. You can do
>
>   struct trienode {
>     char* str;
>     trienode* next;
>     trienode* down;
>   };
>
> and use a linked list for the siblings of a node.
>
> Best
>
> Kai-Uwe Bux

Thanks, could you implement the function of build(filename) ?

Kai-Uwe Bux

11/29/2008 8:55:00 AM

0

dongfei wrote:

> On Nov 29, 12:52 pm, Kai-Uwe Bux <jkherci...@gmx.net> wrote:
>> dongfei wrote:
>> > There is an interview question I am asked in Microsoft. Write a
>> > function to build a word tree from a dictionary ?
>>
>> > Input: a dictionary file
>> > Function: void build(filename);
>> > the sample.
>> > Root--a----t
>> > |      |__
>> > |___     bout
>> > by
>>
>> > At first, I design it using a trie tree that every tier contains 26
>> > letters.
>> > struct trienode
>> > {
>> > trienode* subtree[26];
>> > char* ch;
>> > };
>>
>> > But the interviewer said it wastes a lot space. I only need to insert
>> > the nodes if necessary.  How to design the data structure to support
>> > the dynamic allocated nodes?
>>
>> See Knuth: TAOCP, Vol 3, 6.3 (digital searching).
>>
>> The main idea is a space-time tradeoff. You can do
>>
>> struct trienode {
>> char* str;
>> trienode* next;
>> trienode* down;
>> };
>>
>> and use a linked list for the siblings of a node.
>>
>> Best
>>
>> Kai-Uwe Bux
>
> Thanks, could you implement the function of build(filename) ?

Sure.

Apart from IO checking, the function would roughly look like this:

trienode* build ( std::string const & filename ) {
trienode * root = 0;
std::ifstream dictionary ( filename.c_str() );
std::string word;
while ( dictionary >> word ) {
insert( root, word );
}
return ( root );
}

The insert function would have the signature:

void insert ( trienode* & root, std::string word );

and implementing it is left as an exercise.


Best

Kai-Uwe Bux