Placement Papers - MCQ Practice Questions

Understanding:

We need to determine the time complexity of reversing a singly linked list with $n$ nodes using an iterative approach.

Formula:

For any algorithm that visits each element exactly once:

Step 1: Describe the iterative reversal

The iterative approach uses three pointers — `prev`, `curr`, and `next`. Starting from the head, we traverse the list and reverse each link one by one:

Step 2: Count operations

Each of the $n$ nodes is visited exactly once, and a constant number of pointer operations are performed per node. Therefore the total work is proportional to $n$:

Step 3: Verify space complexity

Only three pointers are used regardless of $n$, so space complexity is $O(1)$.

Answer:

Reversing a linked list iteratively visits each node once, giving a time complexity of $O(n)$.

Quick Tip:

The recursive reversal also runs in $O(n)$ time but uses $O(n)$ stack space — the iterative version is preferred in memory-constrained settings.

Understanding:

This question asks about the definition and purpose of garbage collection in managed languages such as C# (.NET) and Java.

Step 1: Define garbage collection

Garbage collection (GC) is an automatic memory management feature. The runtime periodically identifies objects in the heap that are no longer reachable (i.e., no live reference in the program points to them) and reclaims that memory without requiring the programmer to explicitly free it.

Step 2: Eliminate incorrect options

Disk compression is an OS-level operation unrelated to GC. Removing dead code is a compiler optimization called dead code elimination. Manual `free()` calls describe explicit memory management as in C, which is the opposite of garbage collection.

Step 3: Confirm the correct answer

Garbage collection is specifically about automatic identification and reclamation of unreachable heap memory, which matches the description in option B.

Answer:

Garbage collection automatically identifies and frees heap memory that is no longer reachable by any live reference in the program.

Quick Tip:

C# uses a generational garbage collector (Gen 0, Gen 1, Gen 2) — knowing this detail can impress interviewers at Microsoft.

Understanding:

This question tests knowledge of Python's mutable default argument behavior.

Step 1: Identify the trap

In Python, default argument values are evaluated once when the function is defined, not each time the function is called. Because `lst=[]` uses a mutable list as the default, that same list object is reused across all calls where `lst` is not explicitly provided.

Step 2: Trace the calls

Step 3: State the output

The three print statements produce:

Answer:

Because the default list is shared across calls, each invocation appends to the same list.

Quick Tip:

To avoid this, use `def foo(x, lst=None): if lst is None: lst = []` — a common Python best practice and a frequent Microsoft interview question.

Understanding:

This question asks about the node visiting order in an in-order traversal of a binary tree.

Step 1: Recall the three standard traversals

The three depth-first traversals of a binary tree are:

Step 2: Identify in-order

In-order traversal follows the sequence: visit the entire left subtree first, then visit the root node, then visit the entire right subtree. For a Binary Search Tree (BST), in-order traversal produces nodes in sorted ascending order.

Step 3: Confirm

The sequence Left → Root → Right uniquely defines in-order traversal.

Answer:

In-order traversal visits nodes in the order: Left subtree, Root, Right subtree.

Quick Tip:

A quick memory aid — "in-order" produces in-sequence (sorted) output for a BST, which is its most useful property in interview problems.

Understanding:

We need the worst-case time complexity of searching in a balanced BST.

Formula:

The height of a balanced BST with $n$ nodes is:

Since search traverses at most one path from root to a leaf:

Step 1: Analyze the search process

At each node, the search compares the target key with the current node's value and eliminates half the remaining tree (left or right subtree). This halving continues until the key is found or a null pointer is reached.

Step 2: Count the comparisons

In a balanced BST, the height is $\lfloor {\log }_{2}n\rfloor$. The maximum number of comparisons equals the height:

Step 3: Distinguish from unbalanced BST

An unbalanced BST can degrade to a linear chain, giving $O(n)$ worst-case. The question specifies a balanced BST, so $O(\log n)$ applies.

Answer:

Searching in a balanced BST takes logarithmic time in the worst case.

Quick Tip:

AVL trees and Red-Black trees (used in C++ STL's `std::map`) guarantee $O(\log n)$ height by auto-balancing after insertions and deletions.

Understanding:

This question asks about a specific SOLID design principle related to inheritance and substitutability.

Step 1: Review the SOLID principles

The five SOLID principles are:

Step 2: Match the description

The question describes exactly the Liskov Substitution Principle (LSP), introduced by Barbara Liskov. It states: if S is a subtype of T, then objects of type T may be replaced with objects of type S without breaking the program.

Step 3: Eliminate distractors

Open/Closed is about extension vs modification. Interface Segregation is about interface granularity. Dependency Inversion is about abstraction layers. None of these match the substitutability definition in the question.

Answer:

The principle described is the Liskov Substitution Principle.

Quick Tip:

A classic LSP violation: a `Square` class inheriting from `Rectangle` and overriding `setWidth`/`setHeight` independently breaks the expected invariant that width and height are independent.

Understanding:

We need the time to transfer a 1 GiB file over a 100 Mbps link.

Formula:

Step 1: Convert file size to bits

Step 2: Compute $2^{33}$

Step 3: Divide by bandwidth

Answer:

The file transfer takes approximately 85.9 seconds.

Quick Tip:

Remember that $2^{10}=1024\approx 10^3$, so $2^{30}\approx 10^9$. This approximation is useful for quick mental calculations in networking problems.

Understanding:

We need to identify the data structure combination that supports both get and put operations in $O(1)$ time for an LRU cache.

Step 1: Understand LRU requirements

An LRU cache must:

1. Retrieve a value by key in $O(1)$ time.

2. Insert a new key-value pair in $O(1)$ time.

3. Evict the least recently used item in $O(1)$ time.

4. Update the recency order when an item is accessed.

Step 2: Analyze the correct combination

A Hash Map provides $O(1)$ key-to-node lookup. A Doubly Linked List maintains the usage order — the most recently used item sits at the front (head) and the least recently used at the back (tail). When an item is accessed, its node is moved to the front in $O(1)$ time (since we have a direct pointer from the hash map). When the cache is full, the tail node is evicted in $O(1)$ time.

Step 3: Reject other options

Answer:

The combination of a Doubly Linked List and Hash Map achieves $O(1)$ for both get and put in an LRU cache.

Quick Tip:

This is one of Microsoft's most frequently asked design questions — in Python, `collections.OrderedDict` implements exactly this combination under the hood.