## Friday, March 29, 2013

### Find largest sum in a subarray

Given an array that may contain both positive and negative integers, find the sum of contiguous subarray of numbers which has the largest sum.

Hint: there is a divide & conquer solution in O(nlogn) and one cool solution in O(n)

## Thursday, March 28, 2013

### Given a sorted array which is rotated N times(N is unknown), search a number in it

Hint: binary search with modification

## Wednesday, March 27, 2013

### Find the maxium integer in an array of size N, in O(N) and additional space O(1)

It's easy to make this in O(N) and O(N), or in O(N) and O(K) where K is the maximum int value contained in the array. However, this is requiring O(N) and O(1).

Hint: one way of doing this is to modify the original array.

## Tuesday, March 26, 2013

### My talk at ECIR2013

Gave an invited talk @ ECIR2013 and covered:

• Bing, as a platform, new trends for Microsoft search
• Bing suggestion technologies, an overview
• Bing & Cosmos, massive data mining models compared to Hadoop, Map & Reduce, Hive, Pig

## Monday, March 25, 2013

### Posted a blog about autosuggest for Bing

Last week, I posted a blog about autosuggest for Bing

## Saturday, March 23, 2013

### Find the row with max num of 1s

Given a matrix nxm where all the rows are 0/1 and sorted. Find the row with max num of 1s.

## Thursday, March 21, 2013

### Merge two BST

optimal in time and space

## Monday, March 11, 2013

### Sorted array and rotated

Given a sorted array of distinct elements, and the array is rotated at an unknown position. Find minimum element in the array.

## Sunday, March 10, 2013

### Given an array of positive integers, select two sub-sequences having minimum difference

Hint: one element can be either in one sub-sequence or in the other, so this is a typical recursive problem

In O(logN)

## Thursday, March 7, 2013

### Design a data structure where min, max are O(1) , delete and insert are O(logN)

Hint: min is O(1) for an min-heap, delete and insert are O(log N). Same for max. Question is how to make it for both min and max

## Wednesday, March 6, 2013

### Circular pumps

Given a circular trace with pumps and a car running on a trace. Each pump has a well known distance from the origin, and the amount of kilometers you can run if you stop and refuel your car. Find a suitable starting point so that the car will not run out of fuel and the number of stops are minimal.

## Tuesday, March 5, 2013

### Special sort

Given an array of numbers, arrange them in a way that generate the largest value. For instance, if the given numbers are {34, 345, 348, 50}, the arrangement 5034834534 gives the largest value.

## Monday, March 4, 2013

### Visit a BST in level order

Visit a BST in level order.
Visit a BST in reverse level order

## Friday, March 1, 2013

### Find a pair in a BST with sum 0

Given a BST of integers find a pair with sum 0.