SDE - 1

count amount of such substrings of t that are bigger than corresponding substring of s and begin at the position i.

1.If t[i] < s[i], this amount equals 0.

2.If t[i] > s[i], this amount equals n - i.

3.If t[i] = s[i], then let's find such nearest position j,  j > i , that t[j] ≠ s[j]. If t[j] > s[j], needed amount of substrings will be n - j. If t[j] < s[j], needed amount of substrings will be 0.

We can rephrase this: If t[i] > s[i], it will be (1 + pref)·(n - i) new substrings, where pref means how many last elements in s and t is equal.

Let's make dp. dp[i][sum] means that we viewed i positions, have sum needed substrings and s[i] ≠ t[i]. Lets iterate their common prefix pref.

If t[i] < s[i], dp[i][sum] +  = dp[i - pref - 1][sum]·(s[i] - 'a') — we can count this value using partial sums.

If t[i] > s[i], dp[i][sum] +  = dp[i - pref - 1][sum - (1 + pref)·(n - i)]·('z' - s[i]). Let's iterate pref.

Let's note that sum - pref·(n - i) ≥ 0, so pref ≤ sum / (n - i) and pref ≤ k / (n - i). This means that third cycle will make at most k / (n - i) iterations when we find value of dp[i][sum]. Let's count total number of iterations:

 =   <  k·(n + k·log k).

Build up the tree, then with dfs at any step you could get all ancestor: push it to stack then pop if you processed x, but this could be too slow when the tree is a path (there are n ancestor in the worst case). How to find the max value for e ^ node ? Since you are doing the xor bit by bit we can find the max value also bit by bit, start from the largest possible power of two then you need to know for a given val2=e^node value only if you shift right the e ^ val2 by d then was it in the root-x path shifted by d ?
[notice that node=e^val2 because val2=e^node]
Use a segmented tree to decide this in O(1), hence you can process each query in O(log(n)) time. [sort also the queries to know what you should answer for x].

As there were only four strings hence the number of cases was not much. So i first found the common prefix from all the strings and took them as one node. After that I tried every permutation possible between the strings and find the minimum number of node.

This can be done with Dijkstra:

lets say our dijkstra state is {daysPassed, timeTravelled, vertexId}

initial state is {0,0,startCity} we add it to priority queue (sorted as tuples, min first)

For each state in queue:

try going to all neighboring cities (if timeTravelled + edgeWeigth <= maxTravelTimePerDay), state changes to {daysPassed, timeTravelled + edgeWeight, neighbourId}

try to sleep in current city (if it has a hotel), state changes to {daysPassed + 1, 0, vertexId}

Of course its not profitable to sleep in same hotel 2 times so we can additionally keep a boolean array indicating whether we slept in some hotel and only try to sleep in hotel once (on first time visiting vertex)

if any time during algorithm we reach goal city daysPassed from state is the answer

First of all i gave the naive approach to try all the words that can be formed using the number string and then checking which word is present in the dictionary.
Then i give the reverse approach -> load the dict, then translate each dictionary word character-by-character into its keypad representation.The input number then just need to be directly matched against these number, and return all matching dict words.

After that he asked me to optimise it further. Then. i give the approach using trie in which is each node is linked to a hash map, which contains the value of the key which can used to generate the letter.