## NetApp Interview Question for Analysts

Team: Bigdata analyst
Country: India
Interview Type: In-Person

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

If this was the complete interview question, I would follow up with several clarifying questions to ensure you are on target (and to display that you have the aptitude for developing requirements that your client might not even understand they need).

Q1: Is the file sorted?
Q2: What are the memory constraints? (can we load the entire file to memory, or must we work with the stream)
Q3: Are we finding just the 2 largest, or the Nth largest?

For the sake of my answer, I will assume the file is unsorted, the file is too large to load into memory, and that we are seeking the Nth largest. In this instance, you would establish a file input stream using your chosen programming language, and then parse the input one number at a time. You also declare a linked list to keep track of your Nth largest items in sorted order. Each time you evaluate a number you compare it to the smallest element in your list (the first element). If it is larger, you add to the correct spot in the list to maintain sorted order. If the list size is larger than Nth larger elements, you delete the smallest node.

This algorithm will give you O(n) worst case running time. For the worst case, your file would be sorted ascending and you would have to add every element to your list which requires N*K elements operations, which truncates to O(n). The space complexity is O(N) as you only allocate memory in proportion to the number of elements you want to find.

``````public LinkList findNthLargestFromFile(InputStream in, int n){
int temp;

while(in.hasNext()){
temp = in.getNextInt();
if(temp > list.getFirst() || list.size() < n){
list.sort();
if(list.size() > n){
list.deleteFirst();
}
}
}
return list;
}``````

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

Your approach to problem is correct,but time complexity analysis is wrong.Above is an O(N^2) algorithm(consider when all elements all in descending order then you would do swap for every new element to be inserted in you linked list).It is better to construct an Heap of Size K if you may be required to return k'th smallest element from file.

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

There is only 1 while loop and you are doing constant time operations on every element, even in the worst case. Without a second loop causing you to re-evaluate each and every node, it has to be less than O(n^2). As explained above, even in the worst case you are doing one insert and one deletion from your tracking list. That evaluates to some constant times N, which truncates in asymptotic analysis to O(N).

I do agree that a heap would be more ideal than manually managing a LinkedList. Thank you for the idea/correction!

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

I have written a code to find the first highest and second highest from a file .
1) For better optimization instead of reading character by character , I read the whole line as a string using BufferedReader , and then split the sting and find the first and second higest.
This same program can be modified to find the nth highest/smallest
*** instead of putting them in a string [] - we can put them in an ArrayList and then use the Collections.sort and then find the nth higest or smallest by the array index .

#######################################################################
package com.CareerCup;

import java.io.File;

public class FirstAndSecondLargest {

public static void main(String str[])
{
boolean initializeOnlyOnce=true;
int firstLarge=0;
int secLarge=0;
int nextNumberInFile=0;
StringBuilder integersInFile = new StringBuilder();
File file = new File("c:\\TestFile.txt");
try {
String strr=null;

{
integersInFile.append(strr) ;
}
String resultStr[] = integersInFile.toString().split("\\s+");

firstLarge=Integer.parseInt(resultStr[0]);
secLarge = Integer.parseInt(resultStr[1]);

int len= resultStr.length;

for(int i=1; i<len;i++)
{
int nextNumber = Integer.parseInt(resultStr[i]);

if( nextNumber > firstLarge)
{
secLarge= firstLarge;
firstLarge = nextNumber;
}
else if(secLarge < nextNumber && (secLarge < firstLarge))
{
secLarge = nextNumber;
}

}

System.out.println("first larget ="+firstLarge+"second largest "+secLarge);

}

catch (Exception ex) {
ex.printStackTrace(System.out);

}
finally
{
try {

} catch (Exception ex) {

}

}

}

}

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

Maintain a heap of N elements, and each next item read from the file, push into the heap. If you maintain a max heap, then highest element in file will be at the top and last element in the heap will be the Nth largest element of the file.

Comment hidden because of low score. Click to expand.
0
of 0 vote
1) Use a 2 element array A[] 2) Have a 0/1 flag called "highest." .... assume it's boolean If highest=0, then A[0] is highest, A[1] is 2nd highest If highest=1, then A[1] is highest, A[0] is 2nd highest (Just explaining the variables, no code so far) Pseudocode (I thought of this now, is it cool? May be buggy) : 1) Set A[0]=A[1]=read_num(); // read first int (assume file not empty) 2) loop on reads: {{{ while( file_not_at_end() ) //check if file is empty or not { x=read_int(); //assume this grabs the next int off the file if( x > A[highest] ) { A[!highest]=x; highest = !highest; } else if( x > A[!highest] ) A[!highest] = x; } // now A[highest] is the max, A[!highest] is the min
Comment hidden because of low score. Click to expand.
0
1) Use a 2 element array A[] 2) Have a 0/1 flag called "highest." .... assume it's boolean If highest=0, then A[0] is highest, A[1] is 2nd highest If highest=1, then A[1] is highest, A[0] is 2nd highest (Just explaining the variables, no code so far) Pseudocode (I thought of this now, is it cool? May be buggy) {{{ Set A[0]=A[1]=read_num(); // read first int (assume file not empty) while( file_not_at_end() ) //check if file is empty or not { x=read_int(); //assume this grabs the next int off the file if( x > A[highest] ) { A[!highest]=x; highest = !highest; //too bad "!= won't work here" } else if( x > A[!highest] ) A[!highest] = x; } // now A[highest] is the max, A[!highest] is the min

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.

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