An array is given, and an index present in it.

A window must be chosen such that it includes the index, has this component maximized — sum(a[i]...a[j])*(j-i+1), but the component must be equal to or less than the threshold (sum(a[i]...a[j])*(j-i+1) <= threshold).

How we can solve this question optimally?

One example of the problem:

Input

N: 8
Arr[]: [2,-3,-4,5,5,6,7,8]
Ind: 4
Threshold = 20

Output

One possible answer
[5,5]

Explanation of output
[5, 5] = 10*2 = 20 <= 20 (threshold)

A list of strings of lowercase English alphabets is given.

It is followed by a list of operations, where each operation is denoted by

(a, b, c): append character c to all elements in the range a to b

c can be of three types (#,$,%), and if c is already appended to an element, adding again won't affect.

We need to find minimum number of operations required actually to get the final output.

Note: All operations must be done in the given order. We can decide to skip it or not.

Given list of strings: a, b, c, d

Operations:

1. 1 2 $

2. 1 4 $

Output: 1

It is because 2 would bring the final output itself.

A graph has N vertices numbered from 1 to N. We have two lists. One list M consisted of edges between vertices. The other list K consists of restricted paths. We have to add edges one by one from M and check whether the addition of the particular edge leads to a path between the restricted edges given in K. If it creates a path, we have to discard the edge.

Example: N = 4; K = {(1, 4)}; M = {(1, 2), (2, 3), (3, 4)}. Here, addition of edge (3, 4) will create a path between 1 and 4. Hence we discard edge (3, 4)

Given a list of player names and their scores – {Carl, 70; Alex, 55; Isla, 40}, design a data structure that can support following modules in optimal time-

i). addEntry(string name, int value)

ii) updateEntry(string name)

iii) getEntryFromRank(int rank)

There are 3 integers a, b, w.

There are 2 equations –

w+a=b

a (bitwise AND) b = 0;

I was given the value of w and he asked me to calculate the number of pairs (a, b) satisfying the two equations.

A square grid(NxN) is given to you; Each location on the grid is either a brick (B) or its empty (_).

The total number of bricks is exactly equal to as much is required to build a “wall” in the grid. See example for clearer understanding.

That is, at the end , all bricks(B) should be placed at boundary locations.

For moving a brick from location <x,y> to <i,j> |i-x| + |j-y| fuel is used.

Each brick in the grid can be moved to any location on the boundary with equal probability. What is the expected value of the fuel required to do so? Each brick can be moved at-most once.

In the end (after moving all the bricks), the grid should look like:

 B B B B
 B _ _ B
 B _ _ B
 B B B B

Initially the array contain all 1s.

There are two type of operation:

1 A: update arr[A] = 0.

2 A: Find index of Ath 1 in the array.

Number of elements, 1<=N<=(1e6)

Number of queries, 1<=Q<=(1e6)

I tried tree statistic. However, it didn't pass.

You are given N candies and K boxes. You need to find the number of ways to divide N candies in K boxes such that each box should have one candy and you should not count repetitive sequences. The boxes and candies are identical.

Is there any question similar asked before?

This is word search problem but constraints seem to be quite strict. Can somebody help with a solution which could pass time limit?

Find Word in Grid

Can lower_bound and upper_bound work with vector of pair<pair<int, int>, int> or nested pairs. I tried doing so but it is showing me error. So, how should we do that?

Suppose there are two piles of plates in the table. One has ‘m’ RED plates and other has ‘n’ BLACK plates. In his/her chance, a player can either pick any number of red plates or any number black plates or equal number of red and black plates. A player loses if he cannot make a move in his/her chance. You are playing this game with your friend. Given that you begin the game and both the players play optimally, output ‘L’ if you will lose or ‘W’ if you will win.

Example:

input: m = 1, n = 2

output: L

input: m = 2, n = 2

output: W

Give N=no. of players

K=No. of fans

likeMatrix=It is a sting array of size K where each element of array have size N.

(contains 0 and 1 only) where if a[i][j] ==1 represents fan(i) likes player(j)

Ex. N=5

K=3

like={ "10101","00001","01011","...","...." }

Count min. no. of players required to put in team such that each fan likes atleast one player.

I think it is minimum bipartite matching(just opposite to maximum bipartite matching). So, can anybody tell me how to solve it?

Hi, I have a question:

You are given 100 stations and distance between each adjacent stations. Now you have to select 10 stations(means 10 hops) among those 100 stations in such a way that maximum of distance between any 2 hops will be minimised. By default 1 and 100 stations are selected , so you need to choose only 8 more stations.

Here n=100 I have chosen but n can be large( so bruteforce won't work ).

This is one of Interview Question.

You are given the string of a's and b's, eg. aaabbbaa and some threshold value t which indicates the threshold point, eg if count of a's or count of b's will become equal to t then whose count will be equal to t eg. a or b will win that match, and next game will continue further, eg from that index of a and b new count values will be incremented, and the process will continue, and at the last you have tell who won the match, a or b.

Expected time complexity: O( n*log(n)*log(n) ).

A tree is given in which each edge is having some weight associated with it and you are given a number K.

So starting from root in K-steps how much maximum weight you can collect. You can traverse in any direction either from parent to child or child to parent. You can visit a node multiple times.

~~~~~ ~~~~~

 			    O
 			 5/   \ 6
 		         O	O
 		     24/  1 \     \11

Hi, please provide an algorithm for this question: Click

I am trying it from long time but couldn't reach a proper algo.

This is one of the interview question.

Given row on N house, each is marked either R or B and each house having some gems.

You have to collect gems from these house with some constraint: You can choose gems from any blue house but you have to choose even number of red house ( either from 2 Red houses or from 4 red houses)

Each time you take gem from one house, you will multiply gems received with gems currently, you have.

You have to choose continuous houses and maximise the product. 

You have to return start point and end point of house (remember this should be continuous ).

I can think of O(N^2) solution but not better than that. So, can someone recommend a better algorithm.

You are given a lot of cuboid boxes with different length, breadth and height. You need to find the maximum subset which can fit into each other (length, breadth and height of first block greater than length, breadth and height of second block).

For example:

If Box A has LBH as 7 8 9

If Box B has LBH as 5 6 8

If Box C has LBH as 5 8 7

If Box D has LBH as 4 4 4

then answer is A,B,D

Now, algorithm is first sort in terms of length, then find MIS of breadth and from previous result find MIS of height, however order can play a role here.

So, it is requested if someone can give a proper algorithm for this.

I got solutions on internet but it is quite difficult to understand. Plz can someone explain this.

You are given an integer N. You have to find smallest multiple of N which consists of digits 0 and 1 only. Since this multiple could be large, return it in form of a string.

Note: - Returned string should not contain leading zeroes.

For N = 55, 110 is smallest multiple consisting of digits 0 and 1. For N = 2, 10 is the answer.

Why is this https://ideone.com/gCdcs4 giving me runtime error but this does not https://ideone.com/14lMhi for http://codeforces.net/problemset/problem/779/C?

I have just changed equality sign. I have figured out the input but not aware of why it is happening so?

Please tell the complexity of http://www.geeksforgeeks.org/maximum-bipartite-matching/ ?

And if we use directly Ford-Fulkerson Algorithm, will it be better?

Hi, can somebody point a site or good resources where I could find all APAC editorials. For 2017, I find few blogs on Codeforces, but couldn't find much of previous APACs — 2016, 2015, 2014, etc.

Hi everyone, I am trying to find all permutations of the input elements which will result in the same Binary Search tree as the one formed with the input array.

Eg: I/P: 4, 3, 1, 2, 6, 5, 7

o/p:4 , 6, 3, 7, 5, 1, 2

4, 3, 2, 1, 6, 5, 7

and so on.

I have gone through links on internet but could not code it.

I am unable to print all the permutations correctly. So, I request community to help me with logic ( if recurive function can be provided too )?

Thank You

Order in terms of speed?

Algorithm A requires solving 3 problems of size n/3, and takes 4n computation steps to divide and combine.

Algorithm B requires solving 2 problems of size n/2 and takes n log log n computation steps to divide and combine.

According to me:

A == O(nlogn)

B == O(nlogn)

So both have same speed or how we will distinguish between the two?

Can somebody help me in finding running time of algo: Partitions the problem into two sub-problems of sizes n/5 and 7n/10, and spends O(n/log n) time to divide and combine the solutions.