CollegeStash

interview

Reorganize String (Js)

Post author By Shiva Charan Devabhaktuni
Post date January 16, 2021

/**

* @param {string} S

* @return {string}

const reorganizeString = (S) => {

let counts = [];

for (let i = 0; i < 26; i++) {

counts[i] = 0;

}

for (let i = 0; i < S.length; i++) {

counts[S.charAt(i).charCodeAt(0) - 'a'.charCodeAt(0)] += 100;

}

for (let i = 0; i < 26; i++) {

counts[i] += i;

}

//Encoded counts[i] = 100*(actual count) + (i)

counts.sort((a, b) => a - b);

let t = 1;

let ret = [];

for (let i = 0; i < 26; i++) {

const ch = String.fromCharCode('a'.charCodeAt(0) + (counts[i] % 100));

let count = Math.floor(counts[i] / 100);

if (count > Math.floor((S.length + 1) / 2))

return '';

while (count > 0) {

if (t >= S.length)

t = 0;

ret[t] = ch;

t += 2;

count--;

}

return ret.join('');

};

console.log(reorganizeString('aab'));

// 'aba'

Demo

interview

Decode String (Js)

Post author By Shiva Charan Devabhaktuni
Post date October 11, 2020

Given an encoded string 3[abc]2[bc] the decoded output should be of the form “abcabcabcbcbc”. Assume that all the brackets are well formed and that all strings are encoded correctly.

/**

* @param {string} s

* @return {string}

const decodeString = (s) => {

let stack = [];

for (let i = 0; i < s.length; i++) {

let ch = s.charAt(i);

if (ch === ']') {

let currStr = '';

while (stack[stack.length - 1] !== '[') {

currStr += stack.pop();

}

stack.pop();

let k = 0,

base = 1;

while (stack.length > 0 && !isNaN(parseInt(stack[stack.length - 1]))) {

k += parseInt(stack.pop()) * base;

base *= 10;

}

while (k != 0) {

for (let j = currStr.length - 1; j >= 0; j--) {

stack.push(currStr.charAt(j));

}

k--;

}

} else {

stack.push(ch);

}

return stack.join('');

};

Demo

Tags es6, javascript

interview

Meeting Rooms II

Post author By Shiva Charan Devabhaktuni
Post date September 29, 2020

Given a list of meetings, that may or may not overlap, calculate the total number of rooms that are required to conduct all the meetings according to the schedule.

Java

class Solution {

public int minMeetingRooms(int[][] intervals) {

int[] start = new int[intervals.length];

int[] end = new int[intervals.length];

for (int i = 0; i < intervals.length; i++) {

start[i] = intervals[i][0];

end[i] = intervals[i][1];

}

Arrays.sort(start);

Arrays.sort(end);

int endPtr = 0, rooms = 0;

for (int i = 0; i < intervals.length; i++) {

if (start[i] < end[endPtr]) {

rooms++;

} else {

endPtr++;

}

return rooms;

}

Runtime Complexity: O(nlog(n))

Space Complexity: O(n)

Javascript (ES6)

/**

* @param {number[][]} intervals

* @return {number}

const minMeetingRooms = (intervals) => {

let startList = [];

let endList = [];

let endPos = 0;

let rooms = 0;

for (let i = 0; i < intervals.length; i++) {

startList.push(intervals[i][0]);

endList.push(intervals[i][1]);

}

startList.sort((a, b) => a - b);

endList.sort((a, b) => a - b);

for (let i = 0; i < intervals.length; i++) {

if (startList[i] < endList[endPos]) {

rooms++;

} else {

endPos++;

}

return rooms;

};

// console.log(minMeetingRooms([[7, 10],[2, 4]]));

// 1

Demo

Tags ecmascript, facebook, js, L5, leetcode, medium, problem, software engineer, solution, swe

interview

Word Break

Post author By Shiva Charan Devabhaktuni
Post date September 29, 2020

Given a non-empty string “word” can it be broken into a list of non-empty words contained in a dictionary ? The words can be repeated.

Java

public class Solution {

public boolean wordBreak(String s, List<String> wordDict) {

return word_Break(s, new HashSet(wordDict), 0, new Boolean[s.length()]);

}

public boolean word_Break(String s, Set<String> wordDict, int start, Boolean[] memo) {

if (start == s.length()) {

return true;

}

if (memo[start] != null) {

return memo[start];

}

for (int end = start + 1; end <= s.length(); end++) {

if (wordDict.contains(s.substring(start, end)) && word_Break(s, wordDict, end, memo)) {

return memo[start] = true;

}

return memo[start] = false;

}

JavaScript (ES6)

/**

* @param {string} s

* @param {string[]} wordDict

* @return {boolean}

const wordBreak = (s, wordDict) => canWordBreak(s, 0, wordDict);

const dp = {};

const canWordBreak = (word, index, wordDict) => {

if (index === word.length) {

return dp[index] = true;

}

if (dp[index] !== undefined) {

return dp[index];

}

for (let breakIndex = index + 1; breakIndex <= word.length; breakIndex++) {

if (wordDict.indexOf(word.substring(index, breakIndex)) > -1 && canWordBreak(word, breakIndex, wordDict)) {

return dp[index] = true;

}

return dp[index] = false;

}

// console.log(wordBreak("catsandog",

// ["cats","dog","sand","and","cat"]));

// false

Demo

Tags ecmascript, java, js, leetcode, problem, solution

interview

Script tag Async vs Defer

Post author By Shiva Charan Devabhaktuni
Post date September 23, 2020

In HTML5 you can use async or defer attributes to load javascript scripts using the script tag. Both async and defer tags make the loading of the script file asynchronous. Both these script tag attributes are compatible in all the major browsers out there today.

Async

Using the async attribute on a script tag, makes the script load asynchronously and executes it then.

1	<script src="example_script.js" async></script>

Defer

Using the defer attribute on a script tag, makes the script load asynchronously and then wait until the whole page is finished parsing, for the script to execute. This attribute shouldn’t be used if the scr attribute on the script tag is absent as this has no effect on inline scripts.

1	<script src="example_script.js" defer></script>

If you want to collect/respond to user clicks and you are using deferred loading of the javascript file that handles this, then the page may seem broken to the user, or you might miss some clicks based on the scenario.

Tags es5, es6, html5, javascript, js, loading, tags

Front End Engineer Interview Prep

General Interview Questions