CareerCup

use array int a[9]. The number is the array index, a[index] represents how many of this number received so far.

Do you mean to say we have to avoid duplicate numbers?
If this is the case we can use HashTable.

we can use multiset if we need to account for duplicates

what do you mean?
if it is the case just represents a stream of 1~9, you can use any data structure.

Hash table or a simple array A[10] will do. Anyways I feel the question is not clear.

Hash table or a simple array A[10] will do. Anyways I feel the question is not clear.

Question is pretty much clear.

STL: We can use Vector,Deque,List,Multiset,Multimap to store duplicate elements.
Non-STL: An array i.e. int arr[9]; or a link-list.

I think the question means that there might be an unknown length stream(sequence) of numbers, which lie between 1 and 9.
In this case, something like array A[9] or array A[10] would not be a good idea as the length of the stream is unknown.
Hence, for me, a more correct answer would be a linked list as the length can be variable and would not have to be known at compile time.
Possible drawback of linked list would be that the data(number) we would like to store in each node would be far smaller (shorter in terms of bits needed to represent) than the pointers that would maintain the list.

Any suggestions to get around this issue?

Array solution is simple, fast and straightforward. Secondly if size is an issue one could make an array of "unsigned long long" which can count a max of 2^64 - 1. That should be more than enough to handle trillions of numbers (18,446,744,073,709,551,615 to be precise).

I was asked this question: "You are getting stream of numbers between 1 to 9 (this may contain duplicates). You have to maintain these numbers in SORTED array (don't discard duplicates). Which is the best data structure you would use?"
Answer that I can think of is: link list, because array is bad idea as number of elements is unknown. With link list, insertions are faster so maintain a sorted link list and as you get a new number, insert it at a proper place in link list.

how abt using a binary search tree...insert element at root and it finds its location..if there is duplicate place the number in either the Successor/Predecessor...operations are performend at o(log n)..its way better than linked list..

A balanced AVL tree or a red black tree wud be the best since the worst case insertion & lookup times are O(logn). But, extra time may be consumed for node rotation & tree balancing. Hashmap is a bad approach wherever sorting is required. Hashmap is good if we need to deal with duplicates & want O(1) access time. So, balanced binary is the best i can think of.

How about we have an array of structures. The structure has 2 fields. The number and the no. of instances that the number has occurred. This solution can solve the space problem as well

It depends how those numbers will be used later. It may appear that we don't need to store them at all. The question doesn't say about it anything.