Intel Interview Question for Software Developers


Team: big data
Country: United States
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
0
of 0 vote

My idea is "2 Steps Forward" Then "2 Steps Backwards"
Loop this for 50 times (file.length/2)

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(100);
		}
	}

	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;
		/**
		 * Need to find the golden spot ... Log does not work. 
		 */
		int loopCount = file.length / 2;

		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(10000);
		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");
	}
}

- Vj May 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

[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");
	}
}

- Anon May 10, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Use external sorting. There are two basic algorithms for this, a two way merge and multi way merge.

- angshu1986 May 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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;
}

- zortlord May 12, 2015 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

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).

- rathor.rajeev August 21, 2016 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More