Problem 1: Balanced string

“Everything should be balanced and your life is too. You could spend a lot of time for work but please save time for your family”, said by a good father Toan. “And a string should be as well, I think ToannaoT is better than my name”, he went ahead. And he invented a “balanced string” that its characters are mirrored by its center. For example, abcba or abccba are balanced while abcbc and abccbc are not.

Give you a list of string, compute the sum of length of all balanced strings.

Note: it’s also called “palindrome” which reads the same backward or forward.

Sample input:

Sample output:

Problem 2: Phone number

Cuong has a locked iPhone and it always gives him a headache of contact and phone number mapping. For example, he saved his girlfriend’s number 0987654321 to his contact, but it always shows up 84-9876-54321 as it adds the country code automatically.

As a super programmer, he of course wants to fix this by a coding service to recognize each parts and join it himself. Do you want to solve it with Cuong?

Give you a list of phone numbers, each number in each line. A phone number has a format

PhoneNumber = [CountryCode][separator][LocalAreaCode][separator][Number]

With

  • separator is space or hyphen
  • CountryCode, LocalAreaCode, Number only contain the digits.

Submit the result = [Sum_of_CountryCode] * [Sum_of_LocalAreaCode] * [Sum_of_Number]

Sample input:

Sample output:

Problem 3: Love letter

Yesterday, The just found a love letter that his friend, Long, has writtent to his girldfriend. As a naughty boy, he want to meddle with this letter and change all the words to “ballanced” (palindrome) that Toan has invented. But to be safe, he should follow the rule and save his steps to make this letter recoveryable later.

  • He can reduce the value of a letter but cannot increase. For example, he can change b to a but cannot change a to b.
  • Once a letter has been changed to a, it can no longer to be changed.
  • Each step, he can reduce 1 letter with 1 unit. For example, changing c to a needs 2 steps.

So let find the minimum steps for him to change this letter to palindrome.

Sample input

Sample output

Problem 4: Girl attracting law by Fibonacci approach

After a long time in-door researched, Hung found a good approach to attract a girl and he named it“Girl attracting law by Fibonacci approach” that means the number of presents Hung gives to her is increased by Fibonacci sequence. But don’t stop, he extended to version 2 with some customisation by:

T(n+2) = T(n+1) * T(n+1) + T(n)

with T(n) is a number of presents at the nth dating.

Hung of course has a lot of money but wants to trust a girl, so he should give her 0 present at the first and 1 present at the second dating. And following his theory, 5 presents should be given in the 5th dating as explanation below:

1st number  = 0

2nd number = 1

3rd number = 12 + 0 = 1

4th number = 12 + 1 = 2

5th number = 22 + 1 = 5

Hung said that he has meet her 13 times and today he wants to know how many present he should give. Could you help Hung?

These problems are modified by some in Hackerrank

80 total views, no views today

Problem

After a long time in-door researched, Hung found a good approach to attract a girl and he named it “Girl attracting law by Fibonacci approach” that means the number of presents Hung gives to her is increased by Fibonacci sequence. But don’t stop, he extended to version 2 with some customisation by:

T(n+2) = T(n+1) * T(n+1) + T(n)

with T(n) is a number of presents at the nth dating.

Hung of course has a lot of money but wants to trust a girl, so he should give her 0 present at the first and 1 present at the second dating. And following his theory, 5 presents should be given in the 5th dating as explanation below:

1st number  = 0

2nd number = 1

3rd number = 12 + 0 = 1

4th number = 12 + 1 = 2

5th number = 22 + 1 = 5

Hung said that he has meet her 13 times and today he wants to know how many present he should give. Could you help Hung?

Solution

It seems very easy because the Fibonacci is a basic problem we usually do in learning programming. But, please aware that the number in this sequence increase too fast and need a wide range of positive number. In C# or Java, you could use BigInteger type.

 

63 total views, no views today

Do you remember my post about the interview question? It’s one of my problems in our Code Challenge that I would like to share in this post.

Code Challenge is one of our exciting activities last year where we can learn from each other by solving the problems in a contest. I also published the tool on Github for who wants to host this kind of event, please don’t hesitate to contact me if you want to use or need any support.

Purpose

It makes sense, everybody always needs to improve as every organisation needs to go forward. And learning is a good way to keep us improved and motivated. We have thought about the contest that allows every developers join to learn and measure their coding skill, and we held the Code Challenge last year that was involved by all our developers as contestants.

Joining the contest with our colleagues is very fun thing as we can learn from others and see how good we are right now. But it’s not easy for the host because there are various specific platforms or technologies in one organisation or teams, then the contest should target on a shared knowledge or skills in the whole team. To be fair, we should remove all the dependencies that relate to the language or platform uses and back to the basic of software development: programming.

Follow my experience, the ACM ICPC is very good format that focus on the programming but it seems still complex and has language limitation. Project Euler suits us better but it should have the time constraint to identify the winner.

Format

Our Code Challenge is mostly like the Project Euler format with time limitation as ACM ICPC. It was being held bi-weekly in 5 rounds, each round run from 13:00 to 17:00. In 4 hours, the contestants try to solve about 5 or 6 problems by following rules:

  • Solve problems in order. The contestant needs to solve a problem before taking the next one. So the problems should be arranged by their difficulties.
  • Result comparison. It doesn’t matter with the contestants’ solution as they can solve the problem by any programming language (or sometimes by non-programming as by Excel skill). A problem just shows the issue with a specific input data and compare the result with correct solution.
  • Multiple submissions. Contestant can try submit his solution many times as he wants to get the problem solved. The time spend for a problem is that the time he starts the contest to the first attempt of accepted solution.
  • Faster is better, careful is good. The contestants are ranked by these criteria in order:
    • Number of solved problems. The more number of solved problems are, the higher rank of contestant is.
    • Number of submission. If some contestants have the same number of solved problems, the number of submission should be counted. The contestant get higher rank by fewer attempts.
    • Time spend. The time spend should be the last criteria as its precision was counted to millisecond :). It is the total time spend of all solved problems.

Experiences

As our experience, there are some good things we could have from Code Challenge:

  • Fun. It could come from various sources such as a story in problem or the solution. In the 3rd round, we all surprised by a problem can be solved in 3 minutes as it normally takes at least 15 minutes for programming. But it’s so easy to calculate and submit the possible results manually. Yes, he’s so smart.
  • Share and learn. After the contest, we always sit together to share our different solutions of those problems, so we can learn from others and see what was the best way to solve them.
  • Improve. We of course had a good chance to learn from others or from practice during the contest preparation for getting improved.
  • Motivate. Beside the award for winner, there were some secondary awards such as the best newbie, first solved problem, last accepted attempt…etc for our guys trying to get.

And there are a lot of good things you would see as I think you should host at least one Code Challenge in your team.

Issues

Yes, there are various good things we had but in another hand, some minor issues came.

You could see that our format and tool were designed to target the purpose: removing the technology dependencies where contestant can solve the problem by any language (or by non-programming). But the issue is moved to the problem set as we should design them as free-language algorithm – it’s usually not easy. A lot of problems can be solved quickly by Java, C# but much slower in C++ by coding time but versa in running time.

Another issue is that somebody is very good at basic programming and algorithm but someone isn’t. I truly believe that a good developer should be good at algorithm but it seems not work today as the technology goes so far and developer can build the very good products with a normal algorithm background. He of course cannot be bad but doesn’t need to be very strong in algorithm to be a good developer as some years ago because the high-level technologies support us too much. For example, 10 years ago, every good developer needs to know what best sorting algorithm in his case in C++ but today a normal developer doesn’t care about this, just call Sort() method in C# and it would do in the best way. And of course, the results are mostly the same no matter he knows the Sort() method would run by any algorithm. It’s proved in our Code Challenge last year as there was only 1 winner for all rounds. He is very talent and strong in algorithm but isn’t a top guy in product development.

They are just the minor issues we would face in any contest that targets to wide range of developers. The problem content is the best way to resolve these issues but it usually takes much time to create a good problem like that. Contest is not fair but we should keep it as good as possible 🙂

I will share our problems that were used in our Code Challenge last year in some next posts and hope that you can find some interesting things.

And here is the system we have used: https://github.com/hiennvn/code-challenge. It may have some bugs because it just was the first MVP and one of my 24-coding-hours projects. But it worked fine for us last year.

Keep calm and love code.

Don’t want to wait for my next post? Try this problem:

A motor bike plate number is in the format [AB-CD EFG.HI]. Its value is defined by: AB x C + EFG x HI, if C is a letter, its value is its ASCII code. A plate number is called NICE one if its EFG contains its HI, then its value is doubled than normal. Give you a list of place numbers, find the biggest value.

For example: A plate 29-C1 320.12 has value 5783 (= 29*67+320*12)

What is the biggest value of

28-A1 493.68

83-Y3 453.83

17-Z7 439.48

29-C1 292.29

101 total views, no views today

Some days ago, after I published my interview question, my colleague asked me about having the problems weekly and solving them together. And instead of theory problem, they should be the real problems that we would face in the daily work. And today we did the first one.

One of the daily problems is making the mock test data as we want to have a lot of data and insert them to a test DB. I’m writing a library that can help my team to generate a random data for test and hope that I can complete and share with you in some next days. But I need to solve the first problem while writing it:

When inserting the data to DB, we need to put them in a correct order to satisfied its constraints. Let’s focus on the reference (foreign key) constraints to make it simple enough. For example, if there are 2 tables Product, Category in the DB, one product should belong to 1 category, so the statements should be:

If we change these statements to:

it doesn’t work because the the CategoryId = 1 isn’t existing while the first statement runs. So the problem should be: Giving a clean DB, so we know its schema (and of course, we know all tables’ references), and some INSERT statements, which should be the correct order of these statements? Or which the order of tables should be inserted? For example, it should be (Category, Product) in above sample.

We had a discussion on My Khe (Danang) beach to solve this problem this time, it was very interesting. Finally we had some solutions, and one of them has came up after answering some questions:

1. What are the first tables?

Of course, they are the tables that have no reference to any others. Let call this table set A.

2. What are the next tables?

They are the tables that only refers to the tables in A or itself. Let call this table set B.

3. What are the next tables?

They are the tables that only refers to the tables in A or B or itself. Let call this table set C.

4. The #2 and #3 questions are the same?

Yes.

5. The table set A in #2 answer and (A or B) in #3 answer have the same meaning?

Yes.

So repeat to answer #2 question, we should have a natural approach. The algorithm could be described as: Start with the table that don’t have any reference and add them to table set A, try to find the next tables that their references only belong to A and add them to A in a loop until all table are in A.

And the implementation in C# could be:

I used DatabaseSchemaReader to get the DB’s schema in this C# code. Of course, you can find another appropriate library in your platform or language as it seems a common problem.

Thank you my friend for giving me the solution and hope that I can get the test data generator done and share with you soon.

Solving a problem, get it done by code and publish it on the blog – all on the beach, it’s such a great experience.

Writing on the beach

Note: You could see that it’s not just a DB problem itself, and it can be solved by graph or natural algorithm. The DB problem here is just reasonable for having references between the nodes (we can consider that a table is a node, and its references to other tables are the connections in a graph). So you could see the importance of the basic data structure and algorithm to solve any real problem.

I updated the solution and code by the comment of Nguyen Phuc Dat below in case of self-referenced. Dat, thank you guy.

121 total views, no views today

The most important job is recruiting.

Yes, it’s totally true. I have spent about a quarter of my time for finding the good guys and got both success and failure in seeing how good a candidate is. Then I have tried to create a question and used it for a year in all my interviews with candidates of developer position.

The interview question is:

Writing continuously the non-negative numbers by skipping the number which is built by only one digit (11, 22, 33… 111, 222, …), we have a sequence:

0123456789101213…19202123…

You can see the 10th digit is 1. So let’s say 10th 1. Compute:

10th + 100th + 1.000th + …

My question is “What is your approach to solve this problem? Don’t need to give the final result”.

It’s so easy? Not sure – as it’s a kind of a problem that its hard increases fast by the data limitation. Could you find 100th? 1000th? 100.000.000.000th? Yes, it’s much more different.

OK, let see some solutions that are described below:

Solution 1: Natural thinking

It seems we can build up and store this digit sequence in a string. And it’s so easy to get the digit by the index then. The code should be

But how about the 100.000.000.000th?

Solution 2: Optimisation

We can consider to stop the loop as soon as possible. For example, to generate a string with length 100.000.000.000, the maximum value of number in the loop should be less than 10.000.000.000 (why? could it be a smaller number?).

But it’s still too large. How many memory it takes to store 10.000.000.000 characters? 10.000.000.000 bytes > 9GB. But wait, why do we need to store whole the string? How many meaning digit? They are just 10th, 100th, 1.000th.. digits. So just count to get the meaning digit and skip storing others. The code should look like

This way can reduce the memory use to constant and nearly 0. But 10.000.000.000 seems too big for reaching in loop.

Solution 3: Math approach

Let’s see another approach by math

  • How many digits do we have by writing a sequence from 0 to 9? 10
  • How many digits do we have by writing a sequence from 10 to 99? 162 = (99 – 10 + 1 – 9) * 2. Skipping 9 numbers: 11, 22, …
  • How many digits do we have by writing a sequence from 100 to 999? 2673 = (999 – 100 + 1 – 9) * 3. Skipping 9 numbers: 111, 222, …

OK, so what 4.321th digit? 4321 – 10 – 162 – 2673 = 1476 > 0, this digit belongs to a number that falls in (1.000, 9.999) which has 4 digits. So its index from 1.000 = 1476 / 4 = 369. Then the finding digit should be 1 (in 1.369).

It’s not much easy but not difficult to implement in code and the process time is constant now.

It’s just a problem itself but how people approach or solve it can tell much about them.

After about one hundred interviews, I had a lot of data and categorise the candidates by the common feedback questions:

  1. I cannot understand this question. I get no information because some of developers are super in building software by tools but have never faced this kind of problem. Just explain or give them another question.
  2. I cannot solve this. Say goodbye to him, at least easy giving up is not my style or he should give me #1 feedback.
  3. I think there is a rule here. 10th is 1 so I guess 100th, 1.000th, 10.000th.. are 1 as well. Life is not easy man. The interview question is for testing the logical not tricky thought.
  4. What is its input? How to input data, from console? Why 10th is 1, it is 9?… I usually don’t waste my time for answering these questions. He just focuses on the minor things to forget real problem.
  5. We can generate this string and get the digit by index after that. Yes, it’s the first solution, right? He looks like a normal developer. I usually go ahead with him by some questions depending on how he structure the program. “How many functions or methods you have?”, “How do we check a number that is built by 1 digit?” etc. And of course, some suggestion to optimise the solution, “What should you choose, optimise memory or speed?”, “How many meaning digits we have?” etc, and the story begins.
  6. Ah yes, we should not maintain the whole string, we can remove the unnescessary parts. Sure, the second solution. He seems a good developer.
  7. Yeah, we remove 9 numbers in 2-digit numbers that equals to 18 digits. We also remove 9 numbers in 3-digit numbers that equals to 27 digits. And the actual position of 1.0000 should be minused… He is a must-have guy at least in the talent aspect.

It just a common test for his IQ, but the specific code should shows his knowledge and skills in a specific language or platform. For example, good C# developer should use StringBuilder to build the sequence instead of using string. C++ developer should check the number that is built by 1 digit by operations instead of by converting it to string. Putting the condition like if (sequence.Length > 10.000.000.000) in the loop is not the good way in code in any language.

The guy who can show off the solution 3 in the first time – he is really intelligent or he has solved a thousand problems like that, maybe a code challenger, also a right man we would hire.

The guy who cannot pose the best solution at the first time but can come to the solution 3 after the advises has potential to become a great developer.

The guy who cannot come to the optimised solution after the advises just be a normal developer – not a smart guy. I have never hired him even though he has a lot of experience or certificated.

In my opinion, Java, .NET or what common technologies is so easy for a talent guy learns in a short time but technology-master cannot go far with a week algorithm coding background.

So far, I think it’s a good question to see the developer’s IQ that I used in a long time. Now I’m creating another :).

83 total views, no views today