## tusharrawat831

BAN USER- 0of 0 votes

AnswersWe are given a graph of N nodes. (1-N), where each node has exactly 1 directed edge to some node (this node can be the same node).

We need to answer the queries of type : A, B, which asks time required when 2 objects collide if one start at A and other start at B. Both moves 1 hop in 1 sec. If it's not possible for them to collide time would be -1.

Time : from X -> to Y : 1 hop = 1 second.

Constraints :

N, Q <= 10^5 (number of nodes, number of queries).

Example : for given graph`A -> B -> C -> D -> E ^ | K <- F`

Query(A, E) : 3 seconds, as at time t = 3 secs they both will be on node D.

- tusharrawat831 in United States

Query(C, D) : -1 seconds, as they will never collide.

Brute force will take O(Q * N) time. Can we do better than that?| Report Duplicate | Flag | PURGE

Hi5 Software Developer Programming Skills - 0of 0 votes

AnswersDesign a system to efficiently find 10 top selling products on an online shopping site at a given time with a time window of say 20 minutes.

- tusharrawat831 in India

Say, every second 100 products buy count getting updated.

Which data structure && algorithm would be the best to design such kind of systems ?| Report Duplicate | Flag | PURGE

Accolite software Software Engineer System Design - 0of 0 votes

AnswersQ. find the number of ways a string can be formed from a matrix of characters.

- tusharrawat831 in United States

It can start forming a word from any position in mat[i][j] and can go in any unvisited direction from the 8 directions available across every cell [i][j].

sample case :

input:

N = 3 (length of string)

string = fit

matrix :

fitptoke

orliguek

ifefunef

tforitis

output: 5

explanation:

num of ways to make 'fit' from matrix chars are 5 as given below sequence:

(0,0) (0,1)(0,2)

(2,1) (2,0)(3,0)

(2,3) (1,3)(0,4)

(3,1) (2,0)(3,0)

(2,3) (3,4)(3,5)

How can we solve it efficiently without doing DFS across every position [i][j], which makes time complexity exponential?

Is there a better way possible in terms of time complexity? Maybe caching of values or something!| Report Duplicate | Flag | PURGE

Software Engineer Algorithm

**CareerCup**is the world's biggest and best source for software engineering interview preparation. See all our resources.

Open Chat in New Window