Friday, February 26, 2016

Introduction:
Have you ever misplaced an item and couldn’t recollect where you kept it ? Did you ever have to close your eyes and recollect when and what happened to recall something.  Wouldn’t it be ideal if you had photographs at frequent intervals that told you everything you saw and you could scroll through forwards and backwards. Further lets assume that this capability had very little physical presence but something part of what you already wear. For example your eyeglasses could have a small detachable storage and a pinhole camera that could take frequent pictures.  The size of the pictures can be such that many of them can be taken and stored. In this case even thumbnails would do. Their storage can be detached and fed into a computer. Hence the use of a storage card on the glass and a USB adapter sold separately
How is it different from a google glass ?
First google glass is a computer attached to the eyeglass. Second  google glass appears external to the eyeglass and third it is lot more general purpose that what we propose. Our proposal is just a camera and memory. It sits flush with the glass rim and has no other external add-ons. Customers opt in to it just as they would with the tint or coating for their lenses.  The camera merely captures images at frequent intervals into a circular buffer. If the images are small, it can store say 86400 of them. These images are sufficient for a 24 by 7 timeframe.
Software:
Since the hardware is merely a camera with a detachable storage seamless with the eyeglass, it behaves the same as an external storage. This external storage can then be inserted into any personal computer for facilitating all kinds of operations on the images.
The circular ring buffer used for these images can be configured with a schedule. For example, the frequency can be changed from every second to every minute. Additionally certain hours of the day can be used to deactivate the camera. All of these configurations are mounted for reading by the camera using a predetermined file which is edited only with when the detachable storage is used with a personal computer.
The algorithm to store the images can be one of the following:
Round robin: The images are progressively stored in sequential order and wraps around. This can also be considered First In First Out
Clock is similar to FIFO but more efficient. When there are no empty frames, if the next frame has an R bit or referenced bit set then it is cleared otherwise it is replaced. The reference here comes from when a user taps the camera to pin the image
Least recently Used: These evicts the images based on those that are less frequently used in a specific time interval. A reset operation clears the time interval but not the images. The word 'used' here comes from a predetermined linear range of relevance and not the classical definition of actual usage by something other than the camera.
The difference is that the former doesn’t need to use timestamps where as the latter does.
Aesthetics:
There are some aesthetics involved here just as it would be on Apple devices. The camera and memory should not be conspicuous or interfere with the style and look of the glasses. Therefore they may appear only in full rimmed glasses and the storage can be mounted as a tip of the eyeframe.

#Google code jam exercise:
I have a sequence of N binary digits. I am looking for a substring with just the right proportion of 0s and 1s, but it may not exist, so I will settle for something that's just pretty good.
Can you find a substring where the fraction of 1s is as close as possible to the given fraction F? Output the earliest possible index at which such a substring starts.

Solution
We maintain a running total of 1s encountered so far at any index. When we pick two indexes on this running total such that the difference in the total divided by span of the indexes is closer to the fraction, we return the lower index as the answer :

Int getIndex ( int N, int F, List <int> map)
{
var y = new List <int> (N+2);
for (int i = 0; i < n; ++i) {
    y[i + 1] = y[i] + map[i];
}
double previous =0;
int index = 0;
for (int i = 0; i < n; ++i) {
 for (int j = i + 1; j <= n; ++j) {
double t = (y[j] - y[i]) / (j - i);
if (t > previous && t <= F) {
index = i;
previous = t;
}
}
return index;
}

In the code above we assume 0 to be the default because the question implies that there will be one found 
Also note that we can even have  a threshold of how accurate you want to be with regard to the fraction.
In this case, we would compare t-F to be less than a margin of error and we would make sure that the delta is less than zero. This way we are just under the fraction.




No comments:

Post a Comment