Arrays & Strings Flashcards
Write a function to return a hint according to the secret number and friend’s guess, use A to indicate the bulls and * B to indicate the cows.
Please note that both secret number and friend’s guess may contain duplicate digits.
Example 1:
Input: secret = “1807”, guess = “7810”
Output: “1A3B”
Explanation: 1 bull and 3 cows. The bull is 8, the cows are 0, 1 and 7.
Example 2:
Input: secret = “1123”, guess = “0111”
Output: “1A1B”
Explanation: The 1st 1 in friend’s guess is a bull, the 2nd or 3rd 1 is a cow.
Note: You may assume that the secret number and your friend’s guess only contain digits, and their lengths are always equal.
const getHint = (secret, guess) => {
let bulls = 0;
let cows = 0;
const count = Array(10).fill(0);
for (let i = 0; i < secret.length; i++) {
if (secret[i] === guess[i]) {
bulls++;
} else {
if (count[secret[i] - ‘0’] < 0) cows++;
if (count[guess[i] - ‘0’] > 0) cows++;
count[secret[i] - '0']++; count[guess[i] - '0']--; } }
return ${bulls}A${cows}B;
};
export { getHint };
Write a function, isPrime, that takes in a number as an argument. The function should return a boolean indicating whether or not the given number is prime.
A prime number is a number that is only divisible by two distinct numbers: 1 and itself.
For example, 7 is a prime because it is only divisible by 1 and 7. For example, 6 is not a prime because it is divisible by 1, 2, 3, and 6.
You can assume that the input number is a positive integer.
test_00:
isPrime(2); // -> true
test_01:
isPrime(3); // -> true
const isPrime = (n) => {
if (n < 2) return false;
for (let i = 2; i <= Math.sqrt(n); i += 1) {
if (n % i === 0) return false;
}
return true;
};
n = input number
Time: O(square_root(n))
Space: O(1)
Explanation:
If a number n is not a prime, it can be factored into two factors a and b:
n = a * b
Now a and b can’t be both greater than the square root of n, since then the product a * b would be greater than sqrt(n) * sqrt(n) = n. So in any factorization of n, at least one of the factors must be smaller than the square root of n, and if we can’t find any factors less than or equal to the square root, n must be a prime.
uncompress
Write a function, uncompress, that takes in a string as an argument. The input string will be formatted into multiple groups according to the following pattern:
for example, ‘2c’ or ‘3a’.
The function should return an uncompressed version of the string where each ‘char’ of a group is repeated ‘number’ times consecutively. You may assume that the input string is well-formed according to the previously mentioned pattern.
test_00:
uncompress(“2c3a1t”); // -> ‘ccaaat’
test_01:
uncompress(“4s2b”); // -> ‘ssssbb’
const uncompress = (s) => {
let result = [];
const numbers = '0123456789';
let i = 0;
let j = 0;
while (j < s.length) {
if (numbers.includes(s[j])) {
j += 1;
} else {
const num = Number(s.slice(i, j));
for (let count = 0; count < num; count += 1) {
result.push(s[j]);
}
j += 1;
i = j;
}
}
return result.join('');
};
n = number of groups
m = max num found in any group
Time: O(nm)
Space: O(nm)
compress
Write a function, compress, that takes in a string as an argument. The function should return a compressed version of the string where consecutive occurrences of the same characters are compressed into the number of occurrences followed by the character. Single character occurrences should not be changed.
‘aaa’ compresses to ‘3a’
‘cc’ compresses to ‘2c’
‘t’ should remain as ‘t’
You can assume that the input only contains alphabetic characters.
test_00:
compress(‘ccaaatsss’); // -> ‘2c3at3s’
test_01:
compress(‘ssssbbz’); // -> ‘4s2bz’
const compress = (s) => {
let result = [];
let i = 0;
let j = 0;
while (j <= s.length) {
if (s[i] === s[j]) {
j += 1;
} else {
const num = j - i;
if (num === 1) {
result.push(s[i]);
} else {
result.push(String(num), s[i]);
}
i = j;
}
}
return result.join(‘’);
};
n = length of string
Time: O(n)
Space: O(n)
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
Example 1:
Input: nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
var nextGreaterElement = function(nums1, nums2) {
let nextGreatest = new Map();
let stack = [];
//Loop through nums2 to build a hashmap to find next greatest element for each element
for(let num of nums2){
//We first do a check
//If previous el in stack is less than the current num, then we found the nextGreatest el for the prev
if(stack.length !== 0 & stack[stack.length - 1] < num){
nextGreatest.set(stack.pop(), num);
}
stack.push(num);
}
//Loop through nums1 and modify nums1
for(let i = 0; i < nums1.length; i++){
nums1[i] = nextGreatest.has(nums1[i]) ? nextGreatest.get(nums1[i]) : -1;
}
return nums1;
};
console.log(nextGreaterElement([4, 1, 2], [1, 3, 4, 2]));
Given two strings s and goal, return true if and only if s can become goal after some number of shifts on s.
A shift on s consists of moving the leftmost character of s to the rightmost position.
For example, if s = “abcde”, then it will be “bcdea” after one shift.
Example 1:
Input: s = “abcde”, goal = “cdeab”
Output: true
Example 2:
Input: s = “abcde”, goal = “abced”
Output: false
function rotateString(A, B){
if(A.length !== B.length) return false;
if(A.length === 0 && B.length === 0) return true;
//Create a double version of string by concatenating, "abcdeabcde" A = A + A;
//String will be in String A at some point return A.includes(B);
}
console. log(rotateString(“abcde”, “cdeab”)); // true
console. log(rotateString(“abcde”, “abced”)); // false
paired parentheses:
Write a function, pairedParentheses, that takes in a string as an argument. The function should return a boolean indicating whether or not the string has well-formed parentheses.
You may assume the string contains only alphabetic characters, ‘(‘, or ‘)’.
test_00:
pairedParentheses(“(david)((abby))”); // -> true
test_01:
pairedParentheses(“()rose(jeff”); // -> false
const pairedParentheses = (str) => {
// todo
let count = 0;
for(let i=0; i < str.length; i++){
//Only increment openers
if(str[i] === "(") count++;
//Decrement closers
if(str[i] === ")") {
//guarding against extra closers
if (count === 0){
return false;
}
count -= 1;
}
}
return count === 0;
};
Time Complexity: O(n)
Space Complexity: O(1)
befitting brackets:
Write a function, befittingBrackets, that takes in a string as an argument. The function should return a boolean indicating whether or not the string contains correctly matched brackets.
You may assume the string contains only characters: ( ) [ ] { }
test_00:
befittingBrackets('(){}[](())'); // -> true
test_01:
befittingBrackets('({[]})'); // -> true
test_02:
befittingBrackets('[][}'); // -> false
const befittingBrackets = (str) => {
const stack = [];
const brackets = {
'(': ')',
'[': ']',
'{': '}'
};
for (let char of str) {
if (char in brackets) {
//push closing bracket
stack.push(brackets[char]);
} else {
//finding matching opening bracket once a closing bracket is reached
if (stack.length > 0 && stack[stack.length - 1] === char) {
stack.pop();
} else {
return false;
}
}
}
//leftover items in stack means we have dangling brackets return stack.length === 0; }; n = length of string Time: O(n) Space: O(n)
decompress braces:
Write a function, decompressBraces, that takes in a compressed string as an argument. The function should return the string decompressed.
The compression format of the input string is ‘n{subString}’, where the subString within braces should be repeated n times.
You may assume that every number n is guaranteed to be an integer between 1 through 9.
You may assume that the input is valid and the decompressed string will only contain alphabetic characters.
test_00:
decompressBraces("2{q}3{tu}v");
// -> qqtututuv
test_01:
decompressBraces("ch3{ao}");
// -> chaoaoao
test_02:
decompressBraces("2{y3{o}}s");
// -> yoooyooos
const decompressBraces = (s) => {
const nums = '123456789';
const stack = [];
for (let char of s) {
if (nums.includes(char)) {
stack.push(Number(char));
} else {
if (char === '}') {
let segment = '';
while (typeof stack[stack.length - 1] !== 'number') {
const popped = stack.pop();
segment = popped + segment;
}
const number = stack.pop();
stack.push(repeat(segment, number));
} else if (char !== '{') {
stack.push(char);
}
}
}
return stack.join(‘’);
};
const repeat = (str, n) => {
let result = '';
for (let i = 0; i < n; i += 1) {
result += str;
}
return result;
};
s = length of string
m = count of brace pairs
Time: O((9^m) * s)
Space: O((9^m) * s)
nesting score:
Write a function, nestingScore, that takes in a string of brackets as an argument. The function should return the score of the string according to the following rules:
[] is worth 1 point
XY is worth m + n points where X, Y are substrings of well-formed brackets and m, n are their respective scores
[S] is worth 2 * k points where S is a substring of well-formed brackets and k is the score of that substring
You may assume that the input only contains well-formed square brackets.
test_00:
nestingScore("[]"); // -> 1
test_01:
nestingScore("[][][]"); // -> 3
test_02:
nestingScore("[[]]"); // -> 2
const nestingScore = (str) => {
// todo
let stack = [0];
for(let char of str){
if(char === "["){
stack.push(0);
} else {
//Do different things with stack based on popped value
let popped = stack.pop();
if(popped === 0){
//treat top of stack as 1
stack[stack.length - 1] += 1
} else {
//treat top of stack as 2 * popped
stack[stack.length - 1] += 2 * popped;
}
} }
return stack[0];
};
n = length of string
Time: O(n)
Space: O(n)
Min Stack:
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
MinStack() initializes the stack object. void push(int val) pushes the element val onto the stack. void pop() removes the element on the top of the stack. int top() gets the top element of the stack. int getMin() retrieves the minimum element in the stack. You must implement a solution with O(1) time complexity for each function.
var MinStack = function() {
this.stack = [];
this.min = [];
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function(val) {
if(this.stack.length === 0){
this.min.push(val);
} else {
let minimum = Math.min(val, this.min[this.min.length - 1]);
this.min.push(minimum);
}
this.stack.push(val); };
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
this.stack.pop(0);
this.min.pop(0);
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
return this.stack[this.stack.length - 1]
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return this.min[this.min.length - 1]
};
/**
- Your MinStack object will be instantiated and called as such:
- var obj = new MinStack()
- obj.push(val)
- obj.pop()
- var param_3 = obj.top()
- var param_4 = obj.getMin()
- /
Max Stack:
Design a max stack data structure that supports the stack operations and supports finding the stack’s maximum element.
Implement the MaxStack class:
MaxStack() Initializes the stack object.
void push(int x) Pushes element x onto the stack.
int pop() Removes the element on top of the stack and returns it.
int top() Gets the element on the top of the stack without removing it.
int peekMax() Retrieves the maximum element in the stack without removing it.
int popMax() Retrieves the maximum element in the stack and removes it. If there is more than one maximum element, only remove the top-most one.
You must come up with a solution that supports O(1) for each top call and O(logn) for each other call?
var MaxStack = function() {
this.stack = []
};
/**
* @param {number} x
* @return {void}
*/
MaxStack.prototype.push = function(x) {
this.stack.push(x)
};
/**
* @return {number}
*/
MaxStack.prototype.pop = function() {
return this.stack.pop()
};
/**
* @return {number}
*/
MaxStack.prototype.top = function() {
return this.stack[this.stack.length-1]
};
/**
* @return {number}
*/
MaxStack.prototype.peekMax = function() {
return Math.max(...this.stack)
};
/**
* @return {number}
*/
MaxStack.prototype.popMax = function() {
let max = Math.max(...this.stack)
return this.stack.splice(this.stack.lastIndexOf(max),1)
};
/**
- Your MaxStack object will be instantiated and called as such:
- var obj = new MaxStack()
- obj.push(x)
- var param_2 = obj.pop()
- var param_3 = obj.top()
- var param_4 = obj.peekMax()
- var param_5 = obj.popMax()
- /
Josephus:
Which prisoner survives?
For this problem, given any n, k > 0, find out which prisoner will be the final survivor.
function josephus(init, kill){
// Create an array with the prisoners numbers
let prisoners = [];
let prisonersFilter = [];
let killCounter = kill;
for(let i = 1; i <= init; i++){
prisoners.push(i);
}
//Outer loop keeps looping until one prisoner left
while(prisoners.length > 1){
//Inner loop executes 'kill' prisoner
for(let i = 0; i < prisoners.length; i++){
killCounter--;
if(killCounter === 0){
prisonersFilter.push(prisoners[i])
killCounter = kill;
}
}
//Filter out prisoners array from prisonerFilter criteria
prisoners = prisoners.filter(prisoner => {
return !prisonersFilter.includes(prisoner);
});
}
return prisoners[0]
}
