BoomBleBee: iunie 2024

FROM node:9.4.0-alpine
# copy files
COPY app.js .
COPY package.json .
# execute commands
RUN npm install &&\
    apk update &&\
    apk upgrade
# exposes port 8080 with a specified protocol inside a Docker Container
EXPOSE  8080
# run app.js with executable "node"
CMD node app.js

# Build in the current dir with tag myimage version v1
# > docker build . -t myimage:v1
# > docker images

# Run the image as a container 
# -d=detach, run in background
# -p=publish a container's port to the host
# > docker run -dp 8080:8080 myimage:v1

# Ping the application
# > curl localhost:8080

13 iunie 2024

Probleme Strings

#1. First non-repeating character

Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.

class Solution {
    public int firstUniqChar(String str) {
        Map<Character,Integer> map = new HashMap<>();
        for (int i=0; i<str.length(); i++) {
            Integer count = map.get(str.charAt(i));
            map.put(str.charAt(i), count == null ? 1 : count + 1);
        }
        for (int i=0; i<str.length(); i++) {
            if (map.get(str.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }

    public int firstUniqChar_2(String str) { // str contains only lowercase letters 'a' t o 'z'
        int bitVector = 0;
        int unique = (int) Math.pow(2, 27) - 1; // 1....1 for 26 bits corresponding to 'a' to 'z'
        for (int i=0; i<str.length(); i++) {
            int index = str.charAt(i) - 'a';
            if ((bitVector & (1 << index)) > 0) { // if bit index already set
                unique = unique & ~(1 << index); // clear bit at index
            }
            bitVector = bitVector | (1 << index); // set bit at index
        }
        for (int i=0; i<str.length(); i++) {
            int index = str.charAt(i) - 'a';
            boolean isBitSet = (unique & (1 << index)) > 0;
            if (isBitSet) {
                return i;
            }
        }
        return -1;
    }
}

#2. Permutation of a palindrome

Given a string, return if it is a permutation of a palindrome.

class Solution {

public boolean canBecomePalindrome(String str) {

if (str.length() == 0) {

return false;

}

int bitVector = 0;

for (int i=0; i<str.length(); i++) {

int index = str.charAt(i) - 'a';

if ((bitVector & (1 << index)) > 0) { // if bit set

bitVector = bitVector & ~(1 << index); // clear

} else {

bitVector = bitVector | (1 << index); // set

}

// se poate transforma in palindrom daca:

// Are nr par de caractere si toti bitii 0, SAU

// nr impar de caractere si un singur bit 1

boolean evenAmountOfChar = str.length() % 2 == 0;

boolean hasBit1 = false;

for (int i=0; i<26; i++) { // 26 letters in alphabet

if ((bitVector & (1 << i)) > 0) { // if bit set

if (hasBit1) {

return false; // a second bit is set

}

hasBit1 = true;

}

return evenAmountOfChar ^ hasBit1;

}

06 iunie 2024

A este un array de cifre 0 sau 1 (reprezentarea binară a unui număr, cu A[0] = LSB). Se cere să se afle prima poziție (de la LSB la MSB) de pe care apare cel mai lung șir de biți/cifre 1. De corectat maxim 2 linii (eu am corectat una).

class Solution {

    int solution(int[] A) {

        int n = A.length;

        int i = n - 1;

        int result = -1;

        int k = 0, maximal = 0;

        while (i > 0) {

            if (A[i] == 1) {

                k = k + 1;

                if (k >= maximal) {

                    maximal = k;

                    result = i;

}

}

            else

                k = 0;

            i = i - 1;

}

if (A[i] == 1 && k + 1 >= maximal) // correction >= instead of >

            result = 0;

        return result;

}

}

2. Repartizare pacienți într-un sanatoriu ✔️

Se dau N oaspeți (0... N-1) care așteaptă să fie repartizați pe camere, într-un sanatoriu. Într-o cameră se pot caza oricâți, dar nu toți pacienții vor să aibă mulți colegi de cameră.

Input: un array A cu N elemente, A[K] = numărul maxim de persoane într-o cameră, permis de pacientul K, inclusiv el însuși

Să se afle numărul minim de camere necesare pentru a caza toți pacienții.

import java.util.*;
import java.util.stream.Collectors;

class Solution {
    public int solution(int[] A) {
        int rooms = 0;

        List<Integer> patients = Arrays.stream(A).boxed().collect(Collectors.toList());
        Collections.sort(patients);

        for (int i=0; i<patients.size(); i++) {
            rooms++;
            if (patients.get(i) == 1) {
                continue;
            }
            i += patients.get(i);
        }

        return rooms;
    }
}

3. Reducerea unui șir de caractere ✔️

Un șir S conține doar literele A, B, C, D. El se poate transforma eliminând un grup de litere adiacente „AB” sau „CD” (în orice ordine). Să se afle șirul final, după aplicarea tuturor reducerilor posibile. Algoritmul trebuie să fie eficient pt seturi mari de date (un șir de maxim 250.000 caractere).

class Solution {
    public String solution2(String word) {
        String copy;
        do {
            copy = word;
            word = word.replaceAll("AB", "");
            word = word.replaceAll("BA", "");
            word = word.replaceAll("CD", "");
            word = word.replaceAll("DC", "");
        } while (!copy.equals(word));

        return word;
    }

    public String solution(String word) {
        if (word.isEmpty()) {
            return word;
        }
        int[] marked = new int[word.length()];
        marked[0] = 0;
        for (int i=1; i<word.length(); i++) {
            marked[i] = 0;
            if (condition(word, i, i-1)) {
                    marked[i] = 1;
                    marked[i-1] = 1;
                    i++;
            }
        }

        for (int i=0; i<word.length(); i++) {
            if (marked[i] == 1) {
                marked = circle(word, i, marked);
                i++;
            }
        }

        StringBuilder result = new StringBuilder();
        for (int i=0; i<marked.length; i++) {
            if (marked[i] == 0) {
                result.append(word.charAt(i));
            }
        }

        return result.toString();
    }

    private int[] circle(String word, int pos, int[] marked) {
        int left = pos - 1;
        int right = pos + 2;
        while (left >= 0 && right < marked.length && marked[left] == 0) {
            if (marked[left] == 0 && marked[right] == 0 && condition(word, left, right)) {
                marked[left] = 1;
                marked[right] = 1;
                left--;
                right--;
                continue;
            } 

            int r2 = right;
            while (r2 < marked.length && marked[r2] == 1) {
                r2++;
            }
            if (r2 != right) {
                right = r2;
            } else {
                break;
            }
        }

        return marked;
    }

    private boolean condition(String word, int i, int j) {
        return word.charAt(i) == 'A' && word.charAt(j) == 'B' || 
                word.charAt(i) == 'B' && word.charAt(j) == 'A' ||
                word.charAt(i) == 'C' && word.charAt(j) == 'D' ||
                word.charAt(i) == 'D' && word.charAt(j) == 'C';
    }
}

4. Bonus (demo): First Missing Positive ✖️

Given an unsorted integer array nums, return the smallest positive integer that is not present in nums. You must implement an algorithm that runs in O(n) time and uses O(1) auxiliary space.

Prima implementare (firstMissingPositive2): O(n^2) timp și O(n) spațiu

A doua implementare (firstMissingPositive): O(n) timp și O(1) spațiu

class Solution {
    public int firstMissingPositive2(int[] nums) {
        if (initialCheck(nums) == 1) {
            return 1;
        }
        Set<Integer> elems = new HashSet<>();
        for (int num : nums) {
            elems.add(num);
        }
        for (int i=1; ; i++) {
            if (!elems.contains(i)) {
                return i;
            }
        }
    }

    private int initialCheck(int[] nums) {
        boolean allNegative = true;
        int min = Integer.MAX_VALUE;
        for (int i=0; i<nums.length; i++) {
            if (nums[i] > 0) {
                allNegative = false;
                if (min > nums[i]) {
                    min = nums[i];
                }
            }
        }
        if (allNegative || min > 1) {
            return 1;
        }
        return 0;
    }

    private boolean isArrayComplete(int[] nums, int max) {
        int xor = 0;
        int times = 0;
        for (int i=0; i<nums.length; i++) {
            if (nums[i] > 0) {
                xor = xor ^ nums[i];
                times++;
            }
        }
        for (int i=1; i<=times; i++) {
            xor = xor ^ i;
        }
        return xor == 0 && times == max;
    }

    public int firstMissingPositive(int[] nums) {
        if (initialCheck(nums) == 1) {
            return 1;
        }

        // find min, max
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        for (int i=0; i<nums.length; i++) {
            if (nums[i] < 0) {
                nums[i] = 0;
            }
            if (max < nums[i]) {
                max = nums[i];
            }
            if (min > nums[i] && min > 0) {
                min = nums[i];
            }
        }

        if (min == 1 && isArrayComplete(nums, max)) {
            return max + 1;
        }

        // tag in place
        int tag = max != Integer.MAX_VALUE ? max + 1 : max;
        for (int i=0; i<nums.length; i++) {
            int val = nums[i] >= tag ? nums[i]-tag : nums[i]; // untag/extract if already tagged
            if (val > 0 && val < nums.length && nums[val-1] < tag) { // avoid duplicates
                nums[val-1] += tag;
            }
        }

        // find first untagged
        for (int i=0; i<nums.length; i++) {
            if (nums[i] < tag && nums[i] >= 0) {
                return i+1;
            }
        }

        return max + 1; // should not arrive here
    }
}

01 iunie 2024

50 DSA-Questions: Biti #47, #48, #49, #50

#47. Sum of Two Integers

Given two integers a and b, return the sum of the two integers without using the operators + and -.

class Solution {
    // addition a, b => sum = a ^ b; carry = a & b

    public int getSum1(int a, int b) {
        int carry;
        while (b != 0) {
            carry = a & b;
            a = a ^ b;
            b = carry << 1;
        }
        return a;
    }

    public int getSum2(int a, int b) {
        int carry = (a & b) << 1;
        int result = a ^ b;
        if (carry == 0) {
            return result;
        }             
        return getSum2(carry, result);
    }
}

#48. Number of 1 Bit

Write a function that takes the binary representation of an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

class Solution {
    public int hammingWeight(int num) {
        int bits = 0;
        while (num != 0) {
            boolean is1 = (num & 1) != 0;
            if (is1) {
                bits++;
            }
            num = num >> 1;
        }
        return bits;
    }
}

#49. Counting Bits

Given an integer n, return an array of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.

class Solution {
    public int[] countBits(int n) {
        int[] array = new int[n+1];
        for (int i=0; i<=n; i++) {
            array[i] = hammingWeight(i);
        }
        return array;
    }
}

#50. Missing Number

Given an array nums containing n distinct numbers in the range [0, n], return the only number in the range that is missing from the array.

class Solution {
    public int missingNumber2(int[] nums) {
        int max = nums.length;
        int sum = (max+1) * max / 2;
        for (int num : nums) {
            sum -= num;
        }        
        return sum;
    }

    public int missingNumber(int[] nums) {
        int xor = nums.length;
        // XOR properties:
        // a ^ b = b ^ a => we can xor the elements in any order
        // x ^ x = 0 => nums[k] ^ i = 0 if nums[k] == i => will eliminate matching elements
        // x ^ 0 = x
        // the unmatched i will stand out
        for (int i=0; i<nums.length; i++) {
            xor = xor ^ nums[i] ^ i;
        }        
        return xor;
    }
}

Bonus: Reverse bits

Reverse bits of a given 32 bits unsigned integer.

public class Solution {
    public int reverseBits(int n) {
        int res = 0;
        int i = 32;  // need to fill all 32 bits
        while (i > 0) {
            int currentBit = n & 1;
            res = res << 1 | currentBit; // res = res * 2 + currentBit;
            n = n >> 1;
            i--;
        }
        return res;
    }
}

27 iunie 2024

CATALOG Cracking the code interview

22 iunie 2024

CATALOG 50DSA

21 iunie 2024

Dockerfile

13 iunie 2024

Probleme Strings

06 iunie 2024

Microsoft "technical task"

01 iunie 2024

50 DSA-Questions: Biti #47, #48, #49, #50