Daily Coding Practice

Hi everyone,

I have made a decision that I need to improve my coding skill day by day to keep track with the lightning pace of data industry’s evolution. In this blog, I’m happy to share with you all problems from books that I challenge myself everyday. Hope that it would be useful for you too! Let’s go!

Problem 1: Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i.

For example, if our array is [1,2,3] then output is [6,3,2] .

The problem is easily solved if we can use division: you calculate the total product of all elements, then divide it to each element i of the array to obtain the output.

What if we can’t use division?

I have an ideal of using dynamic programming. Check the code below:

Now I want to test time speed of this algorithm compared with the code using division.

Use division
My algorithm

I’m quite happy because my code seems run faster than the benchmark. Beside, when increasing the size of input, the first algorithm can’t work, but my algorithm still does!

Finally I complete first day of coding training. Hope to discuss with you about next problems.

Now it’s time to share with you the second problem.

This problem looks hard when I read it because it is not easy even when you solve it in the simplest way: find the maximum among sums of consecutive elements. In general we don’t have any other method to solve it but calculate every sum of subarray, the matter is do it quickly.

My solution is as below:

I wrote two samples for testing as below:

First array: [34, -50, 42, 14, -5, 86]
Maximum subarray sum: 137
Second array: [-5, -1, -8, -9]
Maximum subarray sum: 0

It seems right. I’m really happy if you share your solution with me.

I tried two different algorithms: The first is go straight to the loop and check step to step, the second is utilizing the bisect module to solve the problem.

The performance of the second is obviously much better than the first’s. Let see how I did as below:

Solution 1 runtime: 2.46s

Solution 2 runtime: 0.009s

This week I were quite busy so I hadn’t done any code till Wednesday. I’m solving a simple but interesting problem in Project Euler.

For anyone who doesn’t know Project Euler, it’s just a website of 746 mathematical problems which are indeed useful for coders to practice their coding skills and algorithmic thinking also. Let’s go straight to the first problem in Project Euler:

I would like to solve this problem with a general limit n (maybe larger than 1000). The followings are my different solutions for this problem

def set_multiple_of_3_or_5(n):
"""
:param n: integer
:return: get union of set of multiples of 3 and set of multiples of 5
"""
set_multiple_of_3 = set([3*i for i in range(int(n/3)+1)])
set_multiple_of_5 = set([5 * i for i in range(int(n/5) + 1)])
return set_multiple_of_3 | set_multiple_of_5
def set_of_multiple_of_m(m, n):
"""
:param n: integer
:param m: integer, = 3 or = 5
:return: set of multiples of m which are less than n
"""
return set([m*i for i in range(int(n/m)+1)])
def arithmetic_sum(numb, limit):
for last in range(limit, 1, -1):
if last % numb == 0:
return ((limit // numb) * (numb + last)) // 2


def math_power(n):
ans, limit = 0, n
ans += arithmetic_sum(3, limit)
ans += arithmetic_sum(5, limit)
ans -= arithmetic_sum(15, limit)
return ans
number = 10**6
start = time.perf_counter()
print(sum(list_multiple_of_3_or_5(number)))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
start = time.perf_counter()
print(sum(set_multiple_of_3_or_5(number)))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
start = time.perf_counter()
print(sum(set_of_multiple_of_m(3, number)) + sum(set_of_multiple_of_m(5, number)) - sum(set_of_multiple_of_m(15,
number)))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
start = time.perf_counter()
print(sum({*range(3, number, 3)} | {*range(5, number, 5)}))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')
start = time.perf_counter()
print(math_power(number))
end = time.perf_counter()
print(f'Elapsed time: {end - start}')

And the result for these codes above are as below:

The last solution runs super fast but the code is extremely simple: the trick is utilizing my mathematical skills to quickly calculate the sum of multiples.

It’s Sunday, my favorite day in week

Hi everyone, I will continue coding Project Euler problems in this Sunday morning. Let’s see how many problems that I can solve in 3 hours.

Obviously you must find all even Fibonacci numbers which are not greater than four millions. I have two solutions for this problem. The first is simply making a list of all Fibonacci numbers which are not greater than four millions, then calculate sum of all even elements in that list. The second is making a list of all even Fibonacci numbers which are not greater than four millions, then calculate sum of all elements in that list. The later would run faster because I inherit formula to calculate even Fibonacci from previous even numbers in Fibonacci series.

And this is the time elapsed for running each solution with the threshold value is four hundred millions.

Good? Let’s go to next problem:

The solution is following:

This solution is not trivial, because I don’t find out this approach at the first time. Actually I calculate all prime numbers which are less than or equal to n, then pick the largest number that is a divisor of n.

The elapsed time of algorithm is quite impressive:


6857
Elapsed time: 0.0013s

My time is over! I can only solve ONE easy problem in 3 hours :( .

Must work harder next time! See you.

Love that everyday would like Friday

Hi folks, another busy week is passing, finally I can focus to practice coding.

A part of tonight is for solving problems in Project Euler (damn, I love this website so much that I wish I knew it when I was at university!)

I have one solution, these other two below are from other people:

largest palindrome made from the product of two 6-digit numbers: 999000000999
Elapsed time: 0.64s
largest palindrome made from the product of two 6-digit numbers: 999000000999
Elapsed time: 0.56s
largest palindrome made from the product of two 6-digit numbers: 999000000999
Elapsed time: 1.06s

Let’s move to next problem:

I have 2 solutions for this problem: one is trivial, the other is smarter by utilizing Euclidean algorithm.

The smallest positive multiple of first 20 natural numbers is 232792560
Elapsed time: 96.987s
The smallest positive multiple of first 20 natural numbers is 232792560.0
Elapsed time: 0.308s

You can see again, many coding problem can be solved efficiently if we can utilize our mathematical thinking.

Done! It’s time to take a rest, hope that you’ll have a nice weekend! Bonne nuit!

It’s Sunday!

Hi folks,

in this blog today I just want to solve one Project Euler problem to accomplish weekly mission because I want to spend time for learning Scala and try to solve a Kaggle competition problem. Life is too short to resolve solved problems, right? Here we go:

I tried several ways to solve this problem to understand the efficiency of python when calculating simple maths.

To be honest, it made me a little surprise when the runtime of solution3 is longest. But later I understood the reason why: I ran two overlapped loops so the time complexity is squared.

Done! It’s time to conquer other missions, see you next week!

Lily of the Valley — Flower of May

Hi, today work is boring me a little bit. Fortunately my soul is healed while practicing coding in the evening. Let’s go through problems today!

There is obvious way to solve this problem by defining a function to check whether a number is prime or not, then searching prime number from 2 to so on. Despite of its simplicity, the time complexity is quite high, that’s why I suggest a second solution: we estimate the upper bound of nth prime number, then applying the method of sieve of Eratosthenes to find all prime numbers less than the upper bound.

The running time of the solution 1 is greater than 1000 times the solution 2's:

A little bit surprise, huh?

Tonight I’m still busy with my codes at work, so I spend a little time for project Euler.

I know there is another solution for this problem, but it’s not intuitive for me. My solution is as follows:

The elapsed time is not good as I expected, but somehow it can be accepted:

Now it’s time for coming back to company tasks : I need to write unit tests for my codes, which is the most boring thing in the world as I know. See you in a better day!

Growth Seeker

Tonight I solved one more problem as below:

I had two solutions:

And this is the result:

Thank you for your time. Now’s time for sleeping. Bonne nuit!

In next 10 years, I will be at the best place in the world. Now I don’t know where it is but my home

Hi folks,

It’s Saturday morning, let’s solve the problem below for breakfast:

What is the value of the first triangle number to have over five hundred divisors?

I’ll give you two solutions: the first is mine — simple and clear, the second is from other. I don’t think there is too much different of performance between two solution. When I try with a large number, 1000, my solution is even faster.

The elapsed time for finding the first triangle number, which has more than 1000 number of divisors, of each solution is below:

The lesson here is when we solve a problem, we should try to think simple first.

Now it’s time to begin a new problem as below:

Which starting number, under one million, produces the longest chain?

I have three solutions, the third is the fastest by applying dynamic programming.

The performance of each solution is as below:

Work, Eat, Love

Today I have been training my self to prepare for the two coming interviews in tomorrow, so I have solved more coding problems than usual. Let’s review what I have done up to now.

For example, if the array elements at indices 2 and 3 are equal, the distance metric for element 2 is |2-3| = 1. For element 3 it is|3-2|=1.

I’ll give you 4 solutions for this problem. All of them are right, but the first two solutions run extremely slow compare to the the last two solutions.

For testing performances of these solutions, I built a test function like below:

Please try to run the codes and to see how different they are. Now I’m moving to next problem.

And my solution is as below:

The solution is quite good in term of time complexity.

Now, I have another problem:

Given a list of queries, and a pattern, return an answer list of booleans, where answer[i] is true if and only if queries[i] matches the pattern.

I have 2 solutions for this problem:

When I check time running of two solutions, I see that there is no difference between them:

Anh the final problem that i want to share with you is below:

My solution is based on heap techniques:

Springs, Summer, Autumn, Winter, then Springs (again)

I have tried four solutions for this problem. The first one is trivial and slowest, the consecutive solutions are improved better and better.

I built a test for these functions as below:

The last two solutions passed my tests in term of speed:

Burning Cold by Cullan Smith on Unsplash

This is an interesting problem when you extend the exponential number is very large number. Unfortunately I haven’t found the solution for this case yet. The below is solving simple case:

The result when n = 2^1000 is 1366.

The simplest solution is below:

for n = 100, the result is 648.

Photo by Marcel Strauß on Unsplash.com

When something that I don’t expect happens, what is the best thing I can do is to focus to my growth path :)

I think I have a formal solution for this problem:

When I try to run this code on Coderbyte, its performance is acceptable, but I could improve it more if I optimize the code like below:

Let’s try more in the next problem on Coderbyte!

I want to show you the solution that uses dynamic programming technique.

author Clique Images on Unsplash

I have two solutions. Actually the first is the improved version of the second

The first runs faster than the second twice times

by Matt Barton on Unsplash

By using default module itertools I solve this problem quite smoothly as below:

The code runs in 1 second, so I think it’s acceptable.

What is the index of the first term in the Fibonacci sequence to contain 1000 digits?

I tried 2 solutions for this problem. The first I will calculate Fibonacci numbers until I find the first element which has 1000 digits. The second is using Binet formula to estimate the index without calculating any numbers. The second solution runs 100x faster than the first.

The last coding problem for today is as below:

I have 2 solutions for this problem. I’m quite surprised because the solution which is simple and straightforward runs faster than the other.

I think I will check the codes again next time. Now it’s time to turn to another task. Enjoy your weekend!

The problems that I discussed are from books below:

Or other online sources as below:

Quant Researcher, Data Scientist, Food Hater (so I eat them a lot).