Anon
BAN USERUsing Binary search code (as the input is sorted).
Note the input is a rotated array ...
private static int getPeak(int[] input) {
/**
* TODO Handle null/empty checks
*/
int low = 0;
int high = input.length - 1;
int mid = 0;
while (low <= high) {
mid = low + (high - low) / 2;
if (input[mid] < input[high]) {
if (input[mid] >= input[low]) {
low = mid + 1;
} else {
high = mid - 1;
}
} else {
if (input[mid] == input[high]) {
return input[mid];
}
int rightIndex = mid + 1; // Check the right neighbour
if (rightIndex < input.length) {
if (input[mid] < input[rightIndex]) {
low = mid + 1;
} else {
return input[mid];
}
}
}
}
return -1;
}
It is the Java version of the C++ solution above. Brilliant Algo From Anonymous indeed.
static void printSummary(String s) {
Stack<Integer> stack = new Stack<Integer>();
char[] chars = s.toCharArray();
for (int i = 0; i < chars.length; i++) {
if (chars[i] == '(') {
stack.push(i);
} else if (chars[i] == ')') {
if (stack.isEmpty()) {
chars[i] = '^';
} else {
int openingIndex = stack.pop();
chars[openingIndex] = '0';
chars[i] = '1';
}
}
}
while (!stack.isEmpty()) {
chars[stack.pop()] = '^';
}
System.out.println("Summary: " + new String(chars).replace("^", "-1"));
}
[I have edited my answer. Sorry for multiple posts. I am not able to delete my prev posts] My idea is Load chunks of 5 (since 10 is the memory limit and we would need to merge 2 chunks of 5]
Merge Sort 2 Steps Forward and when you hit the end, merge sort 2 steps Backward. Like a Induced Burp effect ;-). Loop this for 5 times
public class MergeSortFromFile {
int[] file;
MergeSortFromFile(int fileLength) {
file = new int[fileLength];
Random r = new Random();
for (int i = 0; i < fileLength; i++) {
file[i] = r.nextInt(fileLength);
}
}
private int[] load(int start, int end) {
if (start > file.length || end > file.length) {
return null;
} else
return Arrays.copyOfRange(file, start, end);
}
private int[] mergeSort(int[] original) {
if (original == null || original.length == 0 || original.length == 1) {
return original;
}
int mid = original.length / 2;
int[] lArray = Arrays.copyOfRange(original, 0, mid);
int[] rArray = Arrays.copyOfRange(original, mid, original.length);
mergeSort(lArray);
mergeSort(rArray);
merge(lArray, rArray, original);
return original;
}
private void merge(int[] l, int[] r, int[] merged) {
int totalElements = l.length + r.length;
int li = 0;
int ri = 0;
int i = 0;
while (i < totalElements) {
if (li < l.length && ri < r.length) {
if (r[ri] < l[li]) {
merged[i] = r[ri];
++ri;
++i;
} else {
merged[i] = l[li];
++li;
++i;
}
} else {
if (li >= l.length) {
while (ri < r.length) {
merged[i] = r[ri];
++i;
++ri;
}
}
if (ri >= r.length) {
while (li < l.length) {
merged[i] = l[li];
++i;
++li;
}
}
}
}
}
public void merge() {
int step = 5;
int loopCount = file.length / step;
for (int z = 0; z < loopCount; z++) {
int i = 0;
/** 2 steps forward **/
while (i + 2 * step < file.length) {
int[] resultArray = load(i, i + 2 * step);
resultArray = mergeSort(resultArray);
for (int j = 0; j < resultArray.length; j++) {
file[i + j] = resultArray[j];
}
i += step;
}
int k = file.length;
/** 2 steps backward **/
int mergeInterval = 2 * step;
while (k - (2 * step) >= 0) {
int[] resultArray = load(k - mergeInterval, k);
resultArray = mergeSort(resultArray);
for (int j = 0; j < resultArray.length; j++) {
file[k - mergeInterval + j] = resultArray[j];
}
k -= step;
}
}
}
public int[] getContents() {
return file;
}
public static void main(String[] args) {
MergeSortFromFile m = new MergeSortFromFile(100);
System.out.println("Original File Contents: "
+ Arrays.toString(m.getContents()));
long t = System.currentTimeMillis();
m.merge();
long timeTaken = System.currentTimeMillis() - t;
System.out.println("Sorted File Contents: "
+ Arrays.toString(m.getContents()));
System.out.println("Time Taken: " + timeTaken + " mSec");
}
}
A Trie [0-9 at each level] can be used this to store this and the bank name can be stored at the terminating node.
- Anon June 10, 2019