DAA Interview Questions
The name 'Algorithm' refers to the sequence of instruction that must be followed to clarify a problem.
The logical description of the instructions which may be executed to perform an essential function.
The time complexity of an algorithm denoted the total time needed by the program to run to completion. It is generally expressed by using the big O notation.
Any subset that satisfies these constraints is known as a feasible solution. A feasible solution, which either maximizes or minimizes a given purpose method is known as an optimal solution.
DP is another method for problems with optimal substructure: An optimal solution to a problem include optimal solutions to subproblems. This doesn't necessarily define that every optimal solution to a subproblem will contribute to the primary solution.
For divide and conquer (top-down), the subproblems are independent, so we can resolve them in any order.
Warshall's algorithm is a function of dynamic programming procedure, which is used to find the transitive closure of a directed graph.
A greedy technique for an optimization problem always makes the option which look best at the moment and add it to the current subsolution.
1.The greedy method produces a feasible solution
2.The greedy method is very easy to solve a problem
3.The greedy method implements an optimal solution directly
A spanning tree for a linked graph is a tree whose vertex set is the same as the vertex set of the given graph, and whose edge set is a subgroup of the edge set of the given graph. i.e., any linked graph will have a spanning tree.
This is a greedy method. A greedy method chooses some local optimum (i.e., selection an edge with the smallest weight in an MST).
Floyd's algorithm is a function, which is used to find all the pairs shortest paths problem. Floyd's algorithm is relevant to both directed and undirected weighted graph, but they do not include a cycle of a negative length.
Prim's algorithm is a greedy and efficient technique, which is used to find the minimum spanning the tree of a weighted linked graph.
Dijkstra's algorithm solves the single-source shortest path method of finding shortest paths from a given vertex (the source), to another vertex of a weighted graph or digraph. Dijkstra's algorithm implements a correct solution for a graph with non-negative weights.
A Huffman tree is a binary tree which reduces the weighted path length from the root to the leaves, including a set of predefined weights. The essential application of Huffman trees is a Huffman code.
A Huffman code is an optimal prefix tree variable-length encoding technique which assign bit strings to characters based on their frequency in a given text.
Depth-first node generation with bounding method is known as backtracking. The backtracking technique has its virtue the ability to yield the solution with far fewer than m trials.
| Dynamic programming | Greedy method |
|---|---|
| Many numbers of decisions are generated. | Only one sequence of decision is generated. |
| It gives an optimal solution always | It does not require to provide an optimal solution always. |
The problem is to area n-queens on an n-by-n chessboard so that no two queens charge each other by being same row or in the same column or the same diagonal.
The types of Notations used for Time Complexity includes:-
Big Oh:It indicates “fewer than or the same as” < expression >iterations
Big Omega:It indicates “more than or same as” < expression >iterations
Big Theta:It indicates “the same as”< expression >iterations
Recursive algorithm is a method of solving a complicated problem by breaking a problem down into smaller and smaller sub-problems until you get the problem small enough that it can be solved easily. Usually, it involves a function calling itself.
It is a language feature that allows a subclass or child class to provide a specific implementation of a method which is already provided by one of its super classes or parent classes.
The constructor has the same name as the class. A constructor is also a special kind of method. It is used to initialize objects of the class.
Access modifiers or access specifiers are the keywords in object-oriented languages. It helps to set the accessibility of classes, methods, and other members.
If you derive a class from another class that is known as inheritance. The child class will inherit all the public and protected properties and methods from the parent class. The child class can also have its own properties and methods. An inherited class is defined by using the extends keyword.
combination of multiple and multi-level inheritance is known as hybrid inheritance.
Hierarchical inheritance is basically when one base class has more than one subclasses. For example, the fruit class can have ‘apple’, ’mango’, ’banana’, ‘cherry’ etc. as its subclasses.
It Increases the execution time and effort. It also requires jumping back and forth between different classes. The parent class and the child class is always tightly coupled.
Afford modifications in the program would require changes for parent and the child class both. Inheritance requires careful implementation otherwise it would lead to incorrect results.
A superclass or base class is also a class which works as a parent to some other class/ classes.
For example, the Vehicle class is a superclass of class Bike.
A subclass is a class that inherits from another class.
For example, the class Bike is
a subclass or a derived of Vehicle class.
Yes, the constructors can be overloaded by changing the number of arguments accepted by the constructor or by changing the data type of the parameters
Static polymorphism or static binding is a one kind of polymorphism which comes at compile time. example of compile-time polymorphism is: method overloading.
Dynamic polymorphism, dynamic binding or Runtime polymorphism is also part of polymorphism which is basically solved during runtime. An example of runtime polymorphism: method overriding.
Operator overloading is used to implement operators using user-defined types, based on the arguments passed along with it.
Data abstraction is one of the most important features of OOPs. It only allows important information to be displayed. It helps to hide the implementation details.
For example, while using a mobile, you know, how can you message or call someone but you don’t know how it actually happens.
This is data abstraction as the implementation details are hidden from the user.
Data abstraction can be achieved using two ways:
1. Abstract class
2. Abstract method
An abstract class is also a class which is consists of abstract methods.
These methods are basically declared but not defined and If these methods need to be used later in some subclass that time those methods haveto be exclusively defined in the subclass.
Virtual functions are also part of the functions which are present in the parent class and they
are overridden by the subclass.
These functions help to achieve runtime polymorphism.
Garbage Collection is a part of automatic memory management. The Garbage collector helps to free the occupied spaces by objects. Those spaces are no longer in existence.
Zero instances will be created for an abstract class. In other words, you cannot create an instance of an Abstract Class.
An exception is a kind of message that interrupts and comes up when there is an issue with normal execution of a program. Exceptions provide a error and transfer that error to the exception handler to resolve it.
Exception handling in Object-Oriented Programming is the most important concept. It is used to manage errors. An exception handler help to throw errors and then catch the error in order to solve them.
A try/ catch block helps to handle exceptions. The try block explains a set of statements that may have an error. The catch block basically catches the exception.
An inline function is a technique used by the compilers and instructs to insert complete body of the function wherever that function is used in the program source code.
A friend function is a friend of a class that is allowed to access to Public, private, or protected data in that same class. If the function is defined outside the class cannot access such information.
The super keyword is used to invoke the overridden method, which overrides one of its superclass methods. This keyword allows to access overridden methods and also to access hidden members of the superclass. It also forwards a call from a constructor, to a constructor in the superclass.
Operator keyword is used for overloading.
An interface is a collection of an abstract method. If the class implements an interface, it thereby inherits all the abstract methods of an interface. Java uses Interface to implement multiple inheritances.
Early binding refers to the assignment of values to variables during design time, whereas late Binding refers to the assignment of values to variables during run time.
A pure virtual function is a function which can be overridden in the derived class but cannot be defined. A virtual function can be declared as Pure by using the operator =0.
No comments:
Post a Comment