Max submatrix

Given a matrix of size n x n fine the maximum sum rectangle

BST and dynamic programming

Given a binary search tree, find the size of the largest independent set of nodes

Games of coins

A set of coins are aligned and two players can pick one coin from each side in turn. Maximize the value of the coins picked by the first player

Maximum value contiguous subsequence

Given an array of real numbers, find a contiguous subsequence with max sum S

Stock prices

Given an histogram array of unsigned integers encoding the price of a stock title during previous year, compute the area for the largest rectangle contained in this histogram

Ship battle

Given a matrix M and an array V match the array in the matrix

Scheduling

Given n jobs, each one with a processing time t1 a profidt p1 and a deadline di maximize the profit

Boolean parentesization

Given a boolean expression of AND, OR, XOR, TRUE, FALSE find the number of ways to parenthesize and evaluate to true

Balanced partition

Given an array of integers between 0 and M divide the integers into two sets such that the difference of their sum is minimized

WEIGHTED DOMINANT SET OF INTERVALS

WEIGHTED SHORTEST PATHS WITH COST ASSOCIATED TO THE NODES

FIND THE FLOW NETWORK USING FORD–FULKERSON’ALGORITHM

FIND THE FLOW NETWORK USING FORD–FULKERSON’ALGORITHM

ASSIGNMENT MATCHING PROBLEM

FIND AN EULERIAN CIRCUIT

Egg drops

Given k eggs and n floors in a building, find the minimum number of trials required to determine the lowest floor from which when we drop an egg it does not break. Provide a Dynamic Programming solution.

Bridge Matching

n cities are sitting on the northern bank of a river and n cities are sitting on the southern bank. You can build a bridge only between cities with the same number. Provide a dynamic programming solution.

LBS

Given an array of integers find the longest bitonic sequence. Provide a dynamic programming solution

Box Stacking

Given a set of 3d boxes compute the largest stack of boxes. A box can be stacked only on the top of another box with lager base. Provide a dynamic programming solution for stacking the boxes

Boolean Parentization

given a Boolean expression of and, or, xor, true, false, find the number of ways to parenthesize and evaluate to true. Provide a dynamic programming solution

Box Stacking

Given a set of 3d boxes compute the largest stack of boxes. A box can be stacked only on the top of another box with lager base.

Maximum value contiguous subsequence

given a real numbers’ array find a contiguous subsequence with max sum. Provide a dynamic programming solution

Balanced partition

given an array of integers between 0 and M divide the integers into two set such that difference of sums is minimized. Provide a dynamic programming solution

Scheduling

given n jobs each of which with a processing time, a profit and a deadline maximize the profit. Provide a dynamic programming solution

Print the binary representation of an unsigned

compute whether or not an unsigned number is a power of two

Find the position with only one bit set in an unsigned

given an unsigned int swap odds and even bits

Multiply two binary strings representing the value of two integers

Add two numbers without using arithmetic operators

Generate all the bit patterns from 0 to 2n-1 such that successive patterns differ by one

Chapter 3 is done

This chapter is about Graph computation and there are classical algorithms (BFS, DFS, MST). MST is implementing the classical Prim's algo but using Fibonacci heap available in Boost. Here you find the first version of the graph code

Writing a programming / algorithmic book

I wanted to take on a new challenge and start writing a book about algorithms and design. The intent is to have Simplicity by Design (SD): every Chapter is a collection of 15-30 questions, followed by the solution, followed by a C++ code snippet which can be easily re-used.

So far, I have drafts for 3 chapters: bit programming, dynamic programming, and graphs. Here an example of graph code with very classical questions: implement a graph, implement bfs, implement dfs, implement topological sort, I already have code for other graph problems.  Dynamic programming has more mathematical content and I will publish an excerpt next weeks.

A number of questions:

1. Should I publish code for public review? If so, can i still use it for the book?
2. Should I publish questions for public review?

I think that this will be one of my side projects off work for the next year or so.

Create your Team

you have a pool of players. Each player ha a set of skills. For creating a team you need to hire the minimum number of players who have together a predetermined set of skills

P0 - what people are saying

Here some previous postings

• PageZero and Ted
• Project PageZero
• What they've said about new Knowledge Suggestions @ Bing

Find i = n^3 + m^3

how can a number be expressed as sum of two cubes?

52 cards

You have 52 cards half of them are red and half of them are black. You have a given amount of money M and every time you can bet k < M money. If you predict the right colour you will win 2k money, if not you will loose k. What is the best strategy?

Sort lexicographically an array of strings in C++ and in C

Create a complete C++ class for bitmaps

Conflits in k keywords

A keyword is made up of n bits. Given k keywords generated with uniform probability what is the probability to have collision? Provide an evaluation and write the code.

Radix Sort -

Write a radix sort implementation in C++

PageZero and Ted

I enjoyed attending Ted and give a talk about PageZero. While I was listening a number of very inspiring talks, I asked to myself would this PageZero really help users?

So I started to write {Ted} and immediately PageZero suggested {Ted Talks} as first suggestions and {Speakers} Speakers as su-bintent. That's exactly what I was looking for!!! I am impressed.

Then, I thought and what if I was interested in the Movie? PageZero predicted that potential choice too. Kind of cool, no?

Buying with constrains

You have a bag with capacity C and can insert items with value wi which will occupy space si. You cannot exceed the capacity. Write an algorithm in C++

Project PageZero

SearchBox never changed since 1993, when the first search engine was created. Bing is disrupting the box by bridging the gap with the World of Entities. Names, Web Sites, and Generic Entities are directly accessible and understood as soon as you type.

http://www.slideshare.net/antoniogulli/project-page-zero-bi 

Given a stream of integers, select one integer with uniform probability

k balls, n floors

There is a building with n floors and you have k balls.  Balls are identical and when you drop them they can break or not. You need to figure out the highest floor of the building an egg can be dropped without breaking.

In a network of n nodes elect a leader

what is the algorithm you would suggest?

In a stream of integers find the ones that appears at least k times

Optimal in space and time

Given a set of intervals (i, j) overlapping find the maximun number of those overlapping

Design Patterns : C++ full collection of Gamma's patterns

Design Patterns : C++ full collection of Gamma's patterns

Full collection of Gamma's patterns in Full collection of Gamma's patterns in c++: 

1. Creational: Abstract Factory, Builder, Factory, Prototype, Object Pool, Singleton,
2. Structural: Adapter, Bridge, Composite, Decorator, Facade, Flyweight, Proxy patterns,
3. Behavioral: Chain of Responsibility, Command, Iterator, Mediator, Memento, Observer, State, Strategy, Template, Visitor, and Interpreter

Capped payrolls

In a company there are different payrolls pi, and we want to find a cap C such that the total amount of money paid is not above a maxim M. How can you determine C?

Int 16 bit - compute the sqrt

Given an integer in 16 bits compute the sqrt

Given an array of sorted lists merge them

in optimal time and space

Given a list find the k largest integers

Count all the safe configurations of queens on a chessboard

Given a BST and two nodes find the common ancestor

How can you detect the endianess of your computer?

Given an array of integers longest non decreasing

Compute and print the longest non decreasing sequence of integers

Given a list of words, detect the longest word

made by concatenating other words in the list

Given a stream of integers select k random entries

Given two integers select the maximum with no comparison

(10^9)!

count the number of trailing zeros

Given two numbers a and b

Swap them with no temp variable. How many way  do you know for achieving that?

What is the complexity for computing x^n

What is the probability of dropping m balls in the same bin?

Suppose there are n bins

Load balancing

We have a set of task i={1, ..., n} and each one has a cost b_i, how can we assigned to m servers so that the load is balanced?

Generate all the permutations of a string

Given an array of 1 million entries

Pick the smallest int.

Implement a class for smart pointers

Triangle and Ants

On a triangle, there are 3 ants what is the probability that they collide when they move

In a number of 64 bits

Swap odd and even bits.

What is wrong with this code?

string FindAddr( list emps, string name )
{
  for( list::iterator i = emps.begin();
       i != emps.end();
       i++ )
  {
    if( *i == name )
    {
      return i->addr;
    }
  }
  return "";
}

generate strings

Write a program that generates from the string "abcdefghijklmnopqrstuvwxyz{" the following: a bcb cdedc defgfed efghihgfe fghijkjihgf ghijklmlkjihg hijklmnonmlkjih ijklmnopqponmlkji jklmnopqrsrqponmlkj klmnopqrstutsrqponmlk lmnopqrstuvwvutsrqponml mnopqrstuvwxyxwvutsrqponm nopqrstuvwxyz{zyxwvutsrqpon

Add two integers without using '+'

How can you add two integers without using + operator

isNumeric(string s)

write the method

Swap two integers

with no temp. How many ways do you know?

how many ways do you know to swap variables?

without using temp vars?

Use a dictionary

Given a string like "thisisalongstringwithmisakenoten" and a dictionary of words, split the string so that the number of non matched words are minimized. Try to optimize the code

Implement a smartpointer class

using templates in C++

Smartpointer s1(T * ptr)
Smartpointer s1(Smartpointer & s2)
and the assigment
s1=s2

Allocate a matrix of ints reducing the fragmentation

Shuffle an array of n elements

Suppose to have a uniform random generator in [0, 1)

Intersect two list of integers

what is the complexity

Given two list of integers A, B - find the minimum distance considering every pair (a, b)

Bing vs Google suggestions

Spot the difference on {royal baby} - which on has better suggestions the unbranded search engine or the other one?

What they've said about new Knowledge Suggestions @ Bing

"This is one area where Bing has a clearly better user experience than Google, if you’re looking to get actionable results from the actual search box. While Google will put a Pitbull Google+ profile in its autosuggest feature, it does little with suggestions for any of the examples Bing provides"

That’s not to say Google’s Knowledge Graph results don’t provide ways for users to distinguish what they’re looking for, but you have to get through the search query before you can tell Google what you’re actually looking for (like the Harry Potter books vs. movies, for example). Of course, you could always specify in your actual query."

Bing Autosuggest Expands to Take on Instant Search, Knowledge Graph In One Fell Swoop - http://t.co/nPS4Z6qufz

Bing has taken search suggestions, autocomplete, and semantic search to a whole new level. -- http://t.co/nPS4Z6qufz

Bing Autosuggest Expands to Take on Instant Search, Knowledge Graph In One Fell Swoop

searchenginewatch.com

Bing initially provided info directly in the search box for a celebrity, politician, athlete or a connection on LinkedIn with a public profile. This has now expanded to include brands, 

I find the experience pretty darn pleasant. Controversial article but our share is increasing. http://t.co/8SryXw61Eb via @MarketingPilgrm

Bing Expands Autosuggest Feature for Search

marketingpilgrim.com

Bing is still out there, folks. Interestingly enough every time I use the engine (which is usually only because I have been urged to do so d

PCMag talks about the new searchbox with Knowledge understanding -http://t.co/pTf0J2xpk6

Bing's People Autosuggest Expanded for Smarter Results

pcmag.com

Bing's People Autosuggest today got a boost, expanding category options to include brands, movies, albums, places, software, sports teams, animal species, and more.

Techcrunch talks about Bing Autosuggest - http://t.co/0DgvxFq8OU

Bing’s Autosuggest Gets Smarter, Now Includes Brands, Movies, Animals And More | TechCrunch

techcrunch.com

Microsoft's Bing today announced an update to its autosuggest feature that expands the number of categories that will trigger this feature. In May, Bing first introduced this tool for celebrities, politicians, athletes and publicly available LinkedIn profiles. Today, it is adding bran

According to webpronews we clearly beats Google - http://t.co/v5HIA9jE1Q

Bing Adds Brands, Movies, Albums, Places, Software, Sports Teams & Animals To Autosuggest

webpronews.com

Bing announced today that it is now including more types of entities in its autosuggest feature, including brands, movies, albums, places, software, sports teams, and …

Searchengineland talks about the searchbox disruption - http://t.co/vLbOjnoKSs

Bing Autosuggest Adds Brands, Movies, Albums, Places, Software, Teams, Animals & More

searchengineland.com

Bing announced they have expanded their search autosuggestions to add more than seven new categories. Bing added autosuggest completions for brands, movies, albums, places, software, sport teams, animal species and more. This is in addition to Bing adding people, 

Microsoft is pushing a bit further by surfacing these differences directly below the search box. -- http://t.co/LcQRmNU7BR

Microsoft expands Bing’s autosuggest for people to include animals, brands, movies, albums,...

thenextweb.com

Microsoft today announced it is expanding its Bing's People Autosuggest feature to include more than just humans. In fact, the search engine will now automatically suggest brands, movies, ...

Help vague Bing users get off of Microsoft's landing page and on with their lives.http://t.co/FeC6kax9EJ via @engadget

Bing updates autosuggest categories, gussies up your vague search parameters

engt.co

Having a hard time finding something on the internet? You're probably doing it wrong -- at least that seems to be Microsoft's supposition. The company

Other articles:

Bing Autosuggest Categories Revamped
UberGizmo (blog)

Microsoft expands Bing’s autosuggest for people to include animals, brands, movies, albums, places, and more
thenextweb.com 

Bing Expands Autosuggest Feature for Search

Marketing Pilgrim

Bing Expands "People Autosuggest" Tool

MediaPost

Microsoft aggiorna la funzione Autosuggest di Bing

WebNews‎ 

People Autosuggest feature on Bing expanded to include more categories

IN 

Microsoft Improves Search Engine Autosuggestions

Softpedia

Disrupting the searchbox

Today,
I published a blog on Microsoft search and it has been quoted by many

“This is one area where Bing has a clearly better user experience than Google, if you’re looking to get actionable results from the actual search box. While Google will put a Pitbull Google+ profile in its autosuggest feature, it does little with suggestions for any of the examples Bing provides.

That’s not to say Google’s Knowledge Graph results don’t provide ways for users to distinguish what they’re looking for, but you have to get through the search query before you can tell Google what you’re actually looking for (like the Harry Potter books vs. movies, for example). Of course, you could always specify in your actual query.”

http://techcrunch.com/2013/07/17/bings-autosuggest-gets-smarter-now-includes-brands-movies-animals-and-more/

http://www.pcmag.com/article2/0,2817,2421909,00.asp

http://searchengineland.com/bing-autosuggest-adds-brands-movies-albums-places-software-teams-animals-more-167107

http://www.webpronews.com/bing-adds-brands-movies-albums-places-software-sports-teams-animals-to-autosuggest-2013-07

SQL-like engines on the top of hadoop map/reduce

I missed to notice that there are new engines, in addition to standard hive and pig.

• stinger is an optimized compiler aiming at introducing almost real time computations in hive
• Impala is another real-time sql engine released by Cloudera
• Drill is yet another real-time sql engine

Apache Kafka

A nice system for distributed logging from multiple platform - apache kafka

Building large scale systems at Twitter

Very interesting article for building large systems at Twitter. Worth reading it, use of sharding on the top of standard mysql makes the trick (gizzard - for sharding , flockdb - for graph db) 

https://twitter.com/zipkinproject

http://www.youtube.com/watch?v=5cKTP36HVgI

http://highscalability.com/blog/2011/12/19/how-twitter-stores-250-million-tweets-a-day-using-mysql.html

http://highscalability.com/blog/2013/7/8/the-architecture-twitter-uses-to-deal-with-150m-active-users.html

Three new patent blocks today on my desk

Just arrived the first 3/9 this year

Othello

Othello is a game played on a square board, with black and white pieces. If a white/black piece is surrounded by a  black/white one (either left/right or up/down) then the piece will change color. Players play in turn until they have valid moves left. Implement Othello following Object Oriented criteria (e.g. what is a piece, what is a board, what is a game, who keeps the score, what is a valid move).

represent a double in [0,1) as binary

First need to understand what is the binary representation for a double in [0,1). Let's see an analogy.  If the number is an integer such as 123 I would probably make something like this

2 ^ 7  = 128 > 123 too large

123 - 2 ^ 6 = 59 -> set bit 1

59 - 2 ^ 5 = 27 -> set bit 1

27 - 2 ^ 4 = 11 -> set bit 1

11 - 2 ^ 3 = 3 -> set bit 1

3 - 2 ^ 2 < 0 -> set bit 0

3 - 2 ^ 1 = 1 -> set bit 1

1 1 1 1 0 1 1  

SearchCharm - Unified Search Experience in Windows 8.1

I am using windows 8.1 preview since many weeks without any problem. Search experience brings together the online and the offline worlds and it allows users to look for information virtually everywhere.

Traditional Web Search
Do I want to access cnn? Easy. I start to insert the query and I get both the web site and some relevant suggestions including cnn news and cnn money. Suggestions are generated by my group in London.

Navigating windows 
Do I want to access windows control panel? No problem, I just use the same interface and search paradigm.



Cloud search

What if I want to access my files stored in the cloud? Here I have my cv saved on Microsoft Skydrive and accessing it is as easy as searching via the charm

Local search

What if I want to access my files stored in my local computer? Here I have some videos saved on my local computer and accessing them is as easy as searching via the charm

Given a very large binary tree T1 and a small binary T2

check whether T2 is contained in T1. Discuss your solution

Given a binary tree, create a list of lists containing all the nodes in one level

write some c++ code / STL. Optimal in space and time

Check whether a tree is a binary tree

Search as you type with snapshots and disambiguation

Exciting day today! Bing is shipping an innovative search feature aiming at helping users to complete their tasks, as soon as they start to type their queries.

Consider the keyword "pitbull". This is a very interesting query because the user can be interested in getting either results about the famous singer (a person) or about the dog (an animal). For this example, we believe no instantaneous decision can be taken on the user's behalf and that only the user has a complete understanding of the intent expressed with a query.

However, we believe that the search engine can help the user to express very quickly this intent. How? In Bing we use the power of Satori (our Microsoft Knowledge Graph) to enrich our suggestions with additional information useful for disambiguating different meanings associated with the query. In this way, the users can select their own most appropriate choice.

Another example is the query {pluto}.  Is the user interested in the planet or is she interested in the cartoon? Those are very different kinds of entities which happens to have the same name but Bing understands the difference and gives to the user the opportunity to select the desired choice.

Now let's suppose that the intent is not ambiguous. For instance consider the keyword {michele obama}, we believe that it is very valuable to have a rich suggestion like the following one.

And what if there are two persons with the same name? In this case, we offer the opportunity to select the desired person as in this example for the query prefix {rachel nich}

One more example. Let's consider the query {u2}. Here, we offer the opportunity to explore all the entities / artists that are playing with the pop band

And what if you search for {harry potter}? In this case Bing provides a snapshot of the filmography, a reference to the book and a reference to the character.

Hope you enjoy it - this is the beginning.

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