50 DSA-Questions: #10, #11

#10. Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]). Find two lines that together with the x-axis form a container, such that the container contains the most water. Return the maximum amount of water a container can store. (The container has rectangle shape)

public class Exercise10 {
    // private final Integer[] HEIGHT = {1,8,6,2,5,4,8,3,7};
    // private final Integer[] HEIGHT = {1,2,4,7,9};
    // private final Integer[] HEIGHT = {6, 2, 0, 20, 1};
    // private final Integer[] HEIGHT = {1, 1, 10, 9, 1, 1};
    // private final Integer[] HEIGHT = {14, 8, 5, 3, 3, 2, 1};
    private final Integer[] HEIGHT = {100, 1, 102};

    private int getArea(int i, int j) {
        return Math.abs(i - j) * Math.min(HEIGHT[i], HEIGHT[j]);
    }

    private void solveBruteForce() {
        int indexI = 0, indexJ = 0;
        int maxArea = 0;
        for (int i=0; i<HEIGHT.length - 1; i++) {
            for (int j=1; j<HEIGHT.length; j++) {
                int area = getArea(i, j);
                if (area > maxArea) {
                    maxArea = area;
                    indexI = i;
                    indexJ = j;
                }
            }
        }
        System.out.println("[Brut] maxArea = " + maxArea + ", i = " + indexI + ", j = " + indexJ);
        // O(n^2)
    }

    private void solveEasy() {
        // sort lines by y desc, x desc;
        // find first common element going from i=0 and from j=0 towards the rest of the arrays;
        // for that element find its best pair;

        List<Integer> unsortedArray = Arrays.asList(HEIGHT);
        List<Integer> sortedArray = Arrays.asList(HEIGHT.clone());
        sortedArray.sort((i1, i2) -> i2 - i1 != 0 ? i2 - i1 : unsortedArray.indexOf(i2) - unsortedArray.indexOf(i1));

        int indexElement = 0;
        Set<String> keys = new HashSet<>();
        for (int i=0; i<HEIGHT.length; i++) {
            String key1 = i + "," + unsortedArray.get(i);
            String key2 = unsortedArray.indexOf(sortedArray.get(i)) + "," + sortedArray.get(i);
            if (keys.contains(key1) || key1.equals(key2)) {
                indexElement = i;
                break;
            }
            if (keys.contains(key2)) {
                indexElement = unsortedArray.indexOf(sortedArray.get(i));
                break;
            }
            keys.add(key1);
            keys.add(key2);
        }

        int maxArea = 0;
        int secondIndex = 0;
        for (int i=0; i<HEIGHT.length; i++) {
            int area = getArea(indexElement, i);
            if (area > maxArea) {
                maxArea = area;
                secondIndex = i;
            }
        }

        System.out.println("[Easy] maxArea = " + maxArea + ", i = " + indexElement + ", j = " + secondIndex);
        // O(n log n) due to sorting
    }

    public static void main(String args[]) {
        new Exercise10().solveBruteForce();
        new Exercise10().solveEasy();
    }
}

#11. Set Matrix Zeroes

Given an m x n integer matrix, if an element is 0, set its entire row and column to 0's. You must do it in place (means no extra memory should be used -> space complexity O(1)).

class Solution {
    void setZeroes(int[][] matrix) {
        boolean row0has0 = false;
        for (int j=0; j<matrix[0].length; j++) {
            if (matrix[0][j] == 0) {
                row0has0 = true;
                break;
            }
        }
        boolean col0has0 = false;
        for (int i=0; i<matrix.length; i++) {
            if (matrix[i][0] == 0) {
                col0has0 = true;
                break;
            }
        }
        
        // set matrix[0][j] = 0 when col j has a zero
        // set matrix[i][0] = 0 when row i has a zero
        for (int i=0; i<matrix.length; i++) {
            for (int j=0; j<matrix[0].length; j++) {
                if (matrix[i][j] == 0) {
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        // set zeroes in matrix by checking which row/col is set to zero
        for (int i=1; i<matrix.length; i++) {
            if (matrix[i][0] == 0) {
                setZerosRow(matrix, i);
            }
        }
        for (int j=1; j<matrix[0].length; j++) {
            if (matrix[0][j] == 0) {
                setZerosCol(matrix, j);
            }
        }
        // finally set row/col 0 to zero if previously checked
        if (row0has0) {
            for (int j=0; j<matrix[0].length; j++) {
                matrix[0][j] = 0;
            }
        }
        if (col0has0) {
            for (int i=0; i<matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
    }
    private void setZerosCol(int[][] matrix, int posJ) {
        for (int i=1; i<matrix.length; i++) {
            matrix[i][posJ] = 0;
        }
    }
    private void setZerosRow(int[][] matrix, int posI) {
        for (int j=1; j<matrix[0].length; j++) {
            matrix[posI][j] = 0;
        }
    }
}

50 DSA-Questions: Arrays #8, #9

#8. Search in Rotated Sorted Array

Given the array nums after the possible rotation and an integer target, return the index of the target if it is in nums, or -1 if it is not in nums. You must write an algorithm with O(log n) runtime complexity.

public class Exercise8 {
    private final int TARGET = 0;
    private final int[] ARRAY = {4,5,6,7,0,1,2}; // index = 4
    // private final int[] ARRAY = {10,12,0,4,5,7}; // index = 2
    // private final int[] ARRAY = {0,7,8,9,10}; // index = 0
    // private final int[] ARRAY = {3,4,6,7,8,9,0}; // index = 6
    // private final int[] ARRAY = {7, -6, -3, -2, -1, 0, 5}; // index = 5

    private void find(int leftIndex, int rightIndex) {
        if (leftIndex == rightIndex || leftIndex + 1 == rightIndex) { // one or two elements left
            int index = ARRAY[leftIndex] == TARGET ? leftIndex : (ARRAY[rightIndex] == TARGET ? rightIndex : -1);
            System.out.println("Index = " + ((index > -1) ? index : "N/A"));
            return;
        }

        int mid = leftIndex + (rightIndex - leftIndex) / 2;

        if (ARRAY[leftIndex] <= ARRAY[mid] && ARRAY[leftIndex] <= TARGET && ARRAY[mid] >= TARGET) { // search in left array
            find(leftIndex, mid);
            return;
        }

        if (ARRAY[mid+1] <= ARRAY[rightIndex] && ARRAY[mid+1] <= TARGET && ARRAY[rightIndex] >= TARGET) { // search in right array
            find(mid+1, rightIndex);
            return;
        }

        if (ARRAY[leftIndex] > ARRAY[mid] && TARGET <= ARRAY[mid]) {
            find(leftIndex, mid); // search in left array
            return;
        }

        find(mid+1, rightIndex); // search in right array
    }

    private void solve() {
        find(0, ARRAY.length - 1);
    }

    public static void main(String args[]) {
        new Exercise8().solve();
    }
}

#9. 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0. Notice that the solution set must not contain duplicate triplets.

public class Exercise9 {
    // private final Integer[] NUMS = {-1,0,1,2,-1,-4}; // triplets [[-1,-1,2],[-1,0,1]]
    private final Integer[] NUMS = {1, 2, -3, 2, -4, 1, 3, 1, -2}; // triplets [[1,2,-3],[2,2,-4],[1,1,-2],[1,-4,3]]
    private final int TARGET_SUM = 0;

    private List<Pair<Integer, Integer>> twoSum(int targetSum, int indexThird) {
        List<Integer> list = Arrays.asList(NUMS);
        List<Pair<Integer, Integer>> result = new ArrayList<>();

        for (int i=0; i<list.size(); i++) {
            if (i == indexThird) {
                continue; // duplicate
            }

            final int element = list.get(i); // to the left
            int key = targetSum - element; // to the right
            if (list.indexOf(element) == list.lastIndexOf(key) || indexThird == list.lastIndexOf(key)) {
                continue; // duplicate
            }

            if (list.contains(key)) {
                result.add(new Pair<>(element, key));
            }
        }
        return result;
    }

    private void solve() {
        Set<String> result = new HashSet<>();
        for (int i=0; i<NUMS.length; i++) {
            int thirdElement = TARGET_SUM - NUMS[i];
            final int element = NUMS[i];
            List<Pair<Integer, Integer>> twoSums = twoSum(thirdElement, i);
            if (!twoSums.isEmpty()) {
                twoSums.forEach(twoSum -> {
                    String label = "[" +
                            getMinValue(element, twoSum.getKey(), twoSum.getValue()) + ","  +
                            getMidValue(element, twoSum.getKey(), twoSum.getValue()) + ","  +
                            getMaxValue(element, twoSum.getKey(), twoSum.getValue()) + "]";
                    result.add(label);
                });
            }
        }
        System.out.println(result);
    }

    private int getMidValue(int a, int b, int c) {
        return Math.max(Math.min(a,b), Math.min(Math.max(a,b),c));
    }

    private int getMaxValue(int a, int b, int c) {
        return Math.max(a, Math.max(b, c));
    }

    private int getMinValue(int a, int b, int c) {
        return Math.min(a, Math.min(b, c));
    }

    public static void main(String args[]) {
        new Exercise9().solve();
    }
}

50 DSA-Questions: Arrays #5, #6, #7

#5. Maximum Subarray
Given an integer array nums, find the subarray with the largest sum, and return its sum.

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        // for each element: what is the largest sum that can be obtained so far?
        // by either addition or keeping the current element
        // modify num semnification to largestSum
        int max = nums[0];
        for (int i=1; i<nums.length; i++) {
            nums[i] = Math.max(nums[i], nums[i-1]+nums[i]); // replace with * for largest product
            if (max < nums[i]) {
                max = nums[i];
            }
        }
        
        return max;
    }
}

#6. La fel ca #5, dar se cere produsul.

#7. Find the Minimum in Rotated Sorted Array

Given the sorted rotated array nums of unique elements, return the minimum element of this array. You must write an algorithm that runs in O(log n) time.

public class Exercise7 {
    private final int[] ARRAY = {3,4,5,1,2}; // min = 1
    // private final int[] ARRAY = {10,12,0,4,5,7}; // min = 0
    // private final int[] ARRAY = {5,7,8,9,10}; // min = 5
    // private final int[] ARRAY = {3,4,6,7,8,9,2}; // min = 2

    private void find(int leftIndex, int rightIndex) {
        if (leftIndex == rightIndex || leftIndex + 1 == rightIndex) { // one or two elements left
            System.out.println("Min = " + Math.min(ARRAY[leftIndex], ARRAY[rightIndex]));
            return;
        }

        int mid = leftIndex + (rightIndex - leftIndex) / 2;
        if (ARRAY[leftIndex] <= ARRAY[mid] && ARRAY[mid] <= ARRAY[rightIndex]) { // sorted array
            System.out.println("Min = " + ARRAY[leftIndex]);
            return;
        }

        if (ARRAY[leftIndex] > ARRAY[mid]) { // search in left array
            find(leftIndex, mid);
            return;
        }

        find(mid+1, rightIndex); // search in right array
    }

    private void solve() {
        find(0, ARRAY.length - 1);
    }

    public static void main(String args[]) {
        new Exercise7().solve();
    }
}

50 DSA-Questions: Arrays #3, #4

#3. Contains Duplicate

Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct.

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int element : nums) {
            if (map.containsKey(element)) {
                return true;
            }
            map.put(element, 0);
        }
        return false;
    }
}

#4. Product of Array Except Self

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[I]. The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer. You must write an algorithm that runs in O(n) time and without using the division operation.

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] leftToRight = new int[nums.length];
        leftToRight[0] = 1;
        leftToRight[1] = nums[0];
        for (int i=2; i<nums.length; i++) {
            leftToRight[i] = leftToRight[i-1] * nums[i-1];
        }
        int[] rightToLeft = new int[nums.length];
        rightToLeft[nums.length-1] = 1;
        rightToLeft[nums.length-2] = nums[nums.length-1];
        for (int i=nums.length-3; i>=0; i--) {
            rightToLeft[i] = rightToLeft[i+1] * nums[i+1];
        }
        int[] result = new int[nums.length];
        for (int i=0; i<nums.length; i++) {
            result[i] = leftToRight[i] * rightToLeft[i];
        }
        
        return result;
        // O(n)
    }
}

// SAU, mai rapid:

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int[] result = new int[nums.length];
        // left to right
        result[0] = 1;
        for (int i=1; i<nums.length; i++) {
            result[i] = result[i-1] * nums[i-1];
        }
        // right to left
        int prevFactor = 1;
        for (int i=nums.length-2; i>=0; i--) {
            int value = prevFactor * nums[i+1];
            result[i] *= value;
            prevFactor = value;
        }
        
        return result;
        // O(n)
    }
}

50 DSA-Questions: Arrays #1, #2

#1. Two Sum

Given an array of integer nums and an integer target, return indices of the two numbers such that they add up to the target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int i=0; i<nums.length; i++) {
            if (!map.containsKey(nums[i])) {
                map.put(nums[i], new ArrayList<>()); // handle duplicate elements
            }
            map.get(nums[i]).add(i);
        }
        int [] indices = new int[2];
        
        for (int i=0; i<nums.length; i++) {
            int element = nums[i];
            map.get(element).remove(0);
            int key = target - element;
            if (map.containsKey(key) && !map.get(key).isEmpty()) {
                indices[0] = i;
                indices[1] = map.get(key).get(0);
                return indices; // assume exactly one solution
            }
        }
        return indices;
    }
}

#2. Best Time to Buy and Sell Stock

You are given an array of prices where prices[i] is the price of a given stock on an i-th day. You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock. Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.

class Solution {
    public int maxProfit(int[] prices) {
        int[] min = new int[prices.length];
        min[0] = prices[0];
        for (int i = 1; i < prices.length; i++) {
            min[i] = prices[i] < min[i-1] ? prices[i] : min[i-1]; // min pana la momentul i, crescator
        }
        int[] max = new int[prices.length];
        max[prices.length - 1] = prices[prices.length - 1];
        for (int i = prices.length - 2; i > 0; i--) {
            max[i] = prices[i] > max[i+1] ? prices[i] : max[i+1]; // max pana la momentul i, descrescator
        }
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            int profit = max[i] - min[i];
            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }
        return maxProfit;
    }
}

Unix/networking interview questions

Lista proceselor in executie:

> px aux

> ps -l

> ps -e

Get thread dump of running Java processes:

> jps -lv      # afla [pid] proces java

> kill -3 [pid]

GREP - cauta linii in fisier text folosind un regex

> cat file.txt | grep "Cauta un rand"

TAIL - tipareste ultimele linii dintr-un fisier (default ultimele 10)

> cat file.txt | tail -n 2

LESS - afiseaza cate o pagina (nu incarca tot)

> less file.txt

> cat file.txt | less -p "pattern"   # afiseaza de la acel rand incolo

MORE - la fel ca LESS, insa navigarea inapoi e limitata si nu are optiuni de cautare 

Diferenta TCP si UDP

TCP = transmission control protocol, bazat pe conexiune, de incredere dar mai lent, verificare buna de erori. Potrivit pt transmitere de texte, fisiere, navigare pe internet.

UDP = user datagram protocol, fara conexiune, rapid dar pierde date (nu retransmite), verificare minimala de erori, permite broadcasting. Potrivit pt transmitere continut media (video, audio), jocuri in retea.

In caz de coliziune, ruterele prefera pachetele TCP si renunta la cele UDP.

Aflare spatiu liber pe disc:

> df

Aflare marime folder

> du

Xor Linked List

O listă simplu-înlănțuită cu proprietăți de dublu-înlănțuită, care are nevoie de un singur pointer în loc de doi. 

Sună frumos în teorie, dar este inaplicabil în Java. De fapt, este o aplicație pur teoretică întrucât memoria nu mai este o problemă acum, fiind foarte ieftină. De asemenea, nu te scutește de parcurgerea întregii liste, la fel ca listele simplu-înlănțuite. Pe scurt, brain fuck for no reason, mai jos este o tentativă de implementare (netestată, pentru că... Java):

Notă: getPrev și getNext au nevoie de nodul următor respectiv anterior pentru a-și îndeplini funcția, ceea ce presupune că ai parcurs lista înainte. Doar oleacă mai flexibil, merită oare? Sau îmi scapă ceva?

public class MemEffLinkdListTest {
    Node head;

    /* Xor Linked List */

    private void initList(int length) {
        if (length < 1) {
            throw new MyBusinessException("Invalid length!");
        }

        head = new Node("A0");
        Node prev = null;
        Node current = head;

        for (int i = 1; i < length; i++) {
            Node next = new Node("A" + i);
            Node ptr = prev ^ next; // not possible in Java, we don't have access to memory addresses
            current.setPtr(ptr);

            prev = current;
            current = next;
        }
    }

    private Node getNext(Node current, Node prev) {
        return current ^ prev; // not possible in Java
    }

    private Node getPrev(Node current, Node next) {
        return current ^ next; // not possible in Java
    }

    private class Node {
        private String data;
        private Node ptr;

        public Node(String data) {
            this.data = data;
            this.ptr = null;
        }

        public void setPtr(Node ptr) {
            this.ptr = ptr;
        }

        public Node getPtr() {
            return ptr;
        }

        public String getData() {
            return data;
        }
    }
}

Angular: trimitere parametri pe route

 Fisierul de routing.ts contine calea de baza extinsa cu 2 parametri (policeReportId si source): 

{
    path: Path.POLICE_REPORT_DETAILS + '/:policeReportId',
    component: PoliceReportDetailsPage,
    canActivate: [Guard]

},
{
    path: Path.POLICE_REPORT_DETAILS + '/:policeReportId/:source',
    component: PoliceReportDetailsPage,
    canActivate: [Guard]

},

In componenta corespunzatoare caii se cauta de parametri:

constructor(private route: ActivatedRoute) {
}

ngOnInit(): void {
    if (isNotNullOrUndefined(this.route.snapshot.paramMap?.get('source'))) {
        switch (this.route.snapshot.paramMap.get('source')) {
            case RedirectSource.DECISIONS:
                // do something 
        }
    }
}

In componenta care face redirectarea se specifica parametrul suplimentar:

refreshPage(path: string): void {
    path = path + '/' + RedirectSource.DECISIONS;
    this.router.navigateByUrl('/', {skipLocationChange: true}).then(() =>
        this.router.navigate([path]));
}

P.S. a nu se uita:

<router-outlet></router-outlet>

Angular form validations triggered at field change

this.form.controls[this.FIELDS.field1].markAsTouched(); // if not touched, it won't validate although it has a value

this.form.controls[this.FIELDS.field].valueChanges.subscribe(() => {

            this.form.controls[this.field1].updateValueAndValidity();

            this.form.controls[this.field2].updateValueAndValidity();

});