What FAANG companies expect in their interview from candidates
Its every software engineer’s dream to work with the big FAANG companies…
July 16, 2019
Counting sort runs on relatively smaller set of input. Counting sort calculates, for every element in array - X, the number of elements which are lesser than - X. It then use this information to put X directly into its position in sorted array.
Selection sort takes two additional array.
Its interesting to note that this algorithm is not a comparison sort. You will not see any comparison in code. This algorithm uses elements values to index into array.
Now iterate equal to length of original array (from last index to 0):
See the code here:
public class CountSort {
private int[] arr;
public CountSort(int[] arr) {
this.arr = arr;
}
/**
* Count sort, max value-k
* @param k, the max value in array
*/
public int[] doSort(int k) {
int[] c = new int[k+1];
//count number of occurence
for (int i=0; i<this.arr.length; i++) {
c[this.arr[i]] ++;
}
//accumulate
for (int i=1; i<c.length; i++) {
c[i] += c[i-1];
}
int[] result = new int[this.arr.length];
//put the number to its designated place
for (int i=this.arr.length-1; i>=0; i--) {
result[c[this.arr[i]]-1] = this.arr[i];
c[this.arr[i]] --;
}
return result;
}
}
The algorithm runs on time complexity of O(n + k) ~= O(n) in worst/average case.
Its every software engineer’s dream to work with the big FAANG companies…
Here are some tips while preparing for your coding interviews. 1. Do study or…
Introduction I will list some of the interesting usage of bitwise operators…
Problem Statement Given a string, find the first non-repeating character in it…
Its a kind of incremental insertion technique, where the algorithm build up…
Problem Statement You are given a string text of words that are placed among…
Problem Statement You are given a rows x cols matrix grid. Initially, you are…
Problem Statement Given a string s, return the maximum number of unique…
Problem The Leetcode file system keeps a log each time some user performs a…
Problem Statement Replace all spaces in a string with ‘%20’ (three characters…
Problem Implement an algorithm to determine if a string has all the characters…