DEV Community: Sergei Golitsyn

Award Budget Cuts

Sergei Golitsyn — Mon, 13 Feb 2023 23:45:58 +0000

Sergei Golitsyn provides solutions to popular algo problems.

Aloha guys today we have a Pramp.com problem Award Budget Cuts:

Description

Given an array grantsArray of the original grants and the reduced budget newBudget, write a function findGrantsCap that finds in the most efficient manner a cap such that the least number of recipients is impacted and that the new budget constraint is met (i.e. sum of the N reallocated grants equals to newBudget).

Analyze the time and space complexities of your solution.

Example:

input:  
grantsArray = [2, 100, 50, 120, 1000], 
newBudget = 190
output: 47 
And given this cap the new grants array would be
[2, 47, 47, 47, 47]. 
Notice that the sum of the new grants is indeed 190

Solution

This problem was mind-blowing for me. First, let's concentrate on the example and figure out what is happening.
We have an array of old budgets and want to distribute new ones. In the best-case scenario, we want to distribute it evenly. For example, if arr = [10, 10, 10] and newBudg = 3, the correct result should be 3. We will put 1 to all grants.
Let's add more examples. arr = [10, 3, 4, 200] and newBudg = 8, result = 2. Do you see a pattern? arr = [10, 1, 2, 20] and newBudg = 7, result = 2. You can ask me why result 2 is correct in the last example. It happens because we can fill grand with budget 1, then we have the rest of the budget as 6. And we can evenly distribute it to 3 other grands.
Hmm, so we have a pattern of how to solve this problem.

First of all, let's sort out the grants array.
Then we can add variable cap = newBudg / grants.length.
After it, we should iterate over the collection and check the cap and current element.
If the current element is lower than the cap, we can subtract it from the budget and recalculate the cap again with a lower length.
We want to do it till we find the first grand > cap. After it, it doesn't make sense. Our algorithm ready for implementation. Let's deep dive to the code implementation

Code

static double findGrantsCap(double[] arr, double newBudget) {
   // your code goes here
   Arrays.sort(arr); // O(N*LogN)
   int n = arr.length-1;
   double cap = newBudget/n+1;
   for(int i = 0; i < n; i++) { // O(N)
     if(arr[i] < cap) {
        newBudget -= arr[i];
        cap = (newBudget/(n-i));
     } else {
       return cap;
     }
   }
   return cap;
}

Greatest Common Divisor of Strings

Sergei Golitsyn — Fri, 10 Feb 2023 17:58:29 +0000

Sergei Golitsyn provides solutions to popular leetcode problems.

Aloha guys today we have a popular GDS problem:

Description

For two strings s and t, we say "t divides s" if and only if s = t + ... + t (i.e., t is concatenated with itself one or more times).

Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.

Example 1:

Input: str1 = "ABCABC", str2 = "ABC"
Output: "ABC"
Example 2:

Input: str1 = "ABABAB", str2 = "ABAB"
Output: "AB"
Example 3:

Input: str1 = "LEET", str2 = "CODE"
Output: ""

Solution

To solve it we need to understand, what we want to find. We need to find greatest common part of two words, and this part should divide word on 1-N the same paths.
For example: a = ABCABC and b = ABC can be divided on a = ABC ABC and b = ABC
In the next example a = ABABAB and b = ABAB we cannot divide a on b because a = ABAB AB and ABAB != AB. That is why we should reduce divider.
We can do it iteratively, but what if we start with the rest of the longest string?
a = ABABAB after divide a has two parts common ABAB and rest AB. Let's try to use rest. Now let's try to divide longest string on short one, a = AB and b = ABAB. b will be AB AB. Hm, obviously that AB is greatest common divisor. But how can we understand it? We need to dive bit deeper and again use rest of division. a = "" and b = AB. If one of the strings is empty, another one will be our result. Wisdom, right?

Code

    public String gcdOfStrings2(String str1, String str2) {
        int l1 = str1.length();
        int l2 = str2.length();

        // Swap the parameters when needed
        if (l1 < l2){
            return gcdOfStrings(str2, str1);
        }

        // Since we swap
        if (l2 == 0){
            return str1;
        }

        // Check if str1 starts with str2
        if (!str1.startsWith(str2)) {
            return "";
        }

        return gcdOfStrings(str1.substring(l2), str2);
    }

Find the Duplicate Number

Sergei Golitsyn — Wed, 26 Oct 2022 03:03:50 +0000

author: Sergei Golitsyn
link: https://leetcode.com/problems/find-the-duplicate-number/

Description:

Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.

There is only one repeated number in nums, return this repeated number.

You must solve the problem without modifying the array nums and uses only constant extra space.

`Example 1:
Input: nums = [1,3,4,2,2]
Output: 2

Example 2:
Input: nums = [3,1,3,4,2]
Output: 3`

Solution:

Ok ok, hello everyone. Let's try to solve this problem.
We know that we have elements from 1 to n.
And all this elements were sorted.
What if
we will check the middle element and calculate count of elements less that the middle
If count less than middle element, that means that that we have duplicate element in the right part.

For example:

[1,2,3,4,5,5,6]
mid = 4
foreach(1 : 6) --> 
if (num <= cur){
 count ++;
}
count = 1 (1)
...
count = 4 (4)

And we have count as 4, that is why we have to move into right part. Is it clear?

Then in the right part we can do the same. And move to the right or to the left part.

Finally in the left part we set result as middle element, because otherwise we move to another side.

And yes, it is a modified binary search. You seem simple algorithm for complicated problem.

Sure you can iterate over array, and it would take O(N) time. In this approach we have O(log(N)) time complexity without additional memory.

Full code below:

    public int findDuplicate(int[] nums) {
        int start = 1;
        int end = nums.length - 1;

        int rez = -1;

        while(start <= end){
            int cur = (end + start) / 2;

            int count = 0;
            for (int num : nums){
                if (num <= cur){
                    count ++;
                }
            }
            if (count > cur){
                rez = cur;
                end = cur - 1;
            } else {
                start = cur + 1;
            }

        }
        return rez;
    }

Linked List Popular problems

Sergei Golitsyn — Fri, 17 Dec 2021 12:13:01 +0000

Hello everyone. Today we will analyse popular tasks for linked lists.
Also you can check Linked List Tips.
The first task on our list is Merge Two Sorted Lists.

You are given the heads of two sorted linked lists list1 and list2.
Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.
Return the head of the merged linked list.

How do we approach this problem? One of the most popular techniques for working with linked lists is two-pointers. In our case, we can use the beginning of each of the lists as pointers and move the elements only if one is larger than the other. Also, do not forget to supplement our resulting list with the remaining elements of the list that is longer.

public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode empty = new ListNode();
        ListNode emptyHead = empty;

        while(list1 != null && list2 != null) {
            if(list1.val > list2.val) {
                empty.next = list2;
                list2 = list2.next;
                empty = empty.next;
            } else {
                empty.next = list1;
                list1 = list1.next;
                empty = empty.next;
            }
        }

        while (list1 != null) {
            empty.next = list1;
            list1 = list1.next;
            empty = empty.next;
        }
        while (list2 != null) {
            empty.next = list2;
            list2 = list2.next;
            empty = empty.next;
        }
        return emptyHead.next;
    }

Next, we will smoothly move on to the **Add Two Numbers **task.

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.
In our case, we need to add numbers. But there may be a situation when the amount will be more than 10. Then it is worth transferring the balance to the next operation. There is also a case when the sum is 10. Then you can take it out in a separate case or combine it with a condition greater than 10.

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode rezNodeHead = new ListNode();
        ListNode rezNode = rezNodeHead;
        int rest = 0;
        while (l1 != null || l2 != null) {
            int val1 = (l1 != null) ? l1.val : 0;
            int val2 = (l2 != null) ? l2.val : 0;

            int rez = rest + val1 + val2;
            ListNode tmp = new ListNode();
            if (rez == 10) {
                tmp.val = 0;
                rezNode.next = tmp;
                rezNode = tmp;
                rest = 1;
            } else if (rez > 10) {
                int val = rez % 10;
                rest = rez / 10;
                tmp.val = val;
                rezNode.next = tmp;
                rezNode = tmp;
            } else {
                tmp.val = rez;
                rezNode.next = tmp;
                rezNode = tmp;
                rest = 0;
            }
            l1 = (l1 != null) ? l1.next : null;
            l2 = (l2 != null) ? l2.next : null;
        }
        if (rest != 0) {
            ListNode tmp = new ListNode();
            tmp.val = rest;
            rezNode.next = tmp;
        }
        return rezNodeHead.next;
    }

_ If you have any questions about this problem, I will be happy to answer._
There is no way around Flatten a Multilevel Doubly Linked List. In this task, a node can have a child node.

You are given a doubly linked list, which contains nodes that have a next pointer, a previous pointer, and an additional child pointer. This child pointer may or may not point to a separate doubly linked list, also containing these special nodes. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure as shown in the example below.

Given the head of the first level of the list, flatten the list so that all the nodes appear in a single-level, doubly linked list. Let curr be a node with a child list. The nodes in the child list should appear after curr and before curr.next in the flattened list.

Return the head of the flattened list. The nodes in the list must have all of their child pointers set to null.

There are several interesting approaches to solving this problem. I will analyse the easiest (for me) to write. It doesn't take long to write this approach. My idea is that we are running through the nodes. When the node has a child, we rearrange the link so that the list with the child sodas fits into our current list. There is a nuance that we will have to run through the child node two times in the worst case.

public static Node flatten(Node head) {
        Node headTmp = head;
        if (head == null) {
            return head;
        }

        while (head != null) {
            Node child = head.child;
            Node next = head.next;

            if (child != null) {
                head.next = child;

                while (child.next != null) {
                    child = child.next;
                }
                child.next = next;
                next.prev = child;
            }
            head.child = null;
            head = head.next;
        }
        return headTmp;
    }

How can this algorithm be improved? When meeting a child node, it is possible to recursively into the depths of the list. We will embed it in the parent when we get to the most profound child element. Visually, it will look completely different from the previous algorithm.
If you have any questions, I will be happy to answer them.

Do not forget about the rather popular **Odd-Even Linked List **task.

Given the head of a singly linked list, group all the nodes with odd indices together followed by the nodes with even indices, and return the reordered list.
The first node is considered odd, and the second node is even, and so on.
Note that the relative order inside both the even and odd groups should remain as it was in the input.
You must solve the problem in O(1) extra space complexity and O(n) time complexity.

You can remember the technique of the two runners. We can prepare two nodes for odd and even elements, and we will successfully add them. In the end, we need to merge two lists. How to do it? For this, we need a tail. Therefore, when filling underneath, we will shift a tail. And at the end, we combine tail odd and head even.

public ListNode oddEvenList(ListNode head) {
        if (head == null){
            return head;
        }
        ListNode oddHead = null;
        ListNode oddTail = null;
        ListNode evenHead = null;
        ListNode evenTail = null;
        int counter = 0;

        while(head != null) {
            counter += 1;
            if (counter % 2 != 0) {
                if (oddHead == null) {
                    oddHead = head;
                    oddTail = head;

                } else {
                    oddTail.next = head;
                    oddTail = head;
                }
            } else {
                if (evenHead == null) {
                    evenHead = head;
                    evenTail = head;

                } else {
                    evenTail.next = head;
                    evenTail = head;
                }
            }
            head = head.next;
        }

        oddTail.next = evenHead;
        if (evenTail != null){
            evenTail.next = null;
        }
        return oddHead;
    }

Linked List Tips

Sergei Golitsyn — Fri, 03 Dec 2021 14:25:20 +0000

Linked List is a fairly popular data structure. And the tasks associated with this structure can often be found at an interview. In this article, we will break down everyday Linked List tasks.

A Linked List is a linked list where one item refers to another.

One of the most common techniques for solving Linked List problems is the two sliders technique. We create a fast and slow slider and move the slow one forward, one non-zero. And fast (for example) by two.

Task. Linked List Cycle

Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail's next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false

How can we know if there is a loop? If you create two sliders, when the slow one enters the loop, the fast one will catch up with it by 1. And it turns out they will meet. And if there is no loop, then the fast slider will be null. I hope the idea is clear. Let's take a look at the code:

` public boolean hasCycle(ListNode head) {
if (head == null) {
return false;
} else {
ListNode slow = head;
ListNode fast = head;

        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast){
                return true;
            }
        }
    }
    return false;
}

How do we find the node where the loop starts? It is not hard to see from the previous algorithm that the fast slider will reach the slow one in N steps. Since our loop may not start from the beginning of the sheet, when the slow slider approaches the beginning of the loop after X steps, the fast slider will go X * 2. And the fast one will be at a distance of N - 2 * X steps. On the other hand, the fast catches up with the slow one by 1 every step. It turns out that the fast lags behind the slow one by N - 2X. Catching up each time by 1, the fast and slow runners will meet at point N - X. This means that we can move any slider to the beginning of the sheet and move the runners step by step from the meeting point and the head. The place where they meet will be the beginning of the loop. If you still have questions about the algorithm, write. I will be happy to answer.
Let's take a look at the code:

`public ListNode detectCycle(ListNode head) {
if (head == null || head.next == null) {
return null;
}
ListNode slow = head;
ListNode fast = head;

    while (fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;

        if (slow == fast){
            break;
        }
    }

    if (fast == null || fast.next == null) {
        return null;
    }
    slow = head;

    while (slow != fast){
        slow = slow.next;
        fast = fast.next;
    }
    return slow;
} `

Oh, I really like the next challenge. The intersection of Two Linked Lists.

Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.

How do we find these intersections? What if the length of the sheets is different? What if they don't intersect at all?

I suggest that you first check if the sheets overlap.
We just go through one and the second sheet and see that the resulting baud is the same.
What to do next?
During the first pass through the sheets, we can calculate the length of each of them. We get the missing number of nodes by subtracting the smaller size from the larger. With this amount, you can move along the sheet. And then, we can begin to run on two sheets and look for the place of their intersection. Cool, isn't it?

`public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode aEnd = headA;
ListNode bEnd = headB;
int aLength = 1;
int bLength = 1;

    while (aEnd != null){
        aEnd = aEnd.next;
        aLength++;
    }

    while (bEnd != null){
        bEnd = bEnd.next;
        bLength++;
    }

    if (aEnd != bEnd) {
        return null;
    }

    aEnd = headA;
    bEnd = headB;
    int shift = 0;
    if (aLength > bLength) {
        shift = aLength - bLength;
        while (shift > 0){
            aEnd = aEnd.next;
            shift --;
        }
    } else if (bLength > aLength) {
        shift = bLength - aLength;
        while (shift > 0){
            bEnd = bEnd.next;
            shift --;
        }
    }

    while(aEnd != null) {
        if (aEnd == bEnd){
            return aEnd;
        }
        aEnd = aEnd.next;
        bEnd = bEnd.next;
    }

    return null;
} `

By the way, have you ever wondered how you can remove a specific node from the end of the List? After all, we only have one direction? How to delete?
Fast and slow runners come to our rescue again. Move the fast slider by the required number of elements.
Next, connect the slow slider and run until the fast slider becomes NULL. When fast is NULL, the slow slider is in front of the element to be removed. And that's all. Then we can simply rearrange the links, and the required part is removed.

`public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode empty = new ListNode();

    empty.next = head;
    ListNode slow = empty;
    ListNode fast = empty;

    for (int i = 0; i < n && fast != null; i++){
        fast = fast.next;
    }

    while (fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next;
    }

    slow.next = slow.next.next;
    return empty.next;
}

Let's summarize. When using the slider technique, always test the next element for NULL. It is necessary to correctly determine the conditions for ending the loop. Run different options to make sure your requirements are correct.