two interesting data structure/algorithm questions

Hi,

I hope this is the appropriate news group for these.

My friend asked me two questions about data structure and algorithms.
I think she got them from some job interview books. I felt they are
interesting but haven't found good solutions yet. Could someone give
some suggestions?

Q1: Suppose you are looking up a contact name on your cell phone's
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?

Q2: Suppose you have a book written in English. Your goal is to search
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?
I can think out using hashes but since the string to look up can be
arbitrary, the hash table will be huge...

.

Relevant Pages

  • Re: two interesting data structure/algorithm questions
    ... My friend asked me two questions about data structure and algorithms. ... cell phone shows all names start with letters "ab" in sorted order. ... what's the best data structure and algorithm to implement ... for an arbitrary string and return the page numbers where this string ...
    (comp.programming)
  • Re: two interesting data structure/algorithm questions
    ... cell phone shows all names start with letters "ab" in sorted order. ... what's the best data structure and algorithm to implement ... for an arbitrary string and return the page numbers where this string ... you can compute distance of texts got from index database and ...
    (comp.programming)
  • Re: String count algorithm
    ... wrote in message news: ... Which is the best data structure and best algorithm to ... You want the fast A algorithm. ... Essentially you pick out uncommon pairs in the target string, and use that as the basis for further investigation, ...
    (comp.programming)
  • Re: Writing a Text Editor in Lisp
    ... It is hard to say which is the "best" data structure without knowing ... changed) a gap buffer to hold the entire text of the buffer. ... Multics Emacs used a doubly linked list of strings, ... editing operations on different lines, ...
    (comp.lang.lisp)
  • This Weeks Finds in Mathematical Physics (Week 226)
    ... The first week they had lots of talks on "higher-dimensional rewriting", ... to find two files that give the same bit string. ... Now, if you're a mathematician, the whole idea of a cryptographic ... You can see the algorithm for this ...
    (sci.math.research)