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)).

public class Exercise11 {
    private final Integer[][] MATRIX = {{1,1,1},{1,0,1},{1,1,1}}; // 1 <= m, n <= 200
    // private final Integer[][] MATRIX = {{1,0,1,1},{1,1,1,1},{1,1,1,0}};
    // private final Integer[][] MATRIX = {{1,1,2,4},{3,1,9,3},{7,0,8,1}};

    private void showMatrix(long mask, String label) {
        System.out.println(label);
        for (int i=0; i< MATRIX.length; i++) {
            System.out.print("[ ");
            for (int j=0; j<MATRIX[i].length; j++) {
                int elem = getBitAt(mask, i, j) > 0 ? MATRIX[i][j] : 0;
                System.out.print(elem + " ");
            }
            System.out.println("]");
        }
        System.out.println();
    }

    private long clearBitAt(long mask, int i, int j) {
        int pos = i * MATRIX[0].length + j;
        int clearMask = ~ (1 << pos);
        return clearMask & mask;
    }

    private long getBitAt(long mask, int i, int j) {
        int pos = i * MATRIX[0].length + j;
        return mask & (1 << pos);
    }

    private long setZerosFor(long mask, int posI, int posJ) {
        for (int i=0; i<MATRIX.length; i++) {
            mask = clearBitAt(mask, i, posJ);
        }
        for (int j=0; j<MATRIX[0].length; j++) {
            mask = clearBitAt(mask, posI, j);
        }
        return mask;
    }

    private void solve() {
        // matrix has a initial mask (number), where each bit is 0 if element = 0, else 1
        long mask = (long) Math.pow(2, MATRIX.length * MATRIX[0].length) - 1;
        showMatrix(mask, "Initial:");

        for (int i=0; i<MATRIX.length; i++) {
            for (int j=0; j<MATRIX[0].length; j++) {
                if (MATRIX[i][j] == 0) {
                    mask = setZerosFor(mask, i , j);
                }
            }
        }
        showMatrix(mask, "After Zeros set:");

        // O(1) space complexity
    }

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

50 DSA-Questions: #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: #5, #6, #7

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

public class Exercise5 {
    // private final int[] ARRAY = {-2, 1, -3, 4, -1, 2, 1, -5, 4}; // largest subarray sum is 6; [4,-1,2,1]
    private final int[] ARRAY = {5, -9, 1, -2, 8, 0, 4}; // largest subarray sum is 12; [8,0,4]

    private void solve() {
        if (ARRAY.length == 0) {
            System.out.println("N/A");
            return;
        }

        if (ARRAY.length == 1) {
            System.out.println(ARRAY[0]);
            return;
        }

        // for each element: what is the largest sum that can be obtained so far?
        // by either addition or keeping the current element
        Integer[] largestSum = new Integer[ARRAY.length];
        largestSum[0] = ARRAY[0];
        for (int i=1; i<ARRAY.length; i++) {
            largestSum[i] = Math.max(ARRAY[i], largestSum[i-1]+ARRAY[i]); // replace with * for largest product
        }

        int max = largestSum[0];
        for (int i=1; i<largestSum.length; i++) {
            if (max < largestSum[i]) {
                max = largestSum[i];
            }
        }
        System.out.println("Largest sum = " + max);
    }

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

#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: #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.

public class Exercise3 {
    private final Integer[] NUMS = {5,2,21,8,4,12,9,19,1,13};

    private void solve() {
        Map<Integer, Integer> map = new HashMap<>();
        for (int element : Arrays.asList(NUMS)) {
            if (map.containsKey(element)) {
                System.out.println("True");
                return;
            }
            map.put(element, 0);
        }
        System.out.println("False");
    }

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

#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.

public class Exercise4 {
    // private final Integer[] NUMS = {1,2,3,4};
    // private final Integer[] NUMS = {2,5,4,3,5};
    private final Integer[] NUMS = {0};

    private void solve() {
        if (NUMS.length <= 1) {
            System.out.println("Result N/A");
            return;
        }

        Integer[] leftToRight = new Integer[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];
        }

        Integer[] rightToLeft = new Integer[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];
        }

        Integer[] result = new Integer[NUMS.length];
        for (int i=0; i<NUMS.length; i++) {
            result[i] = leftToRight[i] * rightToLeft[i];
        }
        System.out.println("Result = " + Arrays.asList(result));
        // O(n)
    }

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

50 DSA-Questions: #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.

public class Exercise1 {
    private final Integer[] ARRAY = {0, 1, 2, 4, 6, 7, 8, 9, 15};
    private final int TARGET = 10;

    private void solve() {
        Map<Integer, Integer> map = new HashMap<>();
        List<Integer> list = Arrays.asList(ARRAY);
        for (int element : list) {
            map.put(element, list.indexOf(element));
        }
        for (int element : list) {
            int key = TARGET - element;
            if (map.containsKey(key)) {
                System.out.println("[" + map.get(element) + "," + map.get(key) + "]");
                map.remove(element);
                map.remove(key);
            }
        }
    }

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

#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.

public class Exercise2 {
    // private final Integer[] PRICES = {7,1,5,3,6,4}; // prices on i-th day
    private final Integer[] PRICES = {5,2,21,8,4,2,12,5,9,19,1,13}; // prices on i-th day

    // Return max profit (buy min possible & sell max possible)
    private void solve() {
        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];
        }

        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];
        }

        int maxProfit = 0;
        for (int i = 1; i < PRICES.length; i++) {
            int profit = max[i] - min[i];
            if (profit > maxProfit) {
                maxProfit = profit;
            }
        }

        System.out.println("max profit = " + maxProfit);
        // O(n)
    }

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

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