Given a text and search query which could consist of multiple languages lets say polish and english, you need to find whether the given search query is substring of the input text or not.

There is an added condition, you are allowed to replace any substring with its corresponding meaning in other language. For example, given the following mapping:

ó - u
ł - ou
ż - zg

You can replace ó with u and vice versa, same for ł and ż

Following are some example inputs and output as per the above mentioned mapping.

Text | Term | Result

soł | u | false

soł | ou | true

soł | ł | true

sou | ł | true

Explanation for second test case: input text is 'soł', since ł can be replaced with ou, and input text will become soou, and the search query is 'ou', the result is true.

Could anyone suggest some optimal solution for this problem. Please let me know in the comments if the problem statement is unclear.

Could anyone share an optimal approach for solving the following question:

Given an n array tree, we need to find out the number of nodes whose value is less than the median value of all the nodes in the subtree for a given node.

You can assume the tree has structure like this:

struct Node {
  int value;
  vector<Node*> children;
}

Example:

In above example there are 3 such nodes where the value of the node is less than the median value of all nodes in its subtree.

Node-2 value is less than the median value that is 4(coming from Node-5).

Node-3 value is less than the median value that is 12(coming from Node-6).

Node-1 value is less than the median value that is 10(median of 2,4,10,12,22)

Let me know if the example is not clear.

Given two strings s1 and s2, the task is to find the minimum number of steps required to convert s1 into s2. The only operation allowed is to swap adjacent elements in the first string. Every swap is counted as a single step.

Examples:

Input: s1 = “abcd”, s2 = “cdab” 

Output: 4 

Swap 2nd and 3rd element, abcd => acbd 

Swap 1st and 2nd element, acbd => cabd 

Swap 3rd and 4th element, cabd => cadb 

Swap 2nd and 3rd element, cadb => cdab 

Minimum 4 swaps are required.

Input: s1 = “abcfdegji”, s2 = “fjiacbdge” 

Output:17 

There is a GFG post present for the same question. The time complexity on the post is O(n^2).

GFG post link: https://www.geeksforgeeks.org/minimum-number-of-adjacent-swaps-to-convert-a-string-into-its-given-anagram/

Question is can it be solved in better time complexity.

Thanks in advance.

Hello Guys,

Could you share your thoughts on the following question:

Given an undirected graph with node values as string, and a path to follow, you have to find a path which is most similar to the input path.

For example, for the following graph:

Please note that the value in the input path could be completely different from any existing node. The task is to find out a path which resembles the most with the given path. There could be multiple possible outputs.

Input Path: ["KPG"->"DPS"->"SIN"->"AUH"]

Expected Output: ["KUL"->"DPS"->"CGK"->"AUH"]

In the above example, the least number of changes that you have to make is to replace KPG with KUL, and SIN with CGK.

Input Path: ["XXX", "TBS", "DME"]

Expected Output: ["ATH", "TBS", "DME"]

Update:

Pasting from comment for better explanation:

As you can see from the example, most similar path here means the actual path which deflects the least from the given path in the input. So, for the given example where input path is ["XXX"->"TBS"->"DME"], the starting node "XXX" is not there but the remaining nodes TBS and DME are there and they are in the same order, what I am trying to say here is that TBS->DME are already here, so I just need to replace "XXX" with something which connects to TBS. By replacing XXX, I am making only one change, which is the best that I could do in this case.

If the input would have been something like ["ATH"->"TBS"->"DME"], then as we can see that "ATH"->"TBS"->"DME" already exist in the graph and I don't need to make any change, so in this case output is same as input that is "ATH,TBS,DME".

Problem: Given a matrix of dimension m*n. There are x number of penguins standing on some cell(i,j) in the matrix initially(none of the penguin are on the same cell). And there are some safe spots/cells in the matrix. Our job is figure out the minimum time for penguins to reach the safe spot with following conditions:

1. If a spot is already taken by some penguin, any other penguin cannot take that spot.
2. While traversing, If some penguin passes through cell (i,j) in its path to reach some safe spot, it is banned for other penguins to use that cell.

Print -1 in case if it not possible for all penguins to reach to some safe spot.

Penguins can move in four directions i.e either up, down, left, right. All penguins can move to one of the adjacent cells in 1 unit of time.

Let me know if the problem statement is not clear.

Test case:

P1 . . P2

. S S .

. . . .

S S . .

P1 and P2 are penguins and they are standing on cell (0,0) and (0,3) initially and there are multiple safe spot in this example located at (1,1), (1,2), (3,0) and (3,1). The minimum time for both penguin to reach at the safe spot will be 2.

Output: 2

Test case:

. S . .

P1 . P2 P3

. S S .

. . . .

Output: 2

There is a single solution possible for this test case, P1 has to follow:(1,0)->(0,0)->(0,1), P1 cannot use the path:(1,0)->(1,1)->(0,1) because if P1 uses this path then (1,1) will get banned for P2 to use and we won't be able to take P2 on safe spot.

Would love to hear about your approach.

Hello Guys,

Can you share your thoughts on the following question:

Given a string, we have to find the longest non-overlapping repeating subsequence. For example, If we have a string like "abdead", then here the answer is "ad" because longest repeating subsequence is "ad" which is non-overlapping.

My initial thought on this question is that we can use the concept of longest common subsequence but we need to manage the non-overlapping part.

Thanks in advance!

Hello all,

Can you please share your thoughts on the following question:

Given an array of integers and some queries, you have to tell the length of the longest increasing subsequence for each query. The query is in the form such that you have to change the value at a given index to given value. Each query is independent of others. So the array gets backs to its original state after each query.

Example: Arr[]={1,6,2,4};

query: 1 4 : means: arr[1]=4, Now calculate the length of LIS.

Thanks in advance.

Hello all,

Could someone share their thoughts on the problem mentioned below:

Given an array of sorted integers, find the number of unique triplets such that (a[i]*a[k])+a[j]=target and i<j<k.

Ex: A={1,3,3,5,5} and target=18 o/p should be {[3,3,5]} . Explanation a[1]*a[3]+a[2].

I know we can solve it in O(n^2) time.

Ques-1: Can we solve it in less than O(n^2) time. If yes, how?

Quest-2: What if the given array is not sorted? What will be the time complexity in this case?

Thanks in advance.

Hello all,

Can someone share their thoughts on the following question :

Given a array of n elements. You have to find the median of difference of pairs. For Example: Lets say the elements are {1,2,4,5}. So the pairs will be {(1,2),(1,4),(1,5),(2,4),(2,5),(4,5)}. The array formed by those pairs are {1,3,4,2,3,1}. So you have to find the median of this new array generated by the difference of pairs.

I know it can be easily done in O(n^2). Could anyone share their approach to solve it in less than O(n^2) time.

Thanks in advance.

Hi All,

Can someone share their ideas on how to do the following problem in O(n): http://www.geeksforgeeks.org/lexicographically-smallest-rotated-sequence-set-2/

I have found on wikipedia that it can be done in O(n). I am not able to understand the booth's algorithm given on wikipedia.

Can someone share their approach to solve this problem in O(n).

Thanks in advance