Tuesday, January 19, 2016

(Algorithm) Turn string into integer

Question: Turn given number(integer) as string into integer.
Ex. "one million two hundreds thousands fifty seven" => 1200057

Resource: http://www.careercup.com/page?pid=algorithm-interview-questions
Question Owner: tamashionuth


ANSWER

I modified this example as all words only contain lower case characters. However you can easily handle upper case characters with this algorithm too. Whenever we try to solve a problem, we try to catch the algorithm. However, sometimes it is not enough that get only "regularity", and we also have to "teach" computer some "human-made" words.

As basic, we have twelve numbers and common special words to create an integer.
zero
one
two
three
four
five
six
seven
eight
nine
ten
eleven
twelve
"teen"

I think this key words are enough to create all numbers. We don't have to remember keywords like hundred, thousand, billion etc.

Let's split algorithms we have, to define numbers.
From 0 to 12
We have defined them, so computer can understand when it sees the number.

From 13 to 19
We have "teen" keyword in the whole word(eg. fourteen).
First we have to check if word contains this keyword.
If our answer is "yes", then look whole word's first two letter. These letters tell us what number is.
These two letters are abbreviation of first nine numbers from one.
(eg. thirteen => starts with 1 because of teen, continues with 3 because of th)

From 20 to 99
We look first two letters again. When we see "abbreviation" of first 9 numbers, we can talk about it's first digit. Then look second word and try to match it with our first 9 numbers. If we find matching, we can say it's second digit; if we don't find, it means second digit is zero.
(eg. fifty one => abbreviation of 5 and full word of one. So number is 51)

From 100 to 999
We will only have hundred keyword as extra which is already known by our program.
(e.g five hundred sixty two => 5 because of fi, 6 because of si, and two. So 562)

From 1000 to 9999
We will continue from there with only examples, because I think you get the algorithm.
(e.g ten thousand seven hundred eleven => 10711)

And, so on... We only have one step to reach the number:
1. Catch the keyword
Then write the number easily.

No comments:

Post a Comment