Divide in two equal parts

You are given an array of positive integers, and you have to find a split point such that the two parts have equal sum

Longest increasing sub-sequence

This is a well know algorithm, but it is useful to know for interviews

Subsequences

Given a sequence of integers, find a continuous subsequence which maximizes the sum of its elements

DP bracket problem

Given an increasing sequence of integers s1, ...., sk how many balanced parenthesis strings can you generate?

Count the number of inversions in an array

Given an array A unsorted, count the number of inversions.

Reverse a string with O(1) additional space

Old interview question

Implement quicksort algo on a list

Implement a sorting algorithm on a list

Nesting envelopes

Given k different types of envelopes. The dimensions of envelope type i are xi × yi. You can place envelope A inside envelope B if and only if the dimensions A are
strictly smaller than the dimensions of B. how many possible combination you can have?

Modify a stack to implement min/max in O(1)

Modify a stack to implement min/max operations in O(1)

Maximize the number of items you collect

This is a classical DP problem. A table composed of N*M cells with certain items non zero. Start from (0, 0) and you can go down or right one cell. Design an algorithm to find the maximum number of non zero items you can collect, if you are moving from upper-left corner to bottom-right corner.

What is the complexity and the space needed?

Launched News in UK, and FR

Another year, another news product. Optimized local rankers, classifiers and clustering. Oh yes, clustering my dear.

Are you the average of your friend actions?

A lot of people are enthusiastic about the benefits of social signals for selecting and ranking information. My question for you is: do you believe that you are well represented by the average actions of your most active social friends? or do you also have differences and a personal identity?

Related Searches shipped in 8 countries

What an amazing ride. We shipped 8 countries in less than one year with localized filtering, aggregation, and ranking. Italy is part of the list (yeah!!!)


More pictures here

Maximize and expression with no parenthesis

Given an expression E of n numbers with *, + operations and no precedence among the operators, identify the set of parenthesis which maximize the results for E.

Autosuggest shipped in 5 countries

What an amazing ride. We shipped 5 countries in less than one year with localized filtering, aggregation, and ranking.

More pictures here

Encode and Decode a document

A 'Document' is defined as a collection of 'Fields'. Some fields can be optional. A 'Field' can be a first-order type (int, char, float), or an array of first order types.

Write the code to serialize and de-serialize a collection of 'Documents'

Hive, SQL like, Facebook and the map join optimization

Hive is the SQL-like processor on the top of Hadoop, the open source Map-Reduce implementation. Facebook recently proposed an interesting optimization for the sort and merge phase adopted by the Reducer: "The motivation of map join is to save the shuffle and reduce stages and do the join work only in the map stage. By doing so, when one of the join tables is small enough to fit into the memory, all the mappers can hold the data in memory and do the join work there. So all the join operations can be finished in the map stage. However there are some scaling problems with this type of map join. When thousands of mappers read the small join table from the Hadoop Distributed File System (HDFS) into memory at the same time, the join table easily becomes the performance bottleneck, causing the mappers to time out during the read operation".

This is the optimization: "Hive-1641 solves this scaling problem. The basic idea of optimization is to create a new MapReduce local task just before the original join MapReduce task. This new task reads the small table data from HDFS to an in-memory hash table. After reading, it serializes the in-memory hash table into a hashtable file. In the next stage, when the MapReduce task is launching, it uploads this hashtable file to the Hadoop distributed cache, which populates these files to each mapper's local disk. So all the mappers can load this persistent hashtable file back into memory and do the join work as before."

So they are doing some pre-computation before the join operation itself for computing an hash table which is then pre-loaded in the memory of the local mapper. The performance gains are amazing since optimized map join is 12 to 26 times faster than the previous one.

I wonder how a fast compression scheme could help here. Paolo?

K-th sum for two sorted arrays

You are given 2 arrays A, B sorted in decreasing order of size m and n respectively and a number k, such that 1 <= k <= m*n. You need to fine the kth largest sum(a+b) possible where a \in A, and b \in B.

Hint: i like this problem, a possible solution is by induction and the complexity is O(n+m).

Interesting google talk

Available here, with more information about current G's index compression, spanner project, and many other features.