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

About the openness

Google is complaining about the direction where Internet is going. Apparently, they say that there is less openness these days and it seems that the bad guy is Facebook, which is collecting user generated content which is not shared in an open way.  I am puzzled.

If this is a genuine rant why are they building Google+ which is just a copycat of Facebook? Also, why they collect search data since 1998 about everyone's behaviour but they don't share this data with the rest of the world?

Long time ago, I dreamt about a different world with open standards for exchanging facebook-like news feeds but hosted by different providers (remember RSS and ATOM? something similar but social) so that data is public. Then, the aggregation is centralized and you access aggregated information in a similar way to what is happening nowadays with search engines. In that ideal world, login would be no longer centralized but it would be based on openID. The social graph would be shared across different servers and remote nodes would be just special form of href, so that someone can index public data.

(this is my personal idea and it's not representing any opinion expressed by my company)

Birthday

you are at a party with a friend and 10 people are present including you and the friend. your friend makes you a wager that for every person you find that has the same birthday as you, you get $1; for every person he finds that does not have the same birthday as you, he gets $2. would you accept the wager?

Better a game where you can win in 1 shot or better one where you can win 2 out of 3 shots?

An interesting project for parallel machine learning:

Interesting collection of data parallel machine learning algorithms

"MADlib is an open-source library for scalable in-database analytics. It provides data-parallel implementations of mathematical, statistical and machine-learning methods for structured and unstructured data.

The MADlib mission: to foster widespread development of scalable analytic skills, by harnessing efforts from commercial practice, academic research, and open-source development."

How many zeros at the end of 100!

This is tricky but funny

how many different ways there are to paint a cube with 3 colours?

how many different ways there are to paint a cube with 6 colours?

Compute 2^128 -- no computer and possibly no paper

can you just compute it in your mind?

Can you estimate the cost of Facebook data center?

Search ads is a well consolidate business: how large it is ? and how can you innovate?

How many servers do you need to index the web?

How many numbers with a 7 in the first 10000 integers?

DBScan

Hi Antonio,

First of all apologies if this query is out of scope- I appreciate you may have moved on to other things, or may be just too busy at the moment.

I was looking for a simple implementation of DBSCAN to use as a starting point for some work and I found your implemention here (http://codingplayground.blogspot.com/2009/11/dbscan-clustering-algorithm.html). I found it worked quite well for small enough data sets, but for large ones it was allocating excessive amounts of memory, and I eventually looked at the code to see where the problem could be. It seems to me there may be an issue with the cluster expansion part of your algorithm- this issue may not affect the results (I think it may still produce the correct clusters), but it uses much more memory than it needs and this problem is more severe for larger input datasets.

The problem is with these lines of code

  Neighbors ne1 = findNeighbors(nPid, _eps);

              // enough support
              if (ne1.size() >= _minPts)
            {
              debug_cerr << "\t Expanding to pid=" << nPid << std::endl;   
              // join
              BOOST_FOREACH(Neighbors::value_type n1, ne1)
                {
                  // join neighbord
                  ne.push_back(n1);
                  //debug_cerr << "\tPushback pid=" << n1 << std::endl;
                }
              //debug_cerr << std::endl;
              //debug_cerr << " ne: " << ne << endl;
              debug_cerr << " ne size " << ne.size() << " " << ne1.size() << endl;
            }

specifically the line "ne.push_back(n1)". At this point in the algorithm you have found a cluster and are looking for density connected neighbours. You are adding all the new neighbours to the list to be considered, when you only need to add the ones that have not been considered yet. So rather than extending the original list with the full contents of the new list, you need to extend it with the difference of the two lists. This small change stabilises the memory usage and makes it run much faster.

kind regards

aonghus

Check if Alice has my phone number, and don't tell Eve

Alice is a friend of mine, Bob is my assistant but I don't want him to know my super-private phone number. Also, I want to check whether Alice has my super-private phone number but I don't want to communicate the number to Bob. What can I do to preserve my number?

An airplane is going from city A to city B

what would be the impact of the wind for a round-trip travel A to B?

Helium balloon in a car

What direction will the balloon go when you accelerate?

One biased coin

You have a biased coin and the result can be H or T but biased towards T. How can you make sure whatever is the toss the result will be fair?

magic square

You have a 3x3 square, fill with integers such that the sum for each row, for each column and in diagonal is 15. All the numbers must be different.

Hint: brute force is difficult (how many?), what would be number you put in the middle?

Table of reals

Given a table of real numbers of size mxn, is there an algorithm for making all the column sums and all the row sums positive? The only operation allowed is to change the sign of all the numbers in a column or in a row (one or more times).

Celebrities

In a group of persons, a celebrity is know by everyone and all the other people are known by none. Detect all the celebreties

What's next

10, 9, 60, 90, 70, 66, ...?

You have n companies: how many ways of acquiring them and how many ways of merging them?

A classical one: reduced size and put into a bladder

This is one of those classical interview questions that are supposed to probe your creativity. i don't like those problems, if you want to test creativity just present some really hard problem you are trying to solve and perhaps you can be surprised by a new approach.

Anyway, suppose that you are reduced by 90% but still retaining your mass (what a sci-fi situation?) and you are put in a bladder (really?). What can you to do to safe your life?

Ads -- betting on a query

You are a search engine which is selling ads for the query Q and your current valuation is 100$. Your competitor  has similar search performance but it's selling at 40$. What will you do?

Given N horses, how many races do you need?

Given N horses, how many races do you need to identify top 3 horses. Assume that a race cannot have more than 5 horse together.

Given N horses, how many races do you need?

Given N horses, how many races do you need to identify top 3 horses. Assume that a race cannot have more than 5 horse together.

You have 25 bits

Every time you turn a bit on, you should put it as far away as possible from the the other bit already turned on. What is the best bit to turn on at the beginning?

D'oh: Facebook Buys 750 IBM Patents For Defense

http://www.allfacebook.com/facebook-patents-ibm-2012-03

Facebook is purchasing 750 patents from IBM in order to bolster defenses against patent infringement suits, especially the one filed by Yahoo.

You have a fleet of 100 trunks and everyone has a fuel for 100 miles

what is the maximum distance you can cover?

Write an algorithm for multiply BigInt

BigInt is a class for representing very large integers

Compute the bigram of a repository with hundreds of millions of documents

how many aircrafts are flighting in this moment in the world?

IP to Countries

Write a function that will return a two character string representing a country code given an IP address as its input. Can this be made in memory?

a classical problem: coin change

Given a value in money N, and we want to change N into coins extracted from a set S={S1, ... Sm} of different coin values. How many diffferent ways to do we have to make the change. Assume that there are infinite coins of type Si.

Solution:

Define C(S, N, M) the way of changing the N given the M coins in S and compute the recursive solution

Given two databases one with login names and the other one with login actions

Select all the names with no login actions

Social activities will be soon more popular than search

According to this PEW study

Connect all the nodes at the same level in a binary tree

Find the maximum in an array increasing and than decreasing

Can you make this better than linear?

Convert a BST into a linked list and an linked list into a BST

Given a stream of integers compute the average in every instant

Convert a BST into a linked list and an linked list into a BST

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

Read an article about LinkedIn where the founder was complaining about people who are not using LinkedIn for searching new talents.  He says: "I have a frustration that people don't understand it. I had a CEO at one of my portfolio companies say to me, 'How do I use LinkedIn to find a CFO?' I said, 'Well have you tried typing "CFO" into the search box?' It's flabbergasting"

Perhaps, this is because the ranking system and the recommendation system in Linkedin are both fundamentally broken. Everyone can write whatever she likes in her CV and she can collude with other members for increasing the number of external references. There is no control and no sound ranking system in place. In short, anyone can inflate the value of her own LinkedIn profile.

Now why this is happening? Linkedin ranks users just using on their distance from my position in the social graph. Also, they consider textual match as a ranking feature. In my view, this is indeed a very primitive form of ranking and they should start investigating the idea of assigning credits to users. In this model, you spend a credit whenever you endorse a user and you gain credit when your endorsement was judged as positive by other users. This is a model used in real world where you spend some part of your social credit when you endorse someone. Plus, you earn some money when your endorsement will become a new hire.

So, Just a little feature suggestion for my friends in LinkedIn.

Social reverse dating

Ok, now I saw everything in social. Social reverse dating is outrageous ;)

Money related startups -- An overview

I am started to be interested into systems for transferring money in Internet. Here an overview of the most interesting technologies and startups

• Bitcoin for moving money with safe transactions
• Transferwise, move money in different currencies with very low commissions
• Square, pay with your credit card using your mobile phone
• Boku, charge your mobile bill and get an sms for confirming the transaction
• Monitise, use your mobile as a bank

This was my posting for turning Skype into a cash cow for mobile payments and facilitate money transfer using your own Skype account.