알고리즘

Can you solve this real interview question? Find if Path Exists in Graph - There is a bi-directional graph with n vertices, where each vertex is labeled from 0 to n - 1 (inclusive). The edges in the graph are represented as a 2D integer array edges, where each edges[i] = [ui, vi] denotes a bi-directional edge between vertex ui and vertex vi. Every vertex pair is connected by at most one edge, and no vertex has an edge to itself. You want to determine if there is a valid path that exists from vertex source to vertex destination. Given edges and the integers n, source, and destination, return true if there is a valid path from source to destination, or false otherwise.   Example 1: [https://assets.leetcode.com/uploads/2021/08/14/validpath-ex1.png] Input: n = 3, edges = [[0,1],[1,2],[2,0]], source = 0, destination = 2 Output: true Explanation: There are two paths from vertex 0 to vertex 2: - 0 → 1 → 2 - 0 → 2 Example 2: [https://assets.leetcode.com/uploads/2021/08/14/validpath-ex2.png] Input: n = 6, edges = [[0,1],[0,2],[3,5],[5,4],[4,3]], source = 0, destination = 5 Output: false Explanation: There is no path from vertex 0 to vertex 5.   Constraints: * 1 <= n <= 2 * 105 * 0 <= edges.length <= 2 * 105 * edges[i].length == 2 * 0 <= ui, vi <= n - 1 * ui != vi * 0 <= source, destination <= n - 1 * There are no duplicate edges. * There are no self edges.

Can you solve this real interview question? Minimum Number of Arrows to Burst Balloons - There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons. Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path. Given the array points, return the minimum number of arrows that must be shot to burst all balloons.   Example 1: Input: points = [[10,16],[2,8],[1,6],[7,12]] Output: 2 Explanation: The balloons can be burst by 2 arrows: - Shoot an arrow at x = 6, bursting the balloons [2,8] and [1,6]. - Shoot an arrow at x = 11, bursting the balloons [10,16] and [7,12]. Example 2: Input: points = [[1,2],[3,4],[5,6],[7,8]] Output: 4 Explanation: One arrow needs to be shot for each balloon for a total of 4 arrows. Example 3: Input: points = [[1,2],[2,3],[3,4],[4,5]] Output: 2 Explanation: The balloons can be burst by 2 arrows: - Shoot an arrow at x = 2, bursting the balloons [1,2] and [2,3]. - Shoot an arrow at x = 4, bursting the balloons [3,4] and [4,5].   Constraints: * 1 <= points.length <= 105 * points[i].length == 2 * -231 <= xstart < xend <= 231 - 1

Can you solve this real interview question? Insert Interval - You are given an array of non-overlapping intervals intervals where intervals[i] = [starti, endi] represent the start and the end of the ith interval and intervals is sorted in ascending order by starti. You are also given an interval newInterval = [start, end] that represents the start and end of another interval. Insert newInterval into intervals such that intervals is still sorted in ascending order by starti and intervals still does not have any overlapping intervals (merge overlapping intervals if necessary). Return intervals after the insertion. Note that you don't need to modify intervals in-place. You can make a new array and return it.   Example 1: Input: intervals = [[1,3],[6,9]], newInterval = [2,5] Output: [[1,5],[6,9]] Example 2: Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].   Constraints: * 0 <= intervals.length <= 104 * intervals[i].length == 2 * 0 <= starti <= endi <= 105 * intervals is sorted by starti in ascending order. * newInterval.length == 2 * 0 <= start <= end <= 105

Can you solve this real interview question? Contiguous Array - Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 1.   Example 1: Input: nums = [0,1] Output: 2 Explanation: [0, 1] is the longest contiguous subarray with an equal number of 0 and 1. Example 2: Input: nums = [0,1,0] Output: 2 Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.   Constraints: * 1 <= nums.length <= 105 * nums[i] is either 0 or 1.

Can you solve this real interview question? Remove Zero Sum Consecutive Nodes from Linked List - Given the head of a linked list, we repeatedly delete consecutive sequences of nodes that sum to 0 until there are no such sequences. After doing so, return the head of the final linked list.  You may return any such answer.   (Note that in the examples below, all sequences are serializations of ListNode objects.) Example 1: Input: head = [1,2,-3,3,1] Output: [3,1] Note: The answer [1,2,1] would also be accepted. Example 2: Input: head = [1,2,3,-3,4] Output: [1,2,4] Example 3: Input: head = [1,2,3,-3,-2] Output: [1]   Constraints: * The given linked list will contain between 1 and 1000 nodes. * Each node in the linked list has -1000 <= node.val <= 1000.

Can you solve this real interview question? Custom Sort String - You are given two strings order and s. All the characters of order are unique and were sorted in some custom order previously. Permute the characters of s so that they match the order that order was sorted. More specifically, if a character x occurs before a character y in order, then x should occur before y in the permuted string. Return any permutation of s that satisfies this property.   Example 1: Input: order = "cba", s = "abcd" Output: "cbad" Explanation: "a", "b", "c" appear in order, so the order of "a", "b", "c" should be "c", "b", and "a". Since "d" does not appear in order, it can be at any position in the returned string. "dcba", "cdba", "cbda" are also valid outputs. Example 2: Input: order = "bcafg", s = "abcd" Output: "bcad" Explanation: The characters "b", "c", and "a" from order dictate the order for the characters in s. The character "d" in s does not appear in order, so its position is flexible. Following the order of appearance in order, "b", "c", and "a" from s should be arranged as "b", "c", "a". "d" can be placed at any position since it's not in order. The output "bcad" correctly follows this rule. Other arrangements like "bacd" or "bcda" would also be valid, as long as "b", "c", "a" maintain their order.   Constraints: * 1 <= order.length <= 26 * 1 <= s.length <= 200 * order and s consist of lowercase English letters. * All the characters of order are unique.

Can you solve this real interview question? Intersection of Two Arrays - Given two integer arrays nums1 and nums2, return an array of their intersection. Each element in the result must be unique and you may return the result in any order.   Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output: [2] Example 2: Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output: [9,4] Explanation: [4,9] is also accepted.   Constraints: * 1 <= nums1.length, nums2.length <= 1000 * 0 <= nums1[i], nums2[i] <= 1000

Can you solve this real interview question? Minimum Common Value - Given two integer arrays nums1 and nums2, sorted in non-decreasing order, return the minimum integer common to both arrays. If there is no common integer amongst nums1 and nums2, return -1. Note that an integer is said to be common to nums1 and nums2 if both arrays have at least one occurrence of that integer.   Example 1: Input: nums1 = [1,2,3], nums2 = [2,4] Output: 2 Explanation: The smallest element common to both arrays is 2, so we return 2. Example 2: Input: nums1 = [1,2,3,6], nums2 = [2,3,4,5] Output: 2 Explanation: There are two common elements in the array 2 and 3 out of which 2 is the smallest, so 2 is returned.   Constraints: * 1 <= nums1.length, nums2.length <= 105 * 1 <= nums1[i], nums2[j] <= 109 * Both nums1 and nums2 are sorted in non-decreasing order.

Can you solve this real interview question? Count Elements With Maximum Frequency - You are given an array nums consisting of positive integers. Return the total frequencies of elements in nums such that those elements all have the maximum frequency. The frequency of an element is the number of occurrences of that element in the array.   Example 1: Input: nums = [1,2,2,3,1,4] Output: 4 Explanation: The elements 1 and 2 have a frequency of 2 which is the maximum frequency in the array. So the number of elements in the array with maximum frequency is 4. Example 2: Input: nums = [1,2,3,4,5] Output: 5 Explanation: All elements of the array have a frequency of 1 which is the maximum. So the number of elements in the array with maximum frequency is 5.   Constraints: * 1 <= nums.length <= 100 * 1 <= nums[i] <= 100