Given an array N, return true if it is possible we can pair all the numbers in the array with equal values. E.g N = [1, 2, 2, 1] -> true as we can pair (N[0], N[3]) and (N[1], N[2]). N = [7, 7, 7] would return false.
find_min function is implemented wrongly (the function was implemented to always return 0), write a function to return a counter example array of size n that when passed to find_min will always return a wrong answer. E.g n = 4, [100, 500, 200, 300].
Given a string s, find the minimum number of substrings you can create without having the same letters repeating in each substring.
E.g world -> 5, as the string has no letters that occur more than once.
dddd -> 4, as you can only create substring of each character.
abba -> 2, as you can make substrings of ab, ba.
cycle-> 2, you can create substrings of (cy, cle) or (c, ycle)
Hope this helps someone out there! I passed my OA. Now preparing for my onsite in a month. If you guys have any resources I can refer to as I prepare for my onsite, I'd greatly appreciated.
P.S This community is awesome!!!!
My exp: don't to the OTS (the online Assessment). They have some crazy questions and time for 3 question is 1 hour (2-4 yoe) and 1.5 hour (4-6 yoe).
Pick the Phone screen, you can share more information and idea with interviewer, then improve your alg (just one) in 45 mins -> this is the best choice
======
Debugging
Given an array of nums, determine the final sign of the product of all numbers in the array.
Multiple choice questions - 8 of them. this was quite time consuming and tricky imo.
https://leetcode.com/problems/count-good-nodes-in-binary-tree/ - straight from LC.
https://leetcode.com/discuss/interview-question/555702/Microsoft-or-Online-Codility-Assessment-or-Counterexample-(Task-1)/486118
Debugging
Given an array of nums, determine the final sign of the product of all numbers in the array.
Multiple choice questions - 8 of them. this was quite time consuming and tricky imo.
https://leetcode.com/problems/count-good-nodes-in-binary-tree/ - straight from LC.
Edit:
https://leetcode.com/discuss/interview-question/525982/Microsoft-or-OA-2020-or-Fair-Indexes
=======
MCQ questions: 2 where algorithms & data structures. The other one was a what's the output of a code block
Given an array of coins [1,0,1,1] representing tails and heads get the minimum number of flips required so no two adjacent coins have the https://leetcode.com/problems/minimum-changes-to-make-alternating-binary-string/
face
public int flips(int[] in) {
int f = 1;
int nf = 0;
for (int i = 1;i<in.length;i++) {
int curr = in[i];
int prev = in[i-1];
if (curr != prev) {
f++;
} else {
int t = f;
f = nf + 1;
nf = t;
}
}
return Math.min(f,nf);
}
Given a string S. Deletion of the K-th letter of S costs C[K]. After deleting a letter, the costs of deleting other letters do not change. You want to delete some letters from S to obtain a string without two identical letters next to each other. What is the minimum total cost of deletions to achieve such a string? Example: Given S = "aabbcc" and C = [1, 2, 1, 2, 1, 2], the function should return 3.
https://leetcode.com/problems/minimum-deletion-cost-to-avoid-repeating-letters/
===
m Aligned subset
===
May 2022
There are 2 wooden sticks of length A and B. Each of them can be cut into shorter sticks of integer length. Our goal is to construct the largest possible square. In order to do this, we want to cut the sticks in such a way as to achieve four sticks of the same length (there can be some leftover). What is the longest side of the square that we can achieve?
Eg; A=10,B=21 Output = 7. 10+21//4=7 Binary search from 0.....7 to get larger number. (Similar to https://leetcode.com/problems/koko-eating-bananas/)
https://leetcode.com/discuss/interview-question/1774669/largest-possible-square-for-cut-sticks
int solution (int A, int B)
{
if(A > B) swap(A,B);
if (A+B<=3) return 0;
if (B/4 > A) return B/4;
else if (B/3 >= A) return A;
else if (B/3<A) return max(A/2, B/3 );
return 0;
Game of dominoes has 28 domino tiles. each tile would have between 0-6 dots. Tiles can be reversed and used. Given list of N dominos tiles, find any tile that isn't on a list.
Eg; ["0-0","0-1","2-3","2-0"] One of many possible output = "0-3".
0-0 0-1 1-0 2-3 3-2 2-0 0-2 return anything except this. Create set and store all possibilities. Remove the one given and also remove the reversed version. Then randomly select anything and return
def getMissingTile(dominos):
possibilities = set("%i-%i" % (i, j) for i in range(0, 6 + 1) for j in range(0, 6 + 1))
for dom in dominos:
if dom in possibilities:
possibilities.remove(dom)
rev = dom[::-1]
if rev in possibilities:
possibilities.remove(rev)
if len(possibilities) == 0:
return None
else:
return possibilities.pop()
===
An infrastructure consisting of N cities, from 1 to N and M bidirectional roads between them is given. Roads do not intersect apart from their start and end points. Netwrok rank is defined as the total number of roads that are connected to either of the two cities. Return the maximal network rank. (This is similar but not same as https://leetcode.com/problems/maximal-network-rank/)
Eg: A=[1,2,3,3] B=[2,3,1,4]N=4 Output = 4
Create adjacency list from A->B and B->A. Dictionary would look like
{
1=[2,3],
2=[1,3],
3=[2,1,4],
4=[3]
}
Traverse through A and B and get network rank of each of them and keep track of maximum.
Network rank of 1<->2 = 3 (network rank of 1 is 2 (as the len of 1 in dictionary is 2) + network rank of 2 is 2 - 1(as this is bidirectional road, the same road shouldn't be counted again))
Network rank of 2<->3 = 4 (2+3-1)
Network rank of 3<->1 = 4 (3+2-1)
Network rank of 3<->4 = 2 (3+1-1)
Maximum is 4
int solution(const vector&A, const vector&B, int N){
int roads_num = A.size(); // M
vector cities(N + 1, 0);
// count number of roads to the pair of cities
for(int i = 0; i < roads_num; ++i) {
cities[A[i]]++;
cities[B[i]]++;
}
int result = INT_MIN;
// Find maximum number of roads connected to the pair
// of cities except the road between these two cities
// because it was counted twice for each city.
for(int i = 0; i < roads_num; ++i) {
result = max(result, cities[A[i]] + cities[B[i]] - 1);
}
return result;
}
Rearrange digits of a given non negative number to get the largest number possible. If result exceeds 10^9 , return -1.
Input: 567, Output 765; Input 299, Output 992; Input Int.Max, Output -1.
b. A slightly simpler version of a monotonic stack question - Trapping Rain Water.
===
dec 2021
Heaters
https://leetcode.com/problems/heaters/
https://leetcode.com/problems/find-median-from-data-stream/
Find Median from Data Stream that requires add() and get() function less than o(n) complexity, the input can be any number unlike (-100, 100).
Reorder List
https://leetcode.com/problems/reorder-list/
Merge Two Sorted List (You may also meet Merge K Sorted List)
Implement a Singleton that is thread safety.
https://leetcode.com/problems/merge-two-sorted-lists/
===
given an array arr of n positive integers returns 1 if arr contains at least two items which differ by 1 otherwise 0.
===
Find the number of nodes on the longest distinct path that starts at the root in a binary tree.
====
sept 2022
given a string s give the minimum amount of substrings without repeting characters, for example
"word" the answer will be 1 as "word" dont have any duplicate
"dddd" the answer will be 4 as we can only form "d" "d" "d" "d"
"cycle" the answer will be 2 as we can make "cy" "cle"
frog game - given an array blocks where each cell represents the height of the current block, we have two frogs starting on the same block (what ever block) . The frog can only jump to another adjacent block if it is higher or equal to the one she is on. return the max distance that can be between the two frogs if they can start together on any block, for example:
[9,2,5,3,0] the answer will be 2, let the two frogs start on cell 4 and one of them go to cell 2. ( there is another option here that will give you 2)
[1,2,3,4,5,8] the answer will be 6, if both frogs starts at cell 5.
questions.
https://leetcode.com/problems/minimum-moves-to-equal-array-elements-ii/
https://leetcode.com/problems/find-n-unique-integers-sum-up-to-zero/
(variation of https://leetcode.com/problems/number-of-steps-to-reduce-a-number-in-binary-representation-to-one/):
Given the binary representation of an integer as a string s, return the number of steps to reduce it to 0 under the following rules:
If the current number is even, you have to divide it by 2.
If the current number is odd, you have to subtract 1 from it.
==
May 27 2022 oa drive:
There are N transfers between two banks. Lets Asume Bank A and Bank. You are given a string with only A and B. A shows transfer made from B to A and B shows transfer made A to B.
You are given one array of integers for transfers. You have to tell minimum initial balance required to complete all transactions.
Q2 - There are two strings of size N. We can create fragments from these strings. Rule of fragments are as below -
- Fragments should start from same position from both the string
- both string fragments should have same character but character can be ra-arranged.
We return the count of such fragments.
===
SENIOR SE
gave my online assessment test on Jul 13 . 2 questions total time = 70 mins.
https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/
you are playing a game and rolling the dice. You remembers some results which is in the form of array N. you forgot some results(Array) which is F. But you remember the arithmetic mean of all results combined as M. Find missing set of F.
Find all entries that can be missing.
Example: Given an array [3,5,4,4] , F=2 , M = 4,
F could be [4,4], [2,6] . you can return any one of this.
Answer: This problem is very much similar with
https://leetcode.com/problems/combination-sum-iii/ with some updates .
But you need to first convert problem in this manner
Here , we need to formulate the k, Sum needed to generate combinations of numbers from dice which has options[1,2,3,4,5,6]
k = M*(N.length+F.length)-sum(N)
no we have K as sum we are looking for and we have F.length as total numbers in a set we are looking for and have options[1,2,3,4,5,6]. This becomes problem similar to https://leetcode.com/problems/combination-sum-iii/
===
2021
given two arrays of integers A and B, returns the number of fair indexes such that the sum on either side of the index in both arrays are equal
Maximum count of pairs which generate the same sum
public int MaximumSum(int[] A) {
// write your code here
Map<Integer, int[]> map = new HashMap<>();
for (int a : A) {
int s = 0, tmp = a;
while (tmp > 0) {
s += tmp % 10;
tmp /= 10;
}
map.putIfAbsent(s, new int[2]);
int[] nums = map.get(s);
if (a > nums[0]) {
nums[1] = nums[0];
nums[0] = a;
} else if (a > nums[1]) {
nums[1] = a;
}
}
int res = -1;
for (int[] nums : map.values()) {
if (nums[1] == 0) {
continue;
}
res = Math.max(res, nums[0] + nums[1]);
}
return res;}
===
Jan 30 2022
====
Sep 2022
The algorithm takes in input a vector of integer sorted in a non-decreasing order and an integer K. The algorithm returns true if the vector contains only and all the numbers between 1 and k at least once, and false otherwise:
([1,1,2,3,3,4],4) --> true
([1,1,3],3) --> false
This was the implementation:
bool algorithm(vector &A, int k)
{
n = A.size();
for(int i = 0; i < n-1; i++)
{
if(A[i]+1 < A[i+1])
return false;
}
if(A[0] != 1 && A[n-1] != K)
{
return false;
}
else
{
return true;
}
}
and 2) OCR text can sometime cannot read character from source, so it will be replaced with question mark "?"
for example, apple can be translated as a??le by OCR because two p characters are unreadable.
for example, aaaaaaaaaaaaa can be ?????????????
but to save space it is interpret as a13
given two ocr texts, compare if they COULD be equal
a2le and app?e are equal
===
questions 70 mins.
https://leetcode.com/problems/minimum-deletions-to-make-character-frequencies-unique/
https://leetcode.com/problems/find-missing-observations/
===
grid game
class Solution {
public:
long long gridGame(vector& grid) {
int N = grid[0].size();
vector right(N + 1);
for (int i = N - 1; i >= 0; --i) right[i] = right[i + 1] + grid[0][i];
long long left = 0, ans = LONG_MAX;
for (int i = 0; i < N; ++i) {
ans = min(ans, max(left, right[i + 1]));
left += grid[1][i];
}
return ans;
}
};