Three arrays and a triple search

We are given three sorted arrays A[1.. n], B[1.. n], and C[1.. n], and an integer k. Describe an algorithm to find the kth smallest element in A U B U C in O(log n) time.

Circular buffer

Write the multithread code for reading and writing from a circular buffer (multiple read are allowed)

Given a matrix M of size NxN compute efficiently M^k

This is useful to compute PageRank with power method. What is the complexity?

T(K) = T(K/2)+O(multiply)

Mirror a tree

Given a tree mirror it. Oldie one.

Add two polynomyals

this was an old interview question. Please write a space and time efficient code to add two polynomials.

A nice DP problem

Given an array A of positive integers. Convert it to a sorted array with minimum cost. The only valid operation are:
1) Decrement with cost = 1
2) Delete an element completely from the array with cost = value of element

Any solution? convert here means you can get a different sequence, but it must be non decreasing.

A possible solution is with DP. C(n, m) = is the cost of getting n non decreasing elements with the constrain tha no element is greater than m. note that given the # cardinality of the set made up of the elements in #set(A), then 0 < m < #set(A)

C(1,m) = max(a[1] - m, 0)  // because at first step you can only decrease of  value m
C(n, m) =  min (   // min: two options and want to find the min cost

a[n] + C(n - 1, m), // delete operation at step n for value m
                    // express the cost in function of step n-1 for value m

// and sum the cost of the specific delete op as specified  

// decrement

(a[n] <= m) ?       
C(n - 1, a[n]) // there is no need to decrement but for having
// a non decreasing sequence we must have a value
// non larger than a[n] for a[1..n-1]. That is 
// expressed inductively by C(n-1, a[n])
:        C(n-1, m)  +   // decrement with cost m
a[n]-  m       // cost of decrementing a[n] to m with a[n] - m ops

)

Collisions

Hundred of millions of irregular shape objects are moving in random direction. Provide data structure and algo to detect collision.

Lock on a tree

Given an n-ary tree of resources arranged hierarchically. A process needs to lock a resource node in order to use it. But a node cannot be locked if any of its descendant or ancestor is locked. You are supposed to:

write the structure of node
write codes for

* Islock()- returns true if a given node is locked and false if it is not
* Lock()- locks the given node if possible and updates lock information
* Unlock()- unlocks the node and updates information.

Train collapsing

In a Tunnel 1 km long. Two friends are standing at 600m inside the Tunnel.Suddenly they heard the whistle of a train.Both started to run on opposite direction at spead of 10 KM/Hr.Both of them just survived.
What is the speed of train?

Back to the basics

what will happen?

main
{
char *p="safer";
p[0]='j';
p[1]='j';
puts(p);
}

Excel numbers

Excel has a naming convention of A,B..Z,AA,AB,AC..ZZ,AAA... This had to be converted to the column numbers. A will be 1 and AA will 27, and so on and so forth Also find the name provided column number.

HBase and HDFS

Facebook is constantly replacing Yahoo! as the champion of very large scale open source software user. In this article they describe the use of HBase and HDFS for building the new message infrastructure.

Fuel pumps

There are N pumps in a circle, and the distances among the pumps are given. Each pump has a given amount of fuel. You should find a good starting point so that a car can make the circle without running out of fuel.

Given a huge list of strings

1. Find the top 5000 strings (sorted by frequency).
2. Find the duplicates

Playing with indexes

Given an array [a1, a2, ... an, b1, b2, ..., bn] rearrange it for having [a1, b1, a2, b2, ....an, bn]

Copy a list

you have an unidirectional list, where each element has pointer pointing to a random element forward in the list. This additional pointer allows to skip positions in the list, but this skip amount is not constant and changes randomically with the position.

Copy the list with constant space.

A simple problems with serialization

A tree is serialized in such a way that all the leaves are market with L and all the other nodes with N. The tree is serialized keeping the order derived by a pre-order traversal. Write an algorithm for reconstructing the tree. Also, suggest a methodology for improving the serialization.

Jump or not jump

>Given an array of integers of size N, each element represents the max number of jumps can make forward. What is the minimum number of element selections to reach the end of the array starting from the first element. Please note that you need to land exactly on the end of the array and not after that point. Obviously you always have a strategy to reach the end in N moves by always avoiding to jump and deciding to move to the next position but N is not necessarily the minimum.

Example: arr = 1, 3, 5, 8, 9, 2, 6, 7, 6, 8, 9
Here the min # of selections is : 3 with the sequence 1-> 3 -> 8 ->9
First element is 1, so can only go to 3.
Second element is 3, so can make at most 3 jumps: eg to 5 (2+1 goes to 3 where you can jump to 5) or 8 (2+2 goes to 4 where you can jump to 8) or 9 (2+3 goes to 5 where you can jump to 9)
If an element is 0, then cannot make any jumps

There is a simple quadratic solution with Dynamic Programming, but I was not able to get any linear solution. Is it possible?

A trivial one, re-arrange the array

I was used to ask this in the past, now no longer. If  [a1,a2,a3...,an,b1,b2...bn] is given input change this to
[a1,b1,a2,b2.....an,bn]

Majority element

This is a classic one, don't bing to solve it -- try to think about a solution. Find the majority element in an array. There is a linear solution with constant space. pay also attention to limit case.

Equilibrium index

The equilibrium index of an array is an index j such that the sum of the elements before j is equal to the sum of elements after j. Find j.

New way of monetizing the social information, a new ads paradigm (Part I)

Today the ads world is dominated by at least four paradigms. The second part of this posting will propose a new one called "CrowdAds" which naturally fits social networks and social sharing. Before that, let's review the current paradigms.

Google Adwords and Microsoft AdCenter are the undisputed champions of search ads paradigm. The idea is pretty simply. You submit your queries to your favorite engine and, together with search results, you will get some related ads. A whole ecosystem has been created where publishers can buy ads by using an auction mechanism. This process is now quite common, but I do remember old days when search was considered a commodity with many people claiming that there was no money in this business. Credit goes to Google for suggesting how to transform search into a cash-cow machine.

Google Adsense is the second major paradigm for ads. The idea is to embed ads related to the content of a given web page. This embedding leverages some algorithms for finding a suitable set of ads in a transparent and automatic way. This paradigm is largely used on Internet and allowed many people to earn money on the content they produce.

In-text ads is the third paradigm which embed ads related to the content of each web page directly in some artificially created links contained in the page itself. A popup window is shown when the user move the mouse over the artificial ads and this particular aspect generated many criticisms about the invasiveness of this paradigm.

Cashback rewards are websites which pay users for their activities. When a customer makes a purchase online, instead of visiting the retailer directly, they may choose to go via a cashback website in order to generate a monetary reward for buying the products or services.

My question to you is what is the best ads paradigm for social networks in terms of relevance, monetization and reduced invasiveness among the four one discussed above? Or would you suggest something else?

0/1 matrix

Given a 0/1 matrix A of size n x n, find the row with the maximum number of 0s

Find top log(n) or top sqt(n) values in an array of integers

Find top log(n) or top sqt(n) values in an array of integers in less than linear time.

Lucky numbers

Lucky numbers are numbers whose prime factors are just 2, 3, 5. Find the first k lucky numbers.

Interesting talk @ facebook for creating Places and entitites

I believe that the problem of extracting entities from social data would be an hot research problem. Here they use naive social mining for building basic information which is than combined with machine learning techniques.
Extending the graph tech talk [HQ]

Longest run of 0s and 1s

Really like the linear solution of this problem. You have an array of 0s and 1s and you want to output all the intervals (i, j) where the number of 0s and numbers of 1s are equal.

Example

pos = 0  1  2  3  4  5  6  7  8

          0  1  0  0  1  1  1  1  0

One interval is (0, 1) because there the number of 0 and 1 are equal. There are many other intervals, find all of them in linear time.

Beauty of xor-lists

XOR-lists are beautiful because your can store a double chained list by using a single pointer for cell. For instance   in the list A, B, C, D, E  you store A (B), B (B xor C), C (C xor D), D ( D xor E), E . So coming from B you can perform a B xor (B xor C) obtaining C and viceversa coming from D, you  have C = ( C xor D) xor D. In modern computers you have enough ram for not paying attention to those xor-lists, but they are still useful in many circumstances.

Do you know when?

Fascinating problems for the maximum subsequence problems

The linear solution for the maximum contiguous subsequence problem is one of most fascinating solution for a problem that is cubic at first glance. Sometime this problem is also known as Maximum subarray problem, and the idea is that you have an array of positive and negative integers and you need to find a "slice" whose sum is maximum (e.g.−2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6). The linear solution is one the pearls in Bentley's book

maxsofar = 0
maxendinghere = 0
for i = [0, n)
    /* invariant: maxendinghere and maxsofar are accurate
       are accurate for x[0..i-1] */
    maxendinghere = max(maxendinghere + x[i], 0)
    maxsofar = max(maxsofar, maxendinghere)

The key observation is to maintain the maximum found so far, putting a zero as minimum because that's the empty sequence. Then we have another variable for computing the global maximum among all the local maximum.

Now given this pearl, can you solve the following problem: "Given an array of 0s and 1s, Find the maximum contiguous subsequence so the number of 0's and 1's in that subsequence are equal"

Amazon service disruption -- an example of open post-mortem

Amazon suffered a large service disruption during past weeks. Summary of the Amazon EC2 and Amazon RDS Service Disruption in the US East Region is a very professional and open post-mortem analysis that I really enjoyed for his transparent form of communication style and very rich informative details.

Sort an array of 0, 1, 2, 3 symbols

with no additional memory and in linear time

Fresh Autosuggest

Clustering news and Bin Laden in International markets

Great collaboration among Asia, Europe and U.S. for shipping the new clustering infrastructure in multiple international countries