Saturday, June 30, 2012

Min and Max

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

Friday, June 29, 2012

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

Thursday, June 28, 2012

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.

Wednesday, June 27, 2012

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.

Monday, June 25, 2012

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.

Sunday, June 24, 2012

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.

Saturday, June 23, 2012

Monday, June 18, 2012

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}

Saturday, June 16, 2012

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.

Friday, June 15, 2012

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 .

Thursday, June 14, 2012

what's next?

 
1
 
 
1 1
 
 
2 1
 
 
1 2 1 1

Wednesday, June 13, 2012

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}}

Monday, June 11, 2012

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?

Sunday, June 10, 2012

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?


Saturday, June 9, 2012

Stars

Find the closest stars in the sky

Thursday, June 7, 2012

Phonebook

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

Monday, June 4, 2012

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);
}

Sunday, June 3, 2012

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;
}

Saturday, June 2, 2012

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;
    }
  }

Friday, June 1, 2012

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++