Amazon面试题

Question 2: A sorted array has been rotated r times to the left. Find r in least possible time.

Question 1: There is a big file of words which is dynamically changing. We are continuously adding some words into it. How would you keep track of top 10 trending words at each moment?

Question 1: There is a binary tree of size N. All nodes are numbered between 1-N(inclusive). There is a N*N integer matrix Arr[N][N], all elements are initialized to zero. So for all the nodes A and B, put Arr[A][B] = 1 if A is an ancestor of B (NOT just the immediate ancestor).

Count total set bits in all numbers from 1 to n

Given a positive integer n, count the number of 1 bits.

Question 1: You are given many slabs each with a length and a breadth. A slab i can be put on slab j if both dimensions of i are less than that of j. In this similar manner, you can keep on putting slabs on each other. Find the maximum stack possible which you can create out of the given slabs.

Question 2: The above question was raised to 3 dimensions.

Question 3: The above question was then raised to k dimensions.

Questions :   Then there were many questions asked on compilers and dynamic memory allocation.

estion 1: You are given pairs of numbers. In a pair the first number is smaller with respect to the second number. Suppose you have two sets (a, b) and (c, d), the second set can follow the first set if b<c.So you can form a long chain in the similar fashion. Find the longest chain which can be formed.

Find the longest increasing subsequence in O(nlogn). Proof and full code was required.