Antonio Gulli's coding playground

A new lighter implementation of K-means

2013-05-12T23:41:00.000-07:00

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

Stocastic Gradient Descent

2013-05-10T23:17:00.000-07:00

Added a stocastic gradient descent to the linear regression code

Learning linear regression with gradient descend

2013-05-09T10:59:00.000-07:00

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

2013-04-03T23:44:00.001-07:00

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

2013-04-01T00:57:00.000-07:00

with minimum number of comparisons

Browser war revisited

2013-03-30T02:38:00.000-07:00

Find largest sum in a subarray

2013-03-29T12:14:00.001-07:00

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

2013-03-28T01:24:00.000-07:00

Hint: binary search with modification

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

2013-03-27T01:14:00.000-07:00

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

2013-03-26T02:56:00.000-07:00

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

2013-03-25T23:36:00.000-07:00

Last week, I posted a blog about autosuggest for Bing

Given n sets, intersect them. preserve the duplication

2013-03-24T22:01:00.000-07:00

Find the row with max num of 1s

2013-03-23T04:57:00.000-07:00

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

2013-03-22T04:57:00.000-07:00

Merge two BST

2013-03-21T04:57:00.000-07:00

optimal in time and space

Merge and Intersect two lists of integers

2013-03-20T04:57:00.000-07:00

Sorted array and rotated

2013-03-11T11:34:00.000-07:00

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

2013-03-10T01:35:00.000-08:00

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

2013-03-09T04:12:00.000-08:00

In O(logN)

Count the number of words in a text.

2013-03-08T04:09:00.000-08:00

Design a data structure where min, max are O(1) , delete and insert are O(logN)

2013-03-07T10:35:00.000-08:00

Hint: min is O(1) for an min-heap, delete and insert are O(log N). Same for max. Question is how to make it for both min and max

Circular pumps

2013-03-06T06:29:00.000-08:00

Given a circular trace with pumps and a car running on a trace. Each pump has a well known distance from the origin, and the amount of kilometers you can run if you stop and refuel your car. Find a suitable starting point so that the car will not run out of fuel and the number of stops are minimal.

Special sort

2013-03-05T03:30:00.000-08:00

Given an array of numbers, arrange them in a way that generate the largest value. For instance, if the given numbers are {34, 345, 348, 50}, the arrangement 5034834534 gives the largest value.

Visit a BST in level order

2013-03-04T11:06:00.000-08:00

Visit a BST in level order.
Visit a BST in reverse level order

Implement T9 dictionary

2013-03-03T12:16:00.000-08:00