Federico Mengozzi

Puzzle – Yet another subarray quiz

Maximum non adjacent subsequence

Find the non adjacent subsequence with maximum sum
Given an arrays of $A$ size $N$, find a sequence of non adjacent value with the larger sum, the sequence should be something like $A_i, A_{i+k}, A_{i+k’}, \cdots, A_{i+k^n}, \forall k > 1$It’s easy to solve this problem with dynamic programming Read More ›

Puzzle – An optimal solution

K-way merge

Merge K sorted container
Given $K$ sorted arrays (or any sequential container) of size $N$, merge them into one sorted array.Naive solutionA naive solution would require to inspect the first element of all $K$ array to find the minimum Read More ›

Data Structures – A new slightly improved version

Improving the Fibonacci Heap

Add a nodes pool and make it mergeable
Since my old post on the fibonacci-heap I made a few changes in the structure, cleaned the code and I had the chances to perform some other tests Read More ›

Linux – Step-by-step guide to get started

Manjaro-i3 on x1 Carbon

Post installation configuration for Manjaro-i3
Below the configuration of Manjaro-i3 that I use on my Lenovo x1 Carbon. Shell configuration and other info at manjaro-dotfiles. Read More ›

Puzzle – A linear solution

Longest positive subarray

Find the largest interval with positive sum
Given an array of $n$ non-all positive integer $a$, find the pair of indeces $(l, r) \in P$, where $P = \{(i, j) \mid 0 \leq i \leq j \le n, \sum\limits_{k = i}^{j} a[k] \geq 0 \}$ such that $r-l \geq i-j\ \forall (i, j) \in P$. Read More ›

Development – Merge branches with just one commit

A clean merge for branches

Keep master branch without intermediate commits
Once the work on a side branch is completed, usually all updates need to be merge to the master branch. To do that it’s possible to Read More ›

Data Structures – An efficent DSU implementation

Disjoint Set

Maximize performances using path compression and union by rank
A Disjoint Set data structure (or Disjoint-Set-Union DSU) allows to efficiently determine whether two elements belong to same set when those set are dynamic Read More ›

Development – Git's stack container for temporary changes

Stashing changes with Git

Move changes between different branches
When working on projects, sometimes, I found myself making changes in the wrong branch. Fortunately I discovered another amazing command in Git: git stash. Read More ›

Algorithms – Brandes’ algorithm for betweeness centrality

Betweeness Centrality

Implementation of Betweeness Centrality using Dijkstra and Fibonacci heap
The betweenness centrality is a measure of centrality in a graph based on shortest paths. It provide useful informationin any kind of situation where a network is involved Read More ›

Unix – Process handler for SIGCHLD signal

SIGCHLD Handler

Intercept SIGCHLD without polling or blocking
To prevent the accumulation of zombie children, a parent should wait to free their resources Read More ›

Go to top