CareerCup

Was asked at GHCI Bangalore at their booth for a prize and perhaps hiring interns or experienced software developers.

Find the return value for N=100

int returnAns(int N){
int ans=0;
for(int i=0; i<N; i++){
for(int j=i+1; j<N; j++){
ans +=((i & -i) == (j & -j)?1:0); //the question missed the condition and was returning a boolean, so I added it myself
}
}
return ans;
}

My answer: 0 ; their answer: 1610, hence got it wrong.
My explanation: I assumed negative of i in binary to be
simply represented by setting the MSB to 1 e.g. for 8 bit representation of 3: +3 is 0000 0011 and -3 is 1000 0011. In the inner loop the value of ans will always evaluate to 0 since Bitwise & of these i and -i or j and -j will always result into i and j respectively. (undergrad computer organization concept.)
Negative numbers can also be represented as 1s and 2's complement and in all modern machines by architecture its 2s complement.
Now if we assume 1's complement, +3: 0000 0011 and -3: 1111 1100. so bitwise & of these two is 0 and so the value of ans will always be incremented by 1. By two loops 100+99+98+97+...+1 = 100*101/2 (i.e. n*(n+1)/2)
Then 2's complement, which is the most relevant representation of signed binary numbers.
Odd numbers:
+3: 0000 0011 -3: 1111 1101 Binary & is 0000 0001.
For all even numbers:
+4: 0000 0100 and -4: 1111 1011+0000 0001 = 1111 1100 and Bitwise & of 4 and -4 is 0000 0100 which is 4.
So, in the innermost loop ans is incremented by 1 when i is odd and j is also odd. ie. when i is 1, 3, 5, 7... 97 and j is 3, 5, 7, 9,...,99 ans is added 1(return value of true ==) when calculated it comes to 1610.

I was asked this during my onsite google interview but was unable to come up with an optimization for it. Here is the question:

There's a list of (x,y) points and a method getCircle with the following signature:

/**
* Given three points returns a circle (Radius, and center) such that all three points lie in its circumference
* or it returns null if no such circle is possible.
*/
Circle getCircle(point1, point2, point3);
getCircle method is already implemented and given to you as a black box. The problems asks you to find the Circle with most points in its perimeter.

The obvious answer is to get all possible triplets of points and find all possible circles and keep track of which one appears most often O(n^3) . Any ideas on how to further optimize this?

You have a table :
Rule1 Rule2 Rule3 Value
A1 B2 C3 40
A1 B1 C1 20
A2 B2 C2 10
A1 B1 C1 40
* B1 * 20
A5 B2 * 10

Now if I have a condition A1 && B2 && C3 i will get output as 40.
If I input A1 && B1 && C1 I will get two results 40 and 20 here there the rule is ambiguous.
"-" in table means any rule, 5th row matches with any row with B1 as rule2, so there is also ambiguity in result.

Now given that table as input (m * n) where n is number of available rules combination (here its 6) and m rules (3 in this case) , output if the table is ambiguous i.e it will output two different result for same query.

Giving a the following:

A list of a store items T={t_1, t_2,...,t_n}.

A list of prices of each item P={p_1, p_2,...,p_n}.

A list of quantities of each item Q={q_1, q_2,...,q_n}, respectively.

And total bill M.

Our goal is to find any possible list of items that its total value is equal to M using dynamic problem.

Write down a recursive solution.

Suppose two arrays are given A and B. A consists of integers and the second one consists of 0 and 1.
Now a operation is given - You can choose any adjacent bits in array B and you can toggle these two bits ( for example - 00->11, 01->10, 10->01, 11->00) and you can perform this operation any number of times.
The output should be the sum of A[0]*B[0]+A[1]*B[1]+....+A[N-1]*B[N-1] such that the sum is maximum

During the interview, my approach to this problem was to get the maximum number of 1's in array B in order to maximize the sum.
So to do that , I first calculated the total number of 1's in O(n) time in B. Let count = No. Of 1's=x
Then I started traversing the array and toggle only if count becomes greater than x or based on the elements of array A(for example : Let B[i]=0 and B[i+1]=1 & A[i]=51 and A[i+1]=50
So I will toggle B[i] B[i+1] because A[i]>A[i+1])

But the interviewer was not quite satisfied with my approach and was asking me further to develop a less time complex algorithm.

Can anyone suggest a better approach with lesser time complexity??

Write a method that merges a fixed number of streams containing an infinite sequence of monotonically increasing integers into an output stream of monotonically increasing integers. It is important to note that the input stream are infinite, so any solution based on the length of the streams would be considered incorrect.

Note that the question was given in the context of Java with the below code given as the base contract for the method.

public void merge(List<Stream> inputStreams, Stream outputStream) {
	// Implement me
}

This was also provided as the definition of "Stream" in this case, and not what is defined in java.util.stream.Stream.

interface Stream {
	
	// Retrieves but does not remove the next item from the stream
	int peek();

	// Retrieves and removes the next item from the stream.
	int poll();

	// Puts an item into the stream
	void put(int i);
}

Given a square (n x n) matrix which only contains 0 and
1. Find the minimum cost to reach from left most column to rightmost column.
Constraints/rules:
a. Starting point: You can start from any cell in the left most column i.e. (i, 0) where i can be between 0 and n( number of rows/ columns)
b. Destination: You can reach any cell in the rightmost column i. e ( k, n) where k can be anything between 0 and n.
c. You cannot visit a cell marked with 0.
d. Cost is defined as the sum of cells visited in path.
e. You can move up, down, left and right but not diagonally.

For example,
take 2x2 matrix
1 | 0
1 | 1

One possible path is 00 -- 10 -- 11 with cost 3
Other one is 10 -- 11 with cost 2
so minimum cost on this case is 2.

N cows are standing at the origin on x-axis, each cow has some appetite, in other word hunger index. A cow can sleep of 1 unit of time or eat for one unit of time or move left or move right. There are some vessels placed on the x-axis, they are having infinite supply of fiod. Find minimum time in which all cows appetite would be filled.

Input:
cow Apetitte = {1,1}
Vessle locations = {-1,1}
Answer would be 2 since both cow can go in different direction they would eat for one seconds. One second for moving and one second for eating.

This problem looks to be similar to rotten eggs/tomatoes.

A special palindrome is a palindrome of size N which contains atmost K distinct characters such that any prefix between the size 2 to N-1 is not a palindrome.
You need to count the number of special palindromes
For example, abba is a special palindrome with N=4 and K=2 and ababa is not a special palindrome because aba is a palindrome and its a prefix of ababa.
If N=3, K=3, possible special palindromes are aba, aca, bab, bcb, cac and cbc. So answer will be 6.

Input format
Two integers N and K

Output format
Answer modulo 10^9+9

Constraints
1<=N,K<=10^9

Sample TC
3 3

Output
6

Given a length n, count the number of strings of length n that can be made using ‘a’, ‘b’ and ‘c’ with at-most one ‘b’ and two ‘c’s allowed.

Implement auto complete for IDE, you will be given strings of classes and input, input can be like MVC, MoClick, MouseClickHand
For MouseClickH => MouseClickHandler

MVC => can match to any classes where first word starts from M then V then C

A stream of data representing the price of a commodity is being read. The data is of the format (price:Int, timestamp:Option[Long]).
If the timestamp is missing, it means the price has to be deleted.
If timestamp is old, it means the previous data with same timestamp has to be updated with this new price.
Else it's the new price of the commodity.
At any point of time the latest, max and min of the price has to be printed.
If the delete instruction is received through the stream, the min/max should be updated accordingly.

There are N stations in a certain region, numbered 1 through N. It takes di,j minutes to travel from Station i to Station j (1 ¥leq i, j ¥leq N)$. Note that di,j=dj,i may not hold.
You are now at Station 1. From here, you have to visit all the stations exactly once. We assume that you have already visited Station 1. However, due to your schedule, there are M restrictions that must be satisfied. The format of each restriction is as follows:
• Station si must be visited before Station ti. (1≤i≤M)
Find the minimum time required to visit all the stations. Note that the last station to visit can be any of the stations.
Constraints
• 1≤N≤14
• 0≤di,j≤108 (1≤i,j≤N)
• di,i=0 (1≤i≤N)
• 0≤M≤N(N−1)⁄2
• 1≤si,ti≤N (1≤i≤M)
• si≠ti (1≤i≤M)
• There exists a path visiting all the stations under the given restrictions.
Input
Input is given from Standard Input in the following format: N d1,1 … d1,N : dN,1 … dN,N M s1 t1 : sM tM
Output
Print the minimum time required to visit all the stations.
Sample Input 1
4
0 2 3 4
1 0 3 4
1 2 0 4
1 2 3 0
3
1 2
2 3
3 4
Sample Output 1
9
Due to the restrictions, we can only travel as follows: Station 1 → Station 2 → Station 3 → Station 4. Thus, the answer is 2+3+4=9 and we should print 9.
Sample Input 2
3
0 1 20
1 0 20
10 20 0
0
Sample Output 2
21

You are given an array of length N consisting of integers, a={a1,…,aN}, and an integer L.
Consider the following subproblem:
• You are given an integer S.
• Find the largest value in the interval [S,S+L−1] in the sequence a, that is, find max(aS,…,aS+L−1).
Solve this subproblem for every S=1,…,N−L+1.
Constraints
• 1≤N≤105
• 1≤L≤N
• −109≤ai≤109
Input
Input is given from Standard Input in the following format: N L a1 … aN
Output
Print the answers in N−L+1 lines. The i-th line should contain the answer to the subproblem where S=i.
Sample Input 1
5 3
3 4 2 1 5
Sample Output 1
4
4
5
• The subproblem where S=1 asks the largest value among a={a1,a2,a3}={3,4,2}, so the first line in the output should contain 4.
• The subproblem where S=2 asks the largest value among a={a2,a3,a4}={4,2,1}, so the second line in the output should contain 4.
• The subproblem where S=3 asks the largest value among a={a3,a4,a5}={2,1,5}, so the third line in the output should contain 5.
Sample Input 2
4 1
-1000000000 1000000000 -1000000000 1000000000
Sample Output 2
-1000000000
1000000000
-1000000000
1000000000

There are N rooms in a row. The i-th room (1≤i≤N) from the left is called Room i. You are given M closed intervals [ai,bi] (1≤i≤M). At time 0, all rooms j such that ai≤j≤bi for some i (1≤i≤M) are occupied, and the other rooms are vacant.
You are given Q queries. The i-th query (1≤i≤Q) represents an event happening at time i, as follows:
• In the i-th query (1≤i≤Q), a closed interval [ci,di] (1≤i≤Q) is given.
• This query asks: "Are all rooms j such that ci≤j≤ci" vacant?
• If all those rooms are vacant, the query should be responded by OK, then all rooms j such that ci≤j≤ci get occupied.
• Otherwise, the query should be responded by OK, then nothing happens.
Process these queries.
Constraints
• 1≤N≤109
• 0≤M≤1000
• 1≤ai≤bi≤N (1≤i≤M)
• There are no rooms k such that ai≤k≤bi and aj≤k≤bj at the same time (1≤i<j≤M).
• 1≤Q≤1000
• 1≤ci≤di≤N
Input
Input is given from Standard Input in the following format: N M a1 b1 : aM bM Q c1 d1 : cQ dQ
Output
Print the responses in Q lines. The i-th line should contain the response to the i-th query.
Sample Input 1
5 2
1 1
4 4
3
3 3
2 3
5 5
Sample Output 1
OK
NG
OK
At time 0, Room 1 and 4 are occupied.
• At time 1, a query asks: "is Room 3 occupied?" Since Room 3 is vacant, we should print OK, then Room 3 gets occupied.
• At time 2, a query asks: "are Room 2 and 3 occupied?" Since Room 3 is occupied, we should print NG.
• At time 3, a query asks: "is Room 5 occupied?" Since Room 5 is vacant, we should print OK, then Room 5 gets occupied.
Sample Input 2
1000000000 1
2 999999999
4
1 1000000000
500000000 500000000
1 1
1000000000 1000000000
Sample Output 2
NG
NG
OK
OK

You are given N records. The content of the i-th record is represented by a string Si. These records are managed in pages, as follows:
• The first page: contains the first, ..., K-th records.
• The second page: contains the (K+1)-th, ..., 2K-th records.
• The third page: contains the (2K+1)-th, ..., 3K-th records.
• :
• The ceil(N⁄K)-th page: contains the ((ceil(N⁄K)−1)K+1)-th, ..., N-th records.
Here, ceil(X) represents the smallest integer not less than X. Print the contents of the records contained in the M-th page, in the order given.
Constraints
• 1≤N≤100
• 1≤K≤N
• 1≤M≤ceil(N⁄K)
• 1≤|Si|≤100 (1≤i≤N), where |S| is the length of S.
• Si is a string consisting of lowercase English letters.
Input
Input is given from Standard Input in the following format:
N K M S1 S2 : SN
Output
Print the contents of the records contained in the M-th page, in the order given. Use L lines, where L is the number of records that should be printed. The i-th line (1≤i≤L) should contain the content of the i-th record contained in the M-th page.
Sample Input 1
5 2 2
aaa
bbb
ccc
ddd
eee
Sample Output 1
ccc
ddd
• The first page contains the first and second records, which are aaa and bbb.
• The second page contains the third and fourth records, which are ccc and ddd.
• The third page contains the fifth record, which is eee.
Since the second page is requested, we should print ccc in the first line and ddd in the second line.
Sample Input 2
7 4 2
this
is
not
displayed
this
is
displayed
Sample Output 2
this
is
displayed

You're given an array of integers sorted ( [1,2,3,5,6,7,10]) you need to serialize and compress this array into a string (1-3, 5-7,10)

Given two points on a directed acyclic graph determine their least common ancestor, give it's time complexity, and describe any improvements you could make (if possible).

Given a binary matrix of 0 and 1 where we can move in 4 directions left, right, top, down and we can only pass through 1's. Find the shortest path from given source coordinate (a,b) to destination (m,n) given we can flip any one of the zero to one.

Given a list of sentences and a list of phrases. The task is to find which sentence(s) contain all the words in a phrase and for every phrase print the sentences number that contains the given phrase.
Constraint: A word cannot be a part of more than 10 sentences.
Examples:

Input:
Sentences:
1. Strings are an array of characters.
2. Sentences are an array of words.
Phrases:
1. an array of
2. sentences are strings
Output:
Phrase1 is present in sentences: 1,2
Phrase2 is present in sentences: None
Since each word in phrase 1 exists in both the sentences,
but all the words in second phrase do not exist in either.

You are given a list of edges in a graph and for each pair of vertices that are connected by an edge, there are two edges between them, one curved edge and one straight edge i.e. the tuple (x, y, w1, w2) means that between vertices x and y, there is a straight edge with weight w1 and a curved edge with weight w2. You are given two vertices a and b and you have to go from a to b through a series of edges such that in the entire path you can use at most 1 curved edge. Your task is to find the shortest path from a to b satisfying the above condition.

You are given a n x m grid consisting of values 0 and 1. A value of 1 means that you can enter that cell and 0 implies that entry to that cell is not allowed. You start at the upper-left corner of the grid (1, 1) and you have to reach the bottom-right corner (n, m) such that you can only move in the right or down direction from every cell. Your task is to calculate the total number of ways of reaching the target.
Constraints :-
1<=n, m<=10, 000

There is a meeting scheduled in an office that lasts for time t and starts at time 0. In between the meeting there are n presentations whose start and end times are given i.e. the ith presentation starts at s[i] and ends at e[i]-1. The presentations do not overlap with each other. You are given k, the maximum number of presentations that you can reschedule keeping the original order intact. Note that the duration of the presentation can't be changed. You can only change the start and end time. Your task is to maximize the longest time period in which there is no presentation scheduled during the meeting.
Constraints :-
1<=t<=1, 000, 000, 000
0<=k<=n
1<=n<=100, 000
e[i]<=s[i+1], 0<=i <n-1
s[i] < e[i] for 0<=i<=n-1

Print numbers that matches with the index in given non-duplicate unordered array.

Write a program to encode a string from --> ABABXBYZXXX --> X4B3A2Y1Z1 (what should be the storage requirements for optimal conversion of 10TB file)

Suppose there is a function given to you that:

def get_friends( person_id ) { /*  returns friends of person */ }

How you are now going to recommend friends to a person based on number of mutual friends? So, come up with the function:

def friend_reco( person_id, max_no_of_friends ){ }

Given billions of Identity cards of the form :

card : {
   my_id : "my id",
   "moms_id" : "mom id",
   "dad_id" : "dads id"  
}

If one gives you two Person's id, how can you tell if these 2 persons are blood related.
So, write a function that is:

def is_blood_related( person_id_1, person_id_2 ) // go on..

Given an array of integers find the maximum value of a[i] - a[j] + a[k]
with constraints i < j < k and a[i] < a[j] < a[k]

You're running a pool of servers where the servers are
numbered sequentially starting from 1. Over time, any
given server might explode, in which case its server
number is made available for reuse. When a new
server is launched, it should be given the lowest available number.

Write a function which, given the list of currently
allocated server numbers, returns the number of the next server to allocate.

For example, your function should behave something like the following:

>> next_server_number([5, 3, 1])
2
>> next_server_number([5, 4, 1, 2])
3
>> next_server_number([3, 2, 1])
4
>> next_server_number([2, 3])
1
>> next_server_number([])
1

Server names consist of an alphabetic host type (e.g. "apibox") concatenated with the server number,
with server numbers allocated as before (so "apibox1",
"apibox2", etc. are valid hostnames).

Write a name tracking class with two operations,
allocate(host_type) and deallocate(hostname).
The former should reserve and return the next
available hostname, while the latter should release
that hostname back into the pool.

# For example:
#
# >> tracker = Tracker.new()
# >> tracker.allocate("apibox")
# "apibox1"
# >> tracker.allocate("apibox")
# "apibox2"
# >> tracker.deallocate("apibox1")
# nil
# >> tracker.allocate("apibox")
# "apibox1"
# >> tracker.allocate("sitebox")
# "sitebox1"

Write a map implementation with a get function that lets you retrieve the value of a key at a particular time.
t:0 A =1
t:2 A = 2
get(A, t:1) -> 1
get(A, t:3) -> 2