#code jam question.
There is a house of pancakes with limited number of pancakes that are initially distributed to D diners with ease having di pancakes on their plate where I is the index of the diner. Each diner takes one minute to eat one pancake.  There are infinite other diners who have empty plates. The server can halt all diners from eating by calling a minute as special. During this minute, he can take away some pancakes from one diner and give it to another. If this is the only move he can do, what is the minimum time to finish the set of pancakes ?
Solution since the number of empty diners are infinite we can increase the degree of parallelism by adding empty diners from one through a large number, say 1001. There is no efficiency possible without increasing the DOP and we exhaust the search space to find the best DOP by incrementing it by 1 at a time.moreover each pancake can contribute to an increase in DOP For each incremental DOP we look for the mininum time. The minimum time
is a cumulative of the reduced number of
 pancakes for each no empty diner. We know that the reduction happens with an increase in DOP x by 1 during a special minute. Consequently our solution is the  minimum time calculated as the minimum of the sum of time takwn by each non empty diner for that DOP.

Int getMinTime (list <int> pancakes)
{
Int min =INT_MAX;
For (int x=1; x < 1001; x++;)
{
   Int sum =0;
   For (int I =0; i < pancakes.count(); i++;)
{
      Sum += (pancakes [i] + x - 1) / x - 1;
}
sum += x;
If (sum < min)
    min = sum;
}
Return min;
}

Today we conclude reading the paper titled Jigsaw : Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.Jigsaw lets mashups be isolated with its framework  and lets them selectively expose private state. At the same time Jigsaw is developer friendly requiring very little changes as compared to the other related work with their cumbersome policies. The use of public/private keywords is also natural to programming languages such as Java. Related work also use frames for isolation. Jigsaw uses boxes that can share the same origin. Jigsaw also uses proxy for principal objects that have to be shared across domain. Moreover Jigsaw facilitates pass by reference for surrogate objects for cross domain access. Jigsaw also has similar or better performance than  other related work.

Today we continue to discuss jigsaw.Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.

Jigsaw lets mashups be isolated with its framework  and lets them selectively expose private state. We were discussing the  related work. There were two techniques that came pretty close to Jigsaw. First, there was ObjectView with its flexible security policy. However it seems too clunky and an overkill as compared to Jigsaw declarative public and private keywords. Second was IFC which required developers to annotate and the engine to apply security tags to variables. Again the public private syntax is much easier. Moreover tagging variables is not suited for managing access to visual fields. Jigsaw does this with the full flexibility that case allows.
Conscript is another library that modifies the browser engine to apply security. Integrators specify policy code and these are attached at specific execution points such as the start of a function or the load of a module. These policies are similar to ObjectView policies and have the same advantages but jigsaw syntax is simpler.
OMash comes closer to Jigsaw in that it allows public functions to be declared for sharing. However it does not enforce private only access by default. Moreover the return value from the function can divulge sensitive data. On the other hand, Jigsaw allows both public and private and supports proxies.
MashupOS provides a new model where services instances are similar to the processes on an operating system and get partitioned physical resources. They communicate with each other using pass by value messages. This is elaborate by itself and still has shortcomings that Jigsaw does not. Jigsaw avoids such communication altogether with its pass by reference semantics.
CommonJs introduces another technique that gives each library it's own namespace  and expose functions. However it suffers from the same limitations with regard to property manipulation and return value exploit as OMash.  This is because the namespace are implemented using closure which allow prototypes to be transformed as opposed to Jigsaw's box.

#Google code jam
Ominoes  are jigsaw puzzle pieces made by joining unit square pieces along one or more of their edges. An X ominous has X such unit squares. Richard picks one of the X Ominoes and Gabrielle uses that piece and Amy other piece or their copies to fill an RxC grid. If Gabrielle fills the grid she wins otherwise Richard wins. Given arbitrary X, R, C determine who wins
Void GetWinner (int X,  int R, int C)
{
String answer = "Richard";
If ((R×C)%X == 0){
if ((R%X==0 || C%X==0) && C >X-1 && R > X-1)
{
 answer = "Gabrielle";
}
Console.Writeline (answer);
}

The problem can also be solved recursively with the assumption that a square of size greater than X  and edge equal to min (R,C) can be filled by X dominoes and accounting for different orientations and positions of the remaining

Another way to solve the problem is to eliminate R-X and C-X and see if it can be solved for X by X as long as those R-X and C-X are divisible by X.

I am going to get a caprese sandwich and squash soup from yellow dot cafe.

Another way to look at this problem is to check if X+1 is greater than double the  minimum of R and C  in which case Richard wins because essentially you are using a vertical line after X.

Today we continue to discuss jigsaw.Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.

Jigsaw lets mashups be isolated with its framework  and lets them selectively expose private state. We were discussing the  end to end performance study of Jigsaw. 

Today we continue to discuss related work. We saw the differences between Jigsaw and Dojo, Fbjs and Caja. We now look into Secure ECMA script. This provides Caja like isolation without the rewriting and runtime virtualization. It pushes security checks into the Javascript engine. This can reduce costs significantly and Jigsaw can use some of thsee checks from the upcoming versions of SES.

We now look at pass by value systems. PostMash uses iframes as isolation containers and performs cross domain communication with asynchronous pass by value calls. These become quite expensive when each container clones the object graph. The degradation was to the tune of 60% for a Google maps mashup.  The expense comes from marshaling as well as asynchronous calls that increase traffic. Moreover  such calls are not really suited for modules that require a lot of computations such as those involving databases, cryptographic methods, input scrubbing, and image manipulation. 

Iframes are better at isolation than Jigsaws box boundaries because a parent can make progress when a child is busy. In Jigsaw, several boxes can exist in the same iframe. If one box misbehaves, it can cause denial of service to others. But this is not a major concern because browsers terminate unresponsive scripts with user consent 

ObjectViews enable full policy code to be written in Javascript

 This is very expressive but the same benefit can be achieved with simpler declarations such as  public private keywords.

#codingexercise

Given an array of prices of a stock in a day on each day and with unlimited sequential transactions, find the max profit.

int GetMaxProfit(List<int> prices)

{

int max = 0;

int sum = 0;

for (int i = 1; i < prices.Count(); i++)

{

int diff = prices[i] - prices[i-1];

if (diff > 0)

    sum+=diff;

}

return sum;

}

If there were two simultaneous transactions that can be performed  then we can use dynamic programming to combine the max profit from each.

TotalMaxProfit = max(MaxProfit(0,i) + MaxProfit(i+1, n))  for 0<=i<n

The maxprofit example shown above can also target  a single transaction only.

On this case,  instead of cumulative positive differences, we keep track of the min price and take the difference between the current price and the minimum price. We return the maximum of such differences as the answer 

int MaxProfit(List <int> prices)

{

int min=INT_MAX; 
int max =0; 
int diff=0; 
for(int i =0; i< prices.Count(); i++) 
{ 
if(prices[i]<min) min = prices[i]; 
diff = prices[i] - min; 
if(max<diff) 
max = diff;
} 
 return max; 
 }

We discuss a Google code jam problem

 A large storage facility has  2⁴⁰ storage locations arranged in a circle.

A truck with a crane on it moves along the circle of storage locations, picking up or putting down crates according to a program. (The truck has an unlimited supply of crates on board, so it can always put more crates down.)

The program consists of a sequence of these instructions:

• b : move back one location
• f : move forward one location
• u : pick up one crate at the current location
• d : put down one crate at the current location
• ( : do nothing
• ) : if there is more than one crate at the current location, move back to the most recent ( in the sequence of instructions, and continue the program from there. (This doesn't move the truck.)

( and ) instructions in the program will always come in pairs: a ( will be followed later by a matching ). There will be at most two such pairs in the program, and if there are two pairs, they will not be nested – that is, there will be either:

• no ( or ) instructions;
• one ( instruction somewhere in the program, followed later by one ) instruction;
• a ( instruction, followed later by a ) instruction, followed later by another (, and again later by another ).
• There are always between 1 and 256 crates at any location.

How many movements will the truck make before reaching the end of the program.

For example :

Input :
ufffdddbbbdd has three forward and three backward movements.
ddd (fdbu)fff had two movements repeated one for instruction in the enclosed sequence and followed by three forward motions totalling 11
dddd (fdddddbu)f (fddddddu) has sixteen motions due to the pattern of the enclosed sequence with the motions from the second sequence repeated twice due to the single forward instruction just prior to the sequence leading to a total of 3×16+1=48

Int getMotions (string sequence)
{
Int  total = 0;
Int I = 0;
While( I < sequence.Count)
{
I++;
If (sequence[i] == 'f'  || sequence  [i] == 'b') {total++; }
If (sequence[i] == '(')
{
 Int count = 0;
 Int sum = 0;
 For ( int j = i+1; j < sequence.Count && sequence [j] != ')'; j++)
 {
  count += 1;
  if (sequence[j] == 'f'  || sequence  [j] == 'b') sum++;  
  assert (sequence[j] == '('  || sequence  [j] == ')');
 }
 sum *= count;
 If ( i > 1 && ( sequence[i-1] == 'f'  || sequence  [i-1] == 'b'))
   sum *= 2;
 total += sum;
 i += count;
}

}

Return total;
}

Today we present a solution to a coding question:

Given an array S of n integers, find three integers in S
such that sum is closest to a given number, target. Return the sum of the three
integers. You may assume that each input would have exactly one solution.

Array S = {-1, 2, 1, -4 } and target = 1. The sum that is
closest to the target is 2. (-1 +2 + 1) = 2

Int getClosestSum(List<int> sorted, int target)

{

sorted.sort();

Int min = INT_MAX;

Int val = 0;

Int len = sorted.count;

For (int i=0; i<len; i++)

{

Int start = I + 1, end = len-1;

While (start<end)

{

Int sum = sorted[i] + sorted[start] + sorted[end];

If (sum == target)

{

min = 0;

val = sum;

break;

}

If (sum  < target)

{

If (target-sum< min)

{

min = target –sum;

val = sum;

}

start++;

}

Else

{

If (sum – target < min)

{

min = sum – target;

val = sum;

}

end--;

}

}

If (val == target) break;

While (i < len -1 && sorted[i] == sorted[i+1]) i++; 

}

Return val;

}

We could also use a different technique for arbitrary length selections such as number of integers chosen = 4, 5, 6,  ... N-1 etc.

Here we could generate all combinations of length = 4, 5, 6 ,... N-1 from the given set of integers.

They need not be sorted in this case.

Then for each combination we find the sum and pick the one that closes to the target.

The combine() method described earlier in the posts does just this - given an array of n elements, generate combinations of all lengths.

Today we continue to discuss jigsaw.Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.

Jigsaw lets mashups be isolated with its framework  and lets them selectively expose private state. We were discussing the  end to end performance study of Jigsaw. 



Today we discuss related work. There are many preexisting frameworks that try to secure mashup applications. Jigsaw differs from those with a simple syntax. Moreover it provides hierarchical security and enables a pass by reference synchronous calls.Dojo Secure uses a restricted portion of the Javascript language and forces legacy applications to be rewritten. Jigsaw on the other hand doesn't. Fbjs also requires rewriting by prepending a prefix to all identifiers. Caja places scripts in virtualize execution environments and defines a tame (obj). A tame method performs many of the security checks that Jigsaw also does.





Jigsaw differs from Caja in the following ways:

Caja implements checks at sharing time not at declaration  time.

Developer must remember to call tame(obj)

Boundary crossings are not clearly discernible.

Caja is focused on making it easy for integrating page to load untrusted scripts. Jigsaw supports guest to guest access just as much.

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.

Today we continue to discuss jigsaw.Efficient, low effort mashup isolation by James Mickens and Matthew Finifter. Mashups are web applications that contain code from different principals.
Jigsaw lets mashups be isolated with its framework  and lets them selectively expose private state. We were discussing the porting effort involved with Jigsaw and performance improvements. We now review end to end performance study of Jigsaw. Jigsaw performs checks on property accesses. It does bookkeeping of all objects be setting their box id and object id. It checks access to virtualized browser resources for compliance to security policies. All this might affect the end to end performance. Consequently three different libraries were ported over to Jigsaw and their performance evaluated. These libraries include  JSON-RPC a library that performs RPC over Ajax connections.  A local host server is chosen over a remote server to avoid network delays in performance evaluation. A DOM-SQL library that uses SQL as the storage for DOM was another library used. The AES encryption function I'm the standard crypto library was also used for the study. Mousemove is another simple benchmark library that registers handlers on mode moves. In each case, the library code was put in a box separate from that of the integrator. All cross box communication with the integrator took place through virtualized resources or via a principal object.
#codejam exercise  Campinatorics 
A park ranger has to distribute families to tents in a N×N grid subject to the following rules:
Families can be 1 or 2 or 3 members 
The number of 3 member families is X
Thereally are plenty of 1 or 2 member families as fillers 
A cell can be occupied by only one tent
The number of members in any row or column must be exactly 3
The number of tents in any row or column cannot exceed two.
Find how many arrangements are possible if two arrangements are different if any of their cells are different or if the members in the same cell are different.
Solution : we are looking at different arrangements of 0, 1, 2 or 3 in an N×N grid subject to the above combinations. Therefore one way to do this would be to combine those values for each N×N cell . After all the cells have been given a number, we can quickly reject or accept an arrangement by running the checks above. We return the count of all accepted arrangements.
If we list the cells row wise as a string then the ith element belongs to the i/N row and i%N column.
Void arrange (StringBuilder a, int start)
{
  If (start == N×N){ print a.toString (); return; }
  For ( int m = 0; m <= 3; m++)
  {

      a [start] = m;
      arrange (a, start +1);
      a [start] = '/0';
}
}

Bool isValid (string s, int N, int X) // representation for 
{
Int [,] matrix = s.toMatrix ();
Int threes = 0;
For ( int I = 0; I < N; i++)
{
Int sum = 0;
Int count = 0;
For (int j=0; j < N; j++)
{
If (matrix [i][j] != 0) count++;
If (count >2) return False;
If (matrix [i][j] == 3) threes++;
sum += matrix [i][j];
}
If (sum != 3) return False;
}
For ( int j = 0; j< N; j++)
{
Int sum = 0;
Int count = 0;
For (int i=0; i< N; i++)
{
If (matrix [i][j] != 0) count++;
If (count >2) return False;
If (matrix [i][j] == 3) threes++;
sum += matrix [i][j];
}
If (sum != 3) return False;
}
If (threes != X) return False;
Return True;
}