A new lighter implementation of K-means

See my old posting K-means in C++ .
Here you have a lightweight code

Stocastic Gradient Descent

Added a stocastic gradient descent to the linear regression code

Learning linear regression with gradient descend

Last week I restarted an old and good behavior (see A collection of algos and data structures published here). Every day, I take an well known algorithm and code it in boost and C++. Nothing else, just pure training and geeky fun. The only constrain is the time limit of 45mins, after a running session in St. James park.

Here you have the code for linear regression with gradient descent in C++, boost, and ublas.  Linear regression is an approach to modeling the relationship between a scalar dependent variable y and one or more explanatory variables denoted X. Ublas is a powerful set of c routines for efficient matrix and vector computations, Boost:: numeric provides an elegant C++ way of using ublas based on templates.

Here you have the code

Scaling requests with MemCached

A nice paper from Facebook about the use of memcached for scaling requests. Classical UDP connection-less techniques, are mixed with TCP coalescing via mcrouter. Also, they implement flow control, new mechanism for cache miss, and excess of requests on a particular key. The concept of pool is quite interesting.

Implement a binary search

with minimum number of comparisons

Browser war revisited

Find largest sum in a subarray

Given an array that may contain both positive and negative integers, find the sum of contiguous subarray of numbers which has the largest sum.

Hint: there is a divide & conquer solution in O(nlogn) and one cool solution in O(n)

Given a sorted array which is rotated N times(N is unknown), search a number in it

Hint: binary search with modification

Find the maxium integer in an array of size N, in O(N) and additional space O(1)

It's easy to make this in O(N) and O(N), or in O(N) and O(K) where K is the maximum int value contained in the array. However, this is requiring O(N) and O(1).

Hint: one way of doing this is to modify the original array.

My talk at ECIR2013

Gave an invited talk @ ECIR2013 and covered:

• Bing, as a platform, new trends for Microsoft search
• Bing suggestion technologies, an overview
• Bing & Cosmos, massive data mining models compared to Hadoop, Map & Reduce, Hive, Pig

Posted a blog about autosuggest for Bing

Last week, I posted a blog about autosuggest for Bing

Given n sets, intersect them. preserve the duplication

Find the row with max num of 1s

Given a matrix nxm where all the rows are 0/1 and sorted. Find the row with max num of 1s.

Do a BFS for a direct graph

Merge two BST

optimal in time and space

Merge and Intersect two lists of integers

Sorted array and rotated

Given a sorted array of distinct elements, and the array is rotated at an unknown position. Find minimum element in the array.

Given an array of positive integers, select two sub-sequences having minimum difference

Hint: one element can be either in one sub-sequence or in the other, so this is a typical recursive problem

A sorted array with duplicates. Count #key

In O(logN)

Count the number of words in a text.