tag:blogger.com,1999:blog-1859167416855250911Mon, 15 Jan 2018 16:32:35 +0000HowToSource codeJavaLinuxOracleMusicJUnitSQLWindowsWebMicrosoftTIBCOPL/SQLPublicationsSpotfireUbuntuApacheDebianOSGiPHPSpringEclipseLUbuntuXfceAPTExcelGRUBIronPythonLXDEPythonBusinessWorksCentOSCryptographyFedoraGNOMEGamesVmWareXUbuntuYumAppleGoogleChromeJavaScriptMatlabMySQLTomcatVirtualBoxiPhoneActiveSpacesAndroidAvaloqBusinessEventsFileZillaHTMLMATEPostgreSQLAccessApacheDSDOSEMSGhostscriptHANAHibernateJMSKodiLDAPLiferayLightDMMPlayerMozillaFirefoxOSIsoftOpenSSHPDFPulseAudioRPMRemminaSAPSFTPSSLSuseTOADVLCVimVisual BasicWineHQWiresharkxorgxtermScumm BarSpreading happiness since 1987http://groglogs.blogspot.com/noreply@blogger.com (Stefano Ghio)Blogger387125tag:blogger.com,1999:blog-1859167416855250911.post-708862719354046839Sun, 10 Dec 2017 15:54:00 +00002017-12-10T16:54:41.044+01:00HowToJavaJUnitSource code[Java] Self balancing AVL binary treeOh. my. god.<br /><br />This has definitely been the hardest one so far; I remembered the traumatic experience since the university time and also remembered why I hid it deep down.<br /><br />You can check the glorious <a href="https://wikimediafoundation.org/wiki/Ways_to_Give">Wikipedia</a> for the full description of the <a href="https://en.wikipedia.org/wiki/AVL_tree">AVL trees</a>, no need for me to repeat it there. I will however list some of the key points I found while implementing it:<br /><ul><li>draw the thing down. It is the best help you can get while your brain tries to make sense of this magic rocket science</li><li><b>TRACK THE HEIGHT, COMPUTE THE BALANCE</b>. This kept me stuck for eons, maybe it's possible to track the balance only as well and perform some more complex update logic, but I have no intention of going down the rabbit hole again for the moment :)</li><li>after inserting a node, backtrack to the root and perform rotations as needed. Update the heights while backtracking</li><li>not everyone defines right and left rotations the same way. Sometimes they are inverted in the directions they will actually rotate; end result in balancing terms is the same but naming might cause confusion. For me right rotate means: take the node, pull it down right and set his left child as parent. So for me: balance -2 means left heavy therefore a right (or right-left) rotation is needed</li></ul>You can find my implementation on my <a href="https://gist.github.com/steghio/ed5fc0607733b0566faa61d2b9a47ff9">Gist</a> in the BST package. The builder function is called buildBalancedAVL, along with extended test cases in <a href="https://gist.github.com/steghio/ed5fc0607733b0566faa61d2b9a47ff9#file-bstjtests-java">BSTJTests</a><br /><br />Lastly, I also link this super useful tool I found that helps with understanding the logic and checking the correctness of the results form the code: <a href="https://www.cs.usfca.edu/~galles/visualization/AVLtree.html">online AVL tree visualization</a>http://feedproxy.google.com/~r/groglogs/~3/nGlCBM-sQhQ/java-self-balancing-avl-binary-tree.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/12/java-self-balancing-avl-binary-tree.htmltag:blogger.com,1999:blog-1859167416855250911.post-6501981696892404383Tue, 21 Nov 2017 20:43:00 +00002017-11-21T21:43:37.685+01:00HowToJavaJUnitSource code[Java] Merge sorted filesHere is a problem that takes more time to code than to figure out: given N files where each line contains a timestamp (as long) and some data sorted in ascending order, merge them in a single file also sorted in ascending order.<br />The files can be arbitrarily big and are passed in input as a full path list; each has content in the format:<br /><br /><span style="font-family: "Courier New", Courier, monospace;">timestamp#data</span><br /><br />Since the files can be arbitrarily big, we might want to avoid loading them all into memory at once; we can instead keep an open pointer to each of them using O(N) additional space.<br /><br />This is not enough though, since we also need to write entries to the output file in ascending order too, which would be a big issue if the input files were themselves not ordered already. As long as they are already ordered, we can avoid using a mergesort modification for example and rely on a min heap (aka <i>PriorityQueue</i>) instead.<br /><br />We will read one line from each file and place it in the min heap which will be in size of O(N) as well and will have a O(log N) handling complexity. To understand later on which entry corresponds to which file and pointer, we use a custom structure <a href="https://gist.github.com/steghio/015dac3326d7cfe63223d16e60d2b515#file-fileentry-java">FileEntry</a> as object for the heap, meaning we override <i>equals</i>, <i>hashCode</i> and <i>compareTo</i> and we also use a <i>HashMap</i> from filename to <i>BufferedReader</i> so that we can quickly read the next line from each input file once we determine from which one we need to read next.<br /><br />We keep looping over the heap until it's empty, meaning we read all the lines and also wrote them out. For each element we remove from the heap, we add, if any, a new element (the next line to read) from the same source file; if the file is finished, we remove the reader from the map.<br /><br />Total runtime is O(N log N) and total space is O(N).<br /><br />The hardest part here is actually the handling of file <i>IOExceptions</i>, as we might have many <i>BufferedReaders</i> active at the same time and need to gracefully try to close all of them if we encounter an error during processing. The algorithm itself is quite short, but there is a lot of file handling code around it unfortunately; also some code was added to have a more graceful error handling, but it is not strictly necessary.<br /><br />You can check the implementation of <i>mergeSortedFiles</i> on my <a href="https://gist.github.com/steghio/015dac3326d7cfe63223d16e60d2b515">Gist</a> along with some test cases (STUB!) in <a href="https://gist.github.com/steghio/015dac3326d7cfe63223d16e60d2b515#file-mergefilesjtests-java">MergeFilesJTests</a>. This time I was too lazy to properly create JUnit tests for these File operations, so please check out the source and edit it as needed, also do NOT run ALL tests together: you will get a "file already exists" exception since the out file is created but never automatically deleted.http://feedproxy.google.com/~r/groglogs/~3/QdZRW_t0sCE/java-merge-sorted-files.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/11/java-merge-sorted-files.htmltag:blogger.com,1999:blog-1859167416855250911.post-4594204128359337033Tue, 14 Nov 2017 21:05:00 +00002017-11-14T22:05:25.791+01:00HowToJavaJUnitSource code[Java] Implement locking mechanism using a binary treeThis is an interesting exercise: implement a locking mechanism backed by a tree structure with parent pointers where a node can be locked if and only if none of his ancestors and descendants are locked.<br />Have the lock testing operation run in O(1) time, while the lock and unlock operations should run in O(H) time where H is the height of the tree.<br /><br />The fact that we are given the desired runtimes is the hint we need to understand how to implement this and the parent pointer is also a key element.<br />A lock testing operation in constant time means we are definitely tracking the information we need on the node itself.<br /><br />An O(H) lock and unlock operation means we are not scanning both branches of a node AND the ancestors every time we need to check whether any of those contains an already locked node.<br />The way we can accomplish this then, is if we are tracking an additional piece of information in each node and increase the complexity of both operations to maintain this information updated.<br /><br />If in each node we track for example the number of locked descendants in both subtrees, we would only need to test if any ancestor is locked during the lock operation before performing the lock and we would need to reduce the count of locked nodes in our ancestors during the unlock operation.<br /><br />You can check my implementation on my <a href="https://gist.github.com/steghio/ed5fc0607733b0566faa61d2b9a47ff9">Gist</a> along with some test cases in <a href="https://gist.github.com/steghio/ed5fc0607733b0566faa61d2b9a47ff9#file-bstlockjtests-java">BSTLockJTests</a>.<br /><br />I was a bit lazy so I reused an existing BST implementation that is not even fully balanced, but I am expanding this code and do not like rewriting too much :)http://feedproxy.google.com/~r/groglogs/~3/kHYdGwxThQg/java-implement-locking-mechanism-using.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/11/java-implement-locking-mechanism-using.htmltag:blogger.com,1999:blog-1859167416855250911.post-2185733632208634971Sun, 12 Nov 2017 13:59:00 +00002017-11-12T15:03:54.937+01:00HowToJavaJUnitSource code[Java] Find duplicate element in array with binary searchDisclaimer: this solution comes from <a href="https://www.interviewcake.com/question/java/find-duplicate-optimize-for-space">interviewcake</a>, where they mention this as being easier to (I guess) derive than the ones we saw before using <a href="https://groglogs.blogspot.ch/2017/11/java-find-duplicate-element-in-array-in.html">Floyd</a>'s and <a href="https://groglogs.blogspot.ch/2017/11/java-find-duplicate-element-in-array-in_12.html">Brent</a>'s cycle detection algorithms, but to be honest I feel the other way around. Plus bonus points because the graph solution is marked as BEAST MODE which definitely makes us feel proud when the implementation is done :)<br /><br />Anyway, we still want to keep space constant and not destroy the input, but we have no idea that graphs exist so what options are we left with?<br /><br />When searching for something, a good idea is to perform a binary search. In our case though, the input structure is not really built in a way where we can safely apply the algorithm since the array is not ordered. But this problem is very specific: given a series of N+1 items in the range 1 to N, find one of the duplicates.<br /><br /><a name='more'></a><br />Well then, what if we do not care much about the array we are given as input and focus on the actual search range we have: 1..N. Our duplicate item MUST be in there, since that is the problem definition. Now we suddenly have an ordered array the is perfectly suitable for binary search, but what are we searching for?<br /><br />If we split the search range in two halves: 1..N/2 and (N/2 + 1)..N we know for sure at least one of the two halves contains at least one duplicate element. Therefore we can evaluate the full array against the search range and compare the number of items found in the range against the expected number of items in that range; if they do not match, our duplicate is definitely there.<br /><br />We can keep iterating (NO recursion, otherwise space cost is no longer constant) until the search space is only one element, our duplicate.<br /><br /><b>Gotchas</b>:<br /><br /><span style="font-family: "courier new" , "courier" , monospace;">mid = <b>floor +</b> ((ceil - floor) / 2);</span><br /><br />tattoo that stuff somewhere, it is the binary magic sauce. You miss that, it will never work.<br /><br /><span style="font-family: "Courier New",Courier,monospace;">floor = 1;</span><br /><br />This is your starting range floor. NOT 0, we are NOT walking through the array, but through the SEARCH SPACE 1..N.<br /><br />You can find the implementation of <i>findRepeatBinarySearch</i> on my <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7">Gist</a> along with some test cases in <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7#file-findrepeatjtests-java">findRepeatJTests</a> and a timing comparison with the <i>findRepeatBrent</i> implementation; in this case the difference is absolutely evident.http://feedproxy.google.com/~r/groglogs/~3/dNZBmw5pvU0/java-find-duplicate-element-in-array.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/11/java-find-duplicate-element-in-array.htmltag:blogger.com,1999:blog-1859167416855250911.post-2259156825409227462Sun, 12 Nov 2017 12:34:00 +00002017-11-12T15:00:32.416+01:00HowToJavaJUnitSource code[Java] Find duplicate element in array in constant space and linear time v2Well a good night's sleep always helps apparently. Yesterday we saw how to <a href="https://groglogs.blogspot.ch/2017/11/java-find-duplicate-element-in-array-in.html">find a duplicate element in a constrained array in linear time and constant space</a> and based the implementation for the cycle detection on Floyd's algorithm.<br />Today we do the same, but use <a href="http://maths-people.anu.edu.au/~brent/pd/rpb051i.pdf">Brent's algorithm</a> instead which supposedly should be overall faster. <br /><br />You can find the implementation of <i>findRepeatBrent</i> on my <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7">Gist</a> and I also provide some timings comparison in the <i>compareFloydAndBrent</i> method in my test cases <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7#file-findrepeatjtests-java">FindRepeatJTests</a>. Of course you need multiple runs and maybe a bigger input as well to appreciate the difference, but it appears that overall there is a small performance improvement with Brent's method.<br /><br />You can also find here an implementation that is slower O(N log N) and still uses constant space, based on <a href="http://groglogs.blogspot.ch/2017/11/java-find-duplicate-element-in-array.html">binary search</a>. http://feedproxy.google.com/~r/groglogs/~3/jwgCL2XSDfU/java-find-duplicate-element-in-array-in_12.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/11/java-find-duplicate-element-in-array-in_12.htmltag:blogger.com,1999:blog-1859167416855250911.post-5026689341889653090Sat, 11 Nov 2017 17:54:00 +00002017-11-12T15:00:45.128+01:00HowToJavaJUnitSource code[Java] Find duplicate element in array in constant space and linear timeSooo.. spoiler alert: this one was way harder than it should be thanks to <a href="https://softwareengineering.stackexchange.com/questions/110804/why-are-zero-based-arrays-the-norm/110836#110836">0-index arrays</a>.<br /><br />Given an array of integers in the range 1..N and length N+1 find one of the possible duplicate elements in O(N) time and O(1) space WITHOUT altering the input.<br /><br />Those constraints are quite strong since finding a duplicate in O(N) time and space is pretty easy: place all elements in a HashSet while iterating over the input and return as soon as a duplicate is found.<br /><br />Finding a duplicate in O(N log N) time and O(log N) space is also easy: sort the input - using a kickass quicksort implementation otherwise good luck keeping those costs down - and then walk over it comparing elements in pairs until the duplicate is found.<br /><br />Finding it without destroying the input and without using additional space is also easy in O(N^2) time: for each element, loop over the full array until a duplicate is found.<br /><br /><a name='more'></a><br />Now, for the real men challenge instead: O(N) time, O(1) space, NO input altering. This is possible only thanks to the nature of the problem itself: we are given N+1 elements in range 1 to N, so there is at least one duplicate.<br /><br />Well then, what if we stop caring about the array and the elements themselves and switch point of view on the problem: consider each element in the array as a node in a graph whose value is the pointer to a <b>single</b> other node.<br /><br />Since we know there is at least one duplicate, the graph must contain at least one loop. Therefore we now simply need to identify the <a href="https://en.wikipedia.org/wiki/Cycle_detection">loop start position</a>.<br /><br />As starting position we must choose the end of the array (N+1), since we know no element can ever point to it (range 1 to N), therefore we will move at least once before entering in a loop avoiding unlucky self loops in the start.<br /><br />Now why is this more complex than it appears? The magic behind the 0-index arrays. We need to shift all our reasoning to reflect that fact while walking over the graph; this by itself would not be a big issue, but it makes the classical off by one errors easy to encounter.<br /><br />You can check my implementation of <i>findRepeat</i> on my <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7">Gist</a> along with some test cases in <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7#file-findrepeatjtests-java">FindRepeatJTests</a>.<br /><br />You can find here the <a href="http://groglogs.blogspot.ch/2017/11/java-find-duplicate-element-in-array-in_12.html">implementation using Brent's algorithm</a> instead as well as a timing comparison.<br /><br />You can also find here an implementation that is slower O(N log N) and still uses constant space, based on <a href="http://groglogs.blogspot.ch/2017/11/java-find-duplicate-element-in-array.html">binary search</a>. http://feedproxy.google.com/~r/groglogs/~3/uvcmYKb76gs/java-find-duplicate-element-in-array-in.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/11/java-find-duplicate-element-in-array-in.htmltag:blogger.com,1999:blog-1859167416855250911.post-2046168816081488607Thu, 09 Nov 2017 20:34:00 +00002017-11-09T21:34:43.610+01:00Music[Sheet Music] Ludovico Einaudi - DivenireA contemporary masterpiece, you can find here the <a href="https://1drv.ms/u/s!Ama1h4Pgj0YZgatNw5spRB60jk1KdA">full album</a>.http://feedproxy.google.com/~r/groglogs/~3/8Ug9LIA4uU8/sheet-music-ludovico-einaudi-divenire.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/11/sheet-music-ludovico-einaudi-divenire.htmltag:blogger.com,1999:blog-1859167416855250911.post-919816901168227124Tue, 07 Nov 2017 21:39:00 +00002017-11-07T22:39:54.954+01:00HowToJavaJUnitSource code[Java] Convert expression to reverse polish notationThe closing chapter of my <a href="https://groglogs.blogspot.ch/2017/11/java-evaluate-reverse-polish-notation_5.html">RPN</a> journey, how to convert an infix notation expression to a postfix notation one, so from <i>3 + 4</i> we get <i>3 4 +</i><br /><br />Here as well it appears immediately that a String is not the most comfortable input structure, so we stick to an array.<br />First idea was to scan the input and tokenize it in a left side portion and right side portion for each operator we found:<br /><br /><i>3 - 4 x 5</i><br /><br />would become first:<br /><br /><i>3, 4 x 5, -</i><br /><br />Then finally:<br /><br /><i>3, 4, 5, x, -</i><br /><br /><a name='more'></a><br />This would also work with parentheses but it poses a challenge on how to recognize the portion to process, meaning we would work in square time if we need to scan the array every time in order to find the ending portion of the subexpression we are evaluating. Maybe this drawback could be eased by keeping a pointer that delimits the search area and decreases its size with every search, but it already looks a bit complicated.<br /><br />Second idea building on that one, is to create a structure to help with this kind of processing, such as a tree, then to get result we would do a postorder traversal. This idea sounds already better but with a small caveat in that building the tree correctly is not very easy to handle; we have to handle many subtrees which - if the expression is well formed - would be merged into a single one in the end. By the way, this approach is useful when parsing more complex expressions or languages and generates a tree known as <a href="https://en.wikipedia.org/wiki/Abstract_syntax_tree">abstract syntax tree</a>.<br /><br />Now, can we do better than that for this specific problem? Well, yes. Dijkstra - this guy was a genius - comes to rescue with his <a href="https://en.wikipedia.org/wiki/Shunting-yard_algorithm">shunting yard algorithm</a> which gives a simple process to parse the input expression and generate the RPN version in O(N) time and space. Given that's his algorithm, I will not repeat the description and you can find my implementation for <i>convertToRPN</i> on my <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7">Gist</a> along some test cases in <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7#file-rpnjtests-java">RPNJTests</a>.<br /><br />I just have a small note on the algorithm as described on the Wikipedia page; the pseudocode says:<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"> if the token is an operator, then:<br /> while <b>there is an operator at the top of the operator stack</b> with<br /> greater than or equal precedence and the operator is left associative:<br /> pop operators from the operator stack, onto the output queue.<br /> push the read operator onto the operator stack.</span></span><br /><br />Pay attention to the marked part, it implicitly means that encountering a parenthesis would break the loop :)<br />This expression would otherwise fail:<br /><br /><i>(3 - 4) x 5</i><br /><br />Since when we encounter '<i>-</i>' we have no idea how to compare it to '<i>(</i>' which is at the top of the stack<br /><br /><br />http://feedproxy.google.com/~r/groglogs/~3/bex9CtC9BjE/java-convert-expression-to-reverse.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/11/java-convert-expression-to-reverse.htmltag:blogger.com,1999:blog-1859167416855250911.post-7834116732323916966Sun, 05 Nov 2017 12:39:00 +00002017-11-07T22:41:02.184+01:00HowToJavaJUnitSource code[Java] Evaluate reverse polish notation in constant spaceYes it is possible, yes it took me one full day research included, but the <a href="https://groglogs.blogspot.ch/2017/11/java-evaluate-reverse-polish-notation.html">RPN</a> can be evaluated in O(N) time and O(1) space, sacrificing the input in the process.<br /><br />There are some key points to this but let's start with the general idea. To get the algorithm down from O(N) space (the stack) to O(1) we cannot use additional costly structures; luckily our input is all we need, if we are allowed to destroy it while processing. This is often the case with this type of optimization, an <a href="https://en.wikipedia.org/wiki/In-place_algorithm">in place algorithm</a>.<br /><br />Consider the following expression corresponding to <i>3 - (4 x 5)</i>: <i>3 4 5 x -</i><br /><br />For RPN <b>reading from left to right</b>, the operator always follows the two operands it should work on and once we evaluated an expression, we no longer need the original data but only the result, so <i>3 4 5 x -</i> can be rewritten as <i>3 20 -</i><br /><br />We can therefore <b>recycle the processed space</b> (always 3 elements, two operands and an operator) in the input structure to somehow track which elements should we process next. This means we need to point to the next unprocessed element in the sequence, so that the next operator can retrieve its two operands as if they were adjacent.<br /><i></i><br /><a name='more'></a><i> 3 4 5 x -</i> should become <i>3 goto:0 20 null -</i> so that when we process the minus operator, we know 20 is the second operand and the item in position 0 is the first operand.<br /><br />Where and how do we store this information? To keep life easy, we can replace the processed operator with the result of the operation, so the next operator can retrieve its <b>second operand</b> (<b>RPN left to right!</b>) quickly as it will always be there at the <b>index before</b> the operator.<br />The <b>first operand</b> instead will either be at <b>two indexes before</b> the operator <b>or</b> at the <b>position</b> designated by the <b>pointer</b> found there, something like:<br /><br /><i>3 null goto:0 20 -</i> <br /><br />Now, how do we know if we have a pointer? We place at the index <b>preceding</b> it a special marker (eg a null value), so that we know whatever element follows it is not a value but a pointer to a value.<br /><br />Some ideas here: <br />- We could put both marker and <b>pointer</b> together as a <b>string</b>, but then we would need to perform a <b>substring</b> operation to retrieve the pointer index, and although on the overall complexity this should not have a big impact, it will still make the algorithm run slower O(N x M) where M is the cost of the substring operation; if M << N, it could be considered negligible.<br />- Actually, the first version I tried had the <b>marker following the pointer</b>:<br /><br /><i>3 0 goto 20 -</i><br /><br />But I could not make it work having issues with the correct handling of pointer operations and out of bounds checks, so I was stuck there until I remembered Google exists and I found this <a href="https://discuss.leetcode.com/topic/67582/accepted-the-best-complexity-o-n-time-o-1-space-well-explained-javascript">awesome post</a> that explained the same algorithm BUT the <b>marker is BEFORE the pointer</b>! And now life smiles :) I still think it should work the other way as well, but I have to finish testing.<br /><br />Last thing to note, we <b>cannot afford the need to follow multiple pointers</b>, otherwise the time would increase to O(N^2) territory because we might need to follow many pointers in a row to find the information we need. To keep this in check, when we update the values to maintain the new pointers, if we determine that we would be pointing to a pointer, we point directly to its value instead. We therefore create a single jump that keeps the retrieval operation in constant time. Eg a situation like:<br /><br /><i>3 goto0 goto1 20 -</i><br /><br />With two pointer jumps, has to be instead:<br /><br /><i>3 goto0 goto0 20 - </i><br /><br />With a single pointer jump. You can't really miss this because the multiple pointer jump forces you to use a loop in the code, and a loop inside a loop is always a warning for potential square time complexity.<br /><br /><b>tl;dr</b>, we can now process the input in one pass with no extra space. Everytime we encounter an operator, we:<br />1) retrieve second operand at the index before<br />2) retrieve first operand at two indexes before OR at the index specified by the pointer at that location<br />3) store the result of the operation in place of the operator<br />4) update the pointers<br /><br />To update the pointers:<br /><br />- if <b>we were not a pointer</b> (no null preceding us), <b>set us as marker</b> and <b>point to the element before us</b> (set the next element to us - 1). This could be a value or a pointer, but in either case we are fine. <b>Do this if we are the very first element as well</b>, otherwise we will end up with an IndexOutOfBounds exception when we try to access the item at index -1. This means we create a useless pointer but luckily we will never access it if the expression is well formed<br />- if <b>we were a pointer</b>, retrieve the value at the location and <b>check the element before us</b>. If the item preceding it (us - 2) <b>is a pointer</b>, <b>copy the pointer value</b>, otherwise if it is <b>not a pointer</b>, <b>point to it</b><br /><br />Now in the main function that parses the input one item at a time, the main difference is the order and way of retrieving the operands. Always go with the <b>SECOND operand first,</b> this can always be retrieved directly at <b>index - 1</b>. Then get the <b>FIRST operand</b>, this need to call the <b>helper function</b> to retrieve the correct value and update the pointers too; no need to use this function twice.<br /><br />You can check the implementation on my <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7">Gist</a> for <i>evaluateRPNinPlace</i> along with some test cases in <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7#file-rpnjtests-java">RPNJTests</a>.<br /><br />You can find here the code to <a href="http://groglogs.blogspot.ch/2017/11/java-convert-expression-to-reverse.html">convert an expression to reverse polish notation</a>. http://feedproxy.google.com/~r/groglogs/~3/wZGCM07esTI/java-evaluate-reverse-polish-notation_5.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/11/java-evaluate-reverse-polish-notation_5.htmltag:blogger.com,1999:blog-1859167416855250911.post-7741972556120306755Sat, 04 Nov 2017 15:43:00 +00002017-11-07T22:41:09.471+01:00HowToJavaJUnitSource code[Java] Evaluate reverse polish notation using a stack<a href="https://en.wikipedia.org/wiki/Reverse_Polish_notation">Reverse polish notation</a>, aka the WTF! way of writing arithmetical expressions, presents an interesting exercise on stacks.<br /><br />The goal is to write a program to evaluate RPN expressions eg: <i>3 4 +</i> would return 7.<br /><br />The input can be passed in many ways, good candidates are arrays and lists, a stack directly or a string, although in this case, you would need a separator character to understand when does a number start and end.<br /><br />The idea here is to process the input sequence from left to right without creating the stack beforehand. If we encounter a number (operand), we push it onto the stack and when we encounter an operator, we pop two items from the stack, then apply the operator in the (<b>gotcha!</b>) REVERSE order because the stack is LIFO and this matters for the asymmetrical operations such as - and /<br /><br />An interesting note, dividing by 0 a double will NOT throw an exception, we must test if we got infinite as result!<br /><br />For the implementation I use a String array as input and a Double stack to allow decimal results. Only the four basic operations (sum, subtraction, multiplication, division) are supported, but the code can easily be expanded to support more and even unary operations (pop one item instead of two).<br /><br />As last note: why can't we do this in constant space while parsing the string itself? Because of situations such as: <i>3 - (4 x 5)</i> which translates to <i>3 4 5 x -</i><br /><br />Therefore we cannot expect an operator to always follow two operands.. So: String as input = bad.<i> </i><br /><br />The current implementation therefore uses O(N) space and time. But you can check here for an <a href="http://groglogs.blogspot.ch/2017/11/java-evaluate-reverse-polish-notation_5.html">implementation that uses O(N) time and O(1) space</a>!<br /><br />You can check the implementation on my <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7">Gist</a> along with some test cases in <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7#file-rpnjtests-java">RPNJTests</a>.<br /><br />You can find here the code to <a href="http://groglogs.blogspot.ch/2017/11/java-convert-expression-to-reverse.html">convert an expression to reverse polish notation</a>. http://feedproxy.google.com/~r/groglogs/~3/5OD2K3JBYTA/java-evaluate-reverse-polish-notation.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/11/java-evaluate-reverse-polish-notation.htmltag:blogger.com,1999:blog-1859167416855250911.post-4374389262226461700Thu, 02 Nov 2017 20:22:00 +00002017-11-02T21:22:38.787+01:00HowToJavaJUnitSource code[Java] Generate string permutations recursivelyAhhhh, string permutations. The timeless classic. Also painfully slow with its O(N!) time and space complexity. Let's put a twist on it and do it recursively just because we can.<br /><br />Also, just because we can, we <a href="https://stackoverflow.com/questions/2971315/string-stringbuffer-and-stringbuilder" target="_blank">use StringBuilders instead of Strings</a>. Is this a good idea? Is the cost of creating lots of <a href="https://docs.oracle.com/javase/7/docs/api/java/lang/StringBuilder.html" target="_blank">StringBuilders</a> offsetting the cost of creating a new String object everytime? That's what <a href="https://stackoverflow.com/questions/180158/how-do-i-time-a-methods-execution-in-java" target="_blank">method timing</a> is for, we'll leave this as "exercise" for the reader.<br /><br />Anyway, enough introduction, let's go to the meat: we call a recursive method which will have as input the size of the result string to create, the string we built so far, the string of unused characters so far and the output collection.<br /><br />Then, for each unused character, we add it to the current string and recurse on the remaining ones leaving that out. The base case is when we no longer have characters to use; if the string we built is the correct length, we add it to the result set and return, otherwise simply return.<br /><br /><b>Note</b>: <a href="https://docs.oracle.com/javase/7/docs/api/java/lang/StringBuilder.html#deleteCharAt(int)">StringBuilder.deleteCharAt</a> alters the source directly instead of returning a new object, therefore calling this method as <i>StringBuilder(x.deleteCharAt)</i> and <i>StringBuilder(x).deleteCharAt</i> makes quite the difference!<br /><br />You can check the implementation on my <a href="https://gist.github.com/steghio/2855fc32d2b0cd226b2117cd3fc43154">Gist</a> along with some test cases in <a href="https://gist.github.com/steghio/2855fc32d2b0cd226b2117cd3fc43154#file-permutatejtests-java">PermutateJTests</a>.<br /><br />http://feedproxy.google.com/~r/groglogs/~3/JxyE5wJdWPY/java-generate-string-permutations.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/11/java-generate-string-permutations.htmltag:blogger.com,1999:blog-1859167416855250911.post-791207264659643690Wed, 01 Nov 2017 21:03:00 +00002017-11-01T22:03:43.613+01:00HowToJavaJUnitSource code[Java] Zip singly linked listList zipping means interleaving the list nodes from the top and bottom of a given list to create a new list.<br /><br />Eg with this input list:<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">A -> B -> C -> D</span></span><br /><br />the zipping is:<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">A -> D -> B -> C</span></span><br /><br />Doing this in constant space and quadratic time is trivial, but there is a better solution that avoids scanning the list every time with two pointers running one ahead of the other to find the current last element in the list.<br /><br />Again as with most linked list problems, the correct handling of the pointers is the trickiest part. The idea is to spend some time to preprocess the list in O(N) time to split it in two halves, and reverse the second half; this way, we now simply need to walk both lists and interleave the nodes in order to produce our result.<br /><br /><a name='more'></a><br />Finding the middle point is easy using the fast and slow pointers method .<br /><br /><b>First gotcha</b>: after finding the middle point, remember to use <i>slow.next</i> to mark the start of the second half and then set it to null to truncate the list there!<br /><br />The code to reverse a singly linked list efficiently can be found <a href="http://groglogs.blogspot.ch/2017/11/java-reverse-singly-linked-list.html" target="_blank">here</a>.<br /><br />After the list is split and the second half is reversed, use two pointers to track the current elements in both lists, plus an auxiliary element to handle the switching. Based on the way we find the half point, the second half will never have more elements than the first half; this is an important note for the looping we'll do later.<br /><br />The logic then is as follows:<br /><br />As long as there are elements in the second half, keep interleaving <b>starting from the second half</b>!<br /><br />1) track the next element from the last<br />2) link the next last element to the next first<br />3) link the next first element to the last element<br />4) move the first pointer to the next element <b>passing through the added node</b>!<br />5) move the last element to the tracked one<br /><br />Easier with a picture maybe. <i>F</i> (first) is pointer to the current element in the first list, <i>L</i> (last) is pointer to the current element in the second list, <i>T</i> is temp node<br /><br />Input is:<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">A -> B -> C -> D -> E</span></span><br /><br />1st iteration:<br /><br /><i>F</i> points to <span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">A -> B -> C</span></span><br /><i>L</i> points to <span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">E -> D</span></span><br /><br />1st step, <i>T</i> points to <i>D </i>(<span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">E -> D</span></span>)<i><br /></i><br />2nd step, link <span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">E -> B</span></span><br />3rd step link <span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">A -> E</span></span><br />4th step <i>F</i> points to <i>B</i> passing through <i>E</i> (<span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">A -> E -> B</span></span>)<br />5th step <i>L</i> points to <i>T</i> which was pointing to <i>D</i><br /><br />the partial result is:<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">A -> E -> B -> C</span></span><br /><br />2nd iteration:<br /><br />1st step <i>T</i> points to null (<span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">D -> null</span></span>)<br />2nd step, link <span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">D -> C</span></span><br />3rd step, link <span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">B -> D</span></span><br />4th step <i>F</i> points to <i>C</i> passing through <i>D</i> (<span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">B -> D -> C</span></span>)<br />5th step <i>L</i> points to <i>T</i> which was pointing to null<br /><br />the partial result is:<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">A -> E -> B -> D -> C</span></span><br /><br />And since <i>L</i> is now pointing to null, there are no more elements in the second half of the list, therefore we have our output.<br /><br />This logic sound complicated, but it translates to 6 lines of code, parenthesis excluded.. magic! <br /><br />You can check more singly and doubly linked lists utilities on my <a href="https://gist.github.com/steghio/93ebdfa1c12009d8036514ae3d62b222" target="_blank">Gist</a> along with some test cases in <a href="https://gist.github.com/steghio/93ebdfa1c12009d8036514ae3d62b222#file-ziplistjtests-java" target="_blank">ZipListJTests</a>. http://feedproxy.google.com/~r/groglogs/~3/s91lwBaUG3c/java-zip-singly-linked-list.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/11/java-zip-singly-linked-list.htmltag:blogger.com,1999:blog-1859167416855250911.post-233815010477200241Wed, 01 Nov 2017 20:39:00 +00002017-11-01T21:39:22.633+01:00HowToJavaJUnitSource code[Java] Reverse singly linked listHere is a simple algorithm to reverse a singly linked list in O(N) time and O(1) space. The only tricky part is the correct handling of the pointers :)<br /><br />The idea is to start with a previous pointer to null and a pointer to the head of the list, then:<br /><br />1) track the next element in a temporary variable<br />2) reverse the current element pointer<br />3) consider the current element as the previous for next iteration<br />4) move the current element to the next one to handle<br />5) when no more elements are left to be processed, the previous pointer will be the new list head<br /><br /><pre style="font-family:arial;font-size:12px;border:1px dashed #CCCCCC;width:99%;height:auto;overflow:auto;background:#f0f0f0;padding:0px;color:#000000;text-align:left;line-height:20px;"><code style="color:#000000;word-wrap:normal;"> //reverse singly linked list <br /> public static SingleLinkedListNode reverseList(SingleLinkedListNode head){ <br /> if(head == null) return head; <br /> <br /> SingleLinkedListNode prev = null, next, curr = head; <br /> <br /> /* <br /> 1) track next element <br /> 2) reverse current element pointer <br /> 3) track current element as previous for next iteration <br /> 4) move current element to the next one to handle <br /> */ <br /> while (curr != null) { <br /> next = curr.next; <br /> curr.next = prev; <br /> prev = curr; <br /> curr = next; <br /> } <br /> <br /> //at this time this will point to the beginning of the reversed list! <br /> return prev; <br /> } <br /></code></pre><br /><br />You can check more singly and doubly linked lists utilities on my <a href="https://gist.github.com/steghio/93ebdfa1c12009d8036514ae3d62b222" target="_blank">Gist</a> along with some test cases in <a href="https://gist.github.com/steghio/93ebdfa1c12009d8036514ae3d62b222#file-singlelinkedlistjtests-java" target="_blank">SingleLinkedListJTests</a>.http://feedproxy.google.com/~r/groglogs/~3/7scbPA_CVvM/java-reverse-singly-linked-list.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/11/java-reverse-singly-linked-list.htmltag:blogger.com,1999:blog-1859167416855250911.post-8838320035929318838Tue, 31 Oct 2017 17:14:00 +00002017-10-31T18:14:20.120+01:00HowToJavaJUnitSource code[Java] Look and say generatorThe <a href="https://en.wikipedia.org/wiki/Look-and-say_sequence" target="_blank">count and say sequence</a> is a self describing sequence where given a starting seed, each subsequent element is the concatenation of the number of times a number appeared consecutively in the previous element. For example with seed 1:<br /><br />1 -> one 1<br />11 -> two 1<br />21 -> one 2, one 1<br /><br />I provide here an implementation to get the nth element given any seed. Unfortunately, we have to compute all elements before getting the one of interest :(<br /><br />This runs in O(M) space, where M is the length of the resulting string and O(NxM) time. Beware that M is not that small since in the worst case at each new iteration we add one character for each current one, thus doubling the size of the string!<br /><br />The idea is simply to iterate from 1 to N and for each iteration, loop over all the characters in the partial output string and count the consecutive appearances to form a new partial string.<br /><br />An improvement could be to identify those special seeds that will always return themselves and skip the calculation, eg: 22 will always be 22 no matter how many iterations we have. <br /><br />You can check the implementation of <i>lookAndSay</i> on my <a href="https://gist.github.com/steghio/2855fc32d2b0cd226b2117cd3fc43154" target="_blank">Gist</a> along with some sample test cases in <a href="https://gist.github.com/steghio/2855fc32d2b0cd226b2117cd3fc43154#file-lookandsayjtests-java" target="_blank">LookAndSayJTests</a>.http://feedproxy.google.com/~r/groglogs/~3/LuKniIAdBvE/java-look-and-say-generator.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/10/java-look-and-say-generator.htmltag:blogger.com,1999:blog-1859167416855250911.post-629832090204863275Tue, 31 Oct 2017 15:49:00 +00002017-10-31T16:49:11.346+01:00HowToJavaJUnitSource code[Java] Partition array in linear time and constant spaceHere is an interesting problem: given an integer array and an index, consider the element at the index as a pivot and then reorganize the array so that all the elements less than the pivot are at the start of the array, followed by the elements equal to the pivot, followed by the elements greater than the pivot.<br /><br />This is trivial to do in a single pass and additional O(N) space, since we scan the array once and store the elements in one of three additional arrays (smaller, equal, greater) and then in another pass we reconstruct the result array.<br />We can get rid of the extra space but run in O(N^2) time by scanning for each element the array multiple times to make sure it is in the proper place, until we reach the end.<br /><br />A better solution that runs in O(N) time and O(1) space, is to partition the array itself in 4 sections: smaller, equal, unclassified, larger and process one unclassified element at a time. For the unclassified section, equal is the pointer to the beginning of it and larger the pointer to the end. At the start, smaller and equals are the same and larger is the end of the array. It is not guaranteed that at each pass the array will be in a consistent state but it will be by the end of the algorithm!<br /><br /><a name='more'></a>So at each pass we inspect the current element and:<br /><br />- if it is smaller, we swap it with the last of the smaller elements and move both pointers forward. We might swap the element with itself, but we are also reducing the unclassified section by 1<br />- if it is equal, we move the equals pointer forward, thus reducing the unclassified section by 1, but we do not move smaller because we might have another element to add there at a later point in time, and therefore we might have to swap again the first equal element to borrow space from it<br />- if it is bigger, we swap it with the first of the bigger elements (which is also the last of the unclassified elements) and only move the larger pointer backwards by 1, reducing the unclassified section by 1 as well. We do not move the equals pointer, because we borrowed space from an unclassified element we still need to check!<br /><br />We stop as soon as the larger pointer surpasses the equals pointer, meaning we checked all unclassified elements.<br /><br />The logic is unfortunately not straightforward, so it greatly helps to draw a sample run to verify it. Suppose our input array is: 5,4,3,2,1 and our index is 0, therefore the pivot is 5. We expect the output to be 4,3,2,1,5 since all other elements are smaller than 5, only one is equal to 5, and no other element is bigger than 5.<br /><br />Start situation, e = equals, s = smaller, l = larger:<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">5 4 3 2 1</span></span><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">s l</span></span><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">e</span></span><br /><br />5 is equal to 5, so move equals up by 1<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">5 4 3 2 1</span></span><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">s e l</span></span><br /><br />4 is smaller than 5, so swap with smaller and move both smaller and equals up by 1<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">4 5 3 2 1</span></span><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"> s e l</span></span><br /><br />3 is smaller than 5, so swap with smaller and move both smaller and equals up by 1<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">4 3 5 2 1</span></span><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"> s e l</span></span><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"><br /></span></span><br />2 is smaller than 5, so swap with smaller and move both smaller and equals up by 1<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">4 3 2 5 1</span></span><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"> s e</span></span><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"> l </span></span><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"><br /></span></span></span></span><br /><br />1 is smaller than 5, so swap with smaller and move both smaller and equals up by 1. This is also why we have to run until equals <= larger, otherwise we would miss the last swap!<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">4 3 2 1 5</span></span><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"> s e</span></span><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"> l </span></span><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"><br /></span></span></span></span><br />Now equals is bigger than larger, therefore we end our loop with a successful partition.<br /><br />You can the code for <i>partitionArray</i> on my <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7" target="_blank">Gist</a> along with some test cases in <a href="https://gist.github.com/steghio/ea6d32381f2e589fd3f09cfed07d65a7#file-partitionarrayjtests-java" target="_blank">PartitionArrayJTests</a>http://feedproxy.google.com/~r/groglogs/~3/o9JcdIvJVd0/java-partition-array-in-linear-time-and.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/10/java-partition-array-in-linear-time-and.htmltag:blogger.com,1999:blog-1859167416855250911.post-6056816300302419185Sun, 29 Oct 2017 09:07:00 +00002017-10-29T10:07:36.459+01:00HowToLinuxxorg[xorg] Set display to full RGB outputDepending on the monitor being used, the <a href="https://en.wikipedia.org/wiki/RGB_color_model" target="_blank">RGB color model</a> supported might be either "Full RGB" or "Limited 16:235"; usually the latter is the one used by TV monitors.<br /><br />To test the output setting when using xorg, first find out the name of the video connection being used by running:<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">xrandr</span></span><br /><br />which will list the names and statuses of the available connections. Then manually change the output setting with:<br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;"><br /></span></span><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">xrandr --output NAME --set "Broadcast RGB" "Full"</span></span><br /><br />Or use <i>"Limited 16:235"</i> instead.<br /><br />This will not survive a reboot, therefore use whatever method suits you best to force this at every boot, eg by editing/creating the <i>~/.xprofile</i> filehttp://feedproxy.google.com/~r/groglogs/~3/1mvnSVy6OyY/xorg-set-display-to-full-rgb-output.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/10/xorg-set-display-to-full-rgb-output.htmltag:blogger.com,1999:blog-1859167416855250911.post-8894305835830822856Mon, 23 Oct 2017 20:46:00 +00002017-10-23T22:46:11.746+02:00HowToJavaJUnitSource code[Java] Test if a number is a power of twoLast trick of the day: check whether a number is a power of 2.<br /><br />The breakdown is:<br /><br />- 0 is never a power of anything<br />- a power of 2 in binary representation will always have only one bit set<br />- we can find the first set LSB in number and XOR it with the number itself<br />- if the number was a power of two the XOR will cancel out all equal bits (only one) and we are left with a 0<br /><br />Which leads to our code:<br /><br /><pre style="font-family:arial;font-size:12px;border:1px dashed #CCCCCC;width:99%;height:auto;overflow:auto;background:#f0f0f0;padding:0px;color:#000000;text-align:left;line-height:20px;"><code style="color:#000000;word-wrap:normal;"> public static boolean isPower2(long n){ <br /> if(n == 0) return false; <br /> return (n ^ getLowestSetBit(n)) == 0; <br /> } <br /></code></pre><br /><br />You can check more bit magic on my <a href="https://gist.github.com/steghio/9262b492568a46ff4bc7388e2a5148b4" target="_blank">Gist</a> along with some test cases.http://feedproxy.google.com/~r/groglogs/~3/sREmtpDJI6w/java-test-if-number-is-power-of-two.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/10/java-test-if-number-is-power-of-two.htmltag:blogger.com,1999:blog-1859167416855250911.post-9198811545823946255Mon, 23 Oct 2017 20:39:00 +00002017-10-23T22:39:58.531+02:00HowToJavaJUnitSource code[Java] Calculate modulus of a number and a power of twoMore bit magic!<br /><br />This time we will efficiently compute the modulus of a number and a power of two. If you write down a couple sample cases you immediately spot the trick; let's use N mod 4 (0<span style="color: red;">1</span>00): <br /><br /><span style="font-size: x-small;"><span style="font-family: "courier new" , "courier" , monospace;"><table border="1"><tbody><tr><td>Number</td><td>Bits</td><td>Modulo</td><td>Modulo bits</td></tr><tr><td>1</td><td>0<span style="color: red;">0</span><b>01</b></td><td>1</td><td>0<span style="color: red;">0</span><b>01</b></td></tr><tr><td>2</td><td>0<span style="color: red;">0</span><b>10</b></td><td>2</td><td>0<span style="color: red;">0</span><b>10</b></td></tr><tr><td>3</td><td>0<span style="color: red;">0</span><b>11</b></td><td>3</td><td>0<span style="color: red;">0</span><b>11</b></td></tr><tr><td>4</td><td>0<span style="color: red;">1</span><b>00</b></td><td>0</td><td>0<span style="color: red;">0</span><b>00</b></td></tr><tr><td>5</td><td>0<span style="color: red;">1</span><b>01</b></td><td>1</td><td>0<span style="color: red;">0</span><b>01</b></td></tr><tr><td>6</td><td>0<span style="color: red;">1</span><b>10</b></td><td>2</td><td>0<span style="color: red;">0</span><b>10</b></td></tr><tr><td>7</td><td>0<span style="color: red;">1</span><b>11</b></td><td>3</td><td>0<span style="color: red;">0</span><b>11</b></td></tr><tr><td>8</td><td>1<span style="color: red;">0</span><b>00</b></td><td>0</td><td>0<span style="color: red;">0</span><b>00</b></td></tr><tr><td>9</td><td>1<span style="color: red;">0</span><b>01</b></td><td>1</td><td>0<span style="color: red;">0</span><b>01</b></td></tr></tbody></table></span></span><br /><br />The red bit is the only set bit in our modulus, the bold bits in both the number and the result are always matching.. interesting.<br />We now have a very easy way of calculating the result by always returning all the bits in the number that appear after the modulo bit:<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">n & (mod - 1)</span></span><br /><br />We already saw <a href="http://groglogs.blogspot.ch/2017/10/java-find-lowest-set-bit-in-number.html" target="_blank">previously</a> that n - 1 will provide us with a mask where all the bits after the first set LSB are set to 1. We can then AND this with the number itself to erase everything that appears before, and including, the modulo bit and return only what's right of it.<br /><br />You can check more bit magic on my <a href="https://gist.github.com/steghio/9262b492568a46ff4bc7388e2a5148b4" target="_blank">Gist</a> along with some test cases.<br /><br /><br />http://feedproxy.google.com/~r/groglogs/~3/HwbWYIxNxsQ/java-calculate-modulus-of-number-and.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/10/java-calculate-modulus-of-number-and.htmltag:blogger.com,1999:blog-1859167416855250911.post-2085251883098571309Mon, 23 Oct 2017 20:22:00 +00002017-10-23T22:22:30.788+02:00HowToJavaJUnitSource code[Java] Right propagate the lowest set bit in numberBuilding on top of the magic to <a href="http://groglogs.blogspot.ch/2017/10/java-find-lowest-set-bit-in-number.html" target="_blank">find the first set LSB in a number</a>, we have another magic trick to right propagate it.<br /><br />Eg:<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">10100</span></span><br /><br />would become:<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">10111</span></span><br /><br />The code for this is:<br /><br /><pre style="font-family:arial;font-size:12px;border:1px dashed #CCCCCC;width:99%;height:auto;overflow:auto;background:#f0f0f0;padding:0px;color:#000000;text-align:left;line-height:20px;"><code style="color:#000000;word-wrap:normal;"> public static long rightPropagateLowestSetBit(long n){ <br /> if(n > 1) return n | getLowestSetBitPosition(n); <br /> return n; <br /> } <br /></code></pre><br /><br />And the breakdown:<br /><br />- 0 and 1 have nothing to propagate, so return them directly<br />- find the lowest set bit<br />- bitwise OR the number with the <b>position</b> of its lowest set bit, that means we start counting from 0 as LSB; the position is then exactly the mask for the missing 1s we need to set.<br /><br />To get the position we simply return the first set LSB - 1 and pay attention to the fact that now 0 has -1 as result :)<br /><br />You can check more bit magic on my <a href="https://gist.github.com/steghio/9262b492568a46ff4bc7388e2a5148b4" target="_blank">Gist</a> along with some test cases.http://feedproxy.google.com/~r/groglogs/~3/y3XMxEDAPHI/java-right-propagate-lowest-set-bit-in.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/10/java-right-propagate-lowest-set-bit-in.htmltag:blogger.com,1999:blog-1859167416855250911.post-6291757099610754663Mon, 23 Oct 2017 20:12:00 +00002017-10-23T22:12:12.625+02:00HowToJavaJUnitSource code[Java] Find lowest set bit in numberThis is a very interesting bit magic trick: given a number, return the first (from least significant) bit set to 1.<br /><br />The magic formula is:<br /><br /><span style="font-size: x-small;"><span style="font-family: "Courier New",Courier,monospace;">n & ~(n - 1)</span></span><br /><br />To break it down:<br /><br />- (n - 1) creates a mask where the last bit set to 1 is now 0<br />- negating that mask gives us a new mask that is the exact opposite of n except for the bit we flipped before<br />- the AND operation of the original number with this mask, will then return only the bit we flipped<br /><br />You can check more bit magic on my <a href="https://gist.github.com/steghio/9262b492568a46ff4bc7388e2a5148b4" target="_blank">Gist</a> along with some test cases. <br /><br /><br /><br /><br />http://feedproxy.google.com/~r/groglogs/~3/mlK9_kwXAuk/java-find-lowest-set-bit-in-number.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/10/java-find-lowest-set-bit-in-number.htmltag:blogger.com,1999:blog-1859167416855250911.post-7375501136352454406Sun, 22 Oct 2017 12:57:00 +00002017-10-22T14:59:37.613+02:00HowToJavaJUnitSource code[Java] Find local maximum gain in listHere is another simple problem: given an ordered input of stock prices, find the best buy and sell times to achieve maximum gain.<br /><br />The buy must happen before the sell and it is not possible to buy and sell in the same day. Return null if no gain can be achieved. <br /><br />The idea is quite straightforward, in O(N) time and O(1) space, track the current maximum gain and current minimum buy date; whenever the gain can be increased, update the buy - if necessary - and store the sell data. Just as caution, it's important to remember to separately track the current and result data, otherwise it could be possible to wrongly overwrite the result before returning.<br /><br />You can check on my <a href="https://gist.github.com/steghio/93ebdfa1c12009d8036514ae3d62b222#file-linkedlistutils-java" target="_blank">Gist</a> the implementation of the <i>getMaxProfit</i> (if only life was that easy..) method along with the test cases <a href="https://gist.github.com/steghio/93ebdfa1c12009d8036514ae3d62b222#file-stocktradejtests-java" target="_blank"><i>StockTradeJTests</i></a> and the aux objects <a href="https://gist.github.com/steghio/93ebdfa1c12009d8036514ae3d62b222#file-stockentry-java" target="_blank"><i>StockEntry</i></a> and <a href="https://gist.github.com/steghio/93ebdfa1c12009d8036514ae3d62b222#file-buysellentry-java" target="_blank"><i>BuySellEntry</i></a>.http://feedproxy.google.com/~r/groglogs/~3/LTgwOjYL9Sc/java-find-local-maximum-gain-in-list.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/10/java-find-local-maximum-gain-in-list.htmltag:blogger.com,1999:blog-1859167416855250911.post-9203943561735750274Tue, 17 Oct 2017 20:48:00 +00002017-10-17T22:48:38.719+02:00HowToOraclePL/SQLSource code[PL/SQL] Convert number to binary stringHere is a simple function to convert a number to a binary string in Oracle PLSQL. This can also easily be converted to an number array instead.<br /><br /><pre style="font-family:arial;font-size:12px;border:1px dashed #CCCCCC;width:99%;height:auto;overflow:auto;background:#f0f0f0;padding:0px;color:#000000;text-align:left;line-height:20px;"><code style="color:#000000;word-wrap:normal;"> function num_to_bin( <br /> n number <br /> ) <br /> return varchar2 <br /> is <br /> binval varchar2(64); <br /> n2 number := n; <br /> begin <br /> while (n2 > 0) loop <br /> binval := mod(n2, 2) || binval; <br /> n2 := trunc(n2 / 2); <br /> end loop; <br /> <br /> return binval; <br /> end num_to_bin; <br /></code></pre>http://feedproxy.google.com/~r/groglogs/~3/SCLC68sx3cM/plsql-convert-number-to-binary-string.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/10/plsql-convert-number-to-binary-string.htmltag:blogger.com,1999:blog-1859167416855250911.post-4376065253191845317Wed, 11 Oct 2017 21:08:00 +00002017-10-11T23:08:51.548+02:00HowToJavaJUnitSource code[Java] Merge linked lists with gapsOk, this is a very specific exercise and a bit hard to summarize in a short title, but in the end it is just an algorithm working on lists, more specifically list of lists.<br /><br />I was asked this at an interview and I am quite surprised by the difficulty of it; coming up with suboptimal solutions is quite easy though I have to admit.<br /><br />The problem is: given a list of ordered lists as input, where the content is an object <i>(date, value)</i>, generate as output a list, ordered by date, where for each date, the value is the sum of the values for that date in each list. If a list does not contain that date, use the previous value, if any. The date can be represented as a long to ease the comparison logic, otherwise we would need to provide a comparator.<br /><br />For example consider this representation <br /><span style="font-family: "courier new" , "courier" , monospace;"><br /> 5/5 5/6 6/11 6/12<br /> A 10 20<br /> B 20 10 20<br /> C 10 20</span><br /><br />The input would be given as a list of lists:<br /><br /><span style="font-family: "Courier New",Courier,monospace;">[</span><br /><span style="font-family: "Courier New",Courier,monospace;"> [(5/5, 10), (6/11, 20)]</span><br /><span style="font-family: "Courier New",Courier,monospace;">,[(5/5, 20), (5/6, 10), (6/12, 20)]</span><br /><span style="font-family: "Courier New",Courier,monospace;">,[(5/6, 10), (6/12, 20)]</span><br /><span style="font-family: "Courier New",Courier,monospace;">]</span><br /><br />The result has to be: <span style="font-family: "Courier New",Courier,monospace;">[(5/5, 30), (5/6, 30), (6/11, 40), (6/12, 60)]</span><br /><br />Because we track the following phantom values, the "holes":<br /><br /><span style="font-family: "Courier New",Courier,monospace;"> 5/5 5/6 6/11 6/12</span><br /><span style="font-family: "Courier New",Courier,monospace;"> A 10 [10] 20 [20]</span><br /><span style="font-family: "Courier New",Courier,monospace;"> B 20 10 [10] 20</span><br /><span style="font-family: "Courier New",Courier,monospace;"> C [0] 10 [10] 20</span><br /><br /><a name='more'></a><br />So, easy solution would be to first find all the unique dates in O(MxN) time where M is the number of lists and N the elements per list, then build a MxN matrix filling the holes when we don't have a value, then sum up each column and produce the result. This solution works in O(MxN) time and space.<br /><br />Can we do better? Timewise, no, since we need to scan all the input values anyway. Spacewise, definitely, we did not use a matrix in the first place because we don't want too much space being taken up!<br /><br />An idea that uses O(1) additional space but runs in O((MxN)xN) time: build the result list while walking through each input list. This means that first we collect all the dates in O(MxN) time, then, for each date we collected O(N), we scan the input lists multiple times in case we have holes O(MxN). We can do this scanning using two pointers for example, one moving one step farther than the other, in order to find the hole boundaries in our list and get the correct value.<br /><br />A faster solution that uses O(M) additional space and runs in O(MxN) time instead is to first collect all the dates in O(MxN) time, then create an array of pointers to each input list and for each date we found O(N), scan the array O(M) and do one of the following actions:<br />- if the date of current element is the one we are considering, update the value in the result but do NOT move to the next element yet, because we might have a hole after us<br />- if the date of the current element is preceding the one we are considering, check if we have a following node:<br />-- if yes, is its date bigger than the one we are considering? If so, we are in the hole, so use the current value and do NOT move forward. If not, it must be equal to the one we are considering, meaning we filled the hole, so FIRST move forward and THEN update the value. We can't have a situation where the next date is smaller, since the lists are ordered<br />-- if no, we are the last element in the current list and are followed only by holes, keep using the same value and never move up<br /><br /><br />If this sounds confusing enough, try coming up with it in 30 minutes ;)<br /><br />By the way, the idea of using a TreeMap/TreeSet to track the result and/or collecting the dates initially was discarded because of the O(logN) insert and update time complexity. At first it sounded like a good idea due to the easiness in tracking in an ordered way all the dates while scanning the lists, but since afterwards the logic with the pointer array would need to be applied there as well (we still need to sum up the values AND consider the holes), I think it's better to settle for a simple list instead (which by the way is also the output :) ).<br /><br /><br />You can check the implementation of the <i>mergeDateLists</i> method on my <a href="https://gist.github.com/steghio/93ebdfa1c12009d8036514ae3d62b222" target="_blank">Gist</a> along with the definition of the <a href="https://gist.github.com/steghio/93ebdfa1c12009d8036514ae3d62b222#file-datenode" target="_blank"><i>DateNode</i></a> class and some <a href="https://gist.github.com/steghio/93ebdfa1c12009d8036514ae3d62b222#file-datelistsjtests-java" target="_blank">test cases</a>. <br /><br />http://feedproxy.google.com/~r/groglogs/~3/adP0nQYuJ7c/java-merge-linked-lists-with-gaps.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/10/java-merge-linked-lists-with-gaps.htmltag:blogger.com,1999:blog-1859167416855250911.post-8490002004849030875Sun, 08 Oct 2017 20:09:00 +00002017-10-08T22:09:25.488+02:00HowToJavaJUnitSource code[Java] Biggest matrix subgroup valueGiven a 2D input matrix with non negative values, consider the subgroupings as all positive values surrounded by zeroes eg:<br /><span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;">________</span></span><br /><span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;">|001003|</span></span><br /><span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;">|002304|</span></span><br /><span style="font-size: small;"><span style="font-family: "Courier New",Courier,monospace;">--------</span></span><br /><br />(1,2,3) and (3,4) are groupings. A matrix with all positive values is a single grouping, an empty matrix has group value 0.<br /><br />The idea is to approach this as a graph walk where each point in the matrix is a node; therefore we can walk the full matrix and every time we encounter a positive value, we start searching for and queuing all contiguous values that are part of the same group and keep summing them up while marking the positions as visited.<br /><br />When we cannot move anymore (queue is empty), we update, if necessary, the current max result and keep walking the matrix. Since we mark the nodes as visited, we will not process each point more than once so the total runtime is O(MxN) and total space is also in O(MxN) because at most we queue the full matrix.<br /><br />Since we are adding points to a queue for later processing, we have to be <b>very careful</b> of the double processing possibility; this means that we have to mark each point we add as visited <b>immediately</b> after it is added and use a <i>Point</i> auxiliary structure so that we can store the data for later processing. If we skip this, we might enqueue the point for processing twice and change its value in between to mark it as visited!<br /><br />As bonus, this logic scales well to higher dimensional matrices, what needs to be adjusted is the looping and queuing logic to accommodate the extra dimensions. <br /><br />You can check the implementation on my <a href="https://gist.github.com/steghio/f37caa0530d5d3d62a3f197b28dd9acb" target="_blank">Gist</a> along with the definition of the <i>Point</i> class and some test cases. http://feedproxy.google.com/~r/groglogs/~3/ihrMNAmCeS0/java-biggest-matrix-subgroup-value.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/10/java-biggest-matrix-subgroup-value.htmltag:blogger.com,1999:blog-1859167416855250911.post-3372537100478087055Sun, 08 Oct 2017 13:46:00 +00002017-10-08T15:46:19.006+02:00HowToMozillaFirefox[Firefox] Open magnet links with external programFor some reason Mozilla Firefox is not set to request which external program to run when you click on a <a href="https://en.wikipedia.org/wiki/Magnet_URI_scheme" target="_blank">magnet link</a>, instead it will try to open and display it in the browser itself.<br /><br />The fix is a simple boolean variable to add in the <a href="https://support.mozilla.org/en-US/kb/about-config-editor-firefox" target="_blank">about:config</a> section. Name it <i>network.protocol-handler.expose.magnet</i> and set its value to <i>false</i>.http://feedproxy.google.com/~r/groglogs/~3/jT88b2J2j7M/firefox-open-magnet-links-with-external.htmlnoreply@blogger.com (Stefano Ghio)0http://groglogs.blogspot.com/2017/10/firefox-open-magnet-links-with-external.html