ashumeow

//----- The ECMAScript 6 meta object protocol (MOP) implemented in ES5
// This is how getting a property is handled internally.
// Double underscore (__) implies internal operation.

Object.prototype.__Get__ = function (propKey, receiver) {
    receiver = receiver || this;
    var desc = this.__GetOwnProperty__(propKey);
    if (desc === undefined) {
        var parent = this.__GetPrototypeOf__();
        if (parent === null) return undefined;

ashumeow

// Build a suffix array in O(n^2*log n);
// kinda too much, but now you can search for a pattern in O(n*log n) where `n` is number of characters in `str`
//
function searchPattern(str) {
  var strLen = str.length;
  var suffixArray = new Array(strLen);
  var suffixes = new Array(strLen);

  for (var i = strLen-1; i >= 0; i--) {
    suffixes[i] = [i, str.substr(i)];

ashumeow

/**
 * Applies HTML formatting to a raw string
 *
 * @param str {String} A raw string
 * @param formats {Array} An array of formats where each one has the following structure: [startOffset, endOffset, tagName]
 * @return formattedString {String}
 **/
function format(str, formats) {
  var formatsLen = formats.length;
  var strLen = str.length;

ashumeow

// For more info about indexed trees visit
// http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees
//
// Sample run:
// var tree = new IndexedTree([2, 5, 6, 9])
// tree.getSumIn(2, 3) -> 15
//
// Why this is cool? It gives the sum of the values of a subarray in O(log n) time, 
// the update of a value also runs in O(log n)

ashumeow

// Construct a table with table[i] as the length of the longest prefix of the substring 0..i
function longestPrefix(str) {
  
  // create a table of size equal to the length of `str`
  // table[i] will store the prefix of the longest prefix of the substring str[0..i]
  var table = new Array(str.length);
  var maxPrefix = 0;
  // the longest prefix of the substring str[0] has length
  table[0] = 0;

ashumeow

// Group all overlaping intervals
// * * * * * * *  
// This is an approach to a problem the engineers at Google Calandar/ Outlook probably faced. 
// You have events that may overlap and you want to display them in such a way that 
// they don't overlap with each other. One approach is to distribute them into columns. 
// Each column has events that don't overlap with each other.
 
// Cost: O(n*log n) if the interval aren't sorted by the starting time, 
//   O(n) otherwise.
// Sample run: groupOverlapingIntervals([ [2, 5], [5, 6],[3, 4] ])

ashumeow

// Returns the closest point from a list to a given point
// the naive approach runs in linear time, which is a quite slow if are calling this procedure a lot.
// The following is an approach using a KD-tree. It runs in <O(n*log n), O(log n)> time
//
// Example:
// var closetPoint = closetPointTree([[2, 3], [10, 17], [5, 6]]);
// closetPoint([10, 16]) 
// -> [ 10, 17 ]

function closetPointTree(points) {

ashumeow

// How fast can you get all the intervals that overlap with another interval?
// WTF.. who cares.  Well if you are given the task to find all the stories 
// from a facebook timeline visible to the user, 
// how would you do that without blocking the user's scrolling?
// Imagine, you mark the stories as read and notify the server that the user saw those stories.
 
// It turns out you can achieve this task in log time using a segment tree.
// More about segment trees: 
// http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor#Segment_Trees
// Sample:

ashumeow

Navigation and Resource Timing provides timing data for the fetch, but currently there is no interoperable way for the server to communicate own timing information to the client. For example:

• What steps were taken to generate the resource, and how long each took. Many sites already embed this type of information via HTML comments - e.g. wordpress emits <!--Page generated in X.X seconds.--> , and many sites provide more detailed stats (cache, db, generation) to enable performance debugging.
• If proxied, where was the time spent - e.g. time to fetch from origin, time to process response, etc.

Instead of relying on arbitrary HTML comments, we can define an HTTP header that can be used to send key-value pairs in a well defined format. Making this data available via a well defined interface would...

• Allow UA and other developer tools to automatically annotate appropriate timelines.
• Allow analytics vendors to gather this data for operational analysis.
• Allows proxies and CDNs to append custom timing d

ashumeow

        [Fact]
        public void RemoveBom()
        {
            foreach (var file in new DirectoryInfo("..\\..").EnumerateFiles("*", SearchOption.AllDirectories))
            {
                try
                {
                    var allBytes = File.ReadAllBytes(file.FullName);
                    var allText = File.ReadAllText(file.FullName);
                    if (allBytes.Length - allText.Length == 3 &&