473,320 Members | 1,946 Online
Bytes | Software Development & Data Engineering Community
Post Job

Home Posts Topics Members FAQ

Join Bytes to post your question to a community of 473,320 software developers and data experts.

data structure/algorithm problem

Hello, all,
This is probably not so much related to C++ (Sorry in advance). But
I did get this question during a C++ job interview.
You are asked to design some data structure and algorith for the
following function:

List getNames ( List nameList, String prefix );

What it does is: given a name list and a prefix, return all the
names in the name list that start with prefix.
For example, if nameList = { "abc", "abdf", "cde" } and prefix =
"ab", the function should return { "abc", "abdf" }.

I did not do well on that question. But I would like to see some
good designs.

Thanks a lot,
Nan

Sep 13 '05 #1
3 1599
Well my choice for the List is an AVL Binary Tree. A tree is used to
avoid excessive string comparing. The string compare you use does not
effect performance really. As long as the compare halts at the end of
the prefix. This means a special compare is required. ( StartsWith() )
I would also return a const ref to avoid copying the tree on return.
Copying an entire collection is expensive on the CPU and memory.
Something like this:

class Tree<typename T>
{
public:
Tree()
{
LeftNode = 0;
RightNode = 0;
}
Tree<T>* Traverse(const T& item)
{
if( item > Value)
return LeftNode;
else
return RightNode;
}
T Value;
private:
Tree<T>* LeftNode;
Tree<T>* RightNode;
};

const Tree<String>& getNames( const Tree<String>& nameList, String
prefix)
{
Tree<T>* current = &nameList;
while(current != 0 && !current.StartsWith(prefix))
nameList.Traverse(prefix);
if(current == 0) //No results
return Tree<String>();
return *current;
}

I'm too lazy to code the StartsWith() and the rest of the AVL tree...
I'll leave that to you.
Hoe that helps.

Sep 13 '05 #2
na******@gmail.com wrote:
Hello, all,
This is probably not so much related to C++ (Sorry in advance). But
I did get this question during a C++ job interview.
You are asked to design some data structure and algorith for the
following function:

List getNames ( List nameList, String prefix );

What it does is: given a name list and a prefix, return all the
names in the name list that start with prefix.
For example, if nameList = { "abc", "abdf", "cde" } and prefix =
"ab", the function should return { "abc", "abdf" }.

I did not do well on that question. But I would like to see some
good designs.

Thanks a lot,
Nan

Here is a simple linear search:
#include <string>
#include <list>
#include <algorithm>
#include <functional>
#include <iterator>
#include <iostream>

template < typename RangeOne, typename RangeTwo >
bool is_prefix ( RangeOne pattern, RangeTwo text ) {
if ( text.size() < pattern.size() ) {
return( false );
}
return( pattern.end()
==
std::mismatch
( pattern.begin(), pattern.end(), text.begin() ).first );
}
// this really should be in std
template < typename IterIn, typename IterOut, typename Predicate >
IterOut copy_if ( IterIn from, IterIn to, IterOut where, Predicate p ) {
while ( from != to ) {
if ( p( *from ) ) {
*where = *from;
++where;
}
++from;
}
return( where );
}

typedef std::string String;
typedef std::list< String > List;
List getNames ( List const & nameList, String const & prefix ) {
List result;
copy_if( nameList.begin(), nameList.end(),
std::back_inserter( result ),
std::bind1st(
std::ptr_fun( is_prefix< String, String > ), prefix ) );
return( result );
}

int main ( void ) {
List l;
l.push_back ( String( "abcd" ) );
l.push_back ( String( "acd" ) );
l.push_back ( String( "abcd" ) );
l.push_back ( String( "acd" ) );
l.push_back ( String( "ab" ) );
l.push_back ( String( "abcd" ) );
l.push_back ( String( "ac" ) );
l.push_back ( String( "ab" ) );
l.push_back ( String( "abx" ) );
String p = "ab";
l = getNames( l, p );
std::copy( l.begin(), l.end(),
std::ostream_iterator< String >( std::cout, "\n" ) );
}



Here is something that might pay if searches for different prefixes are done
but the list ist not changed:

#include <string>
#include <vector>
#include <algorithm>
#include <iterator>
#include <iostream>

typedef std::string String;
typedef std::vector< String > List;

std::string succ ( std::string str ) {
while ( str.size() > 0 ) {
++ *str.rbegin();
if ( 0 == *str.rbegin() ) {
str.erase( str.size() - 1 );
} else {
break;
}
}
return( str );
}

List getNames ( List const &nameList, String prefix ) {
// this one assumes the list to be sorted
List::const_iterator from
= std::lower_bound( nameList.begin(), nameList.end(), prefix );
prefix = succ( prefix );
List::const_iterator to
=
prefix.size() > 0 ?
std::lower_bound( nameList.begin(), nameList.end(), prefix )
:
nameList.end();
List result;
std::copy( from, to, std::back_inserter( result ) );
return( result );
}

int main ( void ) {
List l;
l.push_back ( String( "abcd" ) );
l.push_back ( String( "acd" ) );
l.push_back ( String( "abcd" ) );
l.push_back ( String( "acd" ) );
l.push_back ( String( "ab" ) );
l.push_back ( String( "abcd" ) );
l.push_back ( String( "ac" ) );
l.push_back ( String( "ab" ) );
l.push_back ( String( "abx" ) );
String p = "ab";
std::sort( l.begin(), l.end() );
List range = getNames( l, p );
std::copy( range.begin(), range.end(),
std::ostream_iterator< String >( std::cout, "\n" ) );
}


Best

Kai-Uwe Bux
Sep 13 '05 #3
Thanks for the ideas. Here is my STL solution. The STL set ( based on
some balanced binary search tree, probably red-black tree) certainly
helps here. Another tricky part is to compute the upper bound of all
strings starting with the prefix.
#include <string>
#include <set>
#include <iostream>

using namespace std;

typedef set<string> StrSet;

static const int BASE = 27;

int toNum( const string& s )
{
int num = 0;
for ( int i=0; i< s.length(); i++ )
num = num * BASE + (s[i] - 'a' + 1);
return num;
}

void toStr( int num, string* s )
{
if ( s ) {
if ( num / BASE > 0 )
toStr( num / BASE, s );
if ( num % BASE > 0 )
s->push_back( 'a' + ( num % BASE ) - 1 );
}
}

string plus_one( const string& s )
{
int t_num = toNum( s ) + 1;
string t;
toStr( t_num , &t );
return t;
}

int main()
{
int name_num;
cin >> name_num;
StrSet directory;
for ( int i = 0; i < name_num; i++ ) {
string name;
cin >> name;
directory.insert( name );
}

string prefix;
cin >> prefix;
StrSet::iterator iter1 = directory.lower_bound( prefix );

string prefixNext = plus_one( prefix );
StrSet::iterator iter2;
if ( prefixNext == "a" )
iter2 = directory.end();
else
iter2 = directory.lower_bound( prefixNext );

for ( StrSet::iterator iter = iter1 ; iter != iter2; ++iter )
cout << *iter << endl;

return 0;
}

input:

10
alexandrea
alexandria
alexandrina
alexia
alexina
alexis
aaren
aaron
abbey
zzeppelin
zz

output:
zzeppelin

input:
10
alexandrea
alexandria
alexandrina
alexia
alexina
alexis
aaren
aaron
abbey
zzeppelin
ale

output:
alexandrea
alexandria
alexandrina
alexia
alexina
alexis

Sep 26 '05 #4

This thread has been closed and replies have been disabled. Please start a new discussion.

Similar topics

2
by: yee young han | last post by:
I need a fast data structure and algorithm like below condition. (1) this data structure contain only 10,000 data entry. (2) data structure's one entry is like below typedef struct _DataEntry_...
4
by: Marek Mänd | last post by:
var criterions = { subconds:{ tree: } } // MUSIC , {condID:17, strrep:'Music', subconds:{ tree:
3
by: Peter | last post by:
Hi All, I am looking for what may be a good data structure to use for a given problem. I have to randomly insert,delete and lookup some objects - all three being equally probable. The number of...
11
by: hoopsho | last post by:
Hi Everyone, I am trying to write a program that does a few things very fast and with efficient use of memory... a) I need to parse a space-delimited file that is really large, upwards fo a...
3
by: aurora | last post by:
This is an entry I just added to ASPN. It is a somewhat novel technique I have employed quite successfully in my code. I repost it here for more explosure and discussions. ...
4
by: sakcee | last post by:
Hi I hope that I can learn from your experience . I want to know if you have seen a perticular problem and used a perticular data structure , and why? I usually end up using just arrays,...
11
by: sofeng | last post by:
I'm not sure if "data hiding" is the correct term, but I'm trying to emulate this object-oriented technique. I know C++ probably provides much more than my example, but I'd just like some feedback...
6
by: pj | last post by:
Hi, I 'm currently writing a program that performs transliteration (i.e., converts greek text written using the english alphabet to "pure" greek text using the greek alphabet) as part of my...
2
by: jehugaleahsa | last post by:
Hello: I have a bunch of related items that are either parents, children or not directly related to each other. In my case, I have a bunch of database tables joined with foreign keys. Another...
0
by: ryjfgjl | last post by:
ExcelToDatabase: batch import excel into database automatically...
1
isladogs
by: isladogs | last post by:
The next Access Europe meeting will be on Wednesday 6 Mar 2024 starting at 18:00 UK time (6PM UTC) and finishing at about 19:15 (7.15PM). In this month's session, we are pleased to welcome back...
0
by: jfyes | last post by:
As a hardware engineer, after seeing that CEIWEI recently released a new tool for Modbus RTU Over TCP/UDP filtering and monitoring, I actively went to its official website to take a look. It turned...
0
by: ArrayDB | last post by:
The error message I've encountered is; ERROR:root:Error generating model response: exception: access violation writing 0x0000000000005140, which seems to be indicative of an access violation...
1
by: PapaRatzi | last post by:
Hello, I am teaching myself MS Access forms design and Visual Basic. I've created a table to capture a list of Top 30 singles and forms to capture new entries. The final step is a form (unbound)...
0
by: CloudSolutions | last post by:
Introduction: For many beginners and individual users, requiring a credit card and email registration may pose a barrier when starting to use cloud servers. However, some cloud server providers now...
0
by: Defcon1945 | last post by:
I'm trying to learn Python using Pycharm but import shutil doesn't work
0
by: af34tf | last post by:
Hi Guys, I have a domain whose name is BytesLimited.com, and I want to sell it. Does anyone know about platforms that allow me to list my domain in auction for free. Thank you
0
by: Faith0G | last post by:
I am starting a new it consulting business and it's been a while since I setup a new website. Is wordpress still the best web based software for hosting a 5 page website? The webpages will be...

By using Bytes.com and it's services, you agree to our Privacy Policy and Terms of Use.

To disable or enable advertisements and analytics tracking please visit the manage ads & tracking page.