Hello everyone, I came across this beautiful problem Problem. However in order to solve this problem it assumes that the shortest distance between a king at point (x, y) and any arbitrary point (x', y') is given as max(|x' — x|, |y' — y|).

The above distance is Chebyshev Distance and it is true for Kings on a chessboard. Can someone help me with the proof or at least an intuition why the above formula is true. Thanks in advance :).

Hello everyone, I am stuck at this problem. I think we can use a Trie. But I am unable to handle the special character '?'. Please help me with this problem. Thanks in advance :).

There are N words in a dictionary such that each word is of fixed length M, and consists of only lower case english alphabets. A query word Q also has length M. Query word also contains only lower case english alphabets but at some places instead of an alphabet it has "?". match_count of Q, is the count of words in the dictionary (already populated with words of same length M) and contains the same english letters (excluding the letter that can be in the position of ?) in the same position as the letters are there in the query word Q. Your are given the query word Q and you have to find the match_count.

Input Format

First line contains two space seperated integers N and M denoting the number of words in the dictionary and the length of each word
Next N line contains the words in the dictionary
Next line Q contains the number of query words
Next Q lines contain one query word each

Output
For each query word output the match_count

Constrains
1<=N<=5x10^4
1<=M<=7
1<=Q<=10^5

Time Limit - 4 secs

Sample Input:
5 3
cat
map
bat
man
pen
4
?at
ma?
?a?
??n

Sample Output
2
2
4
2

Problem Link

Hello everyone, I have a rough solution in the end, but I need your views on this. Thanks in advance :)

You are given a tree of N nodes. The tree is rooted at node 1. Each tree node has a value associated with it and is represented as value. For each node, you are required to determine the closest ancestor that contains values that are co-prime to the current node value. If no such nodes exist, then print -1. Two integers a and b are relatively prime, mutually prime, or co-prime if the only positive integer (factor) that can divide both the integers is 1.

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. A parent of a node v is the last difference from v vertex the path from the root to vertex v. Children of vertex v are all nodes for which v is the parent. A vertex is a leaf if it has no children.

Input format

• The first line contains an integer T denoting the number of test cases.

• The first line of each test contains an integer N denoting the number of nodes in the tree.

• The next line of each test case contains N space-separated integers where the ih integer denotes the value at node i represented as value;

• Next N — 1 lines of each test case contain two space separated integers u and v denoting the edge

between node u and node u.

Output format

For each test case, print N space-separated integers where the i' integer denotes the closet ancestor contains coprime values. If no such ancestors exist then print -1.

Constraints:

1 <= T <= 10
1 <= N <= 10^5
1 <= u, v <= N
1 <= valuei <= 100

My solution :

1. Create a list of co-primes for each value from 1 to 100 (Precompute)
2. Traverse the tree and for each node we maintain a hashmap of ancestors(value -> depth). When we visit a node it will contain the path from the root of the tree to this current node. We now traverse the list of co-primes for the current node and select the node that exists in the map as well in the precomputed list of the particular node(value) and select the value which has the maximum depth(closest ancestor).

However the time complexity of the solution per test case is O(N*valuei) which I think might not pass the problem. Can you please help with some optimized approach?

Given a binary tree, return the minimum number of edits to make the value of each node equal to the average of its direct children's. Note that you can only update the value of each tree node, and changing the tree structure is not allowed.

"average of its direct children's" means the average of left and right children.

1. If the left(right) children doesn't exist, then just let the root value equal to the value of its right(left) children.

2. If the root is leaf, then the criteria is always met for this node.

3. It doesn't matter if the value is int or float. We can use float.

Sample 1 :

        2
       / \
      0   2
         / \
        0   2
           / \ 
          0   1
             / \
            0   1
               / \
              0   1

Output : 5

Sample 2 :

         2
          \
           2
            \
             2
              \
               1
                \
                 1
                  \
                   1

Output : 3

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 :)

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).

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 :).

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

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 :).

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

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

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

Can someone please help me with the solution of this problem? (https://www.hackerrank.com/contests/h42-prelims-1/challenges/will-and-good-trees)