I was asked this question by an interviewer. I tried solving it using an array, such that I make sure the array in sorted when I insert. However I don't think this is the best solution. What would be a good solution for this problem?
Make an augmented search tree. This is an ordinary binary search tree, where each node additionally stores the number of elements in its subtree. This data structure is known as order statistic tree.
If we balance the BST (making it an AVL tree for instance) then insertion can, of course, be done in logarithmic time (incrementing the node count along the search path).
Also finding the k-th element is logarithmic time. Let $n$ be the number of nodes in the left subtree of the root. If $k=n+1$ we return the root. If $k\le n$ we continue in the left subtree. If $k>n$ we return the $k-(n+1)$-st node in the right subtree.
You can use Heaps. Min heaps can find kth smallest element in O(k* logn) i.e O(logn) times if heap is already build. If not in O(n + k*logn) times i.e. in O(n) time if heap is to be build from the scratch.
You can refer - https://www.geeksforgeeks.org/kth-smallestlargest-element-unsorted-array/ for more informaiton
Insertion can be done in O(logn) times in heaps.
Refer - Heaps