Question

DE Shaw | OA (SDE intern 2022) | Tubby and Tom | Set-27 | 2022

Answer 1

There were three questions. This is the third one. Please comment the solution if anyone gets it. Thanx in advance :)

 

I dont have screenshots of the first two, but they were something like this:

1)Given a list of strings each od length 10 find the string with minimum mismatches with all other strings.

2)given a sequence
1,2,3,5,6,7,8,9,10,11,12,13,15,16,17,18,19,20,21,22,23,25,26,27,28,29,30,31,32,33,35,36,37,38,39,50,51,52,53,55....
now you will be given a x in string format(which may also contain leading zeros) you have to find position of x in the given sequence
constarints: 1<=length(x)<=10^5
for example,
input: 12 
output: 11

 

 

Answer 2

 It looks like this could be solved with a BFS-based solution, advancing each person 1 at a time. For the both the dog and cat, keep track, for each node, the earliest time he can get to the node. If the dog can reach the cat in the same turn (same meaning time+1 based on how the question words time) or earlier, then that node must be pruned from the cat's BFS search.

 

In the end, the answer is the max time for the dog among the nodes that the cat can reach (that haven't been pruned). Since the graph is a tree and not, say, a cycle, I can't imagine a situation where the dog can't ever catch the cat.

 

These are just my initial thoughts; I haven't given much time into a proof or anything, but this seems like it would work to me.

1st one was pretty simple a brute force
For 2nd one : (my solution got pass)
Consider n = 13
Here ‘1’ denotes there are one 4s at unit place

 

Consider n = 15
Here ‘1’ denotes there are one 4s at unit place + As ‘5’ i> 4 there i one more 4

 

Consider n = 51
Here ‘5’ denotes there will be 5 fours at unit place and as ‘5’>4 denotes that there will once an occurrence of 40-49

 

Consider n = 153
‘15’ denotes there will be 15 fours at unit place
‘1’ denotes there is range of 40-49 + ‘5’ >4 so one more range of 40-49

 

Code :
Prefix[0] = 0
For i in n : prefix[i] = prefix[i-1]*10 + (s[i]-’0’)

 

Cut = 0;
Mult = 1;
For i in [n-1 to 0]
Cut += prefix[i]mult + (s[i]>’4’)
Mult = mult9
Return prefix[n]-cut

 

For 3 question (it also passed):

 

Get dist_d []and dist_c[] as distance of each node using dfs call for each node C and
D.

 

Now for each i :
If our C can reach there before D (which means dist[d]>dist[c]+1)
then : ans = max(ans,2*dist[d]-1)

 

Return ans;

 

Reason :

 

If our node C can reach any node i then he can travel there and wait for D to come.

 

Consider this :

 

1*(D here at start) - 2 - 3 - 4 - 5 - 7
|
6 (C here at start)

 

Now our D at 1 sec goes to 2
Then C at 2 sec goes to 4
Then D at 3 sec goes to 3
Then C at 4 sec goes to 5
And so on

 

My Solution for Second Question:
Time: O(N) Space: O(N)

 

#include<bits/stdc++.h>
using namespace std;
int main()
{
    string s;
    cin >> s;
    vector<int> prefix(s.length() + 1, 0);
    int m = 1;
    for(int i = 1; i <= s.length(); i++){
        prefix[i] = prefix[i - 1] * 10 + m;
        m *= 9;
    }
    int res = 0;
    for(int i = 0; i < s.length(); i++){
        res = res + prefix[s.length() - 1 - i] * (s[i] - '0') + (s[i] - '0' > 4 ? prefix[s.length() - 1 - i + 1] - prefix[s.length() - 1 - i] * 10: 0);
    }
    cout << stoi(s) - res << endl;
    return 0;
}