# Common Questions ### Q1: Name some characteristics of Array Data Structure ☆ **Topics:** Arrays Data Structures #### Answer: Arrays are: ``` Finite (fixed-size) - An array is finite because it contains only limited number of elements. Order -All the elements are stored one by one , in contiguous location of computer memory in a linear order and fashion Homogenous - All the elements of an array are of same data types only and hence it is termed as collection of homogenous ``` ### Q2: Define Stack ☆ **Topics:** Stacks Data Structures #### Answer: A **Stack** is a container of objects that are inserted and removed according to the last-in first-out ( **LIFO** ) principle. In the pushdown stacks only two operations are allowed: push the item into the stack, and pop the item out of the stack. There are basically three operations that can be performed on stacks. They are: ``` 1. inserting an item into a stack ( push ). 2. deleting an item from the stack ( pop ). 3. displaying the contents of the stack ( peek or top ). ``` A stack is a limited access data structure - elements can be added and removed from the stack only at the top. push adds an item to the top of the stack, pop removes the item from the top. A helpful analogy is to think of a stack of books; you can remove only the top book, also you can add a new book on the top. ### Q3: Explain why Stack is a recursive data structure ☆ **Topics:** Stacks Data Structures #### Answer: A **stack** is a **recursive** data structure, so it's: ``` a stack is either empty or it consists of a top and the rest which is a stack by itself; ``` ### Q4: Define Linked List ☆ **Topics:** Linked Lists Data Structures #### Answer: A **linked list** is a linear data structure where each element is a separate object. Each element (we will call it a **node** ) of a list is comprising of two items - the **data** and a **reference (pointer)** to the next node. The last node has a reference to **null**. The entry point into a linked list is called the **head** of the list. It should be noted that **head is not a separate node, but the reference to the first node. If the list is empty then the head is a null** reference. ### Q5: What is Queue? ☆ **Topics:** Queues Data Structures #### Answer: **A queue is a container of objects (a linear collection) that are inserted and removed according to the first-in** first-out (FIFO) principle. The process to add an element into queue is called **Enqueue** and the process of removal of an element from queue is called **Dequeue**. ### Q6: What is Hash Table? ☆ **Topics:** Hash Tables Data Structures #### Answer: A **hash table** (hash map) is a data structure that implements an **associative** array abstract data type, a **structure** that can **map keys to values**. Hash tables implement an associative array, which is indexed by arbitrary objects (keys). A hash table uses a **hash function** to compute an **index** , also called a **hash value** , into an **array of buckets** or slots, from which the desired **value** can be found. ### Q7: What is Heap? ☆ **Topics:** Heaps and Maps Data Structures #### Answer: A **Heap** is a special Tree-based data structure which is an almost complete tree that satisfies the heap property: ``` in a max heap , for any given node C, if P is a parent node of C, then the key (the value) of P is greater than or equal to the key of C. In a min heap , the key of P is less than or equal to the key of C. The node at the "top" of the heap (with no parents) is called the root node. ``` A common implementation of a heap is the binary heap, in which the tree is a **binary tree.** ### Q8: What is Priority Queue? ☆ **Topics:** Heaps and Maps Data Structures #### Answer: A **priority queue** is a data structure that stores **priorities** (comparable values) and perhaps associated information. A **priority queue** is different from a "normal" queue, because instead of being a "first-in-first-out" data structure, values come out in order by **priority**. Think of a priority queue as a kind of bag that holds priorities. You can put one in, and you can take out the current highest priority. ### Q9: Define Tree Data Structure ☆ **Topics:** Trees Data Structures #### Answer: **Trees are well-known as a non-linear data structure. They don’t store data in a linear way. They organize data** **hierarchically.** A **tree** is a collection of entities called **nodes**. Nodes are connected by **edges**. Each node contains a **value** or **data** or **key** , and it may or may not have a **child** node. The first node of the tree is called the **root**. **Leaves** are the last nodes on a tree. They are nodes without children. ### Q10: Define Binary Tree ☆ **Topics:** Binary Tree Trees Data Structures #### Answer: A normal tree has no restrictions on the number of children each node can have. A **binary tree** is made of nodes, where each node contains a "left" pointer, a "right" pointer, and a data element. There are three different types of binary trees: ``` Full binary tree : Every node other than leaf nodes has 2 child nodes. Complete binary tree : All levels are filled except possibly the last one, and all nodes are filled in as far left as possible. Perfect binary tree : All nodes have two children and all leaves are at the same level. ``` ### Q11: What is Trie? ☆ **Topics:** Trie Data Structures #### Answer: **Trie (also called \*\*digital tree \*\*or prefix tree ) is a tree-based data structure, which is used for efficient retrieval** of a key in a large data-set of strings. Unlike a binary search tree, no node in the tree stores the key associated with that node; instead, its position in the tree defines the key with which it is associated; i.e., **the value of the key is distributed across the structure**. All the descendants of a node have a common prefix of the string associated with that node, and the root is associated with the empty string. Each complete English word has an arbitrary integer value associated with it (see image). ### Q12: What is String in Data Structures? ☆ **Topics:** Strings Data Structures #### Answer: A **string** is generally considered as a **data type** and is often implemented as an **array data structure** of bytes (or words) that stores a sequence of elements, typically characters, using some character encoding. String may also denote more general arrays or other sequence (or list) data types and structures. ### Q13: What is a Graph? ☆ **Topics:** Graph Theory Data Structures #### Answer: A **graph** is a common data structure that consists of a finite set of **nodes** (or **vertices** ) and a set of **edges** connecting them. A pair (x,y) is referred to as an edge, which communicates that the **x vertex** connects to the **y vertex**. Graphs are used to solve real-life problems that involve representation of the problem space as a **network**. Examples of networks include telephone networks, circuit networks, social networks (like LinkedIn, Facebook etc.). ### Q14: What are Dynamic Arrays? ☆☆ **Topics:** Arrays Data Structures #### Answer: **A dynamic array is an array with a big improvement: automatic resizing.** **One limitation of arrays is that they're fixed size, meaning you need to specify the number of elements your** array will hold ahead of time. A dynamic array expands as you add more elements. So you don't need to determine the size ahead of time. ### Q15: Why and when should I use Stack or Queue data structures ### instead of Arrays/Lists? ☆☆ **Topics:** Queues Stacks Data Structures #### Answer: **Because they help manage your data in more a particular way than arrays and lists. It means that when you're** debugging a problem, you won't have to wonder if someone randomly inserted an element into the middle of your list, messing up some invariants. **Arrays and lists are random access. They are very flexible and also easily corruptible. If you want to manage your** data as FIFO or LIFO it's best to use those, already implemented, collections. More practically you should: ``` Use a queue when you want to get things out in the order that you put them in (FIFO) Use a stack when you want to get things out in the reverse order than you put them in (LIFO) Use a list when you want to get anything out, regardless of when you put them in (and when you don't want them to automatically be removed). ``` ### Q16: What are some types of Linked List? ☆☆ **Topics:** Linked Lists Data Structures #### Answer: ``` A singly linked list ``` ``` A doubly linked list is a list that has two references, one to the next node and another to previous node. ``` ``` A multiply linked list - each node contains two or more link fields, each field being used to connect the same set of data records in a different order of same set(e.g., by name, by department, by date of birth, etc.). A circular linked list - where last node of the list points back to the first node (or the head) of the list. ``` ### Q17: Name some disadvantages of Linked Lists? ☆☆ **Topics:** Linked Lists Data Structures #### Answer: Few disadvantages of linked lists are : ``` They use more memory than arrays because of the storage used by their pointers. Difficulties arise in linked lists when it comes to reverse traversing. For instance, singly linked lists are cumbersome to navigate backwards and while doubly linked lists are somewhat easier to read, memory is wasted in allocating space for a back-pointer. Nodes in a linked list must be read in order from the beginning as linked lists are inherently sequential access. Random access has linear time. Nodes are stored incontiguously (no or poor cache locality), greatly increasing the time required to access individual elements within the list, especially with a CPU cache. If the link to list's node is accidentally destroyed then the chances of data loss after the destruction point is huge. Data recovery is not possible. Search is linear versus logarithmic for sorted arrays and binary search trees. Different amount of time is required to access each element. Not easy to sort the elements stored in the linear linked list. ``` ### Q18: What is Complexity Analysis of Queue operations? ☆☆ **Topics:** Queues Data Structures #### Answer: ``` Queues offer random access to their contents by shifting the first element off the front of the queue. You have to do this repeatedly to access an arbitrary element somewhere in the queue. Therefore, access is O(n). Searching for a given value in the queue requires iterating until you find it. So search is O(n). Inserting into a queue, by definition, can only happen at the back of the queue, similar to someone getting in line for a delicious Double-Double burger at In 'n Out. Assuming an efficient queue implementation, queue insertion is O( 1 ). Deleting from a queue happens at the front of the queue. Assuming an efficient queue implementation, queue deletion is `O( 1 ). ``` ### Q19: What are some types of Queue? ☆☆ **Topics:** Queues Data Structures #### Answer: Queue can be classified into following types: ``` Simple Queue - is a linear data structure in which removal of elements is done in the same order they were inserted i.e., the element will be removed first which is inserted first. ``` **Circular Queue** - is a linear data structure in which the operations are performed based on FIFO (First In First Out) principle and the last position is connected back to the first position to make a circle. It is also called **Ring Buffer**. Circular queue avoids the wastage of space in a regular queue implementation using arrays. **Priority Queue** - is a type of queue where each element has a priority value and the deletion of the elements is depended upon the priority value In case of **max-priority queue** , the element will be deleted first which has the largest priority value In case of **min-priority queue** the element will be deleted first which has the minimum priority value. **De-queue (Double ended queue)** - allows insertion and deletion from both the ends i.e. elements can be added or removed from rear as well as front end. ``` Input restricted deque - In input restricted double ended queue, the insertion operation is performed at only one end and deletion operation is performed at both the ends. ``` ``` Output restricted deque - In output restricted double ended queue, the deletion operation is performed at only one end and insertion operation is performed at both the ends. ``` ### Q20: What is the space complexity of a Hash Table? ☆☆ **Topics:** Hash Tables Data Structures #### Answer: The space complexity of a datastructure indicates how much space it occupies in relation to the amount of elements it holds. For example a space complexity of O(1) would mean that the datastructure alway consumes constant space no matter how many elements you put in there. O(n) would mean that the space consumption grows linearly with the amount of elements in it. A **hashtable** typically has a space complexity of O(n). --- # Agent Instructions: Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://bryan-guner.gitbook.io/my-docs/job-search/interviewing/common-questions.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.