NetApp Interview Question
AnalystsTeam: Bigdata analyst
Country: India
Interview Type: In-Person
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.
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!
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.BufferedReader;
import java.io.File;
import java.io.FileReader;
public class FirstAndSecondLargest {
public static void main(String str[])
{
FileReader fileReader=null;
BufferedReader buffReader=null;
boolean initializeOnlyOnce=true;
int firstLarge=0;
int secLarge=0;
int nextNumberInFile=0;
StringBuilder integersInFile = new StringBuilder();
File file = new File("c:\\TestFile.txt");
try {
fileReader= new FileReader(file);
buffReader = new BufferedReader(fileReader);
String strr=null;
while ( (strr=buffReader.readLine() )!= 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 {
fileReader.close();
buffReader.close();
} catch (Exception ex) {
}
}
}
}
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.
- masterjaso August 31, 2013