Random commentary about C++, STL, Boost, Perl, Python, Algorithms, Problem Solving and Web Search

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

## Tuesday, June 26, 2012

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

Geek is about founding creative and inexpensive cool technologies.

## Saturday, June 23, 2012

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

## Friday, June 22, 2012

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

## Thursday, June 21, 2012

### Find the k most frequent words from a file

## Tuesday, June 19, 2012

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

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

## Sunday, June 17, 2012

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

Find the first k lucky numbers.

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

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

## Tuesday, June 12, 2012

### 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?

## 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?

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

## Friday, June 8, 2012

### Design a non copyable class

## Thursday, June 7, 2012

### Phonebook

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

## Wednesday, June 6, 2012

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

## Tuesday, June 5, 2012

### Implement a division without division

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

Subscribe to:
Posts (Atom)