Ana
BAN USER- 2of 4 votes
AnswersHow do you find the greatest 1000 elements in a list of a million elements? No other information given. What would be the runtime? Hint: You can do better than O(n log n). I didn't realize but it could be possible with Tree or Heaps.
- Ana in United States| Report Duplicate | Flag | PURGE
Google Software Engineer / Developer Algorithm
I answered this incorrectly during the interview. But now when I did it, I managed to do it properly.
Here's my code : (Please suggest if you think anything's wrong with it)
import java.util.ArrayList;
import java.util.List;
public class FlattenList {
List<List<Integer>> vv;
private int currentIndex = 0;
private int currentList = 0;
private FlattenList(List<List<Integer>> vv) {
this.vv = vv;
}
public boolean hasNext() {
while(currentList < this.vv.size()) {
List<Integer> thisList = this.vv.get(currentList);
if(currentIndex < thisList.size()) {
return true;
}
else {
currentList++;
}
}
return false;
}
public int next() {
if(hasNext()) {
List<Integer> thisList = this.vv.get(currentList);
if(currentIndex == thisList.size() - 1) {
int temp = currentIndex;
currentIndex = 0;
currentList++;
return thisList.get(temp);
}
else if(currentIndex < thisList.size()) {
return thisList.get(currentIndex++);
}
}
return -1;
}
public static void main(String[] args) {
int[] ints1 = {8, 3, 5};
List<Integer> intList = new ArrayList<Integer>();
for (int index = 0; index < ints1.length; index++)
{
intList.add(ints1[index]);
}
int[] ints2 = {2, 7};
List<Integer> intList2 = new ArrayList<Integer>();
for (int index = 0; index < ints2.length; index++)
{
intList.add(ints2[index]);
}
List<List<Integer>> listOfLists = new ArrayList<List<Integer>>();
listOfLists.add(intList);
listOfLists.add(intList2);
FlattenList fl = new FlattenList(listOfLists);
while(fl.hasNext())
System.out.println(fl.next());
}
}
Deleting extra comments is tad easy. Just edit select all the content, delete it and then click on delete. Don't you think these additional comments are way too many??
- Ana April 24, 2013