rahul_1234's blog

By rahul_1234, history, 2 months ago, In English,

Find if two people in a family tree are blood-related. I can't get what the question is and how to solve it.

Read more »

 
 
 
 
  • Vote: I like it  
  • -19
  • Vote: I do not like it  

By rahul_1234, history, 3 months ago, In English,

Can anybody provide solution to this?

Link

Read more »

 
 
 
 
  • Vote: I like it  
  • -16
  • Vote: I do not like it  

By rahul_1234, history, 4 months ago, In English,

If I want 1/i for 1<=i<=5000000, i.e. inv[i]

inv[1] = 1;
for (int i=2; i<p; ++i)
	inv[i] = (p - (p/i) * inv[p%i] % p) % p;

I used this but it times out. So I wanted a way for this.

Besides that, if I use fact[i-1]*invfact[i] : would that solve? It is not giving me correct answer so plz tell me what is wrong over here?

Read more »

 
 
 
 
  • Vote: I like it  
  • -21
  • Vote: I do not like it  

By rahul_1234, history, 4 months ago, In English,

For serialising and deserialising a binary tree( or a n-ary tree ) only preorder traversal with # for Null is used in the given Link but I think both inorder and preorder are required to construct tree.

Please tell me what is that I am missing?

Read more »

 
 
 
 
  • Vote: I like it  
  • -3
  • Vote: I do not like it  

By rahul_1234, history, 4 months ago, In English,

Q1).

 Image 1

Given isosceles right angled triangle, find the radius of the smaller circle.

Q2).

Image2

Given a rectangle ABCD with length l and breadth b, it is folded along diagonal BD. i.e. A is joined to C. Find the length of the line segment EF

Read more »

 
 
 
 
  • Vote: I like it  
  • -19
  • Vote: I do not like it  

By rahul_1234, history, 4 months ago, In English,

You have a set of N objects. Each of these objects have certain properties associated with them. A property is represented by a (key, value) pair. For example, assume you have the following two objects.

Tower: { (height, 100), (weight, 50), (xposition, 25), (yposition, 36) }

Tree: { (area, 100), (noofleaves, 500), (height, 25), (yposition, 36) }

Each object you have, will have at most 4 properties. An object will have at least 1 property. Note, from the two objects above, that it is not necessary for key in the properties to be same for all the objects. Also, it is not necessary for the key to be different. Now, given N such objects, you wish to answer M queries. Each query is represented by a set of properties (again, at most 4 properties, and at least 1 property). The answer for the query is the number of objects in the set, that have all the given properties. Two properties are considered equal iff both the key and the value match. For example, if you have the above two objects, then the answer for the following queries is

Query: { (height, 100), (yposition, 36) }

Answer: 1 // matches Tower, but not Tree

Query: { (yposition, 36) }

Answer: 2 // matches both Tower and Tree

Query: { (height, 100), (noofleaves, 500) }

Answer: 0 // neither Tower, not Tree satisfy both properties

Input:

The first line of input contains N and M. This is followed by the description of the N objects. The description of the i-th object will start by a number k, which is the number of properties associated with the object. The next k lines contain two space separated strings – the property key and the property value. Note that the property value is not necessarily an integer (although this is so for the example above). This is followed by the description of M queries. The format of a query will be exactly same to that of the objects. Check the Sample Input for clarification. One test file will contain only one test case. A single test case may contain several queries.

Output:

Print M lines. Each line must be the answer of the respective query.

Constraints:

1 <= N <= 10000

1 <= M <= 100000

1 <= k <= 4

Sample Input 2 3

4

height 100a

weight 50b

xposition 25a

yposition 36b

4

area 100a

noofleaves 500

height 25

yposition 36b

3

weight 80

xposition 25a

yposition 36b

1

yposition 36b

2

xposition 25a

yposition 36b

Sample Output:

0

2

1

Read more »

 
 
 
 
  • Vote: I like it  
  • -5
  • Vote: I do not like it  

By rahul_1234, history, 4 months ago, In English,
Given n boxes of different weights and m machines of different weight carrying capacity. Find the minimum time required to move all boxes. Each machine take 1 minute to carry one time.

Read more »

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By rahul_1234, history, 4 months ago, In English,

Can somebody suggest a approach.

Link : In the given link it says if the word is in min heap, then also you can increase the count but it is slightly confusing. Can somebody suggest an approach for this or another way for updation if the word already exists in min_heap.

Read more »

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By rahul_1234, history, 5 months ago, In English,

I am sharing image of question as link is not working:

Img1

Img2

Please someone help me in his question.

Read more »

 
 
 
 
  • Vote: I like it  
  • +1
  • Vote: I do not like it  

By rahul_1234, history, 5 months ago, In English,

I had a doubt how this solution clears large dataset of Kickstart Round B as it is (N*M*K) which is dp entries and each entry is computed in approx (N*M). Lastly T test cases too and each of the variable, that is, N, M, K, T is in range 1,..,100.

Link of solution

Link Of Problem

Am I making an error in understanding or test cases were weak as I tried locally on large dataset and it worked within 2 mins.

Read more »

 
 
 
 
  • Vote: I like it  
  • +6
  • Vote: I do not like it  

By rahul_1234, history, 5 months ago, In English,

You are given a string of ‘n’ characters where n is even. The string only consist of 6 type of characters: (){}[]. The task is to form a well formed expression. A well formed expression consist of proper nesting of braces and their is no priority between the braces like [ > } > ). You can edit any bracket and change it to remaining types for accomplishing the task.

Example 

A. "(){}" is valid 

B. "({[]})” is valid 

C. “((})” is invalid

Read more »

 
 
 
 
  • Vote: I like it  
  • -17
  • Vote: I do not like it  

By rahul_1234, history, 5 months ago, In English,

You are given a number of points on the XY-plane, [(x0,y0),(x1,y1),(x2,y2),...]. A point (xi,yi) is dominant to another point (xj,yj) iff xi>xj and yi>yj. Calculate all pairs of points such that one dominates the other.

A time complexity less then O(n*n) was required.

Read more »

 
 
 
 

By rahul_1234, history, 5 months ago, In English,

In a city, the rents of apartments change every month according to the demand. If there are x apartments in the city, all the rents for 12 months are given for each apartment and also x one time relocation prices are given(Applies when you move from one apartment to other in the first month).

If a person comes to this city and wants to rent an apartment, optimize the rental cost for whole year by generating a month wise plan on where he must stay each month?

Read more »

 
 
 
 
  • Vote: I like it  
  • -2
  • Vote: I do not like it  

By rahul_1234, history, 5 months ago, In English,

Given a set of restaurants (the number being quite large) and its geographical location(x,y) , you are allowed to do an significant amount of pre-processing on it. Now suppose there are x customers located at position (s,t), design an efficient algorithm to find the k nearest restaurants to these customers.

Read more »

 
 
 
 
  • Vote: I like it  
  • -2
  • Vote: I do not like it  

By rahul_1234, history, 5 months ago, In English,

Problem: Write a method that, given a digit 'd' and number of its occurences 'k', returns a range which has that many occurrences of d. More precisely, return a lower and upper bound of this number N.

Example:

input: d=4, k=1

output {4, 13}

Range: 4-14

input: d=4, k=0

output {1, 3} Range: 1-3

Can anybody help me in this?

Read more »

 
 
 
 
  • Vote: I like it  
  • -13
  • Vote: I do not like it  

By rahul_1234, history, 5 months ago, In English,

Hi,

Given a max-heap represented as an array, return the kth largest element without modifying the heap. Pleaae provide an algorithm which is most optimised. There are few answers on net but I guess most are following a particular structure of heap, so I want a correct answer.

Read more »

 
 
 
 
  • Vote: I like it  
  • -9
  • Vote: I do not like it  

By rahul_1234, history, 5 months ago, In English,

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The cell itself does not count as an adjacent cell. The same letter cell may be used more than once.

1). Grid: ab

Word = abab

return 0

2). Grid

[ ["ABCE"],

["SFCS"],

["ADEE"] ]

Word = "ABCCED"

return 1

I cannot get a proper solution to this which handle all cases so if someone can help, it would be very helpful?

Read more »

 
 
 
 
  • Vote: I like it  
  • +14
  • Vote: I do not like it  

By rahul_1234, history, 7 months ago, In English,

Given 'n' circles (each defined by center and radius) Write an algorithm to detect if given circles intersect with any other circles in the same plane

Better than O(n^2) complexity

Read more »

 
 
 
 
  • Vote: I like it  
  • +16
  • Vote: I do not like it  

By rahul_1234, history, 7 months ago, In English,

Giving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.

Example:

S = abpcplea,

Dict = {ale, apple, monkey, plea},

the return "apple"

Can somebody provide trie solution( O(N*K) ), N: length of string, K: length of longest word?

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it  

By rahul_1234, history, 8 months ago, In English,

In today's kickstart problem, https://codejam.withgoogle.com/codejam/contest/6304486/dashboard#s=p1

I am getting wrong answer on big input but smaller input works fine and gives correct answer. Here is my code: https://ideone.com/7Ffer4

I tried with bigger input and answer is coming mostly as 0.

I can't find the error. Can someone tell the error and how to correct it.

Read more »

 
 
 
 
  • Vote: I like it  
  • -3
  • Vote: I do not like it  

By rahul_1234, history, 15 months ago, In English,

Hi, I wanted to solve this question in O(N) but couldn't think of it. I did it in O(N logN ) using priority queue but can somebody provide me O(N) solution.

https://postimg.org/image/c31iexg13/

The link of question is not opening now, so I have shared the pic of question.

Read more »

 
 
 
 
  • Vote: I like it  
  • -15
  • Vote: I do not like it  

By rahul_1234, history, 21 month(s) ago, In English,

Can anybodyt help to find complexity oof this algo: T(n) = n^ (1/3) T( sqrt( n) ) + 2n

I solved it and found it be O(n) but is it correct? Please confirm.

Read more »

 
 
 
 
  • Vote: I like it  
  • +20
  • Vote: I do not like it  

By rahul_1234, history, 21 month(s) ago, In English,

Given an array A of n numbers, we want to select a sub-sequence of A such that each number in the sub-sequence is at least as large as the previous one, and such that the length of this sub-sequence is as large as possible. Give a divide-and-conquer algorithm for this problem. What is the running time of your algorithm?

I got this explanation but could not understand:

A natural algorithm is to divide the problem into n problems of size n/2, where for problems on the left, we compute the longest increasing subsequence ending at a given position, for the ones on the right we want to compute the longest increasing subsequence with a given element as the smallest. The recursion is therefore T(n) = nT(n/2) + O(1).

So please explain this to me. I'll be thankful to you.

Read more »

 
 
 
 
  • Vote: I like it  
  • -12
  • Vote: I do not like it  

By rahul_1234, history, 22 months ago, In English,

I want to sort the numbers using linked list in O(nlogn) time complexity and O(1) space complexity? Plz help me in this.

Read more »

 
 
 
 
  • Vote: I like it  
  • -14
  • Vote: I do not like it  

By rahul_1234, history, 22 months ago, In English,

In the problem https://www.codechef.com/problems/CHEFQUE,

submission : https://ideone.com/l2LPvy got TLE. It used comp().

However, when I didn't use comp() and just used sort( vc.begin(), vc.end() ) it got accepted. Submission link https://ideone.com/NgbwUO.

Even though both are doing same thing, why comp() is giving TLE and how can we improve on it. Please somebody guide me on this.

Read more »

 
 
 
 
  • Vote: I like it  
  • +3
  • Vote: I do not like it