Ad:

C++ Discussion Thread
Unsolved
Views: 709

Jul 16th, 2008

How to optimize this function(about pattern match,A problem in a Interview)

Expand Post »

Question is :
Write a function

c++ Syntax (Toggle Plain Text)
 int f(char* str, long pattern)
 int f(char* str, long pattern)

to find out how many pattern does the str contain? str is a char array consist of '1' and '0';
for example: str = "11010101110101011110100011001" ,pattern = 110;

My solution is change pattern and str to std::string, then use std::string::find to search.
but I think this solution is not efficient.

1.Could you tell me other efficient solution? thanks.

2. if the second parameter is a array, how to optimize it?

Thank you very much!

littlestone

Reputation Points: 14

Solved Threads: 6

Light Poster

Offline

42 posts
since Mar 2008

Permalink

Jul 16th, 2008

Re: How to optimize this function(about pattern match,A problem in a Interview)

>but I think this solution is not efficient.
Why? If you're just guessing or using your "programmer's intuition", you're probably wrong. Interviewers (good ones) tend to smile more on people who aren't afraid to say "I'd rather optimize clean, correct code than fix fast code". That's the sign of an experienced programmer.

Narue

Administrator

Reputation Points: 6442

Solved Threads: 1393

Bad Cop

Offline

11,807 posts
since Sep 2004

Permalink

Jul 16th, 2008

Re: How to optimize this function(about pattern match,A problem in a Interview)

Thank you!

I don't know the answer of the second question: if pattern is a array, how to optimize it?

littlestone

Reputation Points: 14

Solved Threads: 6

Light Poster

Offline

42 posts
since Mar 2008

Permalink

Jul 16th, 2008

Re: How to optimize this function(about pattern match,A problem in a Interview)

>I don't know the answer of the second question:
>if pattern is a array, how to optimize it?
The answer is the same.

Narue

Administrator

Reputation Points: 6442

Solved Threads: 1393

Bad Cop

Offline

11,807 posts
since Sep 2004

Permalink

Jul 16th, 2008

Re: How to optimize this function(about pattern match,A problem in a Interview)

if the pattern matching is done on a very long sequence of characters (eg. searching for the occurrence of a particular phrase or word in a large book), there are several interesting algorithms. here is a link that explores some of them. http://www.jea.acm.org/ARTICLES/Vol4Nbr2/index.html

vijayan121

Reputation Points: 1159

Solved Threads: 285

Posting Virtuoso

Offline

1,606 posts
since Dec 2006

This thread is more than three months old

No one has posted to this discussion for at least three months. Please let old threads die and do not reply to them unless you feel you have something new and valuable to contribute that absolutely must be added to make the discussion complete. Otherwise, please start a new thread in this forum instead.

Previous Thread in C++ Forum Timeline: difficulty in providing delay in gcc compiler

Next Thread in C++ Forum Timeline: Interface in DOS

DaniWeb Message

Cancel Changes

User Name
Password