DSA Related interview question answers with example

1. What is a Data Structure?

A data structure is a specialized way of organizing and storing data in a computer so that it can be accessed and modified efficiently. Common types include arrays, linked lists, stacks, queues, trees, graphs, hash tables, etc.

2. Explain Arrays with example.

An array is a collection of elements identified by index, stored in contiguous memory locations. Access is O(1), but insertion/deletion (except at the end) is O(n).

Example:

java

int[] arr = {1, 2, 3, 4, 5}; System.out.println(arr[2]); // Outputs 3

3. What is a Linked List? Types?

A linked list is a linear data structure where each element (node) points to the next, allowing efficient insertion and deletion. Types: singly, doubly, and circular linked lists.

Example node:

java

class Node { int data; Node next; Node(int d) { data = d; next = null; } }

4. Difference between Stack and Queue?

• Stack: LIFO (Last In, First Out). Example: Undo functionality.

• Queue: FIFO (First In, First Out). Example: Task scheduling.

5. Implement a stack using array in Java (Simple Example)

java

class Stack { int[] arr; int top; Stack(int size) { arr = new int[size]; top = -1; } void push(int val) { if(top == arr.length - 1) throw new RuntimeException("Stack Overflow"); arr[++top] = val; } int pop() { if(top == -1) throw new RuntimeException("Stack Underflow"); return arr[top--]; } }

6. What is a Binary Tree?

A tree data structure where each node has at most two children, called left and right.

7. Explain Binary Search Tree (BST).

BST is a binary tree where left child nodes contain values less than the parent, and right child nodes contain values greater than the parent. Enables O(log n) average search time.

8. How to traverse a Binary Tree?

Common methods:

• Inorder (Left, Root, Right)

• Preorder (Root, Left, Right)

• Postorder (Left, Right, Root)

• Level order traversal (Breadth First)

Example of inorder traversal:

java

void inorder(Node root) { if (root != null) { inorder(root.left); System.out.print(root.data + " "); inorder(root.right); } }

9. What is a Hash Table? How does it work?

Hash table stores key-value pairs; it uses a hash function to compute an index where the value is stored. Enables average O(1) access time.

10. Explain the concept of Recursion with example.

Recursion is a function calling itself to solve smaller instances of a problem.

Example: factorial

java

int factorial(int n) { if (n <= 1) return 1; else return n * factorial(n - 1); }

11. What is Dynamic Programming? When to use?

Dynamic programming solves problems by breaking them into simpler overlapping subproblems and storing their results to avoid recomputation. Use when problem exhibits optimal substructure and overlapping subproblems, e.g., Fibonacci series, knapsack problem.

12. Explain Sorting Algorithms (QuickSort & MergeSort)

• QuickSort: Divides array into partitions based on a pivot, sort each side recursively. Average O(n log n).

• MergeSort: Divides array into halves, sorts each half, then merges sorted halves. O(n log n).

13. What is a Graph? Types?

A graph is a set of nodes (vertices) connected by edges. Types: directed, undirected; weighted, unweighted.

14. How to find shortest path in a graph?

Use algorithms like:

• Dijkstra’s (for graphs with non-negative weights)

• Bellman-Ford (handles negative weights)

• BFS (for unweighted graphs)

15. Explain the concept of Big-O notation.

Represents time or space complexity of an algorithm in terms of input size n; helps analyze scalability (e.g., O(1), O(n), O(n²)).

16. Sample Problem: Find first non-repeating character in string

java

public char firstNonRepeatingChar(String s) { int[] counts = new int[256]; for(char c : s.toCharArray()) counts[c]++; for(char c : s.toCharArray()) if(counts[c] == 1) return c; return '_'; }

17. Sample Problem: Reverse a Linked List

java

Node reverseList(Node head) { Node prev = null, curr = head; while (curr != null) { Node next = curr.next; curr.next = prev; prev = curr; curr = next; } return prev; }

18. Sample Problem: Detect Cycle in Linked List

Using Floyd’s Cycle Detection Algorithm:

java

boolean hasCycle(Node head) { Node slow = head, fast = head; while (fast != null && fast.next != null) { slow = slow.next; fast = fast.next.next; if (slow == fast) return true; } return false; }

19. Sample Problem: Merge Two Sorted Arrays

java

int[] merge(int[] a, int[] b) { int[] result = new int[a.length + b.length]; int i=0, j=0, k=0; while(i<a.length && j<b.length) { if(a[i] <= b[j]) result[k++] = a[i++]; else result[k++] = b[j++]; } while(i<a.length) result[k++] = a[i++]; while(j<b.length) result[k++] = b[j++]; return result; }

20. Sample Problem: Maximum Subarray Sum (Kadane’s Algorithm)

java

int maxSubArray(int[] nums) { int maxCurrent = nums[0], maxGlobal = nums[0]; for (int i=1; i < nums.length; i++) { maxCurrent = Math.max(nums[i], maxCurrent + nums[i]); if (maxCurrent > maxGlobal) maxGlobal = maxCurrent; } return maxGlobal; }

These questions and answers cover foundational and advanced data structures and algorithm topics frequently encountered during interviews at top tech companies like Google. Including code examples demonstrates practical understanding and readiness for coding rounds.