Data structures and algorithms for IT Officer

What the subject covers

Data structures are ways to organise data in memory (arrays, lists, trees, graphs, hash tables). Algorithms are step-by-step methods that work on them (searching, sorting, traversing, optimising). The exam tests whether you know how each structure behaves, how fast each algorithm is (Big-O), and whether you can trace small examples by hand.

Key topics

Complexity

• Big-O, Ω, Θ. Big-O is an upper bound, Ω a lower bound, Θ a tight bound. Common orders, from fastest-growing down: n!, 2ⁿ, n², n log n, n, log n, 1.
• Typical recurrences: T(n) = 2T(n/2) + n gives O(n log n), as in merge sort; T(n) = T(n/2) + 1 gives O(log n), as in binary search.

Linear structures

• Arrays and linked lists.
  • An array gives O(1) access by index, but inserting in the middle costs O(n).
  • A linked list inserts in O(1) once you hold the node, but access costs O(n).
  • Variants: singly, doubly and circular lists.
• Stacks and queues.
  • A stack is LIFO (push, pop). It is used for function calls, undo, and expression conversion and evaluation.
  • A queue is FIFO. Variants: circular queue, deque, priority queue.
• Expression conversion with a stack. Infix a + b * c becomes postfix a b c * +, because * binds tighter. Evaluate postfix left to right: push operands, and on each operator pop two (the right operand first, then the left: for a b − compute a − b) and push the result.
• Linear vs non-linear. Arrays, lists, stacks and queues are linear. Trees and graphs are non-linear.

Trees

• Binary tree facts.
  • At most 2ˡ nodes on level l (root = level 0).
  • At most 2ʰ⁺¹ − 1 nodes in a tree of height h.
  • With n nodes there are n − 1 edges.
• Traversals.
  • Preorder: root, left, right. Inorder: left, root, right. Postorder: left, right, root. Level order uses a queue.
  • Inorder of a BST gives the keys in sorted order.
• Binary search tree (BST). Left < node < right. Search, insert and delete are O(h): O(log n) when balanced, O(n) when skewed, for example after inserting sorted keys.
• AVL tree.
  • A self-balancing BST: each node's balance factor (left height − right height) is −1, 0 or +1.
  • Insertions are fixed with LL, RR, LR and RL rotations.
  • The fewest nodes an AVL tree of height h can have follows N(h) = N(h−1) + N(h−2) + 1, with N(0) = 1, N(1) = 2 when a single node has height 0 (so N(2) = 4, N(3) = 7, N(4) = 12).
• Heaps.
  • A complete binary tree stored in an array. In a max-heap every parent ≥ its children.
  • With 0-based indexes, the children of i are 2i + 1 and 2i + 2.
  • Insert and delete-max are O(log n); building a heap is O(n).
• B and B+ trees (see DBMS), tries (prefix search), spanning trees.

Graphs

• Representation. An adjacency matrix takes O(V²) space and gives O(1) edge lookup. An adjacency list takes O(V + E) space and suits sparse graphs.
• Traversal. BFS uses a queue and finds shortest paths in unweighted graphs; DFS uses a stack or recursion. Both are O(V + E) with adjacency lists.
• Shortest paths.
  • Dijkstra: non-negative weights only.
  • Bellman-Ford: handles negative edges and detects negative cycles.
  • Floyd-Warshall: all pairs, O(V³).
• Minimum spanning tree. Prim grows from a vertex; Kruskal adds the cheapest edges that don't form a cycle (union-find). An MST of V vertices has V − 1 edges.
• Topological sort orders the vertices of a directed acyclic graph (DAG).

Searching and sorting

All complexities in the table are O(·).

• Selection sort makes at most n − 1 swaps, the fewest among the simple in-place sorts. Merge, heap and selection sort take the same time in every case.
• Insertion sort is fast on nearly sorted data.
• Quick sort's worst case comes from bad pivots, for example an already sorted array with the first element as pivot.
• Linear search is O(n). Binary search is O(log n) and needs sorted data.

Hashing

• Basics. A hash function maps a key to a slot. The load factor α = number of stored keys ÷ number of slots.
• Collision handling.
  • Chaining keeps a list per slot.
  • Open addressing probes for another slot: linear probing (causes primary clustering), quadratic probing, or double hashing.
• Average search is O(1) when α is kept small; the worst case is O(n).

Algorithm design

• Divide and conquer: split, solve the parts, combine. Examples: merge sort, quick sort, binary search.
• Greedy: take the best local choice each step. Examples: Kruskal, Prim, Huffman coding, fractional knapsack.
• Dynamic programming: overlapping subproblems plus optimal substructure.
  • Memoization (top-down) caches the results of recursive calls so each subproblem is solved once; tabulation (bottom-up) fills a table.
  • Examples: 0/1 knapsack, longest common subsequence (O(mn)), longest increasing subsequence (O(n²) with the classic double loop, O(n log n) with binary search).
• Backtracking: N-queens, subsets.

How it is asked

These are the facts about the format from the official IBPS documents:

• Professional Knowledge in the Mains has 50 questions for 100 marks in 40 minutes (2 marks each, −0.50 for a wrong answer).
• Each question has five options.

IBPS doesn't publish past papers. Based on memory-based papers shared by candidates (unofficial) for two previous IT Officer Mains exams (January 2023 and December 2024; possibly incomplete), data-structure questions were mostly short and exact:

• Trace a small example: the inorder traversal of a BST built from a given insertion order, converting an infix expression to postfix, and the height of an AVL tree with a given number of nodes.
• Complexity and properties: which sort takes the same time in every case, which in-place sort makes the fewest swaps, the time complexity of a DP solution, and what memoization is for.
• Definitions: what a hash table's load factor means, which structure is not linear, and which method is an example of divide and conquer.

We don't give a number of questions, because IBPS publishes no weightage.

Common mistakes

• Height vs depth vs level. Check whether the question counts the root as height 0 or 1. The answer changes by one.
• "Quick sort is O(n log n)." That's only on average; its worst case is O(n²). Merge and heap sort are O(n log n) in every case.
• Stable vs in-place. Merge sort is stable but not in place; heap sort is in place but not stable.
• Binary search on unsorted data. It only works on sorted data.
• Dijkstra with negative edges. It may give wrong answers; use Bellman-Ford.
• Postfix precedence. * and / bind tighter than + and −; operators of equal precedence are processed left to right, except ^ (exponent), which is right to left: a ^ b ^ c → a b c ^ ^.
• Forgetting edge cases: an empty structure, a single node, a skewed tree.

Two-week study plan

A suggestion. Adjust it to your own pace.