Given a stream of characters, find the first non-repeating character from stream. You need to tell the first non-repeating character in O(1) time at any moment.

Given an array of integers of size N, if M elements are removed from it the rest of the elements will be in sorted order. What is a good algorithm to find those M elements?

Print the objects of an array in the order of decreasing frequency. PS: Please make sure order of object should remain same

E.g. if array is of integer is given as  5 2 2 8 5 6 8 8, then we should get 8 8 8 5 5 2 2 6 , here freq. of 5 and 2 are same but 5 comes before 2 in array thus its should come before in output as well.

Here is the working code , let me know if it will fail for any test case and  if we can improve it?

/********************************************************

Time Complexity :  O(n)+O(nlogn)+O(n)=O(nlogn)

Space Complexity : Auxallery Space O(2n)= O(n)

*********************************************************/

 Run Here http://ideone.com/FQ65xM

How would you design a logging system for something like Google , you should be able to query for the number of times a URL was opened within two time frames.

i/p : start_time , end_time , URL1 

o/p : number of times URL1 was opened between start and end time.

Some specs : Database is not an optimal solution A URL might have been opened multiple times for given time stamp. A URL might have been opened a large number of times within two time stamps. start_time and end_time can be a month apart. time could be granular to a second.

Find the largest contiguous rectangle having all 1's in matrix of size m*n ; Matrix have only 0 and 1 .

Find the minimal required number of white balls to achieve below criteria

You are given C containers, B black balls and an unlimited number of white balls. You want to distribute balls between the containers in a way that every container contains at least one ball and the probability of selecting a white ball is greater or equal to P percent. The selection is done by randomly picking a container followed by randomly picking a ball from it.

Given two set , 1st one is of 1 to n numbers where n is very very large say this set T and other set is very small contains only number {3,5,7} , Now generate all number from set T (bigger) except element in smaller set , with "equal probability" , you have given rand function , also minimize the call to rand function so solve it in most optimal way

Given a BST, maximum and minimum value, find the sum of nodes with values between the above range

Given 2 arrays A,B, where x(A.length) < y(B.length), we want to insert (y - x) 0's to A at various places such that A*B is minimum. For instance, if A = (1, -1) and B = (1,2, 3, 4), then inserting two 0's in the middle of A such that A = (1, 0, 0, -1) would minimize

assume that dictionary has only 5 words... APPLE,APE,BABY,BALL,CAT write a program which will accept a string and list all possible words in the dictionary which start with that string.

Say you have an HTML file which contains more than 100,000 characters. How do you extract all the Phone Numbers from it

Given a website you have to find number of hits in the last second, last minute and last hour.

Given a signature, compute the lexicographically smallest permutation of [1,2,....n].

You are given an array of n elements [1,2,....n]. For example {3,2,1,6,7,4,5}.
Now we create a signature of this array by comparing every consecutive pir of elements. If they increase, write I else write D. For example for the above array, the signature would be "DDIIDI". The signature thus has a length of N-1. Now the question is given a signature, compute the lexicographically smallest permutation of [1,2,....n]. Write the below function in language of your choice.   vector* FindPermute(const string& signature);

This is another good one from google easy though :)

Find All subsubsequence of size r in given array of length n

Given a positive integer N, arrange the integers 1 to N such the position of the average of two numbers (if present) falls outside the two numbers. For example, for a[i] and a[j], if b = (a[i] + a[j])/2, then if a[k] = b, k < i or k > j. Hint :- If the average of two numbers is not an integer then we can assume that they do not have an average.

One possible solution  i can think of is  divide the array in two parts , odd and even , sort them and use be.low algo , like if we have the array say N=10 and array is 3 10 2 7 5 3 4 6 9 8 1 after dividing and sorting
array will be 1 3 5 7 9 2 4 6 8 10
now calculate length of even and odd list ,if length is odd,then divide it into 2 equal parts and align alone one middle value like
1 3 5 7 9 2 4 6 8 10
now swap all values of two list except first value based on middle if each sub-list
1 7 5 3 9 2 8 6 4 10

i have not coded it yet so feel free to comment if it fails for any test case :)

Design a system where you can reutrn top 20 queries made in last 24 hours to users. Think on the scale of Google and Yahoo. How would you store data. What will be your data structures, algorithm to get that data.Describe your assumptions etc. For simplicity, you can assume that every web server create a log file with query and timestamp.

Given a string array， return all groups of strings that are anagrams

You have N computers and [Ca, Cb] means a is connected to b and this connectivity is symmetric and transitive. then write a program which checks that all computers are interconnected and talk two each other

I Believe there are multiple way to solve this problem 1. Here is my approach since graph is connected there will be path from each source to destination vertex , isn't it ? so we can simply run a dfs or bfs for all computers to check if all such path exist , finally we can return & of all operation that means all computer are inter connected and can talk to each other . PS.Since graph is undirected if there exist path from u to v then vice-verse also true so we wont calculate it again.

Maximum Sum Subsequence in an unsorted array of size n

We are given an array A having n integers. What we want to find is a contiguous subseqnence (A[i], A[i+1], …, A[j]) such that the sum of the elements in that subsequence is maximized. (Note that, in general, there may be more than one such optimal subsequence.)

Note that if all elements in A are non-negative, we could directly return the entire array as the required optimal subsequence.

APPROACH 1

A simple brute-force method could be to compute the sums of all possible subseqnences in A. How many subsequences are there? There are  possible subsequences. Computing the sum of a subsequence takes O(n) in the worst-case. Hence, the running time of the algorithm would be .

In C++, we could write the following function to do what was explained above:

// start and end are the starting and ending indices of an optimal subsequence.

void f ( int* A, int n, int &start, int& end)

{

int sum, max = A[0];

for (int i = 0; i < n ; i++)

for (int j = i; j < n; j++)

{

sum = 0;

for (int k = i; k <=j; k++)

sum+= A[k];

if (sum >= max)

{

start = i;

end = j;

max = sum;

}

}

}

————

APPROACH 2:

We can improve the running time to  by being a bit more clever in computing the sums of different subsequences. We observe that the sum of the subsequence A[i ... j+1] = A[j+1] + sum of the subsequence A[i ... j].

In C++, we could write as follows:

void f (int *A, int n, int &start, int &end)

{

int sum, max = A[0];

for (int i = 0; i < n; i++)

{

sum = 0;

for (int j = i; j < n; j++)

{

sum + = A[j];

if (sum >= max)

{

start = i;

end = j;

max = sum;

}

}

}

}

———–

APPROACH 3:

Using dynamic programming, we can solve the problem in linear time.

We consider a linear number of subproblems, each of which can be solved using previously solved subproblems in constant time, this giving a running time of .

Let  denote the sum of a maximum sum contiguous subsequence ending exactly at index .

Thus, we have that:

 (for all )

Also, S[0] = A[0].

——–

Using the above recurrence relation, we can compute the sum of the optimal subsequence for array A, which would just be the maximum over  for .

Since we are required to output the starting and ending indices of an optimal subsequence, we would use another array  where  would store the starting index for a maximum sum contiguous subsequence ending at index i.

In prseducode form, the algorithm would look thus:

Create arrays S and T each of size n.

S[0] = A[0];

T[0] = 0;

max = S[0];

max_start = 0, max_end = 0;

For i going from 1 to n-1:

// We know that S[i] = max { S[i-1] + A[i], A[i] .

If ( S[i-1] > 0)

S[i] = S[i-1] + A[i];

T[i] = T[i-1];

Else

S[i] = A[i];

T[i] = i;

If ( S[i] > max)

max_start = T[i];

max_end = i;

max = S[i];

EndFor.

Output max_start and max_end.

———–

The above algorithm takes  time and  space.

——–

We can however improve upon the space requirements, reducing it to . The key idea is this: for computing S[i] and T[i], all we need are the values of S[i-1] and T[i-1] apart from the given array A. Hence, there is no need to store all  values of the S and T arrays.

We could proceed as follows:

max = A[0];

max_start = 0;

max_end = 0;

S = A[0];

T = 0;

For i going from 1 to n-1:

// S = max { S + A[i], A[i] )

if ( S > 0)

S = S + A[i];

Else

S = A[i];

T = i;

If ( S > max)

max_start = T;

max_end = i;

max = S;

End For.

Output max_end and max_start.

———–

The above algorithm takes  time and  space.

Design a new programming language GOOGELY.

The programming language consists of two global character registers X and Y. Both X and Y is initialized with A initially.

It consists of two instructions
next: It increments the contents of x. Resets it to ‘A’ if it was ‘Z’.
Print: Prints the value of X and swaps the value of X and Y.

Sample input for the program: A string say “CBC”
Sample output: Sequence of instruction needed to execute, to obtain the input string.
In this case this output would be “next next print next print print“.