Solve 15 common interview problems

Below are fifteen independent coding problems commonly discussed in software engineering interviews. For each one, write an efficient algorithm and be prepared to explain the time and space complexity, as interviewers may ask for optimizations or follow-up improvements.

1. Find a target-sum pair. Given an integer array nums and an integer target, return the indices of two distinct elements whose values add up to target. You may assume exactly one valid answer exists, and you may return the indices in any order.

2. Count contiguous segments with sum k. Given an integer array nums and an integer k, return the number of contiguous subarrays whose sum is exactly k.

3. Build a product array without division. Given an integer array nums, return an array answer where answer[i] is the product of all elements of nums except nums[i]. Do not use division, and aim for linear time.

4. Find the longest substring with all unique characters. Given a string s, return the length of the longest contiguous substring that contains no repeated characters.

5. Find the shortest covering substring. Given strings s and t, return the smallest substring of s that contains every character of t, including duplicates. If no such substring exists, return an empty string.

6. Expand a nested repetition encoding. Given a string encoded with rules such as k[encoded_part], where the substring inside brackets should be repeated k times, return the fully decoded string. For example, 3[a2[c]] becomes accaccacc.

7. Count connected land regions in a grid. Given a 2D grid of characters where '1' represents land and '0' represents water, return the number of islands. Cells are connected horizontally and vertically.

8. Find the shortest word transformation length. Given a beginWord, an endWord, and a dictionary wordList, transform the begin word into the end word by changing exactly one letter at a time. Every intermediate word must exist in wordList. Return the length of the shortest valid transformation sequence, or 0 if no such sequence exists.

9. Determine whether all courses can be completed. You are given numCourses labeled from 0 to numCourses - 1 and a list of prerequisite pairs [a, b], meaning course b must be taken before course a. Return true if it is possible to finish all courses, otherwise return false.

10. Traverse a binary tree by levels. Given the root of a binary tree, return the node values level by level from top to bottom, where each level is returned as a separate list.

11. Find the nearest shared ancestor in a binary tree. Given the root of a binary tree and two nodes p and q, return their lowest common ancestor. The lowest common ancestor is the deepest node that has both p and q as descendants, where a node may be a descendant of itself.

12. Merge multiple sorted linked lists. You are given an array of k singly linked lists, each sorted in ascending order. Merge them into one sorted linked list and return its head.

13. Deep-copy a linked list with arbitrary cross-links. Each node in a linked list has val, next, and random pointers, where random may point to any node in the list or be null. Return a deep copy of the entire list.

14. Rotate a square matrix in place. Given an n x n matrix, rotate it 90 degrees clockwise without using another matrix for the final result.

15. Compute the longest increasing subsequence length. Given an integer array nums, return the length of the longest strictly increasing subsequence. Aim for an algorithm better than O(n^2) if possible.