CareerCup

you could keep an array of 3 integers that stores the top 3 elements...then in single pass by comparing the current element to these 3 elements we can update the array. the smallest element in this array at the end is 3rd largest

How about create a max heap? you can do this in 1 pass

Assuming that space is not a constraint:
1) create a max heap in one pass
2) take the top 3 elements off the heap

or bitmap?

How about using a Prefix Tree of dictionary words and searching through the given string to find the longest word?

dude did u have to write the code or just did they expect you to give an idea of ur algo ??

here is the o(n) sol with one pass:

public static void thirdLargest(string[] a)
{string fLarge ="";
string sLarge= "";
string tLarge = "";
string temp = "";
for (int i = 0; i < a.Length; i++)
{


if (a[i].Length > tLarge.Length)
{
tLarge = a[i];

}
if (tLarge.Length > sLarge.Length)
{

swap(tLarge, sLarge);<---write a normal swap function

}
if (sLarge.Length > fLarge.Length)
{
swap(sLarge, fLarge);
}

}

Console.WriteLine("Third Largest:"+ tLarge);
}

public static String find3rdLargest(String str) {
char[] ch = str.toCharArray();
int state = 0; //initialized
int count =0;
int noOfSpaces = 0;
int startPos = 0, endPos = 0;

int[] counts = new int[3];
int[] startPoss = new int[3];
int[] endPoss = new int[3];


for(int i=0; i <ch.length; i++) {

// for space (or) end of the array
if(ch[i] == ' ' || i == ch.length -1) {
if(state == 0 || state ==2) {
state=1; //space
if (counts[0] < count) {
counts[2] = counts[1];
endPoss[2] = endPoss[1];
startPoss[2] = startPoss[1];
counts[1] = counts[0];
endPoss[1] = endPoss[0];
startPoss[1] = startPoss[0];
counts[0] = count;
endPoss[0] = i - noOfSpaces;
startPoss[0] = startPos;
} else if (counts[1] < count)
{
counts[2] = counts[1];
endPoss[2] = endPoss[1];
startPoss[2] = startPoss[1];

counts[1] = count;
endPoss[1] = i - noOfSpaces;
startPoss[1] = startPos;

} else if (counts[2] < count)
{
counts[2] = count;
endPoss[2] = i - noOfSpaces;
startPoss[2] = startPos;

}
count = 0;
endPos = i - noOfSpaces;
startPos = i + 1;

} else if(ch[i] == ' '){
noOfSpaces ++;
}


} else {
noOfSpaces = 0;
state =2; //character state
count ++;
}


}

System.out.println(Arrays.toString(counts));
System.out.println(Arrays.toString(startPoss));
System.out.println(Arrays.toString(endPoss));
return str.substring(startPoss[2], endPoss[2]+1);
}