Vibrant Publishers - Data Structures & Algorithms Interview Questions Youll Most Likely Be Asked

Data Structures & Algorithms Interview Questions You'll Most Likely Be Asked Job Interview Questions Series www.vibrantpublishers.com ***** Data Structures & Algorithms Interview Questions You'll Most Likely Be Asked 2011, By Vibrant Publishers, USA. All rights reserved. No part of this publication may be reproduced or distributed in any form or by any means, or stored in a database or retrieval system, without the prior permission of the publisher. This publication is designed to provide accurate and authoritative information in regard to the subject matter covered. The author has made every effort in the preparation of this book to ensure the accuracy of the information. However, information in this book is sold without warranty either expressed or implied.

The Author or the Publisher will not be liable for any damages caused or alleged to be caused either directly or indirectly by this book. The publisher wishes to thank Dana Mitrea (Romania) for her invaluable inputs to this edition. Vibrant Publishers books are available at special quantity discount for sales promotions, or for use in corporate training programs. For more information please write to bulkorders@vibrantpublishers.com Please email feedback / corrections (technical, grammatical or spelling) to spellerrors@vibrantpublishers.com To access the complete catalogue of Vibrant Publishers, visit www.vibrantpublishers.com ***** Contents 1. Data Structures General Concepts Of Data Structures Arrays Stacks Queues Lists Hash Data Structures Trees Sets Graphs 2. Algorithms General Concepts Of Algorithms Sorting Algorithms Search Algorithms Huffman Coding ***** Data Structures & Algorithms Questions Review these typical interview questions and think about how you would answer them.

Read the answers listed; you will find best possible answers along with strategies and suggestions. ***** Data Structures Description: Questions in this category are related to Data Structures Topics: General Concepts Of Data Structures Arrays Stacks Queues Lists Hash Data Structures Trees Sets Graphs ***** General Concepts Of Data Structures 1: What is a data structure? Answer: A data structure is a way to store and organize data in order to facilitate access and modifications. 2: Which are the most important data structures categories? Answer: Data structures can be divided into several main categories: a) data types (primitive, composite, abstract data types) b) linear data structures (arrays, lists) c) trees d) hashes e) graphs 3: Define the abstraction mechanism. What are its benefits? Answer: 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. 4: What is encapsulation? Answer: 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. 5: What is a binary numbering system? Answer: 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. 6: What is the binding process? Answer: Binding is the process of assigning a value to an attribute. When a value is assigned to an attribute, that attribute is said to be bound to the value.

As an example, when defining a variable int i = 5 , the value of integer variable i is bound to . 7: What is the difference between early and late binding? Answer: 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. 8: What is an abstract data type? Answer: An abstract data type is a mathematical model for a certain class of data structures that have similar behavior. It is defined by three main characteristics: encapsulation, inheritance and polymorphism. 9: What is a user-defined data type? Answer: 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) 10: What is an object container? Answer: 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 11: What is the difference between direct and indirect containment? Answer: A direct containment contains copies of objects while indirect containments contain pointers to objects. An example of direct container in C++ is an array, which stores the object values. An indirect containment example would be a dynamic linked list (C++ also). 12: Which are the main primitive data type groups? Answer: 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 13: What is a record structure? Give some practical examples. Answer: 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. 14: How can be determined the size of a structure? Answer: It can be determined by calculating the sum of the sizes of all the primitive data types within the structure. 15: Which are the factors that need to be taken into account when choosing a specific data type for an algorithm? Answer: Relative advantages and disadvantages of different data types include: a) asymptotic operation performance - average lookup and insertion time, worst-case lookup and insertion time b) ordering preservation - allowing one to efficiently iterate over the keys in order or to efficiently locate an association whose key is nearest to a given value c) allocation behavior - the way data is organized into memory d) compactness e) persistence 16: What is a pointer variable? Answer: 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 ; 17: What is the difference between static and dynamic data types? Answer: 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. 18: Describe the referencing mechanism.

Answer: 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. ***** Arrays 19: Describe an array structure. Answer: An array consists of components which are all of the same type, called its base type; it is therefore called a homogeneous structure.

It is a random-access structure, because all components can be selected at random and are equally quickly accessible. In order to denote an individual component, the name of the entire structure is augmented by the index selecting the component. 20: What is a multidimensional array? Answer: A multidimensional array consists of two or more arrays defined by sets of array elements. Each set of array elements is an array. The first set of array elements is considered the primary array, and the second and subsequent sets of array elements are considered subarrays. 21: Give an example of practical use of a multidimensional array.