cluster users by attributes

A massive social network decided to assign an unsigned int as unique id for each user. Also, each user has a set of attributes represented as string and integers. Define a suitable cluster strategy for users based on the common attributes.

Intersect two sorted arrays

Given two arrays A and B, where #A = m and #B = n, how would you intersect A and B? Please discuss complexity and real optimization

Sum maximum

Given an array of n positive integers. Write a program to find the sum of maximum sum subsequence of the given array such that the intgers in the subsequence are sorted in increasing order.

Today, 3 years at Microsoft

Sequences in sorted order

Given two integers k and n, write a function that prints all the sequences of length k composed of numbers 1,2..n. You need to print these sequences in sorted orde

Find the minimum distance

Given an unsorted array arr[] and two numbers x and y, find the minimum distance between x and y in arr[]. The array might also contain duplicates. You may assume that both x and y are different and present in arr[]

A collection of algos and data structures published here

Design Patterns

Design Patterns : C++ full collection of Gamma's p...

Data Structures

KD-Tree: A C++ and Boost implementation

A commodity vector space class

Generic B-Tree

Splay Trees in C++

Decision Trees (part I)

Genetic Programming

Linear Suffix Array

Generic Tree

Hashing, Shingling and HashTrees

Generic Skip list (skiplist)

Generic Graph

Generic heap

Generic list and list iterators

Generic Hash_Map

Chained hash and hash function

Generic list and mergesort

Algorithms

DBSCAN clustering algorithm

Multidimension Scaling

Range minimum queries and LCA

Fuzzy Clustering

Adaboost : improve your weak performance

K-means in C++

Viterbi Algorithm in Boost and C++

Longest common substring, subsequences, increasing...

Maximum sub-array sum

Finding the the more frequent symbol in a stream o...

Shingling and Text Clustering (Broder's shingles)

Maximum sub-array product

Finding a loop in a list

Useful stuff

Memory Mapped files in Boost and C++

Boost::serialization for storing generic class

Boost::asio, Keep-alive, Boost::serialization

A collection of feature suggestions published here

Skype

A feature suggestion for Skype: turning skype in a cash cow machine

Mobile Social payments, Facebook, Skype and Google

Linkedin

Why people are not using LinkedIn for Search? my opinion their ranking is broken

Secret references, A feature suggestion to 

Facebook

Monetizing free login

A feature request for Facebook

Sharing revenues with skilled friends
Skilled friends can gain money after they share 
Skills cannot be faked
An idea for Facebook: from friends to skilled friends

A feature suggestion for facebook: multiple langua..

Facebook Social Wallet

A feature suggestion for facebook: Social calendar..

Shipping that feature one day before of Facebook

Bing and Windows 8

Apparently, I am in the video (someone told me ;))

Autosuggest and Bing

My team is shipping this Autosuggest Backend

 "“As you type results, Bing will offer suggestions and if we do say so, the auto-completion feels pretty quick.”"

http://www.engadget.com/2012/08/15/windows-8-rtm-whats-new/

Related Searches and Bing

My team is shipping this Related Searches ;) ;)

http://news.cnet.com/8301-10805_3-57495215-75/bing-windows-8-app-brings-tiled-goodness-to-your-search-results/

Subset sum

Find subset of elements that are selected from a given set whose sum adds up to a given number K. The set contains non-negative values.

Special Stack

Design a Data Structure SpecialStack that supports all the stack operations like push(), pop(), isEmpty(), isFull() and an additional operation getMin() which should return minimum element from the SpecialStack

Count in an array

Write a function to count number of smaller elements on right of each element in an array.

Celebrity problem

In a party of N people, only one person is known to everyone. Such a person may be present in the party, if yes, (s)he doesn’t know anyone in the party. We can only ask questions like “does A know B? “. Find the stranger (celebrity) in minimum number of questions

Find the two numbers with odd occurrence​s in an unsorted array

Longest Bitonic distance

Given an array arr[0 ... n-1] containing n positive integers, a subsequence of arr[] is called Bitonic if it is first increasing, then decreasing.

Find the smallest positive number missing from an unsorted array

Find a triplet that sum to a given value

Given an array of integers

Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number

Given a sequence, find the length of the longest palindromic subsequence in it.

Check whether two strings are anagram of each other

ind the maximum sum leaf to root path in a Binary Tree

Intersection and Union

Given two Linked Lists, create union and intersection lists that contain union and intersection of the elements present in the given lists. Discuss complexity and make your assumptions.

Add two numbers without using arithmetic operators

Hint: use bit operators

Bing and Facebook

http://searchenginewatch.com/article/2195761/Facebook-Working-on-Better-Search-But-Wont-Rival-Google-Engineer-Confirms

“Facebook is a partner with Google’s biggest rival, Bing, to handle web searches.”

http://allfacebook.com/typeahead-search-the-web_b95572

“Readers: Are you seeing the “search the Web” link in your typeahead search results?”

http://www.insidefacebook.com/2012/07/25/facebook-adds-search-the-web-to-typeahead-results/

“Facebook had previously allowed users to filter their Facebook searches by web results after clicking over to a main results page, but it hadn’t offered the option from the typeahead, which only included Facebook objects. Making it more efficient to search the web from Facebook’s search bar will give users an incentive to use Facebook search rather than going to a separate search engine like Google. “

An hidden gem, not so well known: Academic Search Microsoft. Want it integrated in bing?

http://academic.research.microsoft.com/Author/77558/antonio-gulli?query=antonio+gull

Edit

Antonio Gulli 

Microsoft

Publications: 22 | Citations: 522 | G-Index: 22 | H-Index: 11 

Interests: World Wide Web, Data Mining, Algorithms & Theory 

Collaborated with 10 co-authors from 1997 to 2009; Cited by 905 authors

 Homepage |  Bing

Sharing revenues with skilled friends

In my previous postings I discussed about the opportunity of explicitly share your skills on facebook showing  that the authenticity of those skills would be self-regulated by the social network. Also, I claimed that the current web search ads system is not necessarily the only monetization model available.  In web search, when a query is submitted some relevant content is retrieved and ads are sold together with the results. The engine takes the money and the web content producers take no money. Web content producers take benefits from the traffic received by the search engine, but they directly take no money -- which is strange to me.

Now the question is what incentive could we give the users who are sharing their own skills?

First answer would be to send them traffic in analogy to what happen in web search. Anyway, I am not sure that this would be valuable for my friend Giuseppe who claimed that he is an expert in Photography. Why sending traffic to his Facebook page should have any additional value to him?

The second answer is to share revenue between my skilled friend Giuseppe and Facebook whenever Facebook shows Giuseppe among the friends skilled in Photography. The more likes Giuseppe gets the higher would be the chances to be retrieved for a search about Photography. Whenever ads shown for that topic are clicked Giuseppe will get a little amount of the revenues generated. He produced the content, he has the skill so he takes some direct money for it. In my view, this model would give a natural incentive to share skills and to get likes for those skills.

The third answer is still to about sharing revenues, but would be based on inserting ads into skilled pages. What is a skilled page? pretty simple. If Giuseppe declares a skill in Photography he can create a special page on his profile very similar to the traditional timeline but focused just on Photography. All the ads shown in that page are about the Photograpy topic and again there should be some form of revenue sharing as form of incentive to produce high quality, curated skilled pages. After all, Giuseppe is the expert so he has to tell something about his expertise. 

Skilled friends can gain money after they share their skills for free

An anonymous reader told me: "people need an incentive/experience to provide this information for free. They will assume that their friends know - so why should they tell Facebook this information?"

In my previous posting, I showed that skills cannot be faked because they are judged by the rest of the friends. This is nothing but just applying the power of social ties which self-regulates authenticity.

Now, let's go to the next step. I believe that current web ads system is fundamentally flawed. A lot of people produce web content which is then indexed by search engines. When a query about a topic is submitted by a user some relevant content is retrieved and ads are sold together with the results. The engine takes the money and the content producers take no money.

Why that?

Yes, content producers will receive more traffic and this has certainly an economic value. Anyway, who said that this is the only model we can think of?

Do you have any alternative?

Skills cannot be faked

One more thought about my idea of skilled friends on Facebook. I don't believe the a friend can mystify her skills by declaring a talent which is not there. Her social network will understand this and she will look bad in front of her friends.

So, skills cannot be faked. Plus, when you declare a skill there is always the opportunity to like it and this will be an important signal to rank friends by skills.

An idea for Facebook: from friends to skilled friends (or how to make money)

Facebook has 900 millions of users, and everyone is connected to a number of friends. Sometime you don't know what are your friends' skills. In my network there are people expert in photography, people expert in art, people experts in skiing, people expert in surfing, and people expert in solar power, and people expert in philosophy, and people with an immense musical background, and many geeks, and people with tremendous interest for electrical cars, and people with a passion for astronomy and celestial stuffs, and ....

So many people, so much talent to discover.

So Facebook, let everyone declare their own skills and talents to their social network. Let my friends be skilled friends. Let me also tag the skills of my friends as I tag my friends' faces in pictures.

Then, let me discover this talent when I search:  if I search for photography give the name of my friend Giuseppe who has a skill in this subject, and If I search surfing give me the name of Luca who is the expert here. If no friend is an expert in that topic, please find a skilled expert among the friends of my friend.

Transform generic search in search for skilled friends.

And when I search a skill, here you have the magic opportunity to sell ads about that topic. 

So If i search for surfing give me the name of Luca, but also ads related to the topic. Give me the name of that online market where I can buy great surf tables or show me where to find swimsuits. Likewise, if I search for camera give me the name of Giuseppe but also ads for the latest Nikon D7000. And...

Transform generic search in a search for skilled friends, and make money out of a great user experience.

Implement an hash table with chains in case of collision

Bing search meets Facebook: exciting typeahead progress

Very happy about the integration of typeahead/autosuggestion technologies between Bing and Facebook. Now you can Bing directly from Facebook search box. Congratulation to the teams that made this happening by establishing a collaboration with several locations in the world (California, Washington, and London). My team in London provided core backend technologies for Bing Autosuggestion.

Enjoy!

A phone has two sides. An idea for phone manifactures

Yesterday, I was listening this conversation: "I have always to carry at least two phones. My iphone is great for browsing and the apps, and my blackberry is great for browsing emails". How many of you have a similar  experience: either you have a phone with a large touch display which is great for browsing, or you have a phone with smaller display but with a decent keyboard. So you go out of there and buy your favourite Android, Windows Phone, Iphone AND you possibly buy a traditional Blackberry or the like.

Now I wonder why two devices? Why don't have just one with two sides? On one side you have the large touch display, and on the other side you have the smaller display but a good traditional keyboard.

I should probably patent this idea and sell it to companies out of there, but there is a war so I prefer to publish here and give it for free.. as in freedom

Implement a tree inorder visit with no recursion

What colour would you pain an airplane

motivate your answer

LRU

How to implement LRU caching scheme? What data structures should be used

Implement set and traditional set operation

Please discuss trade-offs in your choice.

Given a stream of integers always maintain the median

This is a bit difficult, try with heaps

Bitonic arrays

iven an array A[0 ... n-1] containing n positive integers, a subarray A[i ... j] is bitonic if there is a k with i <= k <= j such that A[i] <= A[i + 1] ... <= A[k] >= A[k + 1] >= .. A[j - 1] > = A[j]. Write a function that takes an array as argument and returns the length of the maximum length bitonic subarray.

Array and positions

Given an array of n distinct integers sorted in ascending order, write a function that returns true is there is an index i such that arr[i] is equal to i

Strange struct.

struct str

{

    int i: 1;

    int j: 2;

    int k: 3;

    int l: 4;

};




what is this? is it a good and portable code?

Two arrays

Given two sorted arrays of any length, find out the median of them if they are sorted into single array

Find the maximum element in an array which is first increasing and then decreasing

Go with binary search (well, pretty much)

Maze

Write a program to find all the possible paths from a starting point to dest point in a maze(2-D array).

ex: 1 0 1 0
 1 1 1 1
 0 1 0 1
 0 0 1 1 

If there is a block it’s represented by 0.
If there is a path it’s represented by 1.

Beautification

Write a program for beautificaion of a program file in an IDE

Linked list

Write a program to print the n-nodes from tail of the linked list.

IPv4

Write a program to Validate an IPv4 Address

Distributed sort

Given N machines. Each machine contains some numbers in sorted form. The amount of numbers for each machine is not fixed. Output the numbers from all the machine in sorted non-decreasing form.

Unique words

Design a system to calculate the number of unique words in a file.. 1) What if the file is huge ? 2) Assuming that you have more than one computers available, how can you distribute the problem ?

Array of 0 and 1

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. linear

Check Number is perfect Square or Not

Implement a data structure for storing and retrieving non overlapping intervals of integer

Given an array of size n, find all the possible sub set of the array of size k

typical recursive problem

Sum 3 numbers

given an array and a target value. Find a,b,c such that a+b+c=target

fiven n points find m points closer to origin

in a r-space

Solve the coin change problem

def count( n, m ): if n == 0: return 1 if n < 0: return 0 if m <= 0 and n >= 1: #m < 0 for zero indexed programming languages return 0 return count( n, m - 1 ) + count( n - S[m], m )

Regexp match

Write a function checkRegex() which takes two strings as input, one string represents a regex expression and other is an input string to match with the regex expression. Return true if it matches, else false. Regex may contain characters ‘a-z’, ‘.’ and ‘*’ where ‘.’ matches any character and ‘*’ means 0 or more occurrences of the previous character preceding it.

Min and Max

Find the min and max in an array. Now do it in less than 2n comparisons

Event store

Question: Design a component that implements the following functionality.. 1) Record an Event (For the sake of simplicity, treat the Event as an integer code) 2) Return the number of Events recorded in the last one minute. 3) Return the number of Events recorded in the last one hour. i.e implement the following interface

Points closer to a point

You are given a list of points in the plane, write a program that outputs each point along with the three other points that are closest to it. These three points ordered by distance.

Last 60secs

Create a data structure which is supposed to log number of user requests per second. At any point of time your boss can ask you the number of hits for the last 60 seconds.

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

Reverse words

Given a file with billions of records data. The file is too large to in main memory, and you need to reverse each word in that file and then save the reversed words to another file.

Creative d80 -- Bluetooth wireless music box

I recently bought a Creative d80 -- Bluetooth wireless music box and my impression is WOW!! It is very cheap just less than $40 and the quality of music is impressive. I can stream over Bluetooth from my iphone, ipad, android, winphone, and windows 7. I don't have a Mac but it seems as easy as the remaining ones. If you have win7 make sure that your Bluetooth device has a stack supporting a2dp or enhanced data rate.

Geek is about founding creative and inexpensive cool technologies.

This Ph.D. thesis changed the world as we know. 100 years. A true hero, with solid principles

https://webspace.princeton.edu/users/jedwards/Turing%20Centennial%202012/Mudd%20Archive%20files/12285_AC100_Turing_1938.pdf

Given preorder traversal of a binary search tree, construct the BST.

Find the k most frequent words from a file

Given a singly linked list, rotate the linked list counter-clockwise by k nodes

maximal subsets

Given a set S, find all the maximal subsets whose sum <= k. For example, if S = {1, 2, 3, 4, 5} and k = 7 Output is: {1, 2, 3} {1, 2, 4} {1, 5} {2, 5} {3, 4}

Lucky numbers are numbers whose prime factors are just 2, 3, 5.

Find the first k lucky numbers.

Value of A and B

Given two sorted positive integer rrays A(n) and B(n). We define a set S = {(a,b) such that a in A and b in B}. Obviously there are n^2 elements in S. The value of such a pair is defined as Val(a,b) = a + b. Now we want to get the n pairs from S with largest values. The tricky part is that we need an O(n) algorithm.

true and false

Given a function bool Zoo(int x) and its called for y times , how you will generate the true with probability x/y times .

what's next?

 

1

 

 

1 1

 

 

2 1

 

 

1 2 1 1

Eggdrops

Solve the classical Google's interview problem.

Dynamic programming

k: Number of floors

n: Number of Eggs

eggDrop(n, k): Minimum number of trails needed to find the critical
               floor in worst case.

1) If the egg breaks after dropping from xth floor, then we only need to check for floors lower than x with remaining eggs; so the problem reduces to x-1 floors and n-1 eggs

2) If the egg doesn’t break after dropping from the xth floor, then we only need to check for floors higher than x; so the problem reduces to k-x floors and n eggs.





eggDrop(n, k) = 1 + min{max(eggDrop(n - 1, x - 1), eggDrop(n, k - x)): 
                 x in {1, 2, ..., k}}

you have a fleet of trucks and each truck has an autonomy of 1000KMs

How many kms in total you can cover if all the trucks start  from the same place?

You have 25 horses and you can make races of 5 of them in parallell

How many races to get the top 3 horses?

A feature request for Facebook

Sometime I just want to pin a thread and follow it without expressing an explicit like. Would it be possible to just follow a thread?

Monetizing free login

Several different providers are offering universal login schema, including Microsoft, Linkedin and Facebook. Apparently, none is monetizing this phase while there are plenty of opportunities to be leveraged.

Let's analyse a simple scenario where Alice, a Spotify user, decides to login using her Facebook account. Facebook knows Alice's geo-location, Alice's profile, Alice's past postings and likes. So Facebook has a lot of information to be mined for serving ads while Spotify does not have the same information. In other words, Facebook can sell ads to Spotify's users. So this could be the "Adsense" program for Facebook.

So my question is why Facebook is not opening this ads platform?

Stars

Find the closest stars in the sky

Design a non copyable class

Phonebook

Data structure TO use to design a phonebook. What is time complexity for retrieving, adding, and deleting entries

Write a function that finds the square root of a decimal number

Implement a division without division

Write a function that takes 2 arguments: a binary tree and an integer n, it should return the n-th element in the inorder traversal of the binary tree

int findNthElementByInorder(Node *node, int &n)
{
    if (node == null)
        return -1;
    findNthElementByInorder(node->left, n);
    if (n == 0)
        return node-> value;
    else
       n--;
   findNthElementByInorder(node->right, n);
}

N-th

Write a function that takes 2 arguments: a binary tree and an integer n, it should return the n-th element in the inorder traversal of the binary tree.

int findNthElementByInorder(Node *node, int &n)
{
    if (node == null)
        return -1;
    findNthElementByInorder(node->left, n);
    if (n == 0)
        return node-> value;
    else
       n--;
   findNthElementByInorder(node->right, n);
}

Reverse a linked list

Node* reverseLL(Node* n) {
   Node* curr = n;
   Node* prev = null;
   while(curr !=null) {
        Node* temp = curr.next;
        curr.next = prev;
        prev = curr;
        curr = temp;
   }
   return prev;
}

Duch national problem

void threeWayPartition(int data[], int size, int low, int high) {
  int p = -1;
  int q = size;
  for (int i = 0; i < q;) {
    if (data[i] < low) {
      swap(data[i], data[++p]);
      ++i;
    } else if (data[i] >= high) {
      swap(data[i], data[--q]);
    } else {
      ++i;
    }
  }

Given array find 3 elements that sum up to 0

For each i = 1..length do
  left = 0, right = length
  While left < i and right > i do
     if values[left] + values[i] + values[right] == 0
      # Got solution here
    if values[left] + values[i] + values[right] > 0
      # means that right border should be moved
      right--
   else
     # moving left border
      left++

Sort an array of objects

There are just three sizes large, small, medium. what is the optimal complexity? Can you make this in-place?

Given 2 very large numbers, each of which is so large it can only be represented as an array of integers, write a function to multiply them

const unsigned MULTIPLY_BASE = 10;

void multiplyLittleEndian(const vector < unsigned > &a, const vector < unsigned > &b, vector < unsigned >  &r)
{
    r.assign(a.size()+b.size(), 0);
    unsigned ri=0;
    for(unsigned ai=0; ai < a.size(); ++ai)
    {
        unsigned cri = ri++, carry = 0, am = a[ai], cr;
        for(unsigned bi=0; bi < b.size(); ++bi, ++cri)
        {
            cr = carry + am*b[bi] + r[cri];
            r[cri] = cr % MULTIPLY_BASE;
            carry = cr / MULTIPLY_BASE;
        }
        while(carry)
        {
            cr = carry + r[cri];
            r[cri++] = cr % MULTIPLY_BASE;
            carry = cr / MULTIPLY_BASE;
        }
    }
    while((!r.empty()) && r.back() == 0) r.pop_back(); // trim result
}

Write a function to check if polygon is simple based on given list of points

add two numbers represented by strings

First need to reverse both strings, then add char by character and reverse final String again.

Given a matrix of numbers in which some may be zero. If a cell contains a zero, set all the cells in the corresponding column and row to zero

Interweave a linked list

Interweave a linked list. Do it in Linear time and constant space. Input: A->B->C->D->E Output: A->E->B->D->C

Given a matrix with 1's and 0's, find the number of groups of 1's. A group is defined by horiz/vertically adjacent 1's.

Implement a function to compute cubic root what is the time complexity?

pay attention to negative values, but it's a binary search

Roman strings

Get numeric number out of a roman string, linear time Given: mapping I = 1, V = 5, X = 10, L = 50, C = 100, D = 500, M = 1000 Input/Output: II = 2, III = 3, IV = 4 VI, VII, VIII IX = 9 XL = 40, XLIX = 49

mapping = {
            'I' : 1,
            'V' : 5,
            'X' : 10,
            'L' : 50,
            'C' : 100,
            'D' : 500,
            'M' : 1000,
          }

def roman(string):
  prev = 0
  totalsum = 0

  for c in string:
    if mapping[c] <= prev:
      totalsum = totalsum + mapping[c]
    else:
      totalsum = totalsum - prev
      totalsum = totalsum + mapping[c] - prev

    prev = mapping[c]

  print(totalsum)

roman("XCIX")

Compare hash table and stl map

Print the last k lines from a file