Interview Questions

What is Big O notation?

Big O notation describes how an algorithm's runtime or memory usage grows as the size of the input increases. It focuses on scalability rather than exact execution time. Common complexities include O(1), O(log n), O(n), O(n log n), and O(n²).

Why is Big O important?

It helps engineers predict how code will perform as data grows. An algorithm that works well for 100 items may become unusable for 10 million items if its complexity scales poorly.

What is O(1)?

Constant time complexity. The operation takes the same amount of time regardless of input size. Example: array[5]

What is O(log n)?

Logarithmic time complexity. The problem size is reduced by a constant factor in each step.

Example: binary search

What is O(n)?

Linear time complexity. Runtime increases proportionally to input size.

Example: looping through an array

What is O(n²)?

Quadratic time complexity. Runtime grows with the square of the input.

Example: nested loops

What is binary search?

A search algorithm that repeatedly divides a sorted array in half until the target is found.

Time complexity: O(log n)

What condition is required for binary search?

The collection must already be sorted.

Why is binary search faster than linear search?

Binary search eliminates half the remaining data during each step, whereas linear search checks elements one by one.

What is bubble sort?

A simple sorting algorithm that repeatedly swaps adjacent elements if they are in the wrong order.

Complexity: O(n^2) in worst case

What is merge sort?

A divide-and-conquer algorithm that recursively splits data and merges sorted halves.

Complexity: O(n log n)

What is quick sort?

A divide-and-conquer algorithm that partitions data around a pivot.

Average: O(n log n)

Worst Case: O(n²)

What is an array?

A collection of elements stored in contiguous memory locations.

Advantages:

• Fast indexing

Disadvantages:

• Expensive insertions and deletions

What is the time complexity of accessing an array element?

O(1)

What is a linked list?

A sequence of nodes where each node stores data and a reference to the next node.

Array vs linked list

Array:

• O(1) access

• Fixed contiguous memory

Linked List:

• O(n) access

• Dynamic size

• Faster insertions

What is a stack?

A last in, first out (LIFO) data structure.

Example: undo functionality

What operations does a stack support?

• Push

• Pop

• Peek

What is a queue?

A First In, First Out (FIFO) data structure.

Example: print queue

What operations does a queue support?

• Enqueue

• Dequeue

• Peek

What is a hash table?

A data structure that stores key-value pairs using a hash function.

What is a hash function?

A function that converts a key into an index or bucket location.