0
$\begingroup$

Now the question is related to online banking. It states that like in online banking for security banks never ask the whole password but instead they may ask for 3 random numbers in their password.

For example if the password is 52842 and the bank asks for the $1^{st}, 2^{nd}$ and $4^{th}$ number one has to enter 524. Now the bank can ask for any 3 random numbers but they will always be in order.

So if one enters 743. Then 7 comes before in the password. Then comes 4 and then 3.

Now one is given about 50 3 digits numbers and one has to come up with an algorithm that analyses the file and determine the shortest possible password.

Now I just analysed the file and through brute force was able to come with the shortest password in under 5 minutes.

Now they've given a hint alongside the question: "The problem can be set up as a topological sorting problem if you can construct the appropriate DAG." I don't know how to do this method through the method mentioned in the hint and write the specific algorithm for it.

$\endgroup$
1
$\begingroup$

Assuming that the valid characters are the ten digits, set up a $10\times10$ array $G$. Read the list of $3$-digit numbers; when you read $ijk$, set $G(i,j),G(i,k)$, and $G(j,k)$ to $1$. When you’re done, $G$ is the adjacency matrix of a transitive DAG in which there is an edge from $i$ to $j$ if and only if $i$ must precede $j$ in the password. Now apply any topological sorting algorithm to this graph; the first one described here is simple and easy to understand.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.