# Category Archives: Data Structures/Algorithms

http://bigocheatsheet.com/
http://www.graphics.stanford.edu/~seander/bithacks.html

## Maps in Java

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 »

## Find All Elements in an Array which appears more than N/K times, N is Array Size and k is a Number

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 »

## Merge two stored arrays with different sizes.

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 »

## Binary search algorithm

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 »

## Calculating Pi by Leibniz formular

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 in lexicographic order

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 »

## Heap’s algorithm for Permutations

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 Algorithm

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 »

## Know Big-O complexities

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)