Data Structures and Algorithms Interview Questions for Freshers

An array has fixed-size, contiguous memory and fast access by index. A linked list has nodes joined by pointers, so inserting and removing is easy but reaching an item means walking the list.

A stack is last in, first out, used for undo and function calls. A queue is first in, first out, used for scheduling and breadth-first search.

How the running time grows with the input size, written in Big-O. Array access is O(1), binary search O(log n), a single loop O(n), good sorts O(n log n) and nested loops O(n squared).

On a sorted list, check the middle item and discard the half that cannot hold the target, repeating until found. It takes O(log n) time and needs the data sorted.

Use two pointers, one moving one step and the other two steps. If they ever meet there is a cycle, and if the fast one reaches the end there is none. It uses constant extra memory.

A function that calls itself on a smaller version of the problem. The base case stops the calls, and without it the function runs until the stack overflows.

BFS visits nodes level by level using a queue and finds the shortest path in an unweighted graph. DFS goes deep first using a stack or recursion and is useful for paths, cycles and ordering.

Two keys can map to the same slot. Chaining keeps a list in each slot, and open addressing looks for another free slot. A good hash function and resizing keep lookups close to constant time.

Merge sort is always O(n log n) and stable but needs extra memory. Quick sort is O(n log n) on average with little extra memory, but its worst case is O(n squared) with bad pivots.

A tree where each node's left side holds smaller values and its right side larger ones. Searching, inserting and deleting take O(log n) when it is balanced, but a skewed tree degrades to O(n).