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 graphA -> 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