Domain
1. Leetcode 811
We are given a list cpdomains of count-paired domains. We would like a list of count-paired domains, (in the same format as the input, and in any order), that explicitly counts the number of visits to each subdomain.
Example 1:
Input:
["9001 discuss.leetcode.com"]
Output:
["9001 discuss.leetcode.com", "9001 leetcode.com", "9001 com"]
Example 2:
Input:
["900 google.mail.com", "50 yahoo.com", "1 intel.mail.com", "5 wiki.org"]
Output:
["901 mail.com","50 yahoo.com","900 google.mail.com","5 wiki.org","5 org","1 intel.mail.com","951 com"]
/**
過一遍substring用hashmap記一下frequency，然后再遍歷即可。
*/
var subdomainVisits = function(cpdomains) {
if (!cpdomains || cpdomains.length === 0) {
return [];
}
const result = [];
const map = new Map();
for (const pair of cpdomains) {
let [count, domain] = pair.split(' ');
count = parseInt(count);
const subdomains = domain.split('.');
for (let i = subdomains.length - 1; i >= 0; i--) {
const curr = subdomains.slice(i).join('.');
map.set(curr, map.get(curr) ? map.get(curr) + count : count);
}
}
for (const [subdomain, count] of map) {
result.push(`${count} ${subdomain}`);
}
return result;
};
2. Longest Common Continuous Subarray
輸入：
[
["3234.html", "xys.html", "7hsaa.html"], // user1
["3234.html", "sdhsfjdsh.html", "xys.html", "7hsaa.html"] // user2
]
輸出兩個user的最長連續(xù)且相同的訪問記錄。
["xys.html", "7hsaa.html"]
/**
和LCS做法類似，如果當(dāng)前兩個string相等就把當(dāng)前格子變成[i - 1][j - 1] + 1。不相等就保留0。
*/
function longestCommonContinuousHistory(history1, history2) {
if (
!history1 ||
!history2 ||
history1.length === 0 ||
history2.length === 0
) {
return [];
}
let count = -1;
let result = [];
const memo = Array.from({ length: history1.length + 1 }, () =>
Array.from({ length: history2.length }, () => 0)
);
for (let i = 1; i <= history1.length; i++) {
for (let j = 1; j <= history2.length; j++) {
if (history1[i - 1] === history2[j - 1]) {
memo[i][j] = 1 + memo[i - 1][j - 1];
if (memo[i][j] > count) {
count = memo[i][j];
result = history1.slice(i - count, i);
}
}
}
}
return result;
}
3. Ads Conversion Rate
// The people who buy ads on our network don't have enough data about how ads are working for
//their business. They've asked us to find out which ads produce the most purchases on their website.
// Our client provided us with a list of user IDs of customers who bought something on a landing page
//after clicking one of their ads:
// # Each user completed 1 purchase.
// completed_purchase_user_ids = [
// "3123122444","234111110", "8321125440", "99911063"]
// And our ops team provided us with some raw log data from our ad server showing every time a
//user clicked on one of our ads:
// ad_clicks = [
// #"IP_Address,Time,Ad_Text",
// "122.121.0.1,2016-11-03 11:41:19,Buy wool coats for your pets",
// "96.3.199.11,2016-10-15 20:18:31,2017 Pet Mittens",
// "122.121.0.250,2016-11-01 06:13:13,The Best Hollywood Coats",
// "82.1.106.8,2016-11-12 23:05:14,Buy wool coats for your pets",
// "92.130.6.144,2017-01-01 03:18:55,Buy wool coats for your pets",
// "92.130.6.145,2017-01-01 03:18:55,2017 Pet Mittens",
//]
//The client also sent over the IP addresses of all their users.
//all_user_ips = [
// #"User_ID,IP_Address",
// "2339985511,122.121.0.155",
// "234111110,122.121.0.1",
// "3123122444,92.130.6.145",
// "39471289472,2001:0db8:ac10:fe01:0000:0000:0000:0000",
// "8321125440,82.1.106.8",
// "99911063,92.130.6.144"
//]
// Write a function to parse this data, determine how many times each ad was clicked,
//then return the ad text, that ad's number of clicks, and how many of those ad clicks
//were from users who made a purchase.
// Expected output:
// Bought Clicked Ad Text
// 1 of 2 2017 Pet Mittens
// 0 of 1 The Best Hollywood Coats
// 3 of 3 Buy wool coats for your pets
/**
沒什么技術(shù)含量。愣實現(xiàn)就行了。
*/
function adsConversionRate(completedPurchaseUserIds, adClicks, allUserIps) {
const userIds = new Set(completedPurchaseUserIds);
const conversion = new Map();
const ipToUserId = new Map();
for (const userIp of allUserIps) {
const [userId, ip] = userIp.split(',');
ipToUserId.set(ip, userId);
}
for (const click of adClicks) {
const [ip,, adText] = click.split(',');
if (conversion.has(adText)) {
conversion.get(adText)[1]++;
if (userIds.has(ipToUserId.get(ip))) {
conversion.get(adText)[0]++;
}
} else {
const bought = userIds.has(ipToUserId.get(ip)) ? 1 : 0;
conversion.set(adText, [bought, 1]);
}
}
for (const [adText, ratio] of conversion) {
console.log(`${ratio[0]} of ${ratio[1]} ${adText}`);
}
}
選課
1. 兩名學(xué)生的課程overlap
You are a developer for a university. Your current project is to develop a system for students to find courses they share with friends. The university has a system for querying courses students are enrolled in, returned as a list of (ID, course) pairs.
Write a function that takes in a list of (student ID number, course name) pairs and returns, for every pair of students, a list of all courses they share.
Sample Input:
student_course_pairs_1 = [
["58", "Software Design"],
["58", "Linear Algebra"],
["94", "Art History"],
["94", "Operating Systems"],
["17", "Software Design"],
["58", "Mechanics"],
["58", "Economics"],
["17", "Linear Algebra"],
["17", "Political Science"],
["94", "Economics"],
["25", "Economics"],
]
Sample Output (pseudocode, in any order):
find_pairs(student_course_pairs_1) =>
{
[58, 17]: ["Software Design", "Linear Algebra"]
[58, 94]: ["Economics"]
[58, 25]: ["Economics"]
[94, 25]: ["Economics"]
[17, 94]: []
[17, 25]: []
}
Additional test cases:
Sample Input:
student_course_pairs_2 = [
["42", "Software Design"],
["0", "Advanced Mechanics"],
["9", "Art History"],
]
Sample output:
find_pairs(student_course_pairs_2) =>
{
[0, 42]: []
[0, 9]: []
[9, 42]: []
}
function courseOverlaps(studentCoursePairs) {
if (!studentCoursePairs || studentCoursePairs.length === 0) {
return [];
}
const courses = new Map();
for (const [studentId, course] of studentCoursePairs) {
if (courses.has(studentId)) {
courses.get(studentId).push(course);
} else {
courses.set(studentId, [course]);
}
}
const studentIds = [...courses.keys()];
for (let i = 0; i < studentIds.length; i++) {
for (let j = i + 1; j < studentIds.length; j++) {
const overlaps = [];
for (const course1 of courses.get(studentIds[i])) {
for (const course2 of courses.get(studentIds[j])) {
if (course1 === course2) {
overlaps.push(course1);
}
}
}
console.log(`[${studentIds[i]},${studentIds[j]}]: ${overlaps}`);
}
}
}
2. 輸出中間課程
以下是當(dāng)時面試結(jié)束后留在editor里的所有內(nèi)容。沒有整理。題目是第三題，大家大概參考一下吧。。第三題寫的是不對的當(dāng)時沒時間debug了。
/*
Students may decide to take different "tracks" or sequences of courses in the Computer Science curriculum. There may be more than one track that includes the same course, but each student follows a single linear track from a "root" node to a "leaf" node. In the graph below, their path always moves left to right.
Write a function that takes a list of (source, destination) pairs, and returns the name of all of the courses that the students could be taking when they are halfway through their track of courses.
Sample input:
all_courses = [
["Logic", "COBOL"],
["Data Structures", "Algorithms"],
["Creative Writing", "Data Structures"],
["Algorithms", "COBOL"],
["Intro to Computer Science", "Data Structures"],
["Logic", "Compilers"],
["Data Structures", "Logic"],
["Creative Writing", "System Administration"],
["Databases", "System Administration"],
["Creative Writing", "Databases"],
["Intro to Computer Science", "Graphics"],
]
Sample output (in any order):
["Data Structures", "Creative Writing", "Databases", "Intro to Computer Science"]
All paths through the curriculum (midpoint *highlighted*):
*Intro to C.S.* -> Graphics
Intro to C.S. -> *Data Structures* -> Algorithms -> COBOL
Intro to C.S. -> *Data Structures* -> Logic -> COBOL
Intro to C.S. -> *Data Structures* -> Logic -> Compiler
Creative Writing -> *Databases* -> System Administration
*Creative Writing* -> System Administration
Creative Writing -> *Data Structures* -> Algorithms -> COBOL
Creative Writing -> *Data Structures* -> Logic -> COBOL
Creative Writing -> *Data Structures* -> Logic -> Compilers
Visual representation:
____________
| |
| Graphics |
---->|__________|
| ______________
____________ | | |
| | | ______________ -->| Algorithms |--\ _____________
| Intro to | | | | / |____________| \ | |
| C.S. |---+ | Data | / >-->| COBOL |
|__________| \ | Structures |--+ ______________ / |___________|
>->|____________| \ | | /
____________ / \-->| Logic |-+ _____________
| | / ______________ |____________| \ | |
| Creative | / | | \--->| Compilers |
| Writing |-+----->| Databases | |___________|
|__________| \ |____________|-\ _________________________
\ \ | |
\--------------------+-->| System Administration |
|_______________________|
Complexity analysis variables:
n: number of pairs in the input
*/
'use strict';
const prereqs_courses1 = [
['Data Structures', 'Algorithms'],
['Foundations of Computer Science', 'Operating Systems'],
['Computer Networks', 'Computer Architecture'],
['Algorithms', 'Foundations of Computer Science'],
['Computer Architecture', 'Data Structures'],
['Software Design', 'Computer Networks'],
];
const prereqs_courses2 = [
['Data Structures', 'Algorithms'],
['Algorithms', 'Foundations of Computer Science'],
['Foundations of Computer Science', 'Logic'],
];
const prereqs_courses3 = [['Data Structures', 'Algorithms']];
const allCourses = [
['Logic', 'COBOL'],
['Data Structures', 'Algorithms'],
['Creative Writing', 'Data Structures'],
['Algorithms', 'COBOL'],
['Intro to Computer Science', 'Data Structures'],
['Logic', 'Compilers'],
['Data Structures', 'Logic'],
['Creative Writing', 'System Administration'],
['Databases', 'System Administration'],
['Creative Writing', 'Databases'],
['Intro to Computer Science', 'Graphics'],
];
function findAllMidway(prereqs) {
const graph = formGraph(prereqs);
const paths = [];
const backtracking = (path, curr) => {
if (graph.get(curr).length === 0) {
paths.push([...path]);
return;
}
for (const next of graph.get(curr)) {
backtracking(path, next);
}
path.pop(curr);
};
const firstCourses = findAllFirstCourses(prereqs);
for (const course of firstCourses) {
backtracking([], course);
}
const result = new Set();
for (const path of paths) {
if (path.length % 2 === 0) {
result.add(path[path.length / 2 - 1]);
} else {
result.add(path[Math.floor(path.length / 2)]);
}
}
return result;
}
function findAllFirstCourses(prereqs) {
const result = [];
const courses = new Set();
const coursesHavePrereq = new Set();
for (const prereq of prereqs) {
courses.add(prereq[0]);
courses.add(prereq[1]);
coursesHavePrereq.add(prereq[1]);
}
for (const course of courses) {
if (!coursesHavePrereq.has(course)) {
result.push(course);
}
}
return result;
}
function formGraph(prereqs) {
const result = new Map();
for (const prereq of prereqs) {
if (result.has(prereq[0])) {
result.get(prereq[0]).add(prereq[1]);
} else {
result.set(prereq[0], new Set([prereq[1]]));
}
}
for (const prereq of prereqs) {
if (!result.has(prereq[1])) {
result.set(prereq[1], new Set());
}
}
return result;
}
console.log(findAllMidway(allCourses));
function findMidway(prereqs) {
const result = [];
const coursesHavePrereq = new Set();
for (const prereq of prereqs) {
coursesHavePrereq.add(prereq[1]);
}
let curr;
for (const prereq of prereqs) {
if (!coursesHavePrereq.has(prereq[0])) {
curr = prereq[0];
break;
}
}
const courses = [...coursesHavePrereq, curr];
while (result.length !== courses.length) {
result.push(curr);
for (const prereq of prereqs) {
if (curr === prereq[0]) {
curr = prereq[1];
break;
}
}
}
if (result.length % 2 === 0) {
return result[result.length / 2 - 1];
}
return result[Math.floor(result.length / 2)];
}
const studentCoursePairs1 = [
['58', 'Linear Algebra'],
['94', 'Art History'],
['94', 'Operating Systems'],
['17', 'Software Design'],
['58', 'Mechanics'],
['58', 'Economics'],
['17', 'Linear Algebra'],
['17', 'Political Science'],
['94', 'Economics'],
['25', 'Economics'],
['58', 'Software Design'],
];
const studentCoursePairs2 = [
['42', 'Software Design'],
['0', 'Advanced Mechanics'],
['9', 'Art History'],
];
function findAllOverlaps(studentCoursePairs) {
const map = new Map();
for (const [studentId, course] of studentCoursePairs) {
if (map.has(studentId)) {
map.get(studentId).push(course);
} else {
map.set(studentId, [course]);
}
}
const studentIds = [...map.keys()];
const result = new Map();
for (let i = 0; i < studentIds.length; i++) {
for (let j = i + 1; j < studentIds.length; j++) {
const key = `${studentIds[i]},${studentIds[j]}`;
const overlaps = [];
for (const course1 of map.get(studentIds[i])) {
for (const course2 of map.get(studentIds[j])) {
if (course1 === course2) {
overlaps.push(course1);
}
}
}
result.set(key, overlaps);
}
}
return result;
}
// console.log(findAllOverlaps(studentCoursePairs1));
// console.log(findAllOverlaps(studentCoursePairs2));
矩陣題
1. 找一個矩形
- there is an image filled with 0s and 1s. There is at most one rectangle in this image filled with 0s, find the rectangle. Output could be the coordinates of top-left and bottom-right elements of the rectangle, or top-left element, width and height.
function findOneRectangle(board) {
if (!board || board.length === 0 || board[0].length === 0) {
return [];
}
const result = [];
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
if (board[i][j] === 0) {
result.push([i, j]);
let height = 1, width = 1;
while (i + height < board.length && board[i + height][j] === 0) {
height++;
}
while (j + width < board[0].length && board[i][j + width] === 0) {
width++;
}
result.push([i + height - 1, j + width - 1]);
break;
}
if (result.length !== 0) {
break;
}
}
}
return result;
}
2. 找多個矩形
- for the same image, it is filled with 0s and 1s. It may have multiple rectangles filled with 0s. The rectangles are separated by 1s. Find all the rectangles.
function findMultipleRectangle(board) {
if (!board || board.length === 0 || board[0].length === 0) {
return [];
}
const result = [];
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
if (board[i][j] === 0) {
const rectangle = [[i, j]];
board[i][j] = 1;
let height = 1, width = 1;
while (i + height < board.length && board[i + height][j] === 0) {
height++;
}
while (j + width < board[0].length && board[i][j + width] === 0) {
width++;
}
for (let h = 0; h < height; h++) {
for (let w = 0; w < width; w++) {
board[i + h][j + w] = 1;
}
}
rectangle.push([i + height - 1, j + width - 1]);
result.push(rectangle);
}
}
}
return result;
}
3. 找多個形狀
- the image has random shapes filled with 0s, separated by 1s. Find all the shapes. Each shape is represented by coordinates of all the elements inside.
function findMultipleShapes(board) {
if (!board || board.length === 0 || board[0].length === 0) {
return [];
}
const result = [];
const floodFillDFS = (x, y, shape) => {
if (x < 0 || x >= board.length || y < 0 || y >= board[0].length || board[x][y] === 1) {
return;
}
board[x][y] = 1;
shape.push([x, y]);
floodFillDFS(x + 1, y, shape);
floodFillDFS(x - 1, y, shape);
floodFillDFS(x, y - 1, shape);
floodFillDFS(x, y + 1, shape);
};
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
if (board[i][j] === 0) {
shape = [];
floodFillDFS(i, j, shape);
result.push(shape);
}
}
}
return result;
}
reflow字符串
1. word wrap
給一個word list 和最大的長度，要求把這些word用 - 串聯(lián)起來，但不能超過最大的長度。
function wordWrap(words, maxLen) {
if (!words || words.length === 0) {
return [];
}
const result = [];
let i = 0;
while (i < words.length) {
let remain = maxLen;
let count = 0;
while (i < words.length) {
if (remain - words[i].length < 0) {
break;
}
count++;
remain -= words[i++].length + 1;
}
result.push(words.slice(i - count, i).join('-'));
}
return result;
}
2. word processor
We are building a word processor and we would like to implement a "reflow" functionality that also applies full justification to the text.
Given an array containing lines of text and a new maximum width, re-flow the text to fit the new width. Each line should have the exact specified width. If any line is too short, insert '-' (as stand-ins for spaces) between words as equally as possible until it fits.
Note: we are using '-' instead of spaces between words to make testing and visual verification of the results easier.
lines = [ "The day began as still as the",
"night abruptly lighted with",
"brilliant flame" ]
reflowAndJustify(lines, 24) ... "reflow lines and justify to length 24" =>
[ "The--day--began-as-still",
"as--the--night--abruptly",
"lighted--with--brilliant",
"flame" ] // <--- a single word on a line is not padded with spaces
function reflowAndJustify(lines, maxLen) {
if (!lines || lines.length === 0) {
return [];
}
const words = lines.join(' ').split(' ');
const result = [];
let i = 0;
while (i < words.length) {
// split words into lines first
let remain = maxLen;
let count = 0;
while (i < words.length) {
if (remain - words[i].length < 0) {
break;
}
count++;
remain -= words[i++].length + 1;
}
const line = words.slice(i - count, i);
// after splitting into lines, calculate the required dashes between each word
const n = line.reduce((n, word) => n + word.length, 0);
let reflowed = ''; // line result with padded dashes
const baseDash = '-'.repeat(parseInt((maxLen - n) / (line.length - 1)));
let extra = (maxLen - n) % (line.length - 1); // some dashes at the beginning has one extra dash
for (let j = 0; j < line.length; j++) {
if (j === line.length - 1) {
reflowed += line[j];
} else {
reflowed +=
extra-- <= 0 ? line[j] + baseDash : line[j] + baseDash + '-';
}
}
result.push(reflowed);
}
return result;
}
計算器
1. 基本加減計算器
- 給輸入為string，例如"2+3-999"，之包含+-操作，返回計算結(jié)果。
function basicCalculator(expression) {
if (!expression || expression.length === 0) {
return 0;
}
let result = 0;
let sign = 1;
for (let i = 0; i < expression.length; i++) {
if (isNumeric(expression[i])) {
let num = expression[i];
while (i + 1 < expression.length && isNumeric(expression[i + 1])) {
num += expression[++i];
}
num = parseInt(num);
result += num * sign;
} else if (expression[i] === '+') {
sign = 1;
} else if (expression[i] === '-') {
sign = -1;
}
}
return result;
}
function isNumeric(c) {
return c >= '0' && c <= '9';
}
2. 加減計算器帶括號 - Leetcode 224
加上parenthesis， 例如"2+((8+2)+(3-999))"，返回計算結(jié)果。
/*
只是比第一問多了一個stack以及兩個else if語句判斷括號。
*/
function basicCalculator(expression) {
if (!expression || expression.length === 0) {
return 0;
}
let result = 0;
let sign = 1;
let stack = [];
for (let i = 0; i < expression.length; i++) {
if (isNumeric(expression[i])) {
let num = expression[i];
while (i + 1 < expression.length && isNumeric(expression[i + 1])) {
num += expression[++i];
}
num = parseInt(num);
result += num * sign;
} else if (expression[i] === '+') {
sign = 1;
} else if (expression[i] === '-') {
sign = -1;
} else if (expression[i] === '(') {
stack.push(result);
stack.push(sign);
result = 0;
sign = 1;
} else if (expression[i] === ')') {
result = result * stack.pop() + stack.pop();
}
}
return result;
}
function isNumeric(c) {
return c >= '0' && c <= '9';
}
3. 帶變量計算器
不光有數(shù)字和operator，還有一些變量，這些變量有些可以表示為一個數(shù)值，需要從給定的map里去get這個變量的value。然后有的變量不能轉(zhuǎn)為數(shù)字，所以結(jié)果要包含這些不可變成數(shù)字的單詞以及其他數(shù)字部分通過計算器得到的結(jié)果。
這題就寫個思路吧，估計不會問太深。Leetcode770是原題，discussion區(qū)域都是噴這道題的。
矩陣合法
1. 矩陣合法
給一個N*N的矩陣，判定是否是有效的矩陣。有效矩陣的定義是每一行或者每一列的數(shù)字都必須正好是1到N的數(shù)。輸出一個bool。
function isValidMatrix(matrix) {
if (!matrix || matrix.length === 0 || matrix[0].length === 0) {
return false;
}
const n = matrix.length;
for (let i = 0; i < n; i++) {
const rowSet = new Set();
const colSet = new Set();
let rowMin = Number.POSITIVE_INFINITY, rowMax = Number.NEGATIVE_INFINITY;
let colMin = rowMin, colMax = rowMax;
for (let j = 0; j < n; j++) {
if (!rowSet.has(matrix[i][j])) {
rowSet.add(matrix[i][j]);
rowMin = Math.min(rowMin, matrix[i][j]);
rowMax = Math.max(rowMax, matrix[i][j]);
} else {
return false;
}
if (!colSet.has(matrix[j][i])) {
colSet.add(matrix[j][i]);
colMin = Math.min(colMin, matrix[j][i]);
colMax = Math.max(colMax, matrix[j][i]);
} else {
return false;
}
}
if (rowMin !== 1 || colMin !== 1 || rowMax !== n || colMax !== n) {
return false;
}
}
return true;
}
2. nonogram
"""
A nonogram is a logic puzzle, similar to a crossword, in which the player is given a blank grid and has to color it according to some instructions. Specifically, each cell can be either black or white, which we will represent as 0 for black and 1 for white.
+------------+
| 1 1 1 1 |
| 0 1 1 1 |
| 0 1 0 0 |
| 1 1 0 1 |
| 0 0 1 1 |
+------------+
For each row and column, the instructions give the lengths of contiguous runs of black (0) cells. For example, the instructions for one row of [ 2, 1 ] indicate that there must be a run of two black cells, followed later by another run of one black cell, and the rest of the row filled with white cells.
These are valid solutions: [ 1, 0, 0, 1, 0 ] and [ 0, 0, 1, 1, 0 ] and also [ 0, 0, 1, 0, 1 ]
This is not valid: [ 1, 0, 1, 0, 0 ] since the runs are not in the correct order.
This is not valid: [ 1, 0, 0, 0, 1 ] since the two runs of 0s are not separated by 1s.
Your job is to write a function to validate a possible solution against a set of instructions. Given a 2D matrix representing a player's solution; and instructions for each row along with additional instructions for each column; return True or False according to whether both sets of instructions match.
Example instructions #1
matrix1 = [[1,1,1,1],
[0,1,1,1],
[0,1,0,0],
[1,1,0,1],
[0,0,1,1]]
rows1_1 = [], [1], [1,2], [1], [2]
columns1_1 = [2,1], [1], [2], [1]
validateNonogram(matrix1, rows1_1, columns1_1) => True
Example solution matrix:
matrix1 ->
row
+------------+ instructions
| 1 1 1 1 | <-- []
| 0 1 1 1 | <-- [1]
| 0 1 0 0 | <-- [1,2]
| 1 1 0 1 | <-- [1]
| 0 0 1 1 | <-- [2]
+------------+
^ ^ ^ ^
| | | |
column [2,1] | [2] |
instructions [1] [1]
Example instructions #2
(same matrix as above)
rows1_2 = [], [], [1], [1], [1,1]
columns1_2 = [2], [1], [2], [1]
validateNonogram(matrix1, rows1_2, columns1_2) => False
The second and third rows and the first column do not match their respective instructions.
Example instructions #3
matrix2 = [
[ 1, 1 ],
[ 0, 0 ],
[ 0, 0 ],
[ 1, 0 ]
]
rows2_1 = [], [2], [2], [1]
columns2_1 = [1, 1], [3]
validateNonogram(matrix2, rows2_1, columns2_1) => False
The black cells in the first column are not separated by white cells.
n: number of rows in the matrix
m: number of columns in the matrix
"""
matrix1 = [
[1,1,1,1], # []
[0,1,1,1], # [1] -> a single run of _1_ zero (i.e.: "0")
[0,1,0,0], # [1, 2] -> first a run of _1_ zero, then a run of _2_ zeroes
[1,1,0,1], # [1]
[0,0,1,1], # [2]
]
# True
rows1_1 = [[],[1],[1,2],[1],[2]]
columns1_1 = [[2,1],[1],[2],[1]]
# False
rows1_2 = [[],[],[1],[1],[1,1]]
columns1_2 = [[2],[1],[2],[1]]
matrix2 = [
[1,1],
[0,0],
[0,0],
[1,0]
]
# False
rows2_1 = [[],[2],[2],[1]]
columns2_1 = [[1,1],[3]]
function isValidNonogram(matrix, rows, cols) {
if (!matrix || !rows || !cols) {
return false;
}
const n = matrix.length;
const m = matrix[0].length;
if (n === 0 || n !== rows.length || m !== cols.length) {
return false;
}
return (
isNonogramRowsValid(matrix, rows, n, m) &&
isNonogramColsValid(matrix, cols, n, m)
);
}
function isNonogramRowsValid(matrix, rows, n, m) {
for (let i = 0; i < n; i++) {
let rowIndex = 0;
for (let j = 0; j < m; j++) {
if (matrix[i][j] === 0) {
if (rows[i].length === 0) {
return false;
}
for (let k = 0; k < rows[rowIndex]; k++) {
if (j + k >= m || matrix[i][j + k] !== 0) {
return false;
}
}
j += rows[i][rowIndex++];
}
}
if (rowIndex !== rows[i].length) {
return false;
}
}
return true;
}
function isNonogramColsValid(matrix, cols, n, m) {
for (let i = 0; i < m; i++) {
let colIndex = 0;
for (let j = 0; j < n; j++) {
if (matrix[j][i] === 0) {
if (cols[i].length === 0) {
return false;
}
for (let k = 0; k < cols[colIndex]; k++) {
if (j + k >= n || matrix[j + k][i] !== 0) {
return false;
}
}
j += cols[i][colIndex++];
}
}
if (colIndex !== cols[i].length) {
return false;
}
}
return true;
}
祖先
1. 0個或1個parent的節(jié)點
輸入是int[][] input, input[0]是input[1] 的parent，比如 {{1,4}, {1,5}, {2,5}, {3,6}, {6,7}}會形成上面的圖
第一問是只有0個parents和只有1個parent的節(jié)點
1 2 3
/ \ / \
4 5 6
\
7
function findNodesWithZeroOrOneParent(edges) {
if (!edges || edges.length === 0) {
return [];
}
const result = [];
const map = new Map();
for (const [parent, child] of edges) {
if (map.has(child)) {
map.get(child).add(parent);
} else {
map.set(child, new Set([parent]));
}
}
for (const [child, parentSet] of map) {
if (parentSet.length === 0 || parentSet.length === 1) {
result.push(child);
}
}
return result;
}
2. 兩個節(jié)點是否有公共祖先
function hasCommonAncestor(edges, x, y) {
if (!edges || edges.length === 0) {
return false;
}
const directParents = new Map();
for (const [parent, child] of edges) {
if (directParents.has(child)) {
directParents.get(child).add(parent);
} else {
directParents.set(child, new Set([parent]));
}
}
const findAllParents = (e) => {
const result = new Set();
const stack = [];
stack.push(e);
while (stack.length !== 0) {
const curr = stack.pop();
const parents = directParents.get(curr);
if (!parents) {
continue;
}
for (const parent of parents) {
if (result.has(parent)) {
continue;
}
result.add(parent);
stack.push(parent);
}
}
return result;
};
const parentsOfX = findAllParents(x);
const parentsOfY = findAllParents(y);
for (const parentOfX of parentsOfX) {
if (parentsOfY.has(parentOfX)) {
return true;
}
}
return false;
}
3. 最遠祖先
function Queue() {
this.firstStack = [];
this.secondStack = [];
this.length = 0;
}
Queue.prototype.push = function(x) {
this.firstStack.push(x);
this.length++;
};
Queue.prototype.pop = function() {
if (this.secondStack.length === 0) {
while (this.firstStack.length !== 0) {
this.secondStack.push(this.firstStack.pop());
}
}
this.length--;
return this.secondStack.pop();
};
function earliestAncestor(parentChildPairs, x) {
const directParents = new Map();
for (const [parent, child] of parentChildPairs) {
if (directParents.has(child)) {
directParents.get(child).add(parent);
} else {
directParents.set(child, new Set([parent]));
}
}
let currlayer = new Queue();
let prevlayer;
const visited = new Set();
currlayer.push(x);
while (currlayer.length !== 0) {
prevlayer = new Queue();
let size = currlayer.length;
while (size--) {
const curr = currlayer.pop();
prevlayer.push(curr);
const parents = directParents.get(curr);
if (!parents) {
continue;
}
for (const parent of parents) {
if (visited.has(parent)) {
continue;
}
currlayer.push(parent);
visited.add(parent);
}
}
}
return prevlayer.pop();
}
門禁刷卡
1. 找進出記錄不符的人
Given a list of people who enter and exit, find the people who entered without
their badge and who exited without their badge.
// badge_records = [
// ["Martha", "exit"],
// ["Paul", "enter"],
// ["Martha", "enter"],
// ["Martha", "exit"],
// ["Jennifer", "enter"],
// ["Paul", "enter"],
// ["Curtis", "enter"],
// ["Paul", "exit"],
// ["Martha", "enter"],
// ["Martha", "exit"],
// ["Jennifer", "exit"],
// ]
// Expected output: ["Paul", "Curtis"], ["Martha"]
function invalidBadgeRecords(records) {
if (!records || records.length === 0) {
return [];
}
const result = [[], []];
// 0 for exited, 1 for entered
const state = new Map();
const invalidEnter = new Set();
const invalidExit = new Set();
for (const [name, action] of records) {
!state.has(name) && state.set(name, 0);
if (action === 'enter') {
if (state.get(name) === 0) {
state.set(name, 1);
} else {
invalidEnter.add(name);
}
} else {
if (state.get(name) === 1) {
state.set(name, 0);
} else {
invalidExit.add(name);
}
}
}
for (const [name, s] of state) {
if (s === 1) {
invalidEnter.add(name);
}
}
for (const name of invalidEnter) {
result[0].push(name);
}
for (const name of invalidExit) {
result[1].push(name);
}
return result;
}
2. 一小時內(nèi)access多次
給 list of [name, time], time is string format: '1300' //下午一點
return: list of names and the times where their swipe badges within one hour. if there are multiple intervals that satisfy the condition, return any one of them.
name1: time1, time2, time3...
name2: time1, time2, time3, time4, time5...
example:
input: [['James', '1300'], ['Martha', '1600'], ['Martha', '1620'], ['Martha', '1530']]
output: {
'Martha': ['1600', '1620', '1530']
}
function frequentAccess(records) {
if (!records || records.length === 0) {
return [];
}
const result = [];
const times = new Map();
for (const [name, timestamp] of records) {
if (times.has(name)) {
times.get(name).push(timestamp);
} else {
times.set(name, [timestamp]);
}
}
for (const [name, timestamps] of times) {
timestamps.sort(timeDifference);
let i = 0;
let timewindow = [timestamps[i]];
for (let j = 1; j < timestamps.length; j++) {
if (timeDifference(timestamps[i], timestamps[j]) < 60) {
timewindow.push(timestamps[j]);
} else {
timewindow = [timestamps[j]];
i = j;
}
}
if (timewindow.length >= 3) {
result.push([name, timewindow]);
}
}
return result;
}
function timeDifference(a, b) {
const aHour = Math.floor(a / 100);
const bHour = Math.floor(b / 100);
const aMinute = a % 100;
const bMinute = b % 100;
return aHour * 60 + aMinute - (bHour * 60 + bMinute);
}
開會
1. 是否有空余時間
第一題：類似meeting rooms，輸入是一個int[][] meetings, int start, int end, 每個數(shù)都是時間，13：00 =》 1300， 9：30 =》 18930， 看新的meeting 能不能安排到meetings
ex: {[1300, 1500], [930, 1200],[830, 845]}, 新的meeting[820, 830], return true; [1450, 1500] return false;
function canSchedule(meetings, start, end) {
for (const meeting of meetings) {
if (
(start >= meeting[0] && start < meeting[1]) ||
(end > meeting[0] && end <= meeting[1]) ||
(start < meeting[0] && end > meeting[1])
) {
return false;
}
}
return true;
}
2. 返回空閑時間段
類似merge interval，唯一的區(qū)別是輸出，輸出空閑的時間段，merge完后，再把兩兩個之間的空的輸出就好，注意要加上0 - 第一個的start time
function spareTime(meetings) {
if (!meetings || meetings.length === 0) {
return [];
}
meetings = mergeMeetings(meetings);
const result = [];
let start = 0;
for (let i = 0; i < meetings.length; i++) {
result.push([start, meetings[i][0]]);
start = meetings[i][1];
}
return result;
}
function mergeMeetings(meetings) {
const result = [];
meetings.sort((a, b) => a[0] - b[0]);
let [start, end] = meetings[0];
for (const meeting of meetings) {
if (start < meeting[1]) {
end = Math.max(end, meeting[1]);
} else {
result.push(start, end);
start = meeting[0];
end = meeting[0];
}
}
return result;
}
Sparse Vector
1. 設(shè)計sparse vector
sparseVector v = new sparseVector(100); //size constructor; size is 100.
v.set(0, 1.0);
v.set(3, 2.0);
v.set(80,-4.5);
System.out.println(v.get(80)); //should print -4.5
System.out.println(v.get(50)); //should print 0.0
try {
System.out.println(v.get(101)); //error -- index out of range
throw new IllegalStateException("We should not get here, an exception should have been thrown");
} catch (IndexOutOfBoundsException t) {
// success
}
System.out.println(v.toString()); //should print something like [1.0, 0.0, 0.0, 2.0, 0.0, ...]
class IndexOutOfRangeError extends Error {
constructor(message) {
super(message);
}
}
function Node(val, next, index) {
this.val = val;
this.next = next;
this.index = index;
}
function SparseVector(n) {
this.length = n;
this.head = null;
}
SparseVector.prototype.set = function SparseVectorSet(index, val) {
if (index >= this.length) {
throw new IndexOutOfRangeError(
`Index out of range: ${index} of ${this.length}`
);
}
let curr = this.head;
if (!curr) {
const node = new Node(val, null, index);
this.head = node;
return;
}
let prev = new Node();
prev.next = curr;
while (curr && curr.index < index) {
prev = curr;
curr = curr.next;
}
if (curr) {
if (curr.index === index) {
curr.val = val;
} else {
const node = new Node(val, curr, index);
prev.next = node;
}
} else {
prev.next = new Node(val, null, index);
}
};
SparseVector.prototype.get = function SparseVectorGet(index) {
if (index >= this.length) {
throw new IndexOutOfRangeError(
`Index out of range: ${index} of ${this.length}`
);
}
let curr = this.head;
while (curr && curr.index !== index) {
curr = curr.next;
}
return curr ? curr.val : 0;
};
SparseVector.prototype.toString = function SparseVectorToString() {
const result = [];
let curr = this.head;
for (let i = 0; i < this.length; i++) {
if (!curr || i < curr.index) {
result.push(0);
} else if (i === curr.index) {
result.push(curr.val);
} else {
curr = curr.next;
i--;
}
}
return '[' + result.toString() + ']';
};
2. 實現(xiàn)add，dot和cos
Add these operations to your library: Addition, dot product, and cosine. Formulae for each are provided below;
we’re more interested in you writing the code than whether you’ve memorized the formula. For each operation, your code should throw an error if the two input vectors are not equal length.
Sample input/output:
//Note: This is pseudocode. Your actual syntax will vary by language.
v1 = new vector(5)
v1[0] = 4.0
v1[1] = 5.0
. from: 1point3acres.com/bbs
v2 = new vector(5)
v2[1] = 2.0
v2[3] = 3.0. From 1point 3acres bbs
v3 = new vector(2)
print v1.add(v2) //should print [4.0, 7.0, 0.0, 3.0, 0.0]
print v1.add(v3) //error -- vector lengths don’t match
print v1.dot(v2) //should print 10
print v1.dot(v3) //error -- vector lengths don’t match
print v1.cos(v2) //should print 0.433
print v1.cos(v3) //error -- vector lengths don’t match
Formulae:
Addition
a.add(b) = [a[0]+b[0], a[1]+b[1], a[2]+b[2], ...]
Dot product
a.dot(b) = a[0]*b[0] + a[1]*b[1] + a[2]*b[2] + ...
Cosine
a.cos(b) = a.dot(b) / (norm(a) * norm(b))
//norm(a) = sqrt(a[0]^2 + a[1]^2 + a[2]^2 + ...).
SparseVector.prototype.add = function SparseVectorAdd(v2) {
if (this.length !== v2.length) {
throw new Error('length mismatch');
}
const result = [];
for (let i = 0; i < this.length; i++) {
result.push(this.get(i) + v2.get(i));
}
return result;
};
SparseVector.prototype.dot = function SparseVectorDot(v2) {
if (this.length !== v2.length) {
throw new Error('length mismatch');
}
let result = 0;
for (let i = 0; i < this.length; i++) {
result += this.get(i) * v2.get(i);
}
return result;
};
SparseVector.prototype.norm = function SparseVectorNorm() {
let sum = 0;
for (let i = 0; i < this.length; i++) {
const val = this.get(i);
sum += val * val;
}
return Math.sqrt(sum);
};
SparseVector.prototype.cos = function SparseVectorCos(v2) {
return this.dot(b) / (this.norm() * v2.norm());
};
找寶藏
1. Find legal moves
第一問就是給一個i和j，找出身邊四個方向里為0的所有格子。
2. 找能去的所有0區(qū)域
給一個二維matrix，-1代表墻，0代表路。問給定一個起點坐標(biāo)為0，是否能到達所有的0。
function findLegalMoves(matrix, i, j) {
if (!matrix || matrix.length === 0) {
return false;
}
const visited = Array.from({ length: matrix.length }, () =>
Array.from({ length: matrix[0].length }, () => false)
);
const floodFillDFS = (x, y) => {
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || matrix[x][y] === -1 || visited[x][y]) {
return;
}
visited[x][y] = true;
floodFillDFS(x - 1, y);
floodFillDFS(x + 1, y);
floodFillDFS(x, y - 1);
floodFillDFS(x, y + 1);
};
floodFillDFS(i, j);
for (let i = 0; i < matrix.length; i++) {
for (let j = 0; j < matrix[0].length; j++) {
if (!visited[i][j] && matrix[i][j] === 0) {
return false;
}
}
}
return true;
}
3. 最短路徑找treasure
board3 中1代表鉆石，給出起點和終點，問有沒有一條不走回頭路的路線，能從起點走到終點，并拿走所有的鉆石，給出所有的最短路徑。
board3 = [
[ 1, 0, 0, 0, 0 ],
[ 0, -1, -1, 0, 0 ],
[ 0, -1, 0, 1, 0 ],
[ -1, 0, 0, 0, 0 ],
[ 0, 1, -1, 0, 0 ],
[ 0, 0, 0, 0, 0 ],
]
treasure(board3, (5, 0), (0, 4)) -> None
treasure(board3, (5, 2), (2, 0)) ->
[(5, 2), (5, 1), (4, 1), (3, 1), (3, 2), (2, 2), (2, 3), (1, 3), (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (2, 0)]
Or
[(5, 2), (5, 1), (4, 1), (3, 1), (3, 2), (3, 3), (2, 3), (1, 3), (0, 3), (0, 2), (0, 1), (0, 0), (1, 0), (2, 0)]
treasure(board3, (0, 0), (4, 1)) ->
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (2, 2), (3, 2), (3, 1), (4, 1)]
Or
[(0, 0), (0, 1), (0, 2), (0, 3), (1, 3), (2, 3), (3, 3), (3, 2), (3, 1), (4, 1)]
function findAllTreasures(board, start, end) {
if (!board) {
return [];
}
let numTreasures = 0;
for (let i = 0; i < board.length; i++) {
for (let j = 0; j < board[0].length; j++) {
if (board[i][j] === 1) {
numTreasures++;
}
}
}
const paths = [];
const dfs = (x, y, path, remainTreasure) => {
if (
x < 0 ||
x >= board.length ||
y < 0 ||
y >= board[0].length ||
board[x][y] === -1 ||
board[x][y] === 2
) {
return;
}
path.push([x, y]);
const temp = board[x][y];
if (temp === 1) {
remainTreasure--;
}
if (x === end[0] && y === end[1] && remainTreasure === 0) {
paths.push([...path]);
path.pop();
board[x][y] = temp;
return;
}
board[x][y] = 2;
dfs(x + 1, y, path, remainTreasure);
dfs(x - 1, y, path, remainTreasure);
dfs(x, y + 1, path, remainTreasure);
dfs(x, y - 1, path, remainTreasure);
board[x][y] = temp;
path.pop();
};
dfs(start[0], start[1], [], numTreasures);
if (paths.length === 0) {
return [];
}
let minPaths = paths[0].length;
for (let i = 0; i < paths.length; i++) {
minPaths = Math.min(minPaths, paths[i].length);
}
return paths.filter((path) => path.length === minPaths);
}
