any ideas

[Muhammad Ali Ammar]

you are required to design and implement a data structure that works like an array . it minimizes the use of memory and supports the following operations:
a- put(int v, int loc): inserts an integer v in to the location loc. Note that the value of loc is in the range from 0 to 10,000,000. the maximum number of locations in the structure is 10,000
b- get (int loc): returns the value in the location loc. if there is no value at that location is should return 0.
c- find memory required for the data structure and the complexity for each operation. ( Hint: simple array will not work )

[kbw]

What's the problem? Do you understand what you're being asked?

[jonnin]

there are any number of inefficient ways to do this.
struct s{int v; int loc;};
s data[10000];
int num_used;
keep num_used up to date when you insert, and keep data sorted by loc, binary search out to see if a loc is in there when asked. Can you do a one pass sort to put the data where it belongs in only O(n) each time? You don't need a full sort; its all sorted except one value each go... this is a balanced approach, and fairly straightforward.

more interesting, can you find a way to make a hash table off (v,loc) into 10k and handle collisions? This will be very efficient, but a bit more work to really get it right and its going to begin to behave poorly if they give you more than 3k or so inputs.

it would be nice to know more, are they looking for time or space efficiency? What is the expected input (at least, how many inputs would be nice to know).

[salem c]

You can fake an array using a linked list.
struct s{int v; int loc; struct s *next;};
get (int loc) is just following next until node->loc == loc or you fall off the end of the list.

You can fake an array using a binary tree.
struct s{int v; int loc;struct s *left, struct s* right};
get (int loc) is just comparing loc with node->loc and deciding whether to go left or right.