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)

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

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

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.