Re: design a tree structure which generates dynamic substrees

Discussion in 'C++' started by Kai-Uwe Bux, Nov 29, 2008.

  1. Kai-Uwe Bux

    Kai-Uwe Bux Guest

    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
    Kai-Uwe Bux, Nov 29, 2008
    #1
    1. Advertising

  2. Kai-Uwe Bux

    Kai-Uwe Bux Guest

    dongfei wrote:

    > On Nov 29, 12:52 pm, Kai-Uwe Bux <> 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
    Kai-Uwe Bux, Nov 29, 2008
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Stub

    B tree, B+ tree and B* tree

    Stub, Nov 12, 2003, in forum: C Programming
    Replies:
    3
    Views:
    10,096
  2. sharan
    Replies:
    4
    Views:
    675
    CBFalconer
    Oct 30, 2007
  3. sharan
    Replies:
    2
    Views:
    822
    SM Ryan
    Oct 31, 2007
  4. sharan
    Replies:
    1
    Views:
    680
    CBFalconer
    Oct 30, 2007
  5. anne001
    Replies:
    1
    Views:
    228
Loading...

Share This Page