my image

Dmitrii Volyx

Performance Engineer

351. Android Unlock Patterns

Android devices have a special lock screen with a 3 x 3 grid of dots. Users can set an “unlock pattern” by connecting the dots in a specific sequence, forming a series of joined line segments where each segment’s endpoints are two consecutive dots in the sequence. A sequence of k dots is a valid unlock pattern if both of the following are true: All the dots in the sequence are distinct. If the line segment connecting two consecutive dots in the sequence passes through the center of any other dot, the other dot must have previously appeared in the sequence. No jumps through the center non-selected dots are allowed. For example, connecting dots 2 and 9 without dots 5 or 6 appearing beforehand is valid because the line from dot 2 to dot 9 does not pass through the center of either dot 5 or 6. However, connecting dots 1 and 3 without dot 2 appearing beforehand is invalid because the line from dot 1 to dot 3 passes through the center of dot 2. ...

November 9, 2021 · 5 min · volyx

704. Binary Search

Given an array of integers nums which is sorted in ascending order, and an integer target, write a function to search target in nums. If target exists, then return its index. Otherwise, return -1. You must write an algorithm with O(log n) runtime complexity. Example 1: Input: nums = [-1,0,3,5,9,12], target = 9 Output: 4 Explanation: 9 exists in nums and its index is 4 Example 2: Input: nums = [-1,0,3,5,9,12], target = 2 Output: -1 Explanation: 2 does not exist in nums so return -1 Constraints: ...

November 9, 2021 · 2 min · volyx

Contiguous Subarrays

You are given an array arr of N integers. For each index i, you are required to determine the number of contiguous subarrays that fulfill the following conditions: The value at index i must be the maximum element in the contiguous subarrays, and These contiguous subarrays must either start from or end on index i. Signature int[] countSubarrays(int[] arr) Input Array arr is a non-empty list of unique integers that range between 1 to 1,000,000,000 Size N is between 1 and 1,000,000 Output An array where each index i contains an integer denoting the maximum number of contiguous subarrays of arr[i] ...

November 9, 2021 · 4 min · volyx

1269. Number of Ways to Stay in the Same Place After Some Steps

You have a pointer at index 0 in an array of size arrLen. At each step, you can move 1 position to the left, 1 position to the right in the array, or stay in the same place (The pointer should not be placed outside the array at any time). Given two integers steps and arrLen, return the number of ways such that your pointer still at index 0 after exactly steps steps. Since the answer may be too large, return it modulo 109 + 7. ...

November 7, 2021 · 2 min · volyx

1242. Web Crawler Multithreaded

Given a URL startUrl and an interface HtmlParser, implement a Multi-threaded web crawler to crawl all links that are under the same hostname as startUrl. Return all URLs obtained by your web crawler in any order. Your crawler should: Start from the page: startUrl Call HtmlParser.getUrls(url) to get all URLs from a webpage of a given URL. Do not crawl the same link twice. Explore only the links that are under the same hostname as startUrl. As shown in the example URL above, the hostname is example.org. For simplicity’s sake, you may assume all URLs use HTTP protocol without any port specified. For example, the URLs http://leetcode.com/problems and http://leetcode.com/contest are under the same hostname, while URLs http://example.org/test and http://example.com/abc are not under the same hostname. ...

November 4, 2021 · 3 min · volyx

1287. Element Appearing More Than 25% In Sorted Array

Given an integer array sorted in non-decreasing order, there is exactly one integer in the array that occurs more than 25% of the time, return that integer. Example 1: Input: arr = [1,2,2,6,6,6,6,7,10] Output: 6 Example 2: Input: arr = [1,1] Output: 1 Constraints: 1 <= arr.length <= 10^4 0 <= arr[i] <= 10^5 Solution class Solution { public int findSpecialInteger2(int[] arr) { int n = arr.length; int val1 = arr[n / 4]; int val2 = arr[n / 4 * 2] ; int val3 = arr[n / 4 * 3]; int val4 = arr[n - 1]; int count1 = countFreq(arr, val1); int count2 = countFreq(arr, val2); int count3 = countFreq(arr, val3); int count4 = countFreq(arr, val4); if (count1 >= count2 && count1 >= count3 && count1 >= count4) { return val1; } if (count2 >= count1 && count2 >= count3 && count2 >= count4) { return val2; } if (count3 >= count1 && count3 >= count2 && count3 >= count4) { return val3; } return val4; } int countFreq(int[] arr, int val) { int mid = Arrays.binarySearch(arr, val); int right = mid; while (right < arr.length - 1 && arr[right] == arr[right + 1]) { right++; } int left = mid; while (left > 0 && arr[left] == arr[left - 1]) { left--; } return right - left; } } Solution 2 class Solution { public int findSpecialInteger(int[] arr) { int n = arr.length; int t = n / 4; for (int i = 0; i < n - t; i++) { if (arr[i] == arr[i + t]) { return arr[i]; } } return -1; } }

October 28, 2021 · 2 min · volyx

1305. All Elements in Two Binary Search Trees

Given two binary search trees root1 and root2. Return a list containing all the integers from both trees sorted in ascending order. Example 1: Input: root1 = [2,1,4], root2 = [1,0,3] Output: [0,1,1,2,3,4] Example 2: Input: root1 = [0,-10,10], root2 = [5,1,7,0,2] Output: [-10,0,0,1,2,5,7,10] Example 3: Input: root1 = [], root2 = [5,1,7,0,2] Output: [0,1,2,5,7] Example 4: Input: root1 = [0,-10,10], root2 = [] Output: [-10,0,10] Example 5: Input: root1 = [1,null,8], root2 = [8,1] Output: [1,1,8,8] ...

October 28, 2021 · 3 min · volyx

173. Binary Search Tree Iterator

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST): BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST. boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false. int next() Moves the pointer to the right, then returns the number at the pointer. Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST. ...

October 28, 2021 · 3 min · volyx

413. Arithmetic Slices

An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same. For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences. Given an integer array nums, return the number of arithmetic subarrays of nums. A subarray is a contiguous subsequence of the array. Example 1: Input: nums = [1,2,3,4] Output: 3 Explanation: We have 3 arithmetic slices in nums: [1, 2, 3], [2, 3, 4] and [1,2,3,4] itself. Example 2: Input: nums = [1] Output: 0 Constraints: ...

October 26, 2021 · 2 min · volyx

489. Robot Room Cleaner

You are controlling a robot that is located somewhere in a room. The room is modeled as an m x n binary grid where 0 represents a wall and 1 represents an empty slot. The robot starts at an unknown location in the root that is guaranteed to be empty, and you do not have access to the grid, but you can move the robot using the given API Robot. ...

October 26, 2021 · 4 min · volyx