What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?(a) O(S1)(b) O(S2)(c) O(S1+S2)(d) O(1)This interesting question is from Propositional and Directed Acyclic Word Graph topic in section Graph of Data Structures & Algorithms IThis question was posed to me during an online interview.

What is time complexity to check if a string(length S1) is a substring

1.	What is time complexity to check if a string(length S1) is a substring of another string(length S2) stored in a Directed Acyclic Word Graph, given S2 is greater than S1?(a) O(S1)(b) O(S2)(c) O(S1+S2)(d) O(1)This interesting question is from Propositional and Directed Acyclic Word Graph topic in section Graph of Data Structures & Algorithms IThis question was posed to me during an online interview.
Answer» CORRECT option is (a) O(S1) Easiest explanation - For each CHECK of a word of lengthS1, we need to follow at most S1 EDGES.

Discussion

No Comment Found

Related InterviewSolutions

In a Propositional Directed Acyclic Graph Leaves maybe labelled with a boolean variable.(a) True(b) FalseWhat is the answer to this question? I'm confused
What is the number of words that can be formed from the given Directed Acyclic Word Graph?(a) 2(b) 4(c) 12(d) 7Please answer it as soon as possible.
For any two different vertices u and v of an Acyclic Directed Graph if v is reachable from u, u is also reachable from v?(a) True(b) False
Which of the following logical operation can’t be implemented by polynomial time graph manipulation algorithms using Binary Decision Diagrams?(a) Conjunction(b) Disjunction(c) Negation(d) Tautology CheckingI'd like to ask this question from Binary Decision Diagrams &And Inverter Graph in section Graph of Data Structures & Algorithms IThe question was asked in a job interview.
The And Inverter Graph representation of a Boolean function is more efficient than the Binary Decision Diagram.(a) True(b) FalseThis intriguing question originated from Binary Decision Diagrams &And Inverter Graph in section Graph of Data Structures & Algorithms IThis question was addressed to me in a national level competition.
And Inverter Graph is a type of __________(a) Multigraph(b) Cyclic Graph(c) Directed Acyclic Graph(d) Directed Acyclic Word GraphI want to ask this question from Binary Decision Diagrams &And Inverter Graph in chapter Graph of Data Structures & Algorithms IThis question was addressed to me in examination.
Size of an And Inverter Graph is the number of _______ gates and the number of logic levels is number of ________ gates on the __________ path from a primary input to a primary output.(a) AND, AND, average(b) AND, OR, longest(c) OR, OR, shortest(d) AND, AND, longestMy enquiry is from Binary Decision Diagrams &And Inverter Graph in portion Graph of Data Structures & Algorithms IThis question was posed to me in an online quiz.
Two or more And Inverter Graphs can represent same function.(a) True(b) FalseThis intriguing question originated from Binary Decision Diagrams &And Inverter Graph topic in portion Graph of Data Structures & Algorithms IThis question was addressed to me in homework.
How many nodes are required to create a Binary Decision Tree having 4 variables?(a) 2^4(b) 2^4-1(c) 2^5(d) 2^5-1Asked question is from Binary Decision Diagrams &And Inverter Graph topic in portion Graph of Data Structures & Algorithms II got this question in quiz.
In a Binary DecisionDiagrams 0 values by a _________ line and the 1 values are represented by a _________ line.(a) dashed, bold(b) bold, dashed(c) dotted, bold(d) dotted, dashedI want to ask this question from Binary Decision Diagrams &And Inverter Graph in chapter Graph of Data Structures & Algorithms IThe question was posed to me during an internship interview.

Discussion

No Comment Found

Related InterviewSolutions

Reply to Comment