Concrete maps in Java JDK 1.8 Below is the summary of differences between HashMap, LinkedHashMap, TreeMap, and Hashtable in Java: (Source: javarevisited.blogspot.com) If we need to get the key back in insertion order, then use LinkedHashMap. If we need to get the key back in their true/natural order, then use TreeMap. Otherwise, HashMap is best because it… Read More »
Similarly, original Boyer-Moore Majority Vote Algorithm defined “Majority element of an array A[1 … n]: An array is said to have a majority element if more than half of its entries are the same.” In other words, the majority element is the element that appears more than ⌊ n/2 ⌋. One difference is finding more… Read More »
1. Question. You are given two sorted arrays, A and B, where A has a large enough buffer at the end to hold B. Write a method to merge B into A in sorted order. For example: int[] a = {2, 3, 4, 8, 10, 100, 0, 0, 0, 0}; int[] b = {1, 4,… Read More »
1. Getting. In binary search algorithm, we find an element x in a sorted array by using the principle of divide and conquer. First, we compare x to the middle point of the array. If x is less than the middle point, then we search the left of array. Otherwise, we look for the right… Read More »
Problem This is to calculate an approximation to the constant Pi (π). Solution 1.1. Computation fomular will take O(m) steps –linear algorithm or time complexity is O(m) . The Leibniz series converges very slowly if m approaches infinity. To calculate pi to one million decimal places would require 106 terms. 1.2 Calculate the nth digit of… Read More »
Combinations of size k Prints out all C(n, k) = n! / (k! * (n-k)!) combinations of size k in increasing lexicographic order. For example: From a given String “abcde” when n = 5 and k = 3 you should get the following output: abc abd abe acd ace ade bcd bce bde cde Solution:… Read More »
Problem: Find the biggest number from the array [3, 1, 2] (n = 3). For example: 321 is largest number in comparison with all possible numbers from the array. Solving: We need to resolve 2 things. Final all possible Permutations from the array. So possible permutation is n! = 3! = 6 cases. Find a maximum number from… Read More »
Quick sort discovered by C.A.R Hoare in 1962. It is a fast algorithm for internal or in-memory sorting except for sorting data in disk files. Figure 1: Time and Space complexity of quick sort. There are three basic steps: Partition the array or sub-array into left (smaller keys) and right (larger keys) groups. Call ourselves to sort… Read More »
This note covers the space and time Big-O complexities of common algorithms used in Computer Science: Figure 1: Data structure and Sorting Algorithms (Source: bigocheatsheet.com)