Greedy Algorithm

Greedy approach gives a feasible solution to a problem where multiple solutions are possible. Greedy approach doesn’t give you the optimal solution, but if the feasible solution is optimal, then we can accept that solution.

Let’s consider the coin changing problem, which could be solved using greedy algorithm. Assume that, we are given a set of coins, and a sum to be changed. Then we can do so,

import math

def greedy(coins, target):
 remaining = 0
 count = 0
 i = 0
 times = 0
 while(True):
      if(target is 0):
           break
      else:
           times = math.floor(target/coins[i])
           remaining = target - (coins[i]*times)
           target = remaining
           print(coins[i]," needs: ", times," times.")
           i += 1
           count += times
 return count
coins = [10,5,2,1]
print("\ntotal coins needed: ", greedy(coins, 31))
10  needs:  3  times.
5  needs:  0  times.
2  needs:  0  times.
1  needs:  1  times.

total coins needed:  4

As we can see that, we need total 4 coins to make 31 from the list of [10,5,2,1] coins. In this case it is an optimal solution, but if we are given [4,3,1] for 6 then the total number of coins we need would be 3 using the greedy algorithm. Unfortunately, the optimal solution would be 2. So we see that greedy algorithm has some drawbacks, but it could be optimized using the dynamic programming.

Code out loud with ….. !?

I learned number of programming languages in my life. Some of them are just for learning, some for just giving a shot, some for my career. Yet I keep my skills with programming languages very concise in my resume. The reason is simple, just to avoid horrific interview questions.

When I started learning Java back in 2010, once I heard that there aren’t many quality Java EE developers around the world. I took it for granted, and thought things won’t change that much in next 5-6 years. But unfortunately by the time I came out of university, I found everyone around me speaks Java EE. And the experience ones in the interview board really hate the way a fresh graduate codes (no design patterns, smelly codes, less cohesion, high coupling, redundant codes, and so forth).

Along with some other reasons I decided to pack my bag once again for a higher degree, and take a relief from the dog fight in the job market. Once in a spare time I started looking through the list of the programming languages, and tried to find one for myself. I would say python really attracted me, not because it was easy, rather I realized not so many people around the world actually use it professionally, unless they are engaged in a scientific computing. Eventually I got a chance to work for a high performance computing center, and I really did use python ;). I felt like, job, finally I got you bitch.

Nevertheless I still love java, and used it professionally too. But, python holds my first place of attention.

Python Code Interview [Data Scientist]

Problem


I was given an account-data of an user number 7 from a CSV sheet named account.csv. I was asked to evaluate his mean balance over the last 3 months of all his accounts. (Library Pandas is recommended).
The account.csv file has the data as following:
account_csv

Answer


interview