Browser war revisited

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)

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

Hint: binary search with modification

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.

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

Posted a blog about autosuggest for Bing

Last week, I posted a blog about autosuggest for Bing

Given n sets, intersect them. preserve the duplication

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.

Do a BFS for a direct graph

Merge two BST

optimal in time and space

Merge and Intersect two lists of integers

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.

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

A sorted array with duplicates. Count #key

In O(logN)

Count the number of words in a text.

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

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.

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. 

Visit a BST in level order

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

Implement T9 dictionary

Given a BST find a triplet with sum 0

Find a pair in a BST with sum 0

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