Question 1

What is the time complexity of inserting an element at the beginning of a singly linked list?

Accepted Answer

O(1). Inserting at the head of a linked list is O(1) — you create a new node and update the head pointer. No traversal needed, unlike inserting at a specific position which is O(n).

Question 2

What is a hash table?

Accepted Answer

A data structure that maps keys to values using a hash function for O(1) average-case lookup. A hash table applies a hash function to a key to compute an index into an array. Average-case O(1) for insert, delete, and search. Worst case O(n) due to collisions.

Question 3

What is the average-case time complexity of searching in a Binary Search Tree (BST)?

Accepted Answer

O(log n). In a balanced BST, each comparison eliminates half the remaining nodes — O(log n). But in a worst-case skewed BST (like a sorted insertion), it degrades to O(n).

Question 4

What is the core idea of dynamic programming?

Accepted Answer

Breaking a problem into overlapping subproblems, solving each once, and storing results to avoid recomputation. Dynamic programming = memoization (top-down) or tabulation (bottom-up). Classic examples: Fibonacci, 0/1 Knapsack, Longest Common Subsequence. Key insight: overlapping subproblems + optimal substructure.

Question 5

What is the average-case time complexity of QuickSort?

Accepted Answer

O(n log n). QuickSort average case is O(n log n). It partitions around a pivot recursively. Worst case is O(n²) with a bad pivot (e.g., always smallest/largest element on a sorted array).

Data Structures & Algorithms — Fresher Interview Questions

More Fresher Topics

Data Structures & Algorithms at Other Levels