Last active
March 4, 2018 15:44
-
-
Save jjokela/ad292a8e3bcd7831207cff2391edd1c6 to your computer and use it in GitHub Desktop.
Utility code for Hackerrank exercises
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// char array containing lower-case letters from a..z | |
var letters = new char[] {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'}; | |
// int to binary string with leading zeros | |
Convert.ToString(3, 2).PadLeft(4, '0'); // 0011 | |
Convert.ToString(3, 2).PadLeft(8, '0'); // 00000011 | |
// binary to int | |
int output = Convert.ToInt32(input, 2); | |
// QuickSelect | |
static int QuickSelect(int[] arr, int left, int right, int k) | |
{ | |
// array contains only one element | |
if(left == right) | |
{ | |
return arr[left]; | |
} | |
// select pivotIndex between left..right | |
var pivotIndex = (right - left) / 2 + left; | |
pivotIndex = Partition(arr, left, right, pivotIndex); | |
// k is in its final sorted position | |
if(pivotIndex == k) | |
{ | |
return arr[k]; | |
} else if(k < pivotIndex) { // check the left-side of pivot | |
return QuickSelect(arr, left, pivotIndex - 1, k); | |
} else { // check the right-side of pivot | |
return QuickSelect(arr, pivotIndex + 1, right, k); | |
} | |
} | |
// partition | |
static int Partition(int[] arr, int left, int right, int pivotIndex) | |
{ | |
var pivotValue = arr[pivotIndex]; | |
// move pivot to end | |
Swap(ref arr[pivotIndex], ref arr[right]); | |
var storeIndex = left; | |
for(int i = left; i <= right - 1; i++) | |
{ | |
if(arr[i] < pivotValue) | |
{ | |
Swap(ref arr[storeIndex], ref arr[i]); | |
storeIndex++; | |
} | |
} | |
// move pivot from end to it's final place | |
Swap(ref arr[right], ref arr[storeIndex]); | |
return storeIndex; | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment