tag:blogger.com,1999:blog-25978418152809984182018-02-24T12:22:25.802+01:00This Thread<i>tutorial-like examples and some informal chatting on C/C++/Java/Python software development (and more)</i>Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.comBlogger789125tag:blogger.com,1999:blog-2597841815280998418.post-33585353931082757712018-02-21T13:15:00.001+01:002018-02-21T13:15:26.250+01:00Longest Common Subsequence of Three SequencesAnd finally, the last one of this group of Dynamic Programming problems. Actually, from the algorithmic point of view this is the less interesting one, being just a variation on the previous one. Now we have in input three sequences instead of two, still we have to get the longest subsequence among them.
The interest here is all in extending the algorithm to work with a three-dimensional cache. Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-6382940712499583782018-02-21T12:54:00.000+01:002018-02-21T12:56:58.168+01:00Longest Common Subsequence of Two SequencesClose to the previous problem, where we had to compute the minimum edit distance between two strings, here we have to get the maximum number of common elements in the same order between two sequences.
The similarity drives us to look again for a Dynamic Programming solution (adding up to the hint that these problems are in the same lot).
Here is my python solution:
def solution_dp(lhs, rhs):
Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-28009778132423111872018-02-21T12:15:00.000+01:002018-02-21T12:25:43.110+01:00Computing the Edit Distance Between Two StringsGiven two strings, we should compute their edit distance. It is a well know problem, commonly solved by Dynamic Programming.
As we should expect, the idea is very close to the one seen in the previous problem, with the noticeable difference that here we are working on two lists, so our cache is going to be a bidimensional matrix and the complexity of the algorithm is moving to the O(n * m) realmMannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-59411667699350924052018-02-21T11:30:00.000+01:002018-02-21T11:38:09.604+01:00Primitive CalculatorWe always start from 1, and we get the positive integer we should get to. We could apply just three operations, multiply by 2, by 3, or adding one. Which is the minimum number of operations that gives us the expected result? Which sequence will be generated?
This problem is close to the previous one, about changing money. After all, are all part of the same lot about Dynamic Programming.
The Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-10966986458531232182018-02-21T10:45:00.000+01:002018-02-21T10:48:26.927+01:00Money Change AgainAlready seen as greedy problem, now we have to approach it with Dynamic Programming.
We have an integer, representing a total amount that we want to get adding coins of given denominations. Our job is finding the minimum number of required coins.
If the denominations are such that we can always guarantee a safe greedy choice, the greedy solution is better. However, if, as in this case, the Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-61886120712186130852018-02-21T10:21:00.002+01:002018-02-21T13:17:06.546+01:00Almost five Dynamic Programming problemsI'm following edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego, and I've just completed week five, that is about Dynamic Programming. To pass it, I had to solve a few problems, presented in this pdf.
Here I present them, my annotated python solutions in following posts.
Money Change Again
Given an integer amount, and an (infinite) numbers of coins of given denomination, Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-65980435446632546932018-02-19T14:15:00.000+01:002018-02-19T14:49:09.926+01:00The closest pair of pointsGiven n points on a plane, find the smallest distance between a pair of two (different) points.
Let's see first a naive solution:
def solution_naive(points):
size = len(points)
if size < 2: # 1
return 0.0
result = float('inf') # 2
for i in range(size - 1):
for j in range(i+1, size):
result = min(result, distance(points[i], points[j]))
return Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-50631507524022280852018-02-19T13:50:00.002+01:002018-02-19T14:36:50.830+01:00Majority elementGiven a list of integers, return 1 if there is an element that appears more than half the time in the list, otherwise 0.
Naive solution
Loop on all the items in the list, and count each of them. If we find a result that is bigger than half the size of the list, we have a positive result.
We can try to apply some improvement to this algorithm, for instance, we can stop checking as soon as we Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-9958005655715760892018-02-19T12:53:00.000+01:002018-02-19T14:34:57.258+01:00A few divide and conquer problemsThe exercises for week four of edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego are, in my opinion, a bit disappointing. I would have preferred if they pushed me to think more to how the divide and conquer strategy apply to different situation. Still, there are a few interesting points than we can get from them.
Binary Search
Task: Given in input two list of integers, Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-90683752419311957952018-02-13T11:18:00.000+01:002018-02-13T11:20:53.551+01:00Half a dozen of greedy problemsA small collection of greedy problems, as found in week three of edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego.
Kind of disappointing this third week of the course, since they removed the access to their online problem verifier for the unregistered user. Besides, these kind of problems loose large part of their appeal if you already know they could be solved following Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-71350529927066700142018-02-12T13:09:00.000+01:002018-02-13T09:56:18.282+01:00Last Digit of the Sum of Fibonacci NumbersAnother couple of problems in the same lot of the one previously discussed. Now we have to calculate the last digit of the (full or partial) sum of Fibonacci numbers.
Also these problems are presented in the the edX MOOC Algs200x Algorithmic Design and Techniques by the UC San Diego, week 2, so I suggest you to give them a try and then comparing your solutions with my python scripts.
Last DigitMannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-72437955464252819992018-02-09T11:30:00.000+01:002018-02-09T11:35:01.589+01:00Fibonacci modulo with Pisano periodDealing with Fibonacci numbers becomes easily unmanageable for big numbers. However, if we are not interested to the full number, but just to its modulo, there is a handy trick that would help us.
The thing is that if we have a look at the Fibonacci sequence after applying to each element a modulo operator, we would notice that we always get periodic sequences.
Modulo 2 leads to a infinite Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-8039004239233267522018-02-08T11:20:00.000+01:002018-02-08T11:23:16.045+01:00HackerRank DFS: Connected Cell in a GridIn this HackerRack problem, we are given in input an n x m matrix containing as elements just 0s and 1s. We should give as output the size of the largest available region.
As suggested in the name of the problem, we should think of a solution that refers to graphs, and more specifically on the Depth First Search algorithm on them.
To better understand what are we required to get, let's have a Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-71549717280732988712018-02-06T11:53:00.000+01:002018-02-06T12:15:17.581+01:00HackerRank Recursion: Davis' StaircaseThe point of this HackerRank problem is calculating a sort of uber-Fibonacci number. Since we want to have an efficient solution, we should immediately think to a dynamic programming approach, or at least to some kind of memoization.
Let's call Davis number the number of ways we can climb a staircase, with the rule that we can take 1, 2, or 3 steps at a time.
First thing, we want to identify Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-86746013207291382392017-12-27T22:25:00.000+01:002017-12-27T22:25:52.844+01:00HashMap.computeIfAbsent() behavior in Java 9If in your code you are using computeIfAbsent(), be aware that it has changed its behavior in Java 9. Now you get a ConcurrentModificationException if the mapping function changes the map.
So, for instance, this Fibonacci calculator works fine in Java 8:
class Fibonacci {
private static final Map<Integer, Long> cache = new HashMap<>();
static {
cache.put(0, 0L);
cache.putMannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-3824392553637805762017-10-10T11:07:00.001+02:002017-10-10T15:15:53.842+02:00CodeEval Lowest Unique Number revisedGiven a list of numbers, find the pne that is unique and have the smallest value. I have just provided a python solution to this CodeEval problem, but there was something in it that bothered me. So here I provide an alternative solution.
The soft spot in my previous solution was the combined sorting of the buffer counter dictionary added to a call to index() on the data list. I could live with Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-86039298622984100082017-10-09T16:09:00.000+02:002017-10-09T16:16:07.633+02:00CodeEval Lowest unique numberWe have a string in input containing numbers is the range [1 .. 9]. We want to get the index (following the unsettling Pascal habit of giving one for the first element) of the lowest unique number available, if such a beast exists, otherwise zero. This is the CodeEval problem #103.
So, for instance, given these two sequences:
3 3 9 1 6 5 8 1 5 3
9 2 9 9 1 8 8 8 2 1 1
In the first case we should Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-20054471743884371002017-09-30T10:54:00.001+02:002017-09-30T10:55:56.229+02:00CodeEval Pass TriangleWe are given as input a sequence of integers that we should think representing a triangle. We should return the maximum value we can get adding all values from the top vertex of the triangle down to the bottom, chosing a path moving always downwards between adjacent elements. This is CodeEval problem #89.
For example, if this is the triangle we get as input:
5
9 6
4 6 8
0 7 1 5
The expected Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-40879852846348504852017-09-20T09:55:00.000+02:002017-09-20T09:57:37.204+02:00CodeEval Query BoardWe have a square matrix of fixed size, and we receive a bunch of commands in input to operate on it. Two of them are about setting values on it, the other two perform a query and return an integer result.
This problem is quite simple, more detail on CodeEval #87, still, I'm writing a few lines about it because it gave me a way to exercise with a couple of Python features.
Mapping command names Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-64625651869406177832017-08-14T17:29:00.000+02:002017-08-14T17:33:19.493+02:00CodeEval Balanced SmileysThis problem is part of the family of the ones asking to check if parentheses in a sentence are balanced. See for instance the simpler matching brackets one.
In this version, happy ':)' and sad ':(' smileys could be part of the the sentence, so that we have to think if a parentheses has to be considered in the balancing or skipped, being the representation of the mouth of the smiley.
I found itMannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-8447873809304398432017-08-11T09:57:00.000+02:002017-08-20T22:50:38.823+02:00Calling a Stored Function from JDBCThe code we should write to call a stored procedure or function via JDBC is slightly different from the one we write to perform a SQL SELECT. A CallableStatement is used instead of a Statement plus a ResultSet to set the parameter, execute the call, and extract the result.
To check it, I have firstly created a stored function in my Oracle 12 instance, on the HR schema. It takes a SQL CHAR in Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-77169197149624581942017-08-08T10:56:00.000+02:002017-08-08T10:58:48.290+02:00Selecting on Oracle via JDBCOnce we decided how to establish a connection to the database, performing a SELECT on it is pretty simple. Here I'm going to use OracleDataSource as connection provider, using pure JDBC doesn't add any complexity.
The only problem in this Java code is that is slightly boring. So boring that there are a few wrapper aiming at keeping the advantages of JDBC easing its usage. See for instance the Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-49349869909252037672017-08-05T15:42:00.000+02:002017-08-08T10:47:02.266+02:00Connecting to Oracle via JDBCThere are a couple of ways to connect to a recent Oracle Database, going through the standard DriverManager class or the specific OracleDataSource one. Let's see both of them. And, when we are there, let's add also some consideration on connecting to MySql via DriverManager.
It's a bit of an overkill, but I have written a little abstract class that is going to be the root of a hierarchy of Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-50466021035975199292017-07-31T13:24:00.000+02:002017-07-31T13:24:03.897+02:00Installing and configuring Oracle 12cIt was a while since the last time I have installed an instance of the Oracle database for local use. Nothing much has changed in the process, with the noticeable exception of the introduction of pluggable databases. Here I jot down a few remarks I made during the setup of the version 12 release 2.
1. In the page Typical Installation we have to specify the name for our pluggable database. Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0tag:blogger.com,1999:blog-2597841815280998418.post-50957974835843726402017-07-28T10:26:00.001+02:002017-07-28T10:38:38.611+02:00CodeEval Minimum Path SumGiven a squared matrix of integers, find the minimal path sum from top-left to bottom-right, assuming that we can only move down or right.
This is CodeEval problem #72.
For example, give this matrix
4 6
2 8
We have just two possible paths: 4 -> 6 -> 8 and 4 -> 2 -> 8. It is immediate to see that the second one leads to the minimum sum of 14.
The structure of the problem recalls a Dynamic Mannyhttp://www.blogger.com/profile/07393063644320426727noreply@blogger.com0