Coding Problems and Solutions — 2
[1] Clone Linked List with Random Pointer
A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.
Return a deep copy of the list.
(https://leetcode.com/problems/copy-list-with-random-pointer/)
Approach — Use hashmap to map index of node to copy of node pointer and also inverted index to map node to an index used for mapping random node pointer to the index in the node_map.
[2] Valid Palindrome — Given a non-empty string s, you may delete at most one character. Judge whether you can make it a palindrome.
Example:
Input: "abca"
Output: True
Explanation: You could delete the character 'c'.(https://leetcode.com/problems/valid-palindrome-ii/)
[3] Fraction to recurring decimal — Given two integers representing the numerator and denominator of a fraction, return the fraction in string format.
If the fractional part is repeating, enclose the repeating part in parentheses.
Example:
Input: numerator = 1, denominator = 2
Output: "0.5"(https://leetcode.com/problems/fraction-to-recurring-decimal/)
[4] Target Sum — You are given a list of non-negative integers, a1, a2, …, an, and a target, S. Now you have 2 symbols + and -. For each integer, you should choose one from + and - as its new symbol.
Find out how many ways to assign symbols to make sum of integers equal to target S.
Example:
Input: nums is [1, 1, 1, 1, 1], S is 3.
Output: 5
Explanation: -1+1+1+1+1 = 3
+1-1+1+1+1 = 3
+1+1-1+1+1 = 3
+1+1+1-1+1 = 3
+1+1+1+1-1 = 3There are 5 ways to assign symbols to make the sum of nums be target 3.
(https://leetcode.com/problems/target-sum/)
Approach — Use DP, cache[i][x] is the number of ways to form the sum x using the elements 0 to i.
[5] Sort Colors — Given an array with n objects colored red, white or blue, sort them in-place so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Example:
Input: [2,0,2,1,1,0]
Output: [0,0,1,1,2,2](https://leetcode.com/problems/sort-colors/)
Approach — Use two pointers index_1 (first index of 1 in array) and index_2 (first index of 2 in array).
When we encounter 1, we swap with first index of 2 (if it is before).
When we encounter 0, first we swap with first index of 1(if it is before) and then swap 1 with first index of 2 (if it is before).
[6] Binary Tree Right Side View — Given a binary tree, imagine yourself standing on the rightside of it, return the values of the nodes you can see ordered from top to bottom.
Example:
Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation: 1 <---
/ \
2 3 <---
\ \
5 4 <---
(https://leetcode.com/problems/binary-tree-right-side-view/)
Approach — Use BFS with level. Insert the right sub-tree element first and whenever there is change in level the current element would be the element from that level.
[7] Binary Tree Maximum Path Sum — Given a non-empty binary tree, find the maximum path sum.
For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.
Example:
Input: [1,2,3] 1
/ \
2 3Output: 6
(https://leetcode.com/problems/binary-tree-maximum-path-sum/)
Approach — For each node compute the maximum path sums in the left sub-tree and the right sub-tree and also the maximum path sum starting from node to either side (left or right).
[8] Merge k sorted linked lists and return it as one sorted list.
Example:
Input:
[
1->4->5,
1->3->4,
2->6
]
Output: 1->1->2->3->4->4->5->6(https://leetcode.com/problems/merge-k-sorted-lists/)
Approach — Use min-heap to progress each list’s next pointer.
[9] Product of array except self — Given an array nums of n integers, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
Input: [1,2,3,4]
Output: [24,12,8,6]Do not use division operation.
(https://leetcode.com/problems/product-of-array-except-self/)
Approach — Pre-compute suffix product at each index i.
[10] Paint House 3 — There is a row of m houses in a small city, each house must be painted with one of the n colors (labeled from 1 to n), some houses that has been painted last summer should not be painted again.
A neighborhood is a maximal group of continuous houses that are painted with the same color. (For example: houses = [1,2,2,3,3,2,1,1] contains 5 neighborhoods [{1}, {2,2}, {3,3}, {2}, {1,1}]).
Given an array houses, an m*n matrix cost and an integer target where:
- houses[i] : is the color of the house i, 0 if the house is not painted yet.
- cost[i][j] : is the cost of paint the house i with the color j+1
Return the minimum cost of painting all the remaining houses in such a way that there are exactly target neighborhoods, if not possible return -1.
(https://leetcode.com/problems/paint-house-iii/)
Approach — Compute f[i][t][j] i.e. minimum cost to paint houses 0 to i into t neighborhoods and the i-th house using the j-th color.
f[i][t][j] = min(f[i-1][t][j] + cost[i][j], f[i-1][t-1][c1] + cost[i][j], f[i-1][t-1][c2] + cost[i][j], f[i-1][t-1][c3] + cost[i][j], ….)
where c1, c2, .. are colors other than color j.
[11] Given an array of integers arr and an integer k.
A value arr[i] is said to be stronger than a value arr[j] if |arr[i] — m| > |arr[j] — m| where m is the median of the array.
If |arr[i] — m| == |arr[j] — m|, then arr[i] is said to be stronger than arr[j] if arr[i] > arr[j].
Return a list of the strongest k values in the array. return the answer in any arbitrary order.
Median is the middle value in an ordered integer list. More formally, if the length of the list is n, the median is the element in position ((n — 1) / 2) in the sorted list (0-indexed).
(https://leetcode.com/problems/the-k-strongest-values-in-an-array/)
Approach — Sort array then use double ended queue to pop element from either end of the queue depending on the absolute diff. with median.
