Conceptual Problems on Linked Lists, Stacks, and Queues with Big O Constraints Design solutions conceptually (no code) while adhering to specific time

Detect Cycle in Linked List

Use Floyd’s Tortoise and Hare algorithm with two pointers to determine if a cycle exists in O(n) time and O(1) space.

Sort Stack with One Additional Stack

Sort a stack using a temporary stack in O(n²) time and O(n) space.

Reverse Queue Using Stack

Reverse the order of elements in a queue by transferring elements to a stack and back in O(n) time and O(n) space.

Find Middle Element in Linked List

Use two pointers to identify the middle node in O(n) time and O(1) space.

Check Balanced Parentheses

Use a stack to verify if parentheses are balanced in O(n) time and O(n) space.

Implement Queue Using Two Stacks

Design a queue using two stacks to achieve O(1) amortized time for enqueue and dequeue operations.

Remove Nth Node from End of Linked List

Utilize two pointers to remove the Nth node from the end in O(n) time and O(1) space.

Design Min Stack

Implement a stack supporting push, pop, and getMin in O(1) time per operation, using two stacks.

Generate Binary Numbers using Queue

Create binary numbers from 1 to N using a queue in O(n) time and O(n) space.

Check Palindrome in Linked List

Determine if a linked list is a palindrome by reversing the second half and comparing in O(n) time and O(1) space.

Evaluate Postfix Expression

Use a stack to evaluate a postfix expression in O(n) time and O(n) space.

Reverse First K Elements in Queue

Reverse the first K elements of a queue using a stack in O(n) time and O(K) space.

Flatten a Multilevel Linked List

Merge child nodes with the main list in O(n) time and O(1) space.

Design Browser History using Stacks

Simulate browser navigation with two stacks for visited pages and forward operations in O(1) time.

Merge Two Sorted Lists

Merge two sorted linked lists using a dummy node in O(n + m) time and O(1) space.

Validate Stack Sequences

Check if push and pop sequences are valid using a simulated stack in O(n) time and O(n) space.

Circular Buffer Implementation

Design a circular queue with a fixed size that supports O(1) enqueue and dequeue operations.

Remove Duplicates from Sorted List

Eliminate duplicates in a sorted linked list in O(n) time and O(1) space.

Largest Rectangle in Histogram

Find the maximum rectangle area in a histogram using a stack in O(n) time and O(n) space.

Interleave First and Second Halves of Queue

Split and interleave a queue’s halves in O(n) time and O(n) space.

Rotate List by K Places

Rotate a linked list to the right by K places in O(n) time and O(1) space.

Simplify File Path

Convert an absolute file path to canonical form using a stack in O(n) time and O(n) space.

Design Recent Calls Counter

Count requests in the last 3000 milliseconds using a queue with O(1) amortized time and O(n) space.