24時間符号化インタビュー準備課題
99755 ワード
私は、コーディングの課題の60分に基づいて開発者のスキルを測定する大きな信者ではない.これらの問題は、そのような方法では、アルゴリズムを知っていれば15分を解決する必要がありますように設計されています.こんな短い時間で難しい現実の問題を解決した時を思い出すことができません.すべての複雑な問題を解決する時間がかかります.
しかし、1月6日の月曜日に2回のコーディング・インタビューがあります.だから、インタビューのプロセスについて不平を言う代わりに、2020年1月4日の明日の朝、8時00分に8 : 00に1時間5時までに24時間の出費をする.その間、データ構造とアルゴリズムを研究します.
私は定期的に私の進捗状況を更新し、ノートやコードを発行します.ここでは私が心に持っているトピックです配列とストリング 関連リスト スタックとキュー の木 のグラフ ビット操作 リカバリ ダイナミックプログラミング の検索とソート
私は、Gayle Laakmann McdowellとJavaScriptを使ったデータ構造とアルゴリズムによるコーディングインタビューを解読する予定です.
私は他のブログ記事を読んで、多くのコーディング問題を解決することができます.
あなたが知っているどんな良いインタビュー準備資源でも私と共有してください.私は、このポストと会話が彼らがコーディングインタビューの準備をする少しの時間があるとき、誰でも参照することができるすばらしい場所であることを望みます.
1日目(2020年1月4日)
のアレイ のストリング 関連リスト スタック キュー の木 のグラフ 検索 私はトピックを研究し、すべての有用なリソースを文書化し、各トピックで5/10の問題を解決し、2時間ごとにコミュニティを更新します.コミュニティは偉大な説明責任パートナーになると思います.
どのようにマスターデータ構造を迅速に最善のアイデアを共有してください.何か提案があります.
次の更新は午後12時です.
私は 私が取り組んだプログラミング問題は以下の通りです
しかし、1月6日の月曜日に2回のコーディング・インタビューがあります.だから、インタビューのプロセスについて不平を言う代わりに、2020年1月4日の明日の朝、8時00分に8 : 00に1時間5時までに24時間の出費をする.その間、データ構造とアルゴリズムを研究します.
私は定期的に私の進捗状況を更新し、ノートやコードを発行します.ここでは私が心に持っているトピックです
私は、Gayle Laakmann McdowellとJavaScriptを使ったデータ構造とアルゴリズムによるコーディングインタビューを解読する予定です.
私は他のブログ記事を読んで、多くのコーディング問題を解決することができます.
あなたが知っているどんな良いインタビュー準備資源でも私と共有してください.私は、このポストと会話が彼らがコーディングインタビューの準備をする少しの時間があるとき、誰でも参照することができるすばらしい場所であることを望みます.
1日目(2020年1月4日)
私は、午前10時に私の24時間のコーディングインタビュー準備挑戦を始めました.私は完璧なコーヒーカップを持って、私はコーディングインタビューの準備をクラックする準備ができています.
どのようにマスターデータ構造を迅速に最善のアイデアを共有してください.何か提案があります.
次の更新は午後12時です.
12時更新
Cracking the Coding Interview
ブックの最初の章を読んだ.配列と文字列
1一意です:文字列がすべてのユニークな文字を持つかどうかを判断するアルゴリズムを実装します。追加のデータ構造を使用できない場合は?
function uniqueCharacters(str) {
const ASCII_CHARS = 256;
if(str.length > ASCII_CHARS) {
return false;
}
const chars = Array(ASCII_CHARS).fill(false);
for(let char of str){
const index = char.charCodeAt(0);
if (chars[index] === true) {
return false;
}
chars[index] = true;
}
return true;
}
console.log(uniqueCharacters('abcd10jk')); // true
console.log(uniqueCharacters('hutg9mnd!nk9')); // false
2 .チェック置換:2つの文字列を指定し、1つがもう一方の置換であるかどうかを決定するメソッドを書き込みます。
function isPermutation(str1, str2) {
if (str1.length !== str2.length) {
return false;
}
const map = new Map();
for(const char of str1) {
if(map.has(char)) {
map.set(char, map.get(char) + 1);
} else {
map.set(char, 1);
}
}
for(const char of str2) {
if(map.has(char)) {
const value = map.get(char);
if(value === 0) {
return false;
} else {
map.set(char, map.get(char) - 1);
}
}
}
for(const value of map.values()) {
if(value !== 0) {
return false;
}
}
return true;
}
console.log(isPermutation("god", "dog")); // true
3 . urlify :文字列内のすべてのスペースを'% 20 'で置換するメソッドを書き込みます。
function replaceSpaces(str, trueLength) {
let output = "";
let chars = 0;
for(let char of str) {
if(char !== " ") {
chars++;
}
}
let spaces = trueLength - chars;
for(let char of str) {
if(char === " " && spaces > 0) {
output += "%20";
spaces--;
} else if(char !== " ") {
output += char;
}
}
while(spaces > 0) {
output += "%20";
spaces--;
}
return output;
}
console.log(replaceSpaces("Mr 3ohn Smith", 13)); // "Mr%203ohn%20Smith"
3 . Palindrome permutation :文字列を指定して、それをパーマネンドームの置換であるかどうかを調べる関数を書き込む
function isPermutationOfPalindrome(str) {
let charCount = 0;
let map = new Map();
for(let char of str) {
if (char === " ") {
continue;
}
if(map.has(char)) {
map.delete(char);
} else {
map.set(char, true);
}
charCount++;
}
if(charCount % 2 === 0) {
return map.size === 0;
} else {
return map.size === 1;
}
}
console.log(
isPermutationOfPalindrome("tacoa cat") === true,
isPermutationOfPalindrome("atco cat") === true,
isPermutationOfPalindrome(" rac ecar rara ") === true
);
4 . String Compression :繰り返し文字数を使用して基本的な文字列圧縮を実行するメソッドを実装します。
function compress (str) {
const map = new Map();
let result = '';
for(const char of str) {
if(map.has(char)) {
map.set(char, map.get(char) + 1);
} else {
map.set(char, 1);
}
}
for(let [key, value] of map) {
result += key + value;
}
return str.lenght >= result.lenght ? str : result;
}
console.log(compress('aabcccccaaa')); // "a5b1c5"
(5)マトリックスを回転させる:画像中の各画素が4バイトのNXN行列で表される画像を与え、画像を90度回転させる方法を書く。
function rotateMatrix(arr) {
let n = arr.length - 1;
for (let i = 0; i < n; i++) {
for (let j = 0; j < n - i; j++) {
let temp = arr[i][j];
arr[i][j] = arr[n - j][n - i]; // top row
arr[n - j][n - i] = temp; // right column
}
}
return arr;
}
console.log(rotateMatrix([
[1,2,3],
[4,5,6],
[7,8,9]
]));
/*
[
[9, 6, 3],
[8, 5, 2],
[7, 4, 1]
]
*/
6 .文字列の回転つの単語が別の部分文字列であるかどうかを調べるメソッドIssubstrin Gを仮定します。S 1とS 2の2つの文字列が与えられた場合、S 2がS 1の回転であるかどうかをチェックするために書き込みます。
const isSubstring = (str1, str2) => str1.includes(str2);
function isRotation(str1, str2) {
if(!str1 || !str2) {
return false;
}
if(str1.length !== str2.length) {
return false;
}
return isSubstring(str1 + str2, str2);
}
console.log(isRotation("waterbottle", "erbottlewat")); // true
console.log(isRotation("aacdf", "acda")); // false
7 .与えられた文字列あるいは配列の最初のユニークな文字を探す
function findFirstUniqueCharacter(str) {
if(!str) return;
const map = new Map();
for(let char of str) {
if(map.has(char)) {
map.set(char, map.get(char) + 1);
} else {
map.set(char, 1);
}
}
for(let [key, value] of map) {
if(value === 1) {
return key;
}
}
return "None";
}
console.log(findFirstUniqueCharacter('foobar')); // f
console.log(findFirstUniqueCharacter('aabbccdef')); // d
console.log(findFirstUniqueCharacter('aabbcc')); // 'No Unique Character Found'
3時30分更新
連結リスト
リンクリストノードクラス
class Node {
constructor(value, next = null) {
this.value = value;
this.next = next;
}
}
連結リスト印刷機能
function print(node) {
while(node !== null) {
console.log('->' + node.value);
node = node.next;
}
}
DUPSを削除します。ソートされていないリンクリストから重複を取り除くコードを書く。
function removeDups(node) {
if(node === null) return null;
let nodes = new Map();
let current = node.next;
let prev = node;
nodes.set(node.value, 1);
while(current !== null) {
if(nodes.get(current.value) === 1) {
prev.next = current.next;
} else {
nodes.set(current.value, 1);
prev = current;
}
current = current.next;
}
return node;
}
let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);
let node4 = new Node(2);
let node5 = new Node(1);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
print(removeDups(node1));
/*
"->1"
"->2"
"->3"
*/
最後にkth to return :単一リンクリストの最後の要素にkthを見つけるアルゴリズムを実装します。
function KthToLast(root, n) {
if(!root) return null;
let current = root;
let follower = root;
for(let i = 0; i < n; i++) {
current = current.next;
}
while(current.next !== null) {
current = current.next;
follower = follower.next;
}
return follower;
}
let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);
let node4 = new Node(4);
let node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
console.log(KthToLast(node1, 2).value); // 3
3 .リンクリストの削除
function removeDups(head) {
if(head === null) return null;
let fast = head;
let slow = head;
let prev = null;
while(fast !== null && fast.next !== null) {
fast = fast.next.next;
prev = slow;
slow = slow.next;
}
prev.next = slow.next;
return head;
}
let nodeA = new Node('a');
let nodeB = new Node('b');
let nodeC = new Node('c');
let nodeD = new Node('d');
let nodeE = new Node('e');
let nodeF = new Node('f');
nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;
nodeE.next = nodeF;
nodeF.next = null;
print(removeDups(nodeA));
/*
"->a"
"->b"
"->c"
"->e"
"->f"
*/
4 .リンクリストを指定した値の周りに分割し、リストの要素を安定させることが気にならない場合
function partition(head, x) {
let tail = head;
let current = head;
while(current !== null) {
let next = current.next;
if(current.value < x) {
current.next = head;
head = current;
} else {
tail.next = current;
tail = current;
}
current = next;
}
tail.next = null;
return head;
}
let nodeA = new Node(3);
let nodeB = new Node(5);
let nodeC = new Node(8);
let nodeD = new Node(2);
let nodeE = new Node(10);
let nodeF = new Node(2);
let nodeH = new Node(1);
nodeA.next = nodeB;
nodeB.next = nodeC;
nodeC.next = nodeD;
nodeD.next = nodeE;
nodeE.next = nodeF;
nodeF.next = nodeH;
nodeH.next = null;
print(partition(nodeA, 5));
/*
"->1"
"->2"
"->2"
"->3"
"->5"
"->8"
"->10"
*/
各々のノードが2つのポインタを有するリンクリストを与えられて、次のノードおよびリストのランダムなノードへの1つは、連結リストをクローン化する。
function clone(node) {
if(node === null) return node;
let map = new Map();
let copy = new Node(node.value);
let current = node;
let newHead = copy;
map.set(current, copy);
current = current.next;
while(current !== null) {
let temp = new Node(current.value);
map.set(current, temp);
copy.next = temp;
copy = temp;
current = current.next;
}
current = node;
copy = newHead;
while(current !== null) {
if(current.randome !== null) {
copy.random = map.get(current.random);
} else {
copy.random = null;
}
current = current.next;
copy = copy.next;
}
return newHead;
}
リンクされたリストを与えられるなら、それがサイクルを含むかどうか決定してください。
function hasCycle(node) {
if(node === null) return false;
let slow = node;
let fast = node.next;
while(fast !== null && fast.next !== null) {
if(fast === slow) return true;
slow = slow.next;
fast = fast.next.next;
}
return false;
}
let node1 = new Node(1);
let node2 = new Node(2);
let node3 = new Node(3);
let node4 = new Node(4);
let node5 = new Node(5);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = node3;
console.log(hasCycle(node1)); // true
1つのパスでリンクリストの中間要素を見つける方法?
function findMiddle(node) {
if(node === null) return null;
let fast = node.next;
let slow = node;
while(fast !== null && fast.next !== null) {
fast = fast.next.next;
slow = slow.next;
}
console.log(slow.value);
}
let node1 = new Node(5);
let node2 = new Node(6);
let node3 = new Node(7);
let node4 = new Node(1);
let node5 = new Node(2);
node1.next = node2;
node2.next = node3;
node3.next = node4;
node4.next = node5;
node5.next = null;
findMiddle(node1); // 7
2つの数を加える
// Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
// Output: 7 -> 0 -> 8
// Explanation: 342 + 465 = 807.
const addTwoNumbers = function(l1, l2) {
let head = new Node(0);
let carry = 0;
let current = head;
while(l1 !== null || l2 !== null ) {
const x = l1 !== null ? l1.value : 0;
const y = l2 !== null ? l2.value : 0;
const sum = carry + x + y;
carry = Math.floor(sum / 10);
current.next = new Node(sum % 10);
current = current.next;
if(l1 != null) l1 = l1.next;
if(l2 != null) l2 = l2.next;
}
if (carry > 0) {
current.next = new ListNode(carry);
}
return head.next;
};
const node13 = new Node(3);
const node12 = new Node(4);
const node11 = new Node(2);
node11.next = node12;
node12.next = node13;
const l1 = node11;
const node23 = new Node(4);
const node22 = new Node(6);
const node21 = new Node(5);
node22.next = node23;
node21.next = node22;
const l2 = node21;
print(addTwoNumbers(l1, l2));
/*
"->7"
"->0"
"->8"
*/
午後7時45分更新
スタック
スタックを追加した場合、スタック内の要素はアンスタック以外のスタックを使用します
Array.prototype.peek = function() {
return this[this.length -1];
}
Array.prototype.isEmpty = function() {
return this.length <= 0;
}
function sortStack(stack) {
if(!stack || stack.length ===0) return stack;
let newStack = [];
newStack.push(stack.pop());
while(!stack.isEmpty()) {
const temp = stack.pop();
while(!newStack.isEmpty() && temp > newStack.peek()) {
stack.push(newStack.pop());
}
newStack.push(temp);
}
return newStack;
}
console.log(sortStack([5, 1, 3, 2, 4])); // [5, 4, 3, 2, 1]
2 . JavaScriptの逆ポーランド記法を評価する
function reversePolishNotation(seq) {
if(seq.length <= 2) {
return;
}
const operands = ['+', '-', '*', '/'];
const stack = [];
let i = 0;
stack.push(seq[i]);
i++;
while(i <= seq.length) {
let item = seq[i];
let index = operands.indexOf(item);
if(index < 0) {
stack.push(item);
} else {
const a = parseInt(stack.pop(), 10);
const b = parseInt(stack.pop(), 10);
if(index === 0) {
stack.push(a + b);
}
if(index === 1) {
stack.push(a - b);
}
if(index === 2) {
stack.push(a * b);
}
if(index === 3) {
stack.push(b/a);
}
}
i++;
}
return parseInt(stack[0], 0);
}
console.log(reversePolishNotation(["2", "1", "+", "3", "*"])) // 9
console.log(reversePolishNotation(["4", "13", "5", "/", "+"])) // 6
console.log(reversePolishNotation(["10", "6", "9", "3", "+", "-11", "*", "/", "*", "17", "+", "5", "+"])) // 22
console.log(reversePolishNotation(["2", "1"])) // undefined
JavaScriptを使用したスタックの実装
function Stack() {
this.top = null;
}
Stack.prototype.push = function (val) {
let node = {
data : val,
next : null
};
node.next = this.top;
this.top = node;
};
Stack.prototype.pop = function () {
if(this.top === null) {
return null;
} else {
const top = this.top;
this.top = this.top.next;
return top.data;
}
};
Stack.prototype.peek = function() {
if(this.top === null) {
return null;
} else {
return this.top.data;
}
}
var S1 = new Stack();
S1.push(5);
S1.push(6);
S1.push(7);
S1.push(8);
console.log(S1.pop()); // 8
console.log(S1.pop()); // 7
二つのスタックを使用したキュー
function Queue() {
this.pushStack = new Stack();
this.popStack = new Stack();
}
Queue.prototype.enqueue = function(value) {
this.pushStack.push(value);
}
Queue.prototype.dequeue = function() {
let popStack = this.popStack;
let pushStack = this.pushStack;
if(popStack.peek()) {
const deq = popStack.pop();
return deq;
}
while(pushStack.peek()) {
popStack.push(pushStack.pop());
}
}
const q1 = new Queue();
q1.enqueue(3);
q1.enqueue(4);
q1.enqueue(5);
q1.enqueue(6);
q1.enqueue(7);
q1.dequeue();
q1.dequeue();
q1.dequeue();
console.log(q1);
5 .
function stepsToSolveTowerOfHanoi(height, from, to, via) {
if (height >= 1) {
// Move a tower of height - 1 to buffer peg using destination peg
stepsToSolveTowerOfHanoi(height - 1, from, via, to);
// Move the remaining disk to the destination peg.
console.log(`Move disk ${height} from Tower ${from} to Tower ${to}`);
// Move the tower of `height-1` from the `buffer peg` to the `destination peg` using the `source peg`.
stepsToSolveTowerOfHanoi(height - 1, via, to, from);
}
return;
}
stepsToSolveTowerOfHanoi(3, "A", "C", "B");
/*
"Move disk 1 from Tower A to Tower C"
"Move disk 2 from Tower A to Tower B"
"Move disk 1 from Tower C to Tower B"
"Move disk 3 from Tower A to Tower C"
"Move disk 1 from Tower B to Tower A"
"Move disk 2 from Tower B to Tower C"
"Move disk 1 from Tower A to Tower C"
*/
6 .文字列が有効な括弧からなるならば、正当化してください
function isMatchingBrackets(str) {
if(str.length <= 1) {
return false;
}
let stack = [];
const map = {
'{': '}',
'[': ']',
'(': ')'
};
for(let char of str) {
if(char === '(' || char === '[' || char === '{') {
stack.push(char);
} else {
const last = stack.pop();
if (char !== map[last]) {
return false;
}
}
}
return stack.length === 0;
}
console.log(isMatchingBrackets("(){}")); // true
console.log(isMatchingBrackets("[{()()}({[]})]({}[({})])((((((()[])){}))[]{{{({({({{{{{{}}}}}})})})}}}))[][][]")); // true
console.log(isMatchingBrackets("({(()))}}")); // false
Reference
この問題について(24時間符号化インタビュー準備課題), 我々は、より多くの情報をここで見つけました https://dev.to/zahidulislam/24-hour-coding-interview-prep-challenge-29adテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol