CareerCup

Copy pasting here:
here's my explanation and well-commented code, hope it will help :)
Greedy: choose furthest range
0. sort by start, upon same, by end(not necessary)

find eligible intervals for start: base start = target.start
definition of eligible intervals: x is eligible if x.start <= start && x.end > start
special case: if the earliest start > start, no ans, break!!!
Among all eligible intervals, choose the one that has the furthest range
count++;
if(furthest range >= target.end) -> ans found
update start to furthest range
repeat the iteration
public static int leastMerge(List<Interval> list, Interval interval) {
//0. sort by start
Collections.sort(list, (o1, o2) -> o1.start - o2.start);
int i = 0;
int start = interval.start;
int count = 0;
while (i < list.size()) {
//special case, no way to cover
if (list.get(i).start > start) {
break;
}
int furthest = Integer.MIN_VALUE;
//1. find eligible intervals
while (i < list.size() && list.get(i).start <= start) {
if (list.get(i).end > start) { //eligible
//2. choose the one that has the furthest range
if (list.get(i).end > furthest) {
furthest = list.get(i).end;
}
}
i++;
}
count++;

if (furthest >= interval.end) return count;
//3. update start to furthest range
start = furthest;
}
return 0;
}

The solution is wrong since it ll fail for case

1 1 1 3 and target = 4.

The reason is that we 'll be missing {1, 1} while using 2 pointers. The correct approch should involve fixing each number as part of subset.

The problem cannot be reduced to knapsack since if we take a deep element from the stack, all elements above it become unavailable. This does not happen in knapsack problem.

Clear problem statement:

We are given n stacks of different sizes. We can perform k pop operations. Each operation can be done on any stack and in any order. The element popped is added to the result. What is the maximum result we can obtain after performing k operations?

EX:
S1=[1,1,100,3]
S2=[2000,2,3,1]
S3=[10,1,4]

k = 3

the maximum sum of the 3 numbers in the above stacks is 3+100+4=107.

for k = 4 the answer would have been 2000 + 2 + 3 + 1

Clear problem statement:

We are given n stacks of different sizes. We can perform k pop operations. Each operation can be done on any stack and in any order. The element popped is added to the result. What is the maximum result we can obtain after performing k operations?

EX:
S1=[1,1,100,3]
S2=[2000,2,3,1]
S3=[10,1,4]

k = 3

the maximum sum of the 3 numbers in the above stacks is 3+100+4=107.

for k = 4 the answer would have been 2000 + 2 + 3 + 1

O(klogk) approach.
geeksforgeeks.org/k-th-greatest-element-in-a-max-heap/

let dp[i][j] denote the answer if we consider first i elements of arr[] and first j elements of brr[].

if i == j then we have a single choice as we cannot put any 0. dp[i][j] = arr[i] * brr[j] + dp[i - 1][j - 1]

if j > i then it makes the condition invalid. Hence we simply put dp[i][j] = INT_MAX

for the general case, we put 0 or multiply we take min of both.

dp[i][j] = min(dp[i - 1][j - 1] + arr[i] * brr[i], dp[i - 1][j]);

former is the case wherein we choose to multiply, latter we choose to use 0.

dp[0][0] = 0;

    for(i = 1; i <= n; ++i) {
    	dp[i][0] = 0;
    }

    for(i = 1; i <= n; ++i) {
    	for(j = 1; j <= m; ++j) {
    		if(j > i) {
    			dp[i][j] = INT_MAX;
    		} else if(i == j) {
    			dp[i][j] = arr[i - 1] * brr[j - 1] + dp[i - 1][j - 1];
    		} else {
    			dp[i][j] = min(dp[i - 1][j], arr[i - 1] * brr[j - 1] + dp[i - 1][j - 1]);
    		}
    	}
    }

    return dp[n][m];

Simple:

class FreqStack {
public:
    map<int, int> base;
    map<int, stack<int> > freq;
    int maxF;
    FreqStack() {
        maxF = 0;
    }
    
    void push(int x) {
        base[x]++;
        int f = base[x];
        freq[f].push(x);
        maxF = max(maxF, f);
    }
    
    int pop() {
        int x = freq[maxF].top();
        freq[maxF].pop();
        base[x]--;
        if(freq[maxF].empty()) {
            maxF--;
        }
        return x;
    }
};

leetcode.com/problems/maximum-frequency-stack/

Read about NIM's game.

leetcode.com/problems/the-skyline-problem/discuss/719637/C%2B%2B-Solution-or-Sets-Does-it-All-or-O(NlogN)

leetcode.com/problems/the-skyline-problem/

simple

Simple Z.

public static int[] computeZ(String s) {
    int l = 0; r = 0;
    int [] Z = new int[len];
    int len = s.length();
    for (int k =0 ; k < len; k++ ) {
        int j;
        if (k < r) {
            j = (z[k-l] < (r-k)) ? z[k-l] : (r-k)
        } else {
            j = 0;
        }
        while (k + j < len) {
            if (s.charAt(k+j) == s.charAt(j)) {
                j++;
            } else {
                break;
            }
        }
        if (k + j > r) {
            l = k;
            r = k + j;
        }
    }
    Z[0] = len;
    return Z;
}

Use a maximum heap to store the countries, poll one country's player count each round and decrease by 1.
If there are players left, add the country back after this round (Note⚠️: not add it immediately after the poll, or it might be counted more than once in a single round).
If the size of heap is less than k, return the number of rounds.

public int maxNumberOfTeams(int[] countries, int k) {
        if (countries == null || countries.length == 0 || k <= 0) return 0;
        PriorityQueue<Integer> candidatePool = new PriorityQueue<>(((o1, o2) -> o2 - o1));
        for (int country : countries) {
            if (country <= 0) return -1;// Invalid input should be warned
            candidatePool.offer(country);
        }
        int res = 0;
        Stack<Integer> stack = new Stack<>();
        while (candidatePool.size() >= k) {
            for (int i = 0; i < k; i++) {
                int country = candidatePool.poll();
                if (--country > 0) stack.push(country);
            }
            while (!stack.empty()) candidatePool.offer(stack.pop());
            res++;
        }
        return res;
    }

*copied from leet code

Idea is to calculate the number of subsets at including the ith element.

int ans = 0
for(i = 0; i < n; ++i) {
	for(j = i; j >= 0; --j) {
	    int m = arr[i];
	    int M = arr[j];
	    if(m + M <= K) {
            ans += pow(2, j + 1) - 1;
            break;
	    }
	}
}

Solved here:
geeksforgeeks.org/k-numbers-difference-maximum-minimum-k-number-minimized/

Simple BFS with bitmask will work here. Let 1 represents black and 0 represents white.
We need to reach the state (0,0,0) all white from given state (x,y,z).

We can use binary search to process multiple queries efficiently i.e O(logn). But before that, we ll sort the ranges based on starting element. For a given number, we ll check if that number is greater than the middle range last element or lesser than middle range's first element. We ll recure that way. If it is in the mid range then we simply return the range value.

We may use the cantor function to solve this:
en.wikipedia.org/wiki/Pairing_function

The problem can be solved using DSU. DSU will give if a path exists between 2 nodes in almost constant time. Hence the problem can be solved O(K.M)

The problem should be:
"given a bunch of arrays having all unique elements. Find out the shortest common super sequence of em."

This can be solved using topological sorting.

If we don't include the shortest common super sequence then the answer to this will simply be the concatenation of the arrays. If elements are not unique then the answer ll be closely related to LCS of n strings, which is very inefficient.

Based on the question description we see that we need to consider only those integers whose value is = k since elements with value > k and value < k are rejected. So if some window has value k then answer is k else answer is 0. So the problem changes to check each window if it has k in it or not. To do so we can just keep a running window and store the last occurrence of k. Following is the code:

vector<int> average(vector<int> stream, int k, int w) {
	int i, p = 0;
	int n = stream.size();
	int lastIndexOfK = -1;
	vector<int> ans;
	for(i = 0; i < n; ++i) {
	   int p = i % w;
       if(stream[i] == k) {
           lastIndexOfK = p;
       }
       if(lastIndexOfK > p || (lastIndexOfK == 0 && p == 0)) {
          lastIndexOfK = -1;
       }
       if(lastIndexOfK != -1) {
           ans.push_back(k);
       }
	}
	return ans;
}

Solution to 1:

let n be the length of both strings.

if the substring of first string from 0 to n / 2 and reverse of the substring of second index from n / 2 to n is same then answer is yes else no.

Solution to 2:
if first character of first string is same as last character of the second string then ans is yes else no. Why?

Solution to 3:
If both strings have atleast one common character then ans is yes else no. Why?

We can record the timestamp / operation number of each of the operation. With that said we will store the last time setAllTrue was executed and last time setAllFalse was executed. Also we store the last time particular index was updated. We can compare the time to get the value at that index.

vector<bool> arr(n);
vector<int> lastUpdatedAt;
int op = 0;
int lastSetTrue, lastSetFalse;

void setTrue(int i) {
    op++;
	arr[i] = true;
	lastUpdatedAt[i] = op;
}

void setFalse(int i) {
    op++;
	arr[i] = false;
	lastUpdatedAt[i] = op;
}

void setAllTrue() {
	op++;
	lastSetTrue = op;
}
void setAllFalse() {
	op++;
	lastSetFalse = op;
}


bool get(int i) {

    if(lastUpdatedAt[i] < lastSetTrue && lastUpdatedAt[i] < lastSetFalse) {
        return lastSetTrue > lastSetFalse;
    }
    if(lastUpdatedAt[i] < lastSetTrue) {
        return true;
    }
    if(lastUpdatedAt[i] < lastSetFalse) {
        return false;
    }
    return arr[i];
}

}

We can use a regular STL map to store the score for each player.
Next, we define a custom map using AVL tree and ll expose another operation to find the kth element in it. This operation can be implemented in O(log N) time since the AVL tree is always balanced. Link:
geeksforgeeks.org/find-k-th-smallest-element-in-bst-order-statistics-in-bst/

The problem can be solved using a deque or a stack. I am taking a deque here. The idea is to maintain a deque and elements in the deque will hold lexicographically smallest, subsequence till that point of time. The incoming element ll keep popping the elements from the back of the until it is greater than the last element of deque and number of remaining elements + number of elements currently in the deque are >= k

vector<int> smallestLexo(vector<int> s, int k) {
    deque<int> dq;
    for(int i = 0; i < s.size(); i++) {
        while(!dq.empty() && s[i] < dq.back() && (dq.size() + (s.size() - i - 1)) >= k) {
            dq.pop_back();
        }
        if(dq.size() < k) {
            dq.push_back(s[i]);
        }
    }
    return vector<int> (dq.begin(), dq.end());
}

The first part can be solved using BFS from source. For second part running BFS from all source nodes ll be inefficient. To solve this we ll do a multi-source BFS. More information about it can be seen here:
geeksforgeeks.org/multi-source-shortest-path-in-unweighted-graph/

I ll first rephrase the question:
Given an array having 0s and 1s representing the seats. 1 means that the seat is occupied while 0 means it is vacant. Let's define the distance between 2 points

i

and

j

as

|i - j|

. We need to insert a new 1 until all the places are full. The point where 1 is inserted should be at the farthest from its nearest point. For example if the array is

000101

then next 1 will be placed at index 1 (assume 1 based indexing) since its distance from the nearest 1 is max, 3 in this case. After this the array ll be 100101, now next 1 can be inserted at any index since the distance from the nearest 1 ll always be 1. Hence we need to return [1,2,3,4]. Of course, there can be multiple answers. I assume we need to return anyone.


To solve this we make an observation, between 2 ones at i and j, the next one can be placed at a distance of abs(i - j) / 2 from either one. This is because this will be the maximum point from either of the 1s. We ll use this fact to reach the solution.

For each consecutive 1s (lets say i and j) we ll make 2 pairs -> pair<distance, index> where distance is (i + j) / 2 and index is i and j. For example for array:

110001

between one at index 2 and one at index 6 we ll make 2 pairs. The distance between the 2 is 4. So element ll be inserted at 2 distance from either. The 2 pairs ll be

<2, 1> <2, 6>. Likewise, we ll do for all consecutive ones. We ll insert all the pairs in a max heap. (the pairs ll be sorted based on the distance)

Now we know the distance each new one ll go to from each index. We ll keep popping the elemets till heap is not empty. The max element will be popped out and we ll add it's distance in the result array. But once the max distance pair is popped out, we know the entry point of the new one. Now we ll insert 2 new pairs based on the new entry. Of course, there won't be any insertions if there is no 0 between inserted one and the previous one. The cases to handle are the leftmost and the rightmost ones. We can treat those separately in the heap by making 0 and n + 1 handle their distance separately.

Can you please give the link to solution?

The logic of the problem is a mere extension of the diameter of the tree. We will apply the same dp state as that of diameter with an additional check of if the current node has the same color as that children.

int finalAns = 0;
pair<int, int> foobar(int[][] tree, int[] col, int root, int parent) {
vector<int> childDiameters;
for(int node : tree[root]) {
if(node != parent) {
continue;
}
pair<int, int> colorDiameter = foobar(tree, col, node, root);
int color = colorDiameter.first;
int diameter = colorDiameter.second;
if(color == col[root]) {
childDiameters.push_back(diameter);
}
}
sort(childDiameters.rbegin(). childDiameters.rend());
int ans = 0;
for(i = 0; i < min(2, childDiameters.size()); ++i) {
ans += childDiameters[i];
}
finalAns = max(finalAns, ans + 1);
return {col[root], childDiameters.size() == 0 ? 0 : childDiameters[0]};
}

The logic of the problem is a mere extension of the diameter of the tree. We will apply the same dp state as that of diameter with additional check of if the current node has same color as that children.

{{
int finalAns = 0;
pair<int, int> foobar(int[][] tree, int[] col, int root, int parent) {
vector<int> childDiameters;
for(int node : tree[root]) {
if(node != parent) {
continue;
}
pair<int, int> colorDiameter = foobar(tree, col, node, root);
int color = colorDiameter.first;
int diameter = colorDiameter.second;
if(color == col[root]) {
childDiameters.push_back(diameter);
}
}
sort(childDiameters.rbegin(). childDiameters.rend());
int ans = 0;
for(i = 0; i < min(2, childDiameters.size()); ++i) {
ans += childDiameters[i];
}
finalAns = max(finalAns, ans + 1);
return {col[root], childDiameters.size() == 0 ? 0 : childDiameters[0]};
}

}}

Question 1 and question 2 are easy. Just simple BFS will do the trick.
Now comes the third part. For that let we define dp[x][y][z] where the value of z is either 0 or 1. Value 0 means that the path till (x,y) does not have a toggled bit while 1 means that path till (x, y) have some bit toggled. If the bit is toggled, then we cannot toggle it again, while if the bit is not toggled we can move ahead by toggling it or not toggling it.

Instead of pushing coordinate (x, y) in the queue we will now push (x, y, 0/1). 0 will denote (x, y) is visited via normal bfs while 1 will denote it is visited by toggled path.

Now we start the bfs from source and visit neighboring cells. Let's say we are at (x1, y1) and we are looking at (x2, y2). Now there are only possibilities. (x2, y2) is 0 or (x2, y2) is 1. If (x2, y2) is 0 then we continue our normal bfs by inserting (x2, y2, 0) and update dp[x2][y2][0], but if (x2, y2) is 1 then we will first see if (x1, y1) has been through a toggled path or not. If it is from a toggled path then we dont visit (x2, y2) while if it is not then we update dp[x2][y2][1] and insert (x2, y2, 1).

final ans will be min of dp[dx][dy][0] and dp[dx][dy][1]