OneWhoKnocks's blog

By OneWhoKnocks, history, 4 years ago, In English

Rick is planning to install n programs on his computer. He has to figure out how many days will it take for him to install n programs. There are a couple of things though which he has to keep in mind:

a) A program can be dependent on other program(s) — it means if program B is dependent on program A. A will have to be installed any day before B will be installed.

b) He can install at most k programs in a day.

We will be given the dependency relationship between the programs. Eg:

n : 6, K : 2

1 -> 5,6

2 -> 5,6

3 -> 4

4 -> 5,6

It will take Rick 3 days to install all the programs ->

(1st day: 1,3) (2nd Day: 2,4) (3rd Day: 5,6)

I thought of converting the above problem to a graph and then use topological sorting. But i am not able to come up with the whole solution to this problem.

Can anyone help me with this? Thanks.

Full text and comments »

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

By OneWhoKnocks, history, 4 years ago, In English

George went to a shop and is planning to buy food for his family. There are 4 members in his family including himself. And everyone wants to eat something different.

He wants Pizza for himself, his wife just wants salad , his son wants to eat hamburger and his daughter wants to have a burrito for herself.

In the shop there are multiple varieties of each food type, find the number of ways in which George can buy food for each person in the family(same food type as they want) if he has X dollars in his pocket.

Eg:

Prices of each food:

Pizza [1, 4, 5]

Salad [2, 3, 6]

Hamburger [5]

Burrito [6 3 3]

My solution: Sort each list. Find number of ways iterating through each list and doing binary search on the fourth one.

Is there any better solution than this? Thanks.

Constraints: 1 <= x <= 10^9 1 <= size of each list <= 10^3 1 <= price of food item <= 10^9

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By OneWhoKnocks, history, 4 years ago, In English

Problem Statement:

There are n Coins present in a cartesian plane. We have been given coordinates(x,y) of these coins. We can take home as much of these coins possible, given constraint that no 2 coins should have either x or y coordinates in common. Find the maximum number of coins we can take back home.

My Approach:

For a particular coin with x and y coordinates, i added 2 vertices(x and y) having an edge between them. So, i was able to convert this problem to a graph problem which will be to find minimum number of vertices to be removed so that each vertex in the graph has an edge with only one other vertex.

I wanted to discuss the possible approaches to solve this problem. Thanks.

Full text and comments »

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