Latest Data Structures & Algorithms Interview Questions
1.What is a data structure?
data structure is a way to store and organize data in order to facilitate access and modifications.
2.What is a user-defined data type?
A user-defined data type is a group of primitive data types defined by the programmer. As an example,in C programming language,a user can define a new data type using typedef keyword (typedef int age)
3.What is an object container?
A container is an object that holds within it other objects. Generally,container classes are expected to implement methods to do the following: a. create a new empty container (constructor) b. report the number of objects it stores (size) c. delete all the objects in the container (clear) d. insert new objects into the container e. remove objects from it f. provide access to the stored objects
4.What is a record structure?
A record structure is a join of elements of arbitrary types,that are possibly themselves structured types. For example,a Person record may contain fields like FirstName,LastName,Birthday,Person (reference to his children) and so on.
5.Which are the main primitive data type groups?
There are four primitive data type groups: a. Integer – stores whole numbers and signed numbers b. Floating-point – store real numbers (fractional values) c. Character – store characters (for example names of things) d. Boolean – store a true or false value
6.What is the difference between direct and indirect containment?
A direct containment contains copies of objects while indirect containments contain pointers to objects.
7.How can be determined the size of a structure?
It can be determined by calculating the sum of the sizes of all the primitive data types within the structure.
8.What is a pointer variable?
A pointer variable contains a memory address of another memory location,which is usually the memory address of another variable,element of a structure or attribute of a class. In C++ a pointer variable can be declared as: int
* i ;
9.What is the difference between static and dynamic data types?
Static data structures allow fast access to elements but are expensive to insert/remove elements and have fixed,maximum size. On the other side,dynamic data structures offer fast insertion/deletion of element but slower access to elements and have flexible size.
10.Describe the referencing mechanism.
Referencing mechanism tells the computer to copy the memory address of the variable instead of copying the value stored in that memory address. A reference is distinct from the data itself. Typically,a reference is the physical address of where the data is stored in memory or in the storage device. For this reason,a reference is often called a pointer or address,and is said to point to the data.
11.Define the abstraction mechanism. What are its benefits?
Abstraction can be thought of as a mechanism for suppressing irrelevant details while at the same time emphasizing relevant ones. An important benefit of abstraction is that it makes it easier for the programmer to think about the problem to be solved.
12.What is encapsulation?
Encapsulation is the mechanism of enforcing information hiding. Objects encapsulate data and the procedures for manipulating that data,thus the object hides the details of the implementation from the user of that object.
13.What is an abstract data type?
An abstract data type is a mathematical model for a certain class of data structures that have similar behaviour. It is defined by three main characteristics: encapsulation,inheritance and polymorphism.
14.What is the difference between early and late binding?
Early binding is the binding done statically by the compiler – it is realized by method overloading. Late binding is done dynamically at run-time and it is realized through inheritance and polymorphism.
15.What is a binary numbering system?
A binary numbering system consists of two digits called binary digits (bits): zero and one. A switch in the off state represents zero,and a switch in the on state represents one. This means that one transistor can represent one of two digits.
16.Which the main operations defined on basic abstract arrays?
An abstract array structure has two main operations,fetch and store. a. fetch : obtains the data stored in the element of the array whose state is A and whose index is iM b. store : the array state that results by setting the value of that element to V in array state A
17.What is a Judy array?
Judy array is a complex but very fast associative array data structure for storing and looking up values using integer or string keys. Unlike normal arrays,Judy arrays may be sparse; that is,they may have large ranges of unassigned indices. Due to its cache optimizations,Judy arrays are fast,sometimes even faster than a hash table,especially for very big datasets.
18.What is the relation between pointers and arrays?
The array name is like a pointer variable in that the array name by itself references the address of the first element of the array.
19.What is the benefit of using arrays of pointers instead of several pointer variables?
The benefit of using arrays of pointers is that you can use a for loop to step through each element of the array to access memory addresses that are assigned to the array. This must be done in order to efficiently access and reorder the values stored in memory.
20.How are elements of an array stored in memory?
The elements of an array are stored sequentially in memory (one after another). Each element of the array is identified by a unique index.
21.What is a skip list?
A skip list is a data structure for storing a sorted list of items,using a hierarchy of linked lists that connect increasingly sparse subsequences of the items. These auxiliary lists allow item lookup with efficiency comparable to balanced binary search trees.
22.Why insertAfter and insertBefore operations are not provided for sorted lists?
Because they allow arbitrary insertions,but arbitrary insertions do not necessarily result in sorted lists.
23.Give example of a way to improve the speed of random access lookups in a skip list.
The speed of random access lookups in a skip list can be improved by using an indexable skiplist. To index the skiplist and find the i-th value,the skiplist must be traversed and the widths of each traversed link must be counted down.
24.What is an unrolled linked list?
An unrolled linked list is a linked list in which each node contains an array of data values. This leads to improved cache performance,since more list elements are contiguous in memory,and reduced memory overhead,because less metadata needs to be stored for each element of the list.
25.Which are the most common used operations on sorted lists?
The most common used operations on sorted links are the following: a. findPosition – used to find the position of an object in the sorted list b. operator [] – used to access the object at a given position in the sorted list c. withdraw – used to remove the object at a given position from the sorted list
26.What is a hash function?
A hash function is a well-defined procedure or mathematical function that takes a variable-size input m and returns a fixed-size string,usually called hash value,hash code,hash sum or checksum.
27.What are the characteristics of a good hash function?
A good hash function: a. avoids collisions b. tends to spread keys evenly in the array c. is easy to compute
28.What is a chained scatter table?
It is a scatter table whose elements are ordered pairs. Each array element contains a key and a pointer. All the keys are stored in the table itself. Consequently,there is a fixed limit on the number of items that can be stored in a scatter table.
29.Can I use LOCK TABLE on a view?
No. To lock a view,take lock on the underlying tables.
30.What is open addressing?
It is a method of collision resolution in hash tables. With this method a collision is resolved by searching through different locations in the array (the probe sequence) until either the target record is found,or an unused array slot is found,which indicates that there is no such key in the table.