Medlife.com Java Developer interview questions

last round-> input stream of no.s , find count of elements minimum than this coming number in better than O(n), I told max heap but it's n/2 better than O(n) and second is BST which is difficult to implement. Interiewer was ok with heap approach but i told its better than linear but still linear then he said work it out in log n