04/07/2017
[Sheet music] Fabrizio de Andre - Il pescatore
A masterpiece. A poem in a song. Download it here
Tag:
Music
14/05/2017
[Java] Xchange me, sir - Sample REST project to get xrates to EUR
A while ago, while I was going through some interview rounds, a company that will be left unnamed, reluctantly assigned me a sample project to deliver as part of the interview process.
Very annoying though, was the fact that they had me book after some organisational pain, an hour of my time just to call and tell me in five minutes that it was highly unlikely I could deliver since I hadn't worked in Java recently.
Regardless of that quite bold and rude statement, I still asked to have the project just for practice anyway and they agreed, saying if I really wanted I could try and come back to them when I was done .
I of course did not plan to, but turning down some free exercise is never a smart choice, so I rolled with it.
Obviously they had never heard of Google as well, given that the whole project can easily be assembled just by searching code snippets and gluing them with minimal brainpower anyway if you are on a lazy mode day.
So long story short, here we are with the Xchange me, sir project.
Very annoying though, was the fact that they had me book after some organisational pain, an hour of my time just to call and tell me in five minutes that it was highly unlikely I could deliver since I hadn't worked in Java recently.
Regardless of that quite bold and rude statement, I still asked to have the project just for practice anyway and they agreed, saying if I really wanted I could try and come back to them when I was done
I of course did not plan to, but turning down some free exercise is never a smart choice, so I rolled with it.
Obviously they had never heard of Google as well, given that the whole project can easily be assembled just by searching code snippets and gluing them with minimal brainpower anyway if you are on a lazy mode day.
So long story short, here we are with the Xchange me, sir project.
Tag:
HowTo,
Java,
Publications,
Source code,
Spring
11/04/2017
[Java] Reverse doubly linked list
Here is a O(N) time and O(1) space method to reverse a doubly linked list:
You can check the implementation on my Gist along with the definition of the DoubleLinkedList class and some test cases.
//reverse doubly linked list
public static DoubleLinkedListNode reverseList(DoubleLinkedListNode head){
if(head == null) return head;
DoubleLinkedListNode prev = null;
while(head != null){
DoubleLinkedListNode next = head.next;
head.next = prev;
prev = head;
head = next;
}
return prev;
}
You can check the implementation on my Gist along with the definition of the DoubleLinkedList class and some test cases.
Tag:
HowTo,
Java,
JUnit,
Source code
09/04/2017
[Java] Find if binary tree is complete
A binary tree is complete if for each level, there are no holes between two children. For example:
complete =
A
B C
there are no holes between B and C
complete =
A
B
there are no holes after B
non complete =
A
C
there is a hole before C
You can the code on my Gist (isTreeComplete) along with some test cases:
complete =
A
B C
there are no holes between B and C
complete =
A
B
there are no holes after B
non complete =
A
C
there is a hole before C
You can the code on my Gist (isTreeComplete) along with some test cases:
/*
is tree complete
A tree is complete if for each level, there are no holes between children:
complete =
A
B C
no holes between B and C
complete =
A
B
no holes after B
non complete =
A
C
hole before C
*/
public static boolean isTreeComplete(BST root){
//null root is always complete
if(root == null) return true;
/*
otherwise, we must NOT have null nodes between two nodes at each level
so do a BFS BUT CAUTION: track also NULL children, then check we do not have a non null node after we encountered a null one
*/
Queue<BST> levels = new LinkedList<>();
boolean has_null = false;
levels.add(root);
while(!levels.isEmpty()){
BST t = levels.remove();
//if current node is not null
if(t != null) {
//if we had a null, fail
if(has_null) return false;
//otherwise add its children
levels.add(t.left);
levels.add(t.right);
}
//track if the node we just saw was null. CAUTION: do not overwrite it!
has_null = has_null || t == null;
}
//if we navigated the whole tree without problem, it is complete
return true;
}
Tag:
HowTo,
Java,
JUnit,
Source code
[Java] Find if a binary tree is balanced
A binary tree is balanced if the left and right branches do not differ in depth for more than one level.
Here is some code to test this (isTreeBalanced) you can check on my Gist for some test cases as well:
I use an additional data structure (Entry) to pass around two pieces of information:
- is the tree balanced so far
- what is the current depth of the path being analyzed
Here is some code to test this (isTreeBalanced) you can check on my Gist for some test cases as well:
/*
is tree balanced
A tree is balanced if the left and right branches do not differ for more than 1 level in length
*/
private static Entry isTreeBalancedAux(BST root){
//null root is always balanced
if(root == null) return new Entry(true, -1);
Entry left, right;
//check subtrees
left = isTreeBalancedAux(root.left);
right = isTreeBalancedAux(root.right);
//if they are not balanced, we have our answer
if(!left.isBalanced || !right.isBalanced) return new Entry(false, 0);
//otherwise if they are balanced, but they differ for more than 1 level in depth, this node is not balanced
if(Math.abs(left.height - right.height) > 1) return new Entry(false, 0);
//finally, if all is good, return the max depth from this node incuding itself and mark it as balanced
return new Entry(true, Math.max(left.height, right.height) + 1);
}
public static boolean isTreeBalanced(BST root){
return isTreeBalancedAux(root).isBalanced;
}
I use an additional data structure (Entry) to pass around two pieces of information:
- is the tree balanced so far
- what is the current depth of the path being analyzed
Tag:
HowTo,
Java,
JUnit,
Source code
[Java] Find depth of binary tree
Here is a simple method to find the depth of a given binary tree, no matter if it's balanced or not.
The null tree has depth -1, the root has depth 0 and so on. By looking at the depth it is immediately possible to get the max number of elements at that depth: 2^depth.
You can check the code on my Gist (getTreeDepth) along with some test cases:
The null tree has depth -1, the root has depth 0 and so on. By looking at the depth it is immediately possible to get the max number of elements at that depth: 2^depth.
You can check the code on my Gist (getTreeDepth) along with some test cases:
//find depth of the tree
public static int getTreeDepth(BST root){
if(root == null) return -1;
return Math.max(getTreeDepth(root.left), getTreeDepth(root.right)) + 1;
}
Tag:
HowTo,
Java,
JUnit,
Source code
[Java] LinkedList sum
Here's a simple exercise: given two positive numbers represented as linked lists, return their sum as a new linked list.
This is quite easy if we represent the two integers with lists that have the least significant digit at the head, eg:
A = 123 -> 3,2,1
B = 45 -> 5,4
result = 168 -> 8,6,1
You can check the code and some tests on my Gist (LinkedListSumJTests):
This is quite easy if we represent the two integers with lists that have the least significant digit at the head, eg:
A = 123 -> 3,2,1
B = 45 -> 5,4
result = 168 -> 8,6,1
You can check the code and some tests on my Gist (LinkedListSumJTests):
/*
Given two lists representing integer numbers
with the least significant digit in the head position
return a new list containing the sum
*/
public static SingleLinkedListNode sumListsFromLSD(SingleLinkedListNode x, SingleLinkedListNode y){
if(x == null && y == null) return null;
int carry = 0, curr = 0, val = 0;
SingleLinkedListNode result = null, n = null;
//keep going until we have data in either list and do not forget the last carry!
while(x != null || y != null || carry != 0){
curr = ((x == null || x.id == null) ? 0 : x.id) + ((y == null || y.id == null) ? 0 : y.id) + carry; //x + y + carry
val = curr % 10; //take only LSD
//track if we have a carry
carry = (curr >= 10) ? 1 : 0;
if(n == null){
n = new SingleLinkedListNode(val);
result = n;
}
else{
n.next = new SingleLinkedListNode(val);
n = n.next;
}
//move to next digit
if(x != null) x = x.next;
if(y != null) y = y.next;
}
return result;
}
Tag:
HowTo,
Java,
JUnit,
Source code
08/04/2017
[Java] Rolling average for both sorted and unsorted streams
The rolling, moving, running, whatever movement verb you like median or average is a problem regarding the online calculation of the average element in a streaming dataset.
The pro version requires you to sort the data on the fly in order to produce the median result:
input = 9, 4, 10, 3, 3
output = 4 because sorted input is: 3, 3, 4, 9, 10
The base version just wants the actual median element of the stream:
input = 9, 4, 10, 3, 3
output = 10
If the stream length is odd, the median is the actual median element, otherwise it's the average of the two elements near the middle of the stream.
The solution to both returns the median in constant O(1) time and keeps it updated in O(N) time. Also they both use additional O(N) space.
The pro version requires you to sort the data on the fly in order to produce the median result:
input = 9, 4, 10, 3, 3
output = 4 because sorted input is: 3, 3, 4, 9, 10
The base version just wants the actual median element of the stream:
input = 9, 4, 10, 3, 3
output = 10
If the stream length is odd, the median is the actual median element, otherwise it's the average of the two elements near the middle of the stream.
The solution to both returns the median in constant O(1) time and keeps it updated in O(N) time. Also they both use additional O(N) space.
Tag:
HowTo,
Java,
JUnit,
Source code
07/04/2017
[Java] Reconstruct binary tree from visits
An alternative way to represent a binary tree is to use an array. If the tree is a binary search tree and is also perfectly balanced, it's easy to find each node with the formula:
node = idx of node in array
left child = 2 * idx of node in array + 1
right child = 2 * idx of node in array + 2
But if the tree is not balanced, we need more information. For example, given a inorder and a postorder visit of the tree, we can rebuild it easily.
The idea is as such:
CAUTION: if we have duplicate values this method does not work because we search for unique integer items in both arrays. However, if we get an array of BST (nodes) as input instead, then it will work because each node is always equal to itself as object, without considering the content.
node = idx of node in array
left child = 2 * idx of node in array + 1
right child = 2 * idx of node in array + 2
But if the tree is not balanced, we need more information. For example, given a inorder and a postorder visit of the tree, we can rebuild it easily.
The idea is as such:
- in the preorder visit array at position 0 we have the root
- in the inorder visit array before the index of the root found at previous step, we have the left subtree and after we have the right subtree
- we can determine a range to search for our elements inside and recursively compute the left and right subtrees for each subroot
CAUTION: if we have duplicate values this method does not work because we search for unique integer items in both arrays. However, if we get an array of BST (nodes) as input instead, then it will work because each node is always equal to itself as object, without considering the content.
Tag:
HowTo,
Java,
JUnit,
Source code
[Java] Binary Tree visits
Given a binary tree, we have many ways of visiting it, depending on our goals:
- BFS: search tree by levels
- DFS inorder: visit root first, then left, then right
- DFS preorder: visit left, then root, then right. Useful to retrieve the tree values in ascending order
- DFS postorder: visit left, then right, then root. Useful when deleting the tree
You can check the code on my Gist.
BFS:
public static List<Integer> BFSVisitList(BST root){
if(root == null) return null;
List<Integer> out = new ArrayList<>();
Queue<BST> q = new LinkedList<BST>();
q.add(root);
while(!q.isEmpty()){
BST t = q.remove();
out.add(t.getVal());
if(t.left != null) q.add(t.left);
if(t.right != null) q.add(t.right);
}
return out;
}
public static int[] BFSVisit(BST root){
if(root == null) return null;
int[] res = null;
List<Integer> out = BFSVisitList(root);
if(out != null) res = out.stream().mapToInt(i -> i).toArray();
return res;
}
DFS - inorder:
private static List<Integer> doInorderVisit(BST root, List<Integer> out){
if(root != null){
doInorderVisit(root.left, out);
out.add(root.getVal());
doInorderVisit(root.right, out);
}
return out;
}
public static List<Integer> inorderVisitList(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doInorderVisit(root, out);
return out;
}
public static int[] inorderVisit(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doInorderVisit(root, out);
return out.stream().mapToInt(i -> i).toArray();
}
DFS - preorder:
private static List<Integer> doPreorderVisit(BST root, List<Integer> out){
if(root != null){
out.add(root.getVal());
doPreorderVisit(root.left, out);
doPreorderVisit(root.right, out);
}
return out;
}
public static List<Integer> preorderVisitList(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPreorderVisit(root, out);
return out;
}
public static int[] preorderVisit(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPreorderVisit(root, out);
return out.stream().mapToInt(i -> i).toArray();
}
DFS - postorder:
private static List<Integer> doPostorderVisit(BST root, List<Integer> out){
if(root != null){
doPostorderVisit(root.left, out);
doPostorderVisit(root.right, out);
out.add(root.getVal());
}
return out;
}
public static List<Integer> postorderVisitList(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPostorderVisit(root, out);
return out;
}
public static int[] postorderVisit(BST root){
if(root == null) return null;
ArrayList<Integer> out = new ArrayList<>();
out = (ArrayList) doPostorderVisit(root, out);
return out.stream().mapToInt(i -> i).toArray();
}
The code works with Java 8 because converting a List to an array[] is now super simple thanks to the black magic behind list.stream().mapToInt(i -> i).toArray()
Tag:
HowTo,
Java,
JUnit,
Source code
31/03/2017
[Java] Remove kth to last node in a singly LinkedList
Here is a simple method to remove the k-th to last element from a singly LinkedList (not the standard one). Runtime is going to be O(N) and space is going to be O(1). Keep scrolling for a better version that still runs in O(N) time - although actual better running time! - and O(1) space using two pointers.
The idea is simply to walk the list first to find out how many elements are there, then calculate which element we want to remove and walk the list again until we find and remove it. It is not possible to remove the head element, so we must return the, potentially new, head node after editing the list in place.
We count elements in the list starting from 1 so k = 0 means remove the last element and k = length - 1 means remove the first element. If k = length, we are asking to remove element 0 which does not exist.
You can check my Gist for the code with tests (RemoveKtoLastNode) and the LinkedList data structure (SingleLinkedListNode):
The alternative method using two pointers instead does not require us to calculate the list length beforehand, instead we let a pointer walk the list and start running a second pointer only after the first one has done K+1 steps. This means that when the first pointer reaches the end, the second will be exactly before the element to delete.
There is just one thing to be careful about: at the end the slow pointer might not be pointing anywhere. This means we might want to remove the head element or we got a K greater than the length of the list.
Here is the snippet from my Gist:
The idea is simply to walk the list first to find out how many elements are there, then calculate which element we want to remove and walk the list again until we find and remove it. It is not possible to remove the head element, so we must return the, potentially new, head node after editing the list in place.
We count elements in the list starting from 1 so k = 0 means remove the last element and k = length - 1 means remove the first element. If k = length, we are asking to remove element 0 which does not exist.
You can check my Gist for the code with tests (RemoveKtoLastNode) and the LinkedList data structure (SingleLinkedListNode):
//CAUTION: must return a value because otherwise we would not be able to remove the head element
public static SingleLinkedListNode removeKtoLastNode(SingleLinkedListNode head, int k){
if(head == null) return head;
int length = head.length();
/*
list is 1 to length, so check k is in that range
CAUTION: we are removing kth to last so k = 0 means remove last
k = length -1 means remove first
*/
if(k < 0 || k > length - 1) return head;
int n, count = 1;
SingleLinkedListNode prev = head, next;
//find out which element we want to remove
n = length - k;
//if it's the head, just return next
if(n == 1){
return prev.next;
}
//otherwise walk through the list and delete the desired element
while(prev != null){
next = prev.next;
//CAUTION: check with count + 1 so we do not skip the element we want to delete. next will be it!
if(n == count + 1){
if(next != null) prev.next = next.next;
//CAUTION: avoid NullPointerException when we are deleting tail
else prev.next = null;
return head;
}
prev = prev.next;
count++;
}
return head;
}
The alternative method using two pointers instead does not require us to calculate the list length beforehand, instead we let a pointer walk the list and start running a second pointer only after the first one has done K+1 steps. This means that when the first pointer reaches the end, the second will be exactly before the element to delete.
There is just one thing to be careful about: at the end the slow pointer might not be pointing anywhere. This means we might want to remove the head element or we got a K greater than the length of the list.
Here is the snippet from my Gist:
//CAUTION: must return a value because otherwise we would not be able to remove the head element
public static SingleLinkedListNode removeKtoLastNodePointers(SingleLinkedListNode head, int k){
if(head == null || k < 0) return head;
int fast_idx = 0;
SingleLinkedListNode fast = head, slow = null;
/*
keep two pointers running after each other
the slow one starts k+1 steps after the fast one
when the fast one reaches the end of the list, the slow one should be exactly before the element to remove
*/
while(fast.next != null){
if(slow != null) slow = slow.next;
fast = fast.next;
fast_idx++;
if(fast_idx == k + 1) slow = head;
}
//if the slow one is actually pointing somewhere, remove the following node
if(slow != null) slow.next = slow.next.next;
//otherwise if we want to remove the head (k = list length), just return the next from head
if(fast_idx == k) return head.next;
return head;
}
Tag:
HowTo,
Java,
JUnit,
Source code
[Java] Remove duplicates from a singly LinkedList
Here is a simple method to remove all duplicate nodes from a singly LinkedList (not the standard one) without using additional data structures. This means the runtime is going to be O(N^2) and space is going to be O(1).
The idea is simply to walk the list with a pointer and for each element walk the remainder of the list using two pointers. When we find a match to the element we are currently evaluating, we remove it. It is not possible to remove the head element, so we can edit the list in place.
You can check my Gist for the code with tests (RemoveDuplicates) and the LinkedList data structure (SingleLinkedListNode):
The idea is simply to walk the list with a pointer and for each element walk the remainder of the list using two pointers. When we find a match to the element we are currently evaluating, we remove it. It is not possible to remove the head element, so we can edit the list in place.
You can check my Gist for the code with tests (RemoveDuplicates) and the LinkedList data structure (SingleLinkedListNode):
public static void removeDuplicates(SingleLinkedListNode head){
SingleLinkedListNode curr, prev, next;
curr = head;
//for each single node
while(curr != null){
//track 2 nodes at the same time
prev = curr;
next = prev.next;
//walk the whole list
while(next != null){
/*
if the next node is a duplicate, delete it by linking the previous to the next.next
CAUTION: do NOT move the previous node because we could lose a value
*/
if(next.data == curr.data) prev.next = next.next;
//only move previous if the next one was unique
else prev = prev.next;
//move next to the new next element
if(prev != null) next = prev.next;
}
curr = curr.next;
}
}
Tag:
HowTo,
Java,
JUnit,
Source code
30/03/2017
[Java] Compress string by counting character repetitions
Here is a simple method to compress a string by counting the character repetitions and producing a new string containing that information; if the compressed string is longer, just keep the original one.
The idea is simply to walk the string keeping track of the current count for each item we encounter in two separate arrays. Then we walk both arrays at the same time and concatenate each character with the number of appearances he had; lastly we check if the compressed string is shorter and decide what to return.
You can check my Gist for the code (stringCompress) with tests:
The idea is simply to walk the string keeping track of the current count for each item we encounter in two separate arrays. Then we walk both arrays at the same time and concatenate each character with the number of appearances he had; lastly we check if the compressed string is shorter and decide what to return.
You can check my Gist for the code (stringCompress) with tests:
public static String stringCompress(String s){
if(s == null || s.length() <= 1) return s;
int[] counts = new int[s.length()];
char[] chars = new char[s.length()];
char c;
int j = 0;
counts[0] = 1;
chars[0] = s.charAt(0);
//for each character in string, count how many times it appears
for(int i = 1; i < s.length(); i++){
c = s.charAt(i);
if(c == chars[j]) counts[j]++;
else{
j++;
chars[j] = c;
counts[j] = 1;
}
}
//if we compressed the string a bit, then our arrays have some space left, mark the premature end
if(j < counts.length - 1) counts[++j] = -1;
//we do not want to create a new String everytime while we concatenate
StringBuilder sb = new StringBuilder();
j = 0;
while(j < counts.length){
if(counts[j] == -1) break;
//for each character in original string, concatenate it alongside the number of occurrences
sb.append(chars[j]);
sb.append(counts[j]);
j++;
}
//if the compressed string is longer, return original string instead
if(sb.length() > s.length()) return s;
return sb.toString();
}
Tag:
HowTo,
Java,
JUnit,
Source code
[Java] String replaceAll method from space to %20
Here is a simple method to replace all occurrences of space in a string with '%20' without using the replaceAll method.
The idea is to first count how many spaces are there in the string, then allocate a char array of appropriate size and fill it up correctly.
You can check my Gist for the code (replaceSpace) with tests:
The idea is to first count how many spaces are there in the string, then allocate a char array of appropriate size and fill it up correctly.
You can check my Gist for the code (replaceSpace) with tests:
public static String replaceSpace(String s){
if(s == null || s.length() == 0) return null;
int space_count = 0;
char c;
//count how many white spaces we have
for(int i = 0; i < s.length(); i++){
c = s.charAt(i);
if(c == ' ') space_count++;
}
if(space_count == 0) return s;
//allocate space for new string replacement. CAREFUL: we replace 1 char with 3 so we need 2 extra spaces!
char[] res = new char[s.length() + space_count * 2];
//prepare result string. CAREFUL: can't use same index otherwise we skip characters in either string or char[]
for(int i = 0, j = 0; j < s.length(); i++, j++){
c = s.charAt(j);
if(c == ' '){
res[i] = '%';
res[++i] = '2';
res[++i] = '0';
}
else res[i] = c;
}
return new String(res);
}
Tag:
HowTo,
Java,
JUnit,
Source code
29/03/2017
[Java] Find most consecutively repeated character in string
Here is a simple method to find the most consecutively repeated character in a string. In my view punctuation and case should not be ignored.
The idea is simply to walk the string keeping track of the current count for the item we're evaluating. When we encounter a different character, we check if the item we were evaluating appeared more times than the current max and if so, we set it as the current max.
You can check my Gist for the code (maxRepChar) with tests:
The Entry class is simply a helper structure:
char c;
int count = 0;
The idea is simply to walk the string keeping track of the current count for the item we're evaluating. When we encounter a different character, we check if the item we were evaluating appeared more times than the current max and if so, we set it as the current max.
You can check my Gist for the code (maxRepChar) with tests:
public static Entry maxRepChar(String s){
Entry max = new Entry(), curr = new Entry();
char c;
if(s == null || s.length() == 0) return null;
//initialize with first item in string
curr.count = 0;
curr.c = s.charAt(0);
max.count = 0;
for(int i = 0; i < s.length(); i++){
c = s.charAt(i);
/*
keep incrementing the current counter for the item we're evaluating now
as long as we have a subsequent uninterrupted stream
*/
if(c == curr.c) curr.count++;
else{
/*
when we interrupt the stream, check if the item we're evaluating
appeared more times than the current maximum, if so, set it as max
*/
if(curr.count > max.count){
max.count = curr.count;
max.c = curr.c;
}
//and reset the counter for current item
curr.c = c;
curr.count = 1;
}
}
//don't miss the case when the max run untils end of string
if(curr.count > max.count){
max.count = curr.count;
max.c = curr.c;
}
return max;
}
The Entry class is simply a helper structure:
char c;
int count = 0;
Tag:
HowTo,
Java,
JUnit,
Source code
27/03/2017
[Java] Check whether a string is palindrome
Here is a simple method to test if a string is palindrome. In my view punctuation should be ignored as well as case.
The idea is simply to walk the string from the borders towards the middle at the same time, skipping characters that are not alphanumeric until we either reach the middle or find two characters which are not same. Also, a single character is palindrome.
You can check my Gist for the code (isPalindrome) with tests:
The idea is simply to walk the string from the borders towards the middle at the same time, skipping characters that are not alphanumeric until we either reach the middle or find two characters which are not same. Also, a single character is palindrome.
You can check my Gist for the code (isPalindrome) with tests:
public static boolean isPalindrome(String s){
if(s == null || s.length() < 1)return false;
for(int i = 0, j = s.length() - 1; j > i; ){
if(!Character.isLetterOrDigit(s.charAt(i))){
i++;
continue;
}
if(!Character.isLetterOrDigit(s.charAt(j))){
j--;
continue;
}
if(Character.toLowerCase(s.charAt(i)) != Character.toLowerCase(s.charAt(j)))return false;
else{
i++;
j--;
}
}
return true;
}
Tag:
HowTo,
Java,
JUnit,
Source code
[Java] Trie data structure for text input prediction
A Trie is a very useful data structure with a confusing name, which is luckily easier to use than to pronounce.
I have seen it mainly used in input text suggestion or String analysis. The structure is a Tree where each node can have a label and multiple children; nodes with a label represent a full piece of data (eg a word) while nodes without label are used only for navigation or substring evaluation for example.
The list of children can be implemented with different data structures, I propose a version using a HashMap for faster searching: given an input String s, starting from the first character keep calling get(char) until we reach a word to suggest. Each get is O(1) so we are only paying O(M) (worst case is we're going to predict the longest string present).
Using a List would require us to scan the list until we find the entry for the next character which I think due to big-O magic can be assumed to still be O(1) since the list is at most as big as the alphabet we are using and therefore we can call it constant size, but still sounds like an unnecessary operation to me.
LinkedHashMap would not help much unless we associate some meaning with the insertion order eg: most often used words first.
TreeMap would slow the process down but guarantee to retrieve words in the desired order (eg alphabetical).
I have seen it mainly used in input text suggestion or String analysis. The structure is a Tree where each node can have a label and multiple children; nodes with a label represent a full piece of data (eg a word) while nodes without label are used only for navigation or substring evaluation for example.
The list of children can be implemented with different data structures, I propose a version using a HashMap for faster searching: given an input String s, starting from the first character keep calling get(char) until we reach a word to suggest. Each get is O(1) so we are only paying O(M) (worst case is we're going to predict the longest string present).
Using a List would require us to scan the list until we find the entry for the next character which I think due to big-O magic can be assumed to still be O(1) since the list is at most as big as the alphabet we are using and therefore we can call it constant size, but still sounds like an unnecessary operation to me.
LinkedHashMap would not help much unless we associate some meaning with the insertion order eg: most often used words first.
TreeMap would slow the process down but guarantee to retrieve words in the desired order (eg alphabetical).
Tag:
Java,
JUnit,
Source code
26/03/2017
[Java] 0/1 Knapsack problem O(n log n) heuristic
The 0/1 knapsack problem is a fairly common problem in daily life and it's unfortunately one of those problems where you must accept that the optimal solution cannot be computed as quickly as you would like, no matter how hard you think about the problem. As a friend put it, "if the solution looks like black magic, there is probably something wrong with it".
The problem description states: given a recipient with a fixed capacity and a set of items, each with a specific weight and value, the goal is to find the subset that maximises the total value of the chosen items while not exceeding the maximum recipient capacity.
In the 0/1 version, you cannot break an object (not possible to only take a fraction of it) so you can only either take it or not.
Sometimes calculating the optimal solution is too expensive or simply unfeasible (eg online knapsack) so a different, possibly suboptimal approach has to be taken. The one described here uses a greedy algorithm and aims at maximising the total value by selecting items after ordering them by desirability in terms of value per space left after they are picked.
The problem description states: given a recipient with a fixed capacity and a set of items, each with a specific weight and value, the goal is to find the subset that maximises the total value of the chosen items while not exceeding the maximum recipient capacity.
In the 0/1 version, you cannot break an object (not possible to only take a fraction of it) so you can only either take it or not.
Sometimes calculating the optimal solution is too expensive or simply unfeasible (eg online knapsack) so a different, possibly suboptimal approach has to be taken. The one described here uses a greedy algorithm and aims at maximising the total value by selecting items after ordering them by desirability in terms of value per space left after they are picked.
Tag:
Java,
JUnit,
Source code
20/03/2017
[SQL] Excel COUNTIFS - count columns matching criteria in a row
Excel in his arsenal of useful functions has COUNTIFS, basically a count of how many elements in a one dimensional range match a specific criteria. It says multidimensional, but it's not, it's either the same criteria twice for more dimensions or a different criteria. Key point: one list at a time.
However this is a very basic need which is not immediately achievable in SQL as well since we cannot loop over columns in a row. That is, unless we remember that PIVOTing is actually a thing. In this specific case we use the inverse operation, UNPIVOT.
[Java] Mergesort sorting algorithm for int arrays
Mergesort is well known as one of the best sorting algorithms out there with a O(n log n) worst case runtime; it doesn't get much better than this without strange big-O tricks.
But while understanding how it works is easy, implementing it is a different story given that it combines two nested function calls in the recursion and requires careful array index management. Also Java pass by value adds a small gotcha for good measure.
You can find my implementation for int[] arrays (as in: not Integer, not ArrayList, not List, not whatever else. Pure and simple int primitive data type with old fashioned array, the kind that does not change size once created if you can still remember those) on my Gist along with some test cases.
But while understanding how it works is easy, implementing it is a different story given that it combines two nested function calls in the recursion and requires careful array index management. Also Java pass by value adds a small gotcha for good measure.
You can find my implementation for int[] arrays (as in: not Integer, not ArrayList, not List, not whatever else. Pure and simple int primitive data type with old fashioned array, the kind that does not change size once created if you can still remember those) on my Gist along with some test cases.
Tag:
Java,
JUnit,
Source code
12/03/2017
[Python] BloggerBackup script to backup Blogger posts
This script allows users to quickly download posts from their Blogger blog in order to keep a backup copy. On Windows there is the amazing BloggerBackupUtility but sadly that's not available for Linux as well, hence this small project comes to life.
You can get the utility here or check out the source code here. To run it, you must have Python 3 installed.
Usage is:
options:
The script is extremely barebone and definitely improvable. Also, it requires you to setup an own API key in order to issue queries in the free tier. To do so, visit the Google credentials page.
You can get the utility here or check out the source code here. To run it, you must have Python 3 installed.
Usage is:
bloggerbackup --api-key <API key> --blog <blog URL> --backup-dir <backup directory> [--start-date <date>] [--end-date <date>] [--verbose]
options:
--help - prints this help
--api-key <api key> - mandatory API key used to issue queries
--blog <blog URL> - mandatory URL of the blog to operate on
--backup-dir <backup directory> - mandatory directory where to put the posts backup
--start-date <date> - optional, date from which to begin fetching posts in RFC 3339 format: yyyy-MM-ddTHH:mm:ss+HH:mm
--end-date <date> - optional, date where to stop fetching posts in RFC 3339 format: yyyy-MM-ddTHH:mm:ss+HH:mm
--verbose - optional, prints debug information while processing
The script is extremely barebone and definitely improvable. Also, it requires you to setup an own API key in order to issue queries in the free tier. To do so, visit the Google credentials page.
Tag:
Publications,
Python,
Source code
06/03/2017
[Java] BST element distance - parent pointer
Well, that's a bit anticlimactic. After playing with the other approaches, the one that initially gave me the most pain was also quite fast to implement as soon as the AHA! moment came.
However spoiler alert: the results are quite disappointing.
However spoiler alert: the results are quite disappointing.
Tag:
Java,
JUnit,
Source code
[Java] BST element distance - lowest common ancestor
So I was thinking about the parent pointer approach to find the distance between to elements in a binary search tree and avoiding using the path lists approach, which means finding the lowest common ancestor; that's the lowest node in the tree that is common to both paths to the two elements.
If the elements are one the child of the other, then it will be equal to the parent, otherwise it will either be the root if the elements are on completely different branches or the divergence node if the elements are in the same subtree.
Then I got down to coding and when I got to the LCA logic, finally, ... I did not use the parent pointer yet again :(
If the elements are one the child of the other, then it will be equal to the parent, otherwise it will either be the root if the elements are on completely different branches or the divergence node if the elements are in the same subtree.
Then I got down to coding and when I got to the LCA logic, finally, ... I did not use the parent pointer yet again :(
Tag:
Java,
JUnit,
Source code
[Java] BST element distance - path lists
The exercise that stole too much time from me last time was about binary search trees. The description is quite simple: find the distance between two elements in a given tree; that means how many hops do you need to do to navigate to element B from element A; if the elements are the same, distance is 0, if one or both elements are missing, distance is -1.
Tag:
Java,
JUnit,
Source code
04/03/2017
[Java] Scorecard algorithm
Some time ago I took an online coding test which left me with an unfinished exercise; I played too long with the other one and had no time to finish this :(
However it seemed quite easy and interesting so I decided to finish it later, here is the description of the exercise as I remember it and my solution:
Bill plays some kind of game where the score is tracked on a scorecard; in addition to simple scoring moves, he can attempt (and possibly fail) more rewarding moves that will influence the score calculation.
Bill starts with a score of 0 and cannot earn negative points.
Bill can alter his total score by:
However it seemed quite easy and interesting so I decided to finish it later, here is the description of the exercise as I remember it and my solution:
Bill plays some kind of game where the score is tracked on a scorecard; in addition to simple scoring moves, he can attempt (and possibly fail) more rewarding moves that will influence the score calculation.
Bill starts with a score of 0 and cannot earn negative points.
Bill can alter his total score by:
- scoring a point (integer) - it will be added to the total score
- doubling a previous score ("X") - the previous score will be doubled before adding it to the total score. If there is no previous score, it counts as 0
- summing two previous scores ("+") - the two precedent scores will be summed together before adding the result to the total score. If there are no predecessors, it counts as 0; if there is only one predecessor, it will be added again to the total score
- failing a move ("Z") - the previous score will be ignored from the total score and its value will also not be considered for subsequent special moves. If there is no previous score, this has no effects
Tag:
Java,
JUnit,
Source code
[Sheet music] Johann Pachelbel - Kanon
Tag:
Music
09/01/2017
[Oracle] Aurora module exception when compiling Java code on the DB
Sometimes it is possible to receive an exception when compiling Java code or running tools that generate Java code on the Oracle DB with this signature:
ORA-29516: Aurora assertion failure: Assertion failure at some_source:some_line_number
It is usually easy to prevent this error by disabling the JIT compilation on the DB:
alter session set java_jit_enabled = false;
ORA-29516: Aurora assertion failure: Assertion failure at some_source:some_line_number
It is usually easy to prevent this error by disabling the JIT compilation on the DB:
alter session set java_jit_enabled = false;
Subscribe to:
Posts (Atom)