vaidehi.venkatesan
BAN USER1. What is the individual dimension on each chocolate ? L x b x h? It can 1x1x2 or cuberoot(2) ^3. All solutions discussed are assuming each side is of dimension 2 which is not the case from the question atleast.
2. Are all chocolates are of same dimension or different dimension ? [they could still have same volume]
O(n) solution
int findMaxWindowWithDistinctElems(string& s){
int sqStart = 0, sqEnd = 0, numElems = 1;
int resStart = sqStart, resEnd = sqEnd, res = numElems;
int ascii[256];
for(int i=0; i<256; i++){
ascii[i] = 0;
}
ascii[s[0]] = 1;
for(int i=1; i<s.length(); i++){
if(ascii[s[i]] == 0){
ascii[s[i]] = 1;
sqEnd = i;
numElems++;
}else{
if(numElems > res){
res = numElems;
resStart = sqStart;
resEnd = sqEnd;
}
for(int j=0; j<256; j++){
ascii[j] = 0;
}
ascii[s[i]] = 1;
sqStart = i;
sqEnd = i;
numElems = 1;
}
}
if (numElems > res){
resStart = sqStart;
resEnd = sqEnd;
res = numElems;
}
return res;
}
Stats:
- vaidehi.venkatesan November 28, 201510GB data
250 MB RAM
How many movies are there in this world ? 0.5 million ?
Amount of information per movie available = 10GB/0.5M = 20 KB of information. So most likely textual information and not the movie itself.
How much can 250MB RAM hold ? 12.5K movies at a time - 40 loads of the data per query to search for title. (linear search/binary search - you still need to load data to acknowledge that the section of data is not what you are looking for.!).
Alternative approach - MD5 hash the movie title - 16 bytes (128 bits). Another 200 bytes to store the movie location on disk. = 250 bytes per movie stored in a hash map = 1 M movies can be looked up!
So, when a query comes in, MD5 movie title, look up in hash map, go to disk (IIIIIIII/OOOOO) and fetch the description and display it!
- Multidisk arrays ? and store in hash map the disk location
- RAIDs for greater IOPs.? (Prefer read- friendly RAIDs for cheaper cost)
Use multi-core machine to parallelize request processing.