Intel Interview Question
Software DevelopersTeam: big data
Country: United States
Interview Type: Phone Interview
[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");
}
}
Assuming that there is some API in the background that allows access to the different elements, then problem can be easily solved using a merge sort:
//this is part of the assumption regarding the API- that there are API handles for access and handling the content
public static class Reader{
InputStream in;
public Reader(InputStream in){
this.in = in;
}
public SuperObject read(){
//need some implementation here
}
}
public static class Writer{
OutputStream out;
public Writer(OutputStream out){
this.out = out;
}
public void write(SuperObject obj){
//need some implementation here
}
}
private static Comparator<SuperObject> COMPARE = new Comparator<SuperObject(){
public int compare(SuperObject obj1, SuperObject obj2){
//need some implementation here
}
}
public static File sort(Reader reader) throws IOException {
//break up the file into pieces
SuperObject object = null;
LinkedList<File> files = new LinkedList<File>();
ArrayList<SuperObject> objs = new ArrayList<SuperObject>();
while((object = reader.read()) != null){
objs.add(object);
if(objs.size() == 10){
sort_10(objs);
File tempFile = new File.tempFile("temp","txt");
files.add(tempFile);
OutputStream out = new FileOutputStream(tempFile);
Writer writer = new Writer(out);
for(object : objs){
writer.write(object);
}
out.close();
objs.clear();
}
}
LinkedList<File> nextFile = new LinkedList<File>();
while(files.size() > 1){
while(files.size() > 1){
nextFiles.add(merge(files.removeFirst(), files.removeFirst()));
}
if(files.size() > 0){
nextFiles.add(merge(files.removeFirst(), nextFiles.removeFirst());
}
}
return file.removeFirst();
}
private void sort_10(ArrayList<SuperObject> arr){
Collections.sort(arr, COMPARE);
}
private File merge(File file1, File file2) throws IOException{
File retFile = File.tempFile("temp","txt");
OutputStream out = new FileOutputStream(retFile);
Writer writer = new Writer(out);
InputStream in1 = new FileInputStream(file1);
InputStream in2 = new FileInputStream(file2);
Reader reader1 = new Reader(in1);
Reader reader2 = new Reader(in2);
LinkedList<SuperObject> list1 = read_5(reader1);
LinkedList<SuperObject> list2 = read_5(reader2);
while(list1 != null && list2 != null){
SuperObject obj1 = list1.getFirst();
SuperObject obj2 = list2.getFirst();
int compare = COMPARE.compare(obj1, obj2);
if(compare < 0){
writer.write(obj1);
list1.removeFirst();
}
else{
writer.write(obj2);
list2.removeFirst();
}
if(list1.size() == 0){
list1 = read_5(reader1);
}
if(list2.size() == 0{
list2 = read_5(reader2);
}
}
while(list1 != null){
SuperObject obj = list1.removeFirst();
writer.write(obj);
if(list1.size() == 0){
list1 = read_5(reader1);
}
}
while(list2 != null){
SuperObject obj = list2.removeFirst();
writer.write(obj);
if(list2.size() == 0){
list2 = read_5(reader2);
}
}
out.close();
in1.close();
in2.close();
return retFile;
}
public static LinkedList<SuperObject> read_5(Reader reader){
LinkedList<SuperObject> list = new LinkedList<SuperObject>();
SuperObject obj = null;
while((obj = reader.read()) != null){
list.add(obj);
}
if(list.size() == 0){
list = null;
}
return list;
}
take 10 items and create Min Heap with these 10 items and compare next element with root if we found any element greater than root than replace root element with this element and call heapify so that again min heap root element contain minimum value. keep on doing same thing untill we reached at the end of array. So finally min heap contain 10 highest element that we should place at last 10 position. But As we know min-heap does not give guarantee of sorting, we have to call any sorT(Heap Sort ) recommended. now next time just n-10 element need to process as same way.
So Its kind of bubble sort (n,n-10, n-20, n-30,......20,10).
My idea is "2 Steps Forward" Then "2 Steps Backwards"
Loop this for 50 times (file.length/2)
- Vj May 10, 2015