Very quick summary of Union-Find or Disjoint Set data structure
Author: Asif Rehan
Kosaraju’s vs Tarjan’s Kosaraju’s algorithm finds the Topological Sorting of the original directed graph. For this, it uses DFS. Next it reverses the graph and runs DFS on the topologically sorted vertices. So it takes two DFS though the time complexity is O(|V|+|E|). Tarjan’s algorithm, on the other hand, only uses one DFS but uses […]
This is a array/string problem and you can look up this problem on HackerRank. To solve this one, it can not theoretically be any better than O(n) time complexity. Here I convert the string to character array, then for each character and if this is a small ASCII character between a-z, then subtract the value […]
Installing Environment Setup PostgreSQL Database Server We are going to show how to install PostgreSQL database on a Debian Linux system. $ sudo apt-get install postgresql Check status $ /etc/init.d/postgresql status Add password for the postgress account $ sudo -u postgres psql postgres psql (9.5.10) Type “help” for help. postgres=# \password postgres Enter new password: […]
Categories
Reading List
Good to Great – Jim Collins Signal and Noise by Nate Silver Security Analysis by Graham and Dodd
This LeetCode problem is a great practice problem to implement a binary search for a value in a sorted array with duplicate values. It asks to find the indices of the first and start the occurrence of a value in the sorted array with possibly duplicate values. It can be solved in a naive manner […]
The Sort Color problem expects to sort the array with values {0, 1, 2}. This can be done in a typical sorting algorithm in O(nlogn) time. A better approach is to use three-way partitioning of the array. Generic three-way partitioning Below the threeWayPartitionSort() method splits the given an array, [3,2,0,2,1,1,0,-1], into three parts, where values […]
Recently have been looking into some stock market prediction libraries and repositories for our group project for CS7643 Deep Learning at Georgia Tech. Previously I worked on traditional Machine Learning algorithms and Q-Learning algorithm from Reinforcement Learning for CS7646: Machine Learning for Trading commonly known as the “ML4T course”. My codes for ML4T is locked […]
Categories
LeetCode: Find Peak Element Solution
The Find Peak Element problem can be solved using a linear search in O(n) time and O(1) space. but it can be even better to solve it by binary search in O(log n) time complexity. But there can be two cases for binary search solution, the recursive solution creates stacks for each call and thus […]
Find Kth Largest Element in an Array is a problem which can be solved using e.g. QuickSort in O(nlogn) time and then pick the k-th element in the sorted array. Another way is to sort it using QuickSelect in O(n) times. The solution below beats 100% Java submissions on LeetCode for runtime. QuickSelect QuickSelect is […]