ss_96's blog

By ss_96, history, 13 hours ago, In English,

The problem statement:

There is an array given of 1s and -1s and there is a distance K,the output required is the maximum no of pairs such that their sum is 0 and both the numbers are within K distance.

eg: for array:

1 -1 1 -1 and K = 1 answer:2

This can be done with brute force,but i think there would a more efficient algorithm than just brute force.Can anyone please suggest something better,a pseudo code or is there any known algorithm for this?

Edit:A number can be taken only once.

Thanks.

Read more »

 
 
 
 

By ss_96, history, 32 hours ago, In English,

I was trying to solve the following problem:

You are given a grid of size N×N that has the following specifications:

Each cell in the grid contains either a policeman or a thief.

A policeman can only catch a thief if both of them are in the same row.

Each policeman can only catch one thief.

A policeman cannot catch a thief who is more than K units away from the policeman.

Write a program to find the maximum number of thieves that can be caught in the grid.

My solution:solution

PS:This was a question of question and I have completed the test,couldn't qualify ,that's why asking for guidance here.Please suggest what corner cases are missing with the solution code.

Thanks.

Read more »

 
 
 
 

By ss_96, history, 4 days ago, In English,

I was trying to solve this question:link

My solution:solution

The solution is not able to pass all test cases.Please help and suggest what is wrong in the implementation.I have used kruskal algorithm in the 'min_' function of the code.

Thanks.

Read more »

 
 
 
 

By ss_96, history, 4 days ago, In English,

I was trying to solve a simple DFS question and my code was not passing 2 test cases.

Question:link The solution is also given in the first comment of the problem. Can anyone please explain why the check variable is used in that code.

Thanks.

Read more »

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

By ss_96, history, 6 days ago, In English,

I was trying to solve this question:question link

My solution:solution

The problem is that it does not pass all the test cases.

Please suggest what case am I missing to handle in my code.

Thanks!

Read more »

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

By ss_96, history, 10 days ago, In English,

I recently gave an online challenge in which the following question was asked,I was able to pass only 1 test case,just wanted to have some guidance on what would be the right approach for it.

Question: There is grid given of NxM. Each cell value represents a value P,which denotes the number of parking spaces available in that city. A person wants to take his vehicle from city C(1,1) to city C(N,M) such that he parks his vehicle at one of the available parking spaces in any city and then he takes a taxi via which he reaches city C(N,M).He can park his vehicle in any city. We have to output the number of ways in which he can reach his destination.

the first line contains N,M.

In each of N lines,M numbers follow.

sample input:

2 2

1 2

0 1

sample output: 3

I tried to use BFS but that gave wrong answers in every case except 1.Please suggest what should be the approach for this question? Thanks.

Read more »

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

By ss_96, history, 2 weeks ago, In English,

I was trying to solve the following question:

You are playing a game in which you have a rectangular grid of nn cells. Each cell is either empty or has a firework. Empty cells are marked with ".", cells with firework are marked with "" . Two cells are said to be adjacent if they share a side.

If firework in any cell explodes it destroys itself and the empty cells connected to it. Two cells are connected if there is a path of empty adjacent cells between them. You have to find the number of cells that will be destroyed if the fireworks are triggered independently. Input Constraints: 1≤n≤1000 Sample Input 4

* . . *

. . * .

* . . *

* . . *

Sample Output 66(9(for 1st *)+10+10+9+10+9+9(for 7th *)).

I simply applied a BFS and added individual sum.The problem is that it only passed some test cases,wrong answer and time limit exceeded in some.Can some please suggest what test case am I missing in handling? My code: https://gist.github.com/Sharma96/16071e66b0a36828c3566196289f0c92

Read more »

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