Technical Interview Questions
.NET Interview Questions
Unix Interview Questions
C++ Interview Questions
Data Structures Interview Questions and Answers
Does the minimum spanning tree of a graph give the shortest
distance between any 2 specified nodes?
Minimal spanning tree assures that the total weight of the tree is kept at its
minimum. But it doesn't mean that the distance between any two nodes involved in
the minimum-spanning tree is minimum.
Whether Linked List is linear or Non-linear data structure?
According to Access strategies Linked list is a linear one. According to Storage
Linked List is a Non-linear one.
What is the quickest sorting method to use?
The answer depends on what you mean by quickest. For most sorting problems, it
just doesn't matter how quick the sort is because it is done infrequently or
other operations take significantly more time anyway. Even in cases in which
sorting speed is of the essence, there is no one answer. It depends on not only
the size and nature of the data, but also the likely order. No algorithm is best
in all cases. There are three sorting methods in this author's toolbox that are
all very fast and that are useful in different situations. Those methods are
quick sort, merge sort, and radix sort.
The Quick Sort
The quick sort algorithm is of the divide and conquer type. That means it works
by reducing a sorting problem into several easier sorting problems and solving
each of them. A dividing value is chosen from the input data, and the data is
partitioned into three sets: elements that belong before the dividing value, the
value itself, and elements that come after the dividing value. The partitioning
is performed by exchanging elements that are in the first set but belong in the
third with elements that are in the third set but belong in the first Elements
that are equal to the dividing element can be put in any of the three sets the
algorithm will still work properly.
The Merge Sort
The merge sort is a divide and conquer sort as well. It works by considering the
data to be sorted as a sequence of already-sorted lists (in the worst case, each
list is one element long). Adjacent sorted lists are merged into larger sorted
lists until there is a single sorted list containing all the elements. The merge
sort is good at sorting lists and other data structures that are not in arrays,
and it can be used to sort things that don't fit into memory. It also can be
implemented as a stable sort.
The Radix Sort
The radix sort takes a list of integers and puts each element on a smaller list,
depending on the value of its least significant byte. Then the small lists are
concatenated, and the process is repeated for each more significant byte until
the list is sorted. The radix sort is simpler to implement on fixed-length data
such as ints.
How can I search for data in a linked list?
Unfortunately, the only way to search a linked list is with a linear search,
because the only way a linked list's members can be accessed is sequentially.
Sometimes it is quicker to take the data from a linked list and store it in a
different data structure so that searches can be more efficient.
What is the heap?
The heap is where malloc(), calloc(), and realloc() get memory.
Getting memory from the heap is much slower than getting it from the stack. On
the other hand, the heap is much more flexible than the stack. Memory can be
allocated at any time and deallocated in any order. Such memory isn't
deallocated automatically; you have to call free().
Recursive data structures are almost always implemented with memory from the
heap. Strings often come from there too, especially strings that could be very
long at runtime. If you can keep data in a local variable (and allocate it from
the stack), your code will run faster than if you put the data on the heap.
Sometimes you can use a better algorithm if you use the heap faster, or more
robust, or more flexible. Its a tradeoff.
If memory is allocated from the heap, its available until the program ends.
That's great if you remember to deallocate it when you're done. If you forget,
it's a problem. A �memory leak is some allocated memory that's no longer needed
but isn't deallocated. If you have a memory leak inside a loop, you can use up
all the memory on the heap and not be able to get any more. (When that happens,
the allocation functions return a null pointer.) In some environments, if a
program doesn't deallocate everything it allocated, memory stays unavailable
even after the program ends.
Page Numbers :