Sorting a Stack using push,pop,isEmpty and peek
Problem Definition: Sort a Stack using standard operations push,pop,isEmpty and peek. Solutions: 1. Use an additional array of size n, insert into array (Time Complexity O(n)). Use Counting Sort (Complexity O(n)). Memory overhead of O(m+n). 2. Use recursion with no additional space. The time complexity is O(n) and O(1) space complexity. The following code is … Read more
Anagram Checker
A simple way to check if two strings are anagrams is to find out if the numeric sum of the characters in the strings is equal. The approach below uses a hash function that returns the sum of the characters in the string. The running time is O(n) but has a space overhead proportional to … Read more
Finding kth Smallest Value or Largest Value
This problem is a good one. Options available are: 1. Sort the entire array using Counting Sort ( see. linear-sorting-using-counting-sort ) and print out the kth index of the result array. Time Complexity is O(n) and Space Complexity is O(n+m) 2. Use a Randomized Selection Sort. The Time Complexity is O(n) and Space Complexity is … Read more
Linear Sorting using Counting Sort
Nothing much.. just a simple implementation of the Counting Sort. Time Complexity is O(n) and space complexity is O(n+m). package sorting; /** * * @author Sandeep Phukan * Implements a count sort with O(n) time complexity * */ public class CountSort { int[] tempArray=null; int[] resultArray=null; public int[] sort(int[] inputArray,int maxNumber){ tempArray=new int[maxNumber+1]; //Actually this … Read more
