Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### Romok007's blog

By Romok007, history, 6 weeks ago, ,

Given a graph whose nodes are 3-letter words and an array of 3-letter words. Find a path in the graph such that the difference b/w words in the path and given array is minimum.

We are given 2 APIs which work for this graph:

class Graph {
/**
* Get all neighbors of a node.
*/
Set<String> getNeighbors(String node);

/**
* Get a list of all nodes in no particular order.
*/
Set<String> listAllNodes();
}


Consider a graph G: Test Graph

Example 1:

Input: G, arr = [AAA, BBB, CCC, DDD] Output: 2 Explanation: The path [AAA, BBC, CCD, DDD] is closest to given array. In path, BBC differs from BBB by 1 and CCD differs from CCC by 1 hence answer is 1 + 1 = 2. Example 2:

Input: G, arr = [AAA, CCC, AAA, BBD] Output: 3 Explanation: The path [AAA, BBC, AAA, BBC] is closest to given array. In path, BBC differs from CCC by 2 and BBC differs from BBD by 1 hence answer is 2 + 1 = 3.

Notice that we can visit the same node multiple times.

I can only think of a backtracking solution, is there a more optimal way to compute the answer? Thanks in advance :)

• +15

By Romok007, history, 6 months ago, ,

Hi Everyone, I am stuck in an interview problem and not finding any resources on the internet which can help me find a solution, if you provide an idea about the solution it will be of great help. The problem is as follows :

Generate a random binary search tree of 'n' nodes with equal probability.

For example : if n = 3 there are 5 possible binary search trees, our program should return any one tree with equal probability (i.e. 1/5).

• +8

By Romok007, history, 7 months ago, ,

Given an unsorted array find the numbers in the array that return true for the following function (defined below).

1. Function will return true for value x, if all numbers on left side of x are small and all number on the right side of x are greater.

But the question asks us to use randomized binary search (mid element is not decided by (high + low)/2 but by using a random function) to find the solution.

Link to the question : Original Question Source (Round 3 Onsite question)

Example : Input : [ 4, 3, 1, 5, 7, 6, 10] Output : 5,10

Expected Time Complexity : O(n) Expected Space Complexity : O(n)

Any kind of help will be helpful as i am stuck with the question :).

• -18

By Romok007, history, 9 months ago, ,

Hi Everyone, I need help with this problem Problem. It appeared in goldman sachs sample test on hackerrank. Thanks in advance :)

• 0

By Romok007, history, 11 months ago, ,

Hello everyone. The question goes as follows : Given an unweighted undirected connected graph we need to construct the tree with minimum depth such that the tree consists of all the vertices of the graph. Any thoughts about the approach? Thank you in advance :).

• -6

By Romok007, history, 11 months ago, ,

Hello everyone. I am really stuck at this problem, can you please provide a solution? Problem Link : Overlapping Boxes. Thanks in advance :).

Problem Source : TCS Mockvita 2

• -9

By Romok007, history, 12 months ago, ,

Hello everyone. It would be great if someone gives a solution for this problem https://www.codechef.com/problems/CZ17R2Q2. Thank you.

• -1

By Romok007, history, 2 years ago, ,

Can someone please give me a solution and a PROOF of the algorithm for this problem?....Link :

• -3

By Romok007, history, 2 years ago, ,