Coding problems

Question 1

Find the Maximum Product of Two Integers in an Array

Answer 1

[Arrays]
Iterate through the array and keep track of the maximum and second maximum, as well as the minimum and second minimum numbers. The maximum product will be either max1 * max2 or min1 * min2.

Question 2

Rotate an Array (k steps)

Answer 2

[Arrays]
There are various ways to do this, but one method is to reverse the entire array, then reverse the first k elements, and finally reverse the last n-k elements, where k is the number of rotations and n is the length of the array.

Question 3

Maximum Subarray Sum - “Kadane’s Algorithm”

Answer 3

[Arrays]
Initialize two variables, max_current and max_global. Iterate through the array, updating max_current to be the maximum of the current element and the sum of max_current and the current element. Update max_global whenever max_current is greater than max_global.

Question 4

Remove Duplicates from Sorted Array

Answer 4

[Arrays]
Use two pointers. One pointer iterates through the array, while the other points to the location where the next unique element should go. Swap elements as necessary.

Question 5

Move All Zeros to the End

Answer 5

[Arrays]
Use a pointer to keep track of the last non-zero element’s index. Iterate through the array and swap the current non-zero element with the zero after last non-zero element.

Question 6

Two Sum - one array and target, return indices of the two numbers such that they add up to target.

Answer 6

[Arrays]
Use a hash map to store visited numbers and their indices. For each element, check if (target - element) exists in the hash map.

Question 7

Find the “Kth” Max/Min Element of an Array

Answer 7

[Arrays]
Use QuickSelect, a variation of the QuickSort algorithm, to find the Kth smallest/largest element in expected O(n) time.

Question 8

Merge Two Sorted Arrays

Answer 8

[Arrays]
Use two pointers, one for each array. Compare the current elements pointed by the two pointers and put the smaller one into the result array, then move the pointer of the smaller element.

Question 9

Intersection of Two Arrays

Answer 9

[Arrays]
Use two sets to hold the unique elements of each array. Take the intersection of the sets.

Question 10

Longest Consecutive Sequence

Answer 10

[Arrays]
Put all elements in a hash set for quick look-up. Then, iterate through the array. For each number n, first check if this is the first number of subsequence (by checking for n - 1), and then look for consecutive numbers n+1, n+2, … in the set, keeping track of the longest sequence.

Question 11

Find the Majority Element
Given an array of integers, find the element that appears more than n/2 times.

Answer 11

(Boyer-Moore Voting Algorithm)
Initialize a candidate and a counter. Iterate through the array, updating the counter if the element is the same +1 or not -1. If the counter goes below 0, then change the candidate.
Verify the candidate by counting its occurrences in a second pass.

Question 12

Product of Array Except Self
Compute an output array such that output[i] is equal to the product of all elements in the array except arr[i]

Answer 12

First, traverse the array from left-to-right, storing the product of all numbers to the left of each index. Do a second right-to-left traversal to calculate the product of all numbers to the right, and then multiply the two.

Question 13

Search in Rotated Sorted Array
An array is sorted and then rotated. Find a target value in it.

Answer 13

Use binary search with added conditions to identify which half of the array is still sorted after the rotation. Depending on the sorted half, decide whether to adjust low or high pointers.

Question 14

Three Sum
Find all unique triplets in the array that sum up to a specific target.

Answer 14

First, sort the array. Then, for each element, use a two-pointer technique to find pairs that sum up to the negation of the current element.

Question 15

Spiral Order Matrix
Given a matrix, return all elements in spiral order.

Answer 15

Keep track of boundaries (top, bottom, left, right), and iterate through the matrix updating these boundaries as you collect elements in spiral order.

Question 16

Jump Game
Given an array of non-negative integers, you are initially positioned at the first index. Each element in the array represents your maximum jump length from that position. Determine if you can reach the last index.

Answer 16

Iterate through the array while keeping track of the farthest index you can reach. If you ever reach a point that is beyond the farthest reachable index, return false.

Question 17

Subarray Sum Equals K
Find the number of continuous subarrays whose sum equals k.

Answer 17

Use a hash map to store the counts of prefix sums. As you iterate through the array, update the current sum and check if current_sum - k exists in the hash map.

Question 18

Kth Smallest Element in a Sorted Matrix (MxN)
Find the kth smallest element in a row-wise and column-wise sorted matrix.

Answer 18

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/solutions/1322101/c-java-python-maxheap-minheap-binary-search-picture-explain-clean-concise/

1. Brute force - add all elements to max heap of size K. Complexity - O(M * N * logK)
2. Min heap to keep K smallest elements. Put first element of each row into min heap (put tuple with matrix indeces). Pop smallest element and then push the next one in that row in the heap, do this K times.
   Complexity - O(K * logK)
3. Binary search - start from largest and smallest element, then count how many elements are smaller then mid.
   Counting elements need N+M operations - travers from top right to bottom left.
   Complexity - O((M+N) * log(max - min) )

Question 19

Longest Increasing Subsequence
Find the length of the longest increasing subsequence in a given array.

Answer 19

https://leetcode.com/problems/longest-increasing-subsequence/solutions/1326308/c-python-dp-binary-search-bit-segment-tree-solutions-picture-explain-o-nlogn/

1. Dynamic Programming - Let dp[i] is the longest increase subsequence of nums[0..i] which has nums[i] as the end element of the subsequence. Complexity - O(N^2)
2. Greedy with Binary Search - keep array sub, where sub[i] - has the best subsequence of length i (the best - smallest top of subsequence, thus easier to extend). Complexity - O(N * logN)

Question 20

Fibonacci Sequence
Find the n-th Fibonacci number.

Answer 20

1. Loop
2. Recursion like f_helper(n,a,b) - pass two previous numbers

Question 21

Lowest common ancestor in a tree.
Given a tree (node with array of children), tree root and two elements, find a lowest common ancestor of two elements.

Answer 21

Used DFS, and on each step pass back if the element was found and if the common ancestor was found.
Usually the elements are guaranteed unique, then you can just pass up a count of how many elements were found.

Question 22

Merge Sort
Sort an array using merge sort.

Answer 22

Divide the array into two halves, sort each half recursively, and then merge them back together. The base case is an array with 0 or 1 elements, which is already sorted.

Question 23

Gale-Shapley algorithm. Matching interns with teams
You are to match n interns with n teams given the preferences list for each intern and team. Prioritize intern selection first.

Answer 23

Go through all the interns matching them one by one to the best preference, if on the next step the conflict is found (best team for the next intern has already been assigned an intern), use team ranking to choose one of them and push the other intern back into the stack.

Data structures:
1. stack of interns left to match
2. dict with {team: matched intern}, update when needed
3. current best team for each intern start with [0,0, …0] and increment when needed
4. team ranking converted to dicts for each team [{intern: his rank}, …. ]

Question 24

Union Find - Disjoint Set
Implement effective data structure which represent disjoint sets: elements are unique across all sets (operation add element as a single set), each set has a root element (operation find[x] to return root element of the set with x), and can do union of two sets.

Answer 24

1. Data structure is a collection of trees where nodes point up to the parent, represented as a dictionary:
   {e1:e1, e2:e1, e3:e3} - two sets {e1, e2} and {e3}
2. to make union more effective:
   a) keep rank dictionary to remember the depth of the trees from each element, union with shorter tree at the bottom
   b) When running find[] - flatten tree to keep all elements under root, no need to update rank

Question 25

Correct brackets
Crate all versions of n brackets ( ) correctly matching close and open

Answer 25

Dynamic programming.
To correctly calculate N brackets you need to remember all from 1 to N-1.
Example: {n=0} = “”, {n=1} = “()”, etc, {k} - all versions with k brackets
# n = 4: “( {3} ) {0}” + “( {2} ) {1}” + “( {1} ) {2}” + “( {0} ) {3}”

Question 26

Cycles in directed graph
Given a directed unweighted graph (not necessarily connected) find if the graph contains a cycle (could be self-cycle)

Answer 26

One approach is to use DFS. DFS recursively calls the dfs(node) for each children node
1. Check if all the nodes were visited in case of node with no children or unconnected subgraphs
2. Keep the set of currently visited nodes for recursion

Question 27

Biggest island
A matrix has 0 and 1s, 0 represent island (no diagonal connections). Find the largest island size if we change on 1 to 0

Answer 27

Go through the matrix and identify all islands, keep two sides of references: island identifier => island cells and island cell => island identifier.
Iterate second time through all non-islands and check max size

Question 28

Heapify array

Answer 28

1. left and right children have indexes l = 2i+1 and r = 2i+2 for 0 based indexing
2. Loop starting from the middle to the beginning of array calling a helper heapify func
3. Helper function compares and swaps root of subarray with its children then calls itself recursively if one child was swapped with the root

Question 29

Water area in 2d between columns
Given array where nonzero integer mean column height, calculate total water area, if water is poured from the top. [0, 2, 0 3, 0 ,1] => 3 water

Answer 29

1. Create two arrays: for each element calculate the largest column to the left and largest column to the right
2. loop over array, for each element if min(max_left, max_right) > column at this cell, then add necessary amount of water

Question 30

Longest Common Subsequence (LCS)
given two strings (e.g. “ZXVVYZW”, “XKYKZPW”) find the common sequence in order but not necessary consecutive (X Y Z W)

Answer 30

1. Build array (N+1)x(M+1) with empty strings, iterate row by row
2. compare letter i1 from str1 to i2 from str2. If are the same append the letter to the result from array in cell [i1-1][i2-1]
   2.a. If not the same take longest LCS from [i1-1][i2] or [i1][i2-1]
3. Complexity is [MNmin(M,N)]
4. Improvements:
   - Store only two rows
   - Or instead of storing the whole LCS in array store a pointer

Question 31

2 missing numbers from n+2 array:
given array of length n which contains unique numbers form [1, n+2], but two are missing
find missing numbers

Answer 31

1. If only one number is missing we can do missing_number = sum(range(n+1)) - sum(array)
2. For two the same operation will yield sum of the missing numbers sum = n1+ n2
3. Filter input array for all values <= midpoint sum //2 - we can pinpoint smaller number
4. Then sum(filtered array) - sum(midpoint) = smaller number