baran
Hi again;
There are several ways to search in a file. While doing that, you can go as atomic as possible or you can do it in a higher level. You can trust your intuition about your algorithm but what is the drift of a better approach?
This is a part of series – Search, any better?
Let’s examine the following problem:
This is a trivial question/problem to be implemented by various languages.
Programming exercise – Routing of telephone calls
Some telephone operators have submitted their price lists including price per minute for different phone number prefixes. The price lists look like this:
Operator A:
1 0.9
268 5.1
46 0.17
4620 0.0
468 0.15
4631 0.15
4673 0.9
46732 1.1
Operator B:
1 0.92
44 0.5
46 0.2
467 1.0
48 1.2
And so on…
The left column represents the telephone prefix (country + area code) and the right column represents the operators price per minute for a number starting with that prefix. When several prefixes match the same number, the longest one should be used. If you, for example, dial +46-73-212345 you will have to pay $ 1.1/min with Operator A and $ 1.0/min with Operator B.
If a price list does not include a certain prefix you cannot use that operator to dial numbers starting with that prefix. For example it is not possible to dial +44 numbers with operator A but it is possible with Operator B.
The goal with this exercise is to write a program that can handle any number of price lists (operators) and then can calculate which operator that is cheapest for a certain number. You can assume that each price list can have thousands of entries but they will all fit together in memory.
Telephone numbers should be inputted in the same format as in price lists, for example “68123456789”. The challenge is to find the cheapest operator for that number.
< /hr>
So, the drift is actually straight forward, we are going to search for a literal which is a combination of alpha and numerics in a persisten store, let’s say file.
This work is a fun implementation for you to see a versatile nature in algorithm design and programming languages.
I did the implementation in VS2010, with .NET 4.0. in .NET solutions, JDK 1.7 in J2SE solutions, Python2.7 in Python solution.
Totally and currently, there are 5 implementations. 2 in C#.NET folder, 2 in J2SE folder and 1 in Python folder.
///
C#.NET Realm:
Acme.Routing.v1 folder has the solution which aims for trivial search capacity.
It uses VS built-in Test Project features.
Acme.Routing.v2 folder has the solution which aims for balanced binary search tree capacity.
It uses NUnit test features. You have to install NUnit 2.6.2 and run the binary of the test project in it (if x86 is the installation, run x86 version of NUnit).
J2SE Realm:
Acme.Routing.v1 folder has the project which aims for Boyer Moore search capacity.
It uses JUnit 4, Mockito 1.9.5, and Spring framework 3.2.1, all of which are provided in the solution.
Acme.Routing.v2 folder has the project which aims for binary search tree capacity but different approach.
It has no test cases in it currently.
///
Python folder content:
This is a similar approach in the first C#.NET implementation but rather I read the file backwards. I give an example test case, but didn’t do extensive test since I had already done in previous ones.
//
