student student Interview Question
Students StudentsCountry: United States
Can we use bit flags to store vehicle information:
suppose there atmost 4 doors.. these can be represented by only 2 bits.: 00, 01, 10, 11.
Assuming,,00 represents 1 door and 11 represents 4 doors as a car cannot have 0 doors.
Assuming basic Color can be represented by 3 bits: RGB..each bit represent single whether the color is included in car or not. (Not considering the percentage of each color include.just considering the basic color are added or not as a whole)
AC/Non AC can be represented by single bit: 0 - NonAC, 1- AC..
So overall, a vehicle with 4 door, blue color and AC can be represented as:
110011. This byte can then be the key in the hash table and a vehicle can be retrieved.
expanding this solution for N:
if total no doors is N, then we need log2N bits i.e 2^k = N, k bits for storing N doors
if total no colors is N, then we need log2N bits i.e 2^ck = N, ck bits for storing N colors
For AC/NoAc we just need 1 bit.
so total number of bits : K + CK+ 1 ~ log2N + log2N + 1
If there are more than 1 car with same combination, we can store a pointer to start of a linked list
inside the hashstable, and when queried, we can retrieve the entire list by traversing it. and show all
possible vehicles
Steps:
1. Each Object should implement Serializable
2. Let's create a key( from the number of doors and color ) so that the key is incremental and unique.
3. Assuming we have 1-1m doors and 1-1m color. Lets divide the objects and put into files of chunks say 1MB per file(this can be optimized if needed). Each file will be mapped to the key of the first object serialized into the file.
4. Use this keys to create a Binary Search tree and map the key to the file name in a hashmap.
5. Take input of the object search requirement. Create the key. Search in the BST. Find the file which might contain the serialized object. Load the file and do a normal search of the Exact object instance you might need.
The tuning factor might be the file chunk size.
create a string with doornumber+color+hasac and use this as a key for hash table which is of type
- dude March 26, 2013hashtable<String,Arraylist<Vehicle>>
so when we need blue car with six doors with ac,the key would be 6bluetrue and get the list of vehicles against that key