Practical Problem Solving and Coding Challenges
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. Assume no duplicates.
Answer:
This is a classic binary search problem. Initialize low = 0, high = n-1. While low <= high, calculate mid. If nums[mid] == target, return mid. If nums[mid] < target, low = mid + 1. Else, high = mid - 1. Finally, return low.
Explain how to detect a cycle in a linked list and provide a high-level algorithm.
Answer:
Use Floyd's Cycle-Finding Algorithm (Tortoise and Hare). Initialize two pointers, slow and fast, both starting at the head. slow moves one step at a time, fast moves two steps. If they ever meet, a cycle exists. If fast reaches nullptr or fast->next is nullptr, there's no cycle.
How would you reverse a string in-place in C++?
Answer:
Use two pointers, left starting at the beginning and right at the end of the string. Swap characters at left and right, then increment left and decrement right. Continue until left crosses right. This modifies the string directly without extra space.
Answer:
std::vector stores elements contiguously in memory, allowing for O(1) random access and cache efficiency. Insertions/deletions in the middle are O(N). std::list is a doubly-linked list, storing elements non-contiguously. Insertions/deletions are O(1) once the iterator is found, but random access is O(N) due to traversal.
Implement a function to check if a given string is a palindrome, ignoring non-alphanumeric characters and case.
Answer:
Use two pointers, left and right. Move left forward and right backward, skipping non-alphanumeric characters. Convert valid characters to lowercase. Compare characters at left and right. If they don't match, it's not a palindrome. Continue until left >= right.
Given an array of integers, find the maximum sum of a contiguous subarray.
Answer:
This is Kadane's Algorithm. Maintain current_max and global_max. Iterate through the array: current_max = max(num, current_max + num). Update global_max = max(global_max, current_max) in each iteration. Initialize both to the first element or negative infinity.
Explain how to find the 'k'th smallest element in an unsorted array efficiently.
Answer:
The most efficient approach is Quickselect, which is a variation of Quicksort. It has an average time complexity of O(N). Alternatively, using a min-heap (priority queue) and extracting k elements would be O(N log K), or sorting the array first would be O(N log N).
How would you implement a basic LRU (Least Recently Used) cache?
Answer:
Use a std::list (or std::deque) to maintain the order of usage and a std::unordered_map to store key-value pairs along with iterators to their corresponding list nodes. On access, move the item to the front of the list. On insertion when full, remove the item at the back of the list.
Given two sorted arrays, merge them into a single sorted array.
Answer:
Use two pointers, one for each array, starting from their beginnings. Compare the elements pointed to and add the smaller one to the result array, advancing its pointer. If one array is exhausted, append the remaining elements of the other. This is O(M+N) time and O(M+N) space.
Describe a method to find all permutations of a given string.
Answer:
This can be solved using recursion and backtracking. For each character, swap it with every character to its right (including itself) and recursively find permutations for the remaining substring. Use a std::set or check for duplicates if the input string has repeated characters.