CareerCup

All of the operations being O(1) looks like the interviewer is asking for a hashmap implementation.
Simplest way of implementing a hashtable/map requires two things:

1. Data structure to store key value pairs, we take array named A of size = sz
2. A hash function F.

So, our Hashtable will store key value pairs and allow Insert, Delete, Search and getRandom in O(1) time.

Insert:

Using the Hash function F, find the index(idx) where the key-val pair will be stored i.e.
idx  = F(key)
and store the key-val pair over there
H[idx] = key+val
Now, if that position is already occupied, it means we have a collision. Collisions can be handled in 
multiple ways. One simple way is to keep increasing the index till an empty space found (linear probing):
while ( H[idx] != empty && idx < size) {idx++;}. When empty cell found, insert the key-val pair.

Search and Delete are along the same lines. Just find the idx using F(key) and see if it matches the input key
For delete, just insert an special value (called tombstone) to prevent our linear probing from going wrong.

getRandom:
Bascially return any random entry from the array. Pick a random number using random number generator and use
the modulus operator to convert it into a suitable index i.e. idx = random_number % size
Now, return the key-val pair at this size.

Store hash map from items to index in array. For insertion just push back item to the array and add corresponding record to hash map. For deletion determine position of deleted item in array and in array perform swap this item with last item. Decrement size of array and reflect swap changes in hash map.

Can we use built-in data structures to define our own? i.e. if I use a vector or map in my structure, will it be the violation of rules or not?

This is certainly HashMap/HashTable implementation.