Data Structures interview point of you

 Data Structures

The primary purpose of most computer programs is to store, retrieve, and process information. Consequently, data structures and algorithms that manipulate information of computer science. For this reason, many interviewers often focus a number of their questions on these aspects. we will cover typical interview questions about the most common data structures, including arrays, strings, lists, trees, stacks, and queues.
Arrays
Arrays might be the most simple data structure. Elements are sequentially stored in continuous memory in arrays. When an array is created, its size should be specified. Even though it may only store one element at first, the size is required because we have to allocate memory for all of the elements. Since there may be vacancies in arrays, they are not efficient in memory utilization.
In order to improve space efficiency, dynamic arrays were developed. The class vector in the standard template library (STL) of C++ is one such example. Memory is allocated for a few elements in dynamic arrays at first. When the number of elements is greater than the capacity of a dynamic array, more memory is allocated (the capacity doubles when it has to enlarge the capacity of a vector in C++), existing elements are copied to the newly allocated space, and the previous memory is released. It reduces waste in memory, but many extra operations are required to enlarge capacity, so it has negative impact on time efficiency. Therefore, it is better to reduce the times needed to enlarge the capacity of dynamic arrays. The type ArrayList in both C# and Java is similar to vector in C++.
Because memory allocation for arrays is sequential, it only costs O(1) time to access to an element based on its index, and it is very efficient. A simple hash table can be implemented with an array to utilize its advantage of time efficiency. Each index is treated as a key and every element in an array is treated as a value, so an index and its corresponding element form a pair of key and value. Many problems can be solved with such a hash table, and examples are illustrated in the section Hash Tables for Characters. It is a practical solution especially when built-in hash tables are not available in some programming languages such as C/C++.
Arrays and pointers are closely related to each other in C/C++ and also different from each other. The C code in Listing 3-1 shows the relationship between them. What is the output of this code?
Listing 3-1. C Code about Arrays and Pointers
int GetSize(int data[]) {
    return sizeof(data);
}
int _tmain(int argc, _TCHAR* argv[]) {
int data1[] = {1, 2, 3, 4, 5};
    int size1 = sizeof(data1);
 int* data2 = data1;
    int size2 = sizeof(data2);
    int size3 = GetSize(data1);
    printf("%d, %d, %d", size1, size2, size3);
}
The output should be “20, 4, 4” in a 32-bit system. data1 is an array, and sizeof(data1) gets its size. There are five integers in the array, and each integer occupies four bytes, so the total size of array is 20 bytes.
The name of an array is the address of the first element in the array, so data2 points to the first element of an array with the statement data2 = data1. data2 is declared as a pointer, and the sizeof operator returns 4 for any pointers in a 32-bit system.
When an array is passed as a parameter in C/C++, the compiler treats it as a pointer. What gets passed is the address of the first element in an array, rather than the whole array. Therefore, the result of sizeof(data) is also 4 in the function GetSize even though data is declared as an array in the parameter list.
 
www.cinterviews.com appreciates your contribution please mail us the questions you have to cinterviews.blogspot.com@gmail.com so that it will be useful to our job search community

No comments:

 
Top Blogs