Re: two interesting data structure/algorithm questions
- From: rwt <rwt@xxxxxxxxxxxxxx>
- Date: Sun, 18 Nov 2007 02:11:27 +0100
"de" wrote:
Q1: Suppose you are looking up a contact name on your cell phone'ssome sort of linked list of references in the cost of editing of book
address book. Suppose your contact's name is "abc123". Then you type
"a" in the search box. The cell phone shows all names start with
letter "a" in sorted order. Then you type "b" after the first "a". The
cell phone shows all names start with letters "ab" in sorted order.
Then you type "c" after the "ab" and the cell phone shows all names
starts with letters "abc" in sorted order. You keep typing the contact
name and the list shown by your cell phone keeps updating and
shrinking untill at last either you find your contact name or you
don't.
Question: what's the best data structure and algorithm to implement
this real-time lookup effeciently and what's the time complexity of
the implementation?
which is stored as one-dimensional table
or
predict algorithm based on averages of positions into book entries
Q2: Suppose you have a book written in English. Your goal is to searchindex as above sb wrote but no pages just index into character or character multiplier position then
for an arbitrary string and return the page numbers where this string
is found. There could be more than one page number returned if the
string is cross page or if it's found on multiple pages. For example,
you have a string "this is an " on page 20 and then " interesting
book" on page 21. The string you are going to search for could be
"this" or "this is" or "is an" or " an interesting" or "an interesting
book". Then you'll need to return page numbers [20], [20], [20],
[20,21], [20,21] respectively. Of course, if you look for "book", it
could return hundreds of page numbers since "book" is really common.
Question: what's the best data structure and algorithm to implement
this real-time lookup effeciently and what's the time complexity of
the implementation?
you can compute distance of texts got from index database and
break limit of pages
if you wouldn't know it's old problem: segmented or linear memory
distance of locations of searched words is the key and
some informations can be striped out from index database and
searched on request
--
/ qo |) :@=N%_g=v=a=g_eD_e=c()=d=8! =%!Gn@8're. w8in/ad
\ _x/ , ;h-%-a'hA'H4,X0'Xo~xo~xO,R`-%EXp01ITed: *-7/+eh
/ | ng `-%__%--'__%--'__%--~__%--^%B`/$qV3r[o; &GooMee
L o_O http://tech.groups.yahoo.com/group/opRWTng O_o L"EnOF"
.
- References:
- Prev by Date: Re: Can Binary Search Be Improved with Threading
- Next by Date: Re: Path optimizations
- Previous by thread: Re: two interesting data structure/algorithm questions
- Next by thread: Re: two interesting data structure/algorithm questions
- Index(es):
Relevant Pages
|
