interview's People
Forkers
zitup yingpengsha shanxiaohan qiaohong0708 xyyit9 jozdortraz kiesun wgsheng06 quarkgluonplasma trojan0523 imcuttle muyingjie zack-bee snow233 zer0fire sheepy1interview's Issues
1、4、5题用时一小时 其中一题打印用时20分钟
// 1
let arr = [
'Allegoric Alaskans;Blithering Badgers;win',
'Devastating Donkeys;Courageous Californians;draw',
'Devastating Donkeys;Allegoric Alaskans;win',
'Courageous Californians;Blithering Badgers;loss',
'Blithering Badgers;Devastating Donkeys;loss',
'Allegoric Alaskans;Courageous Californians;win'
]
function fn(arr) {
let obj = {}
arr.map(arrItem => {
let splitArr = arrItem.split(';')
splitArr.map((item, index) => {
if (index != 2) {
if (obj[item]) {
obj[item].MP += 1
} else {
obj[item] = {
MP: 1,
W: 0,
D: 0,
L: 0,
P: 0
}
}
}
})
switch (splitArr[2]) {
case 'win':
obj = winCount(splitArr[0], obj)
obj = lossCount(splitArr[1], obj)
break;
case 'draw':
obj = drawCount([splitArr[0], splitArr[1]], obj)
break;
case 'loss':
obj = winCount(splitArr[1], obj)
obj = lossCount(splitArr[0], obj)
break;
default:
break;
}
})
objToArrAndLog(obj)
}
function winCount(win, iobj) {
let obj = { ...iobj }
obj[win].W += 1
obj[win].P += 3
return obj
}
function lossCount(loss, iobj) {
let obj = { ...iobj }
obj[loss].L += 1
return obj
}
function drawCount(arr, iobj) {
let obj = { ...iobj }
arr.map(item => {
obj[item].D += 1
obj[item].P += 1
})
return obj
}
function objToArrAndLog(obj) {
let arr = []
Object.keys(obj).map(item => {
let indexArr = []
indexArr.push(item)
indexArr.push(...Object.values(obj[item]))
arr.push(indexArr)
})
arr = arr.sort(pSort)
logRes(arr)
}
function pSort(x, y) {
if (x[5] === y[5]) {
return wordSort(x[1], y[1])
} else {
return y[5] - x[5]
}
}
function wordSort(x, y) {
let x1 = x.toUpperCase();
let y1 = y.toUpperCase();
if (x1 < y1) {
return -1;
}
if (x1 > y2) {
return 1;
}
return 0;
}
function logRes(arr) {
let newArr = []
console.log('Team | MP | W | D | L | P')
arr.map(item => {
let indexArr = []
item.map((item1, index) => {
if (index === 0) {
indexArr.push(item1.padEnd(26))
} else if (index === 1) {
let newItem1 = item1
newItem1 = String(newItem1).padStart(2)
newItem1 = String(newItem1).padEnd(4)
indexArr.push(newItem1)
} else {
let newItem1 = item1
newItem1 = String(newItem1).padStart(2)
newItem1 = String(newItem1).padEnd(3)
indexArr.push(newItem1)
}
})
newArr.push(indexArr)
})
newArr.map(item => {
let str = JSON.stringify(item).replace(/\[|\]|"|"/g, '')
str = str.replace(/,/g, '|')
console.log(str)
})
}
fn(arr)
// 4
let inputArr = [[1, 2], [1, 2], [1, 6], [2, 3], [2, 4], [3, 1], [3, 4], [4, 1], [5, 6], [5, 1], [4, 5], [5, 6], [6, 1]]
function fn(inputArr) {
let indexObj = {}
let sortArr = []
inputArr.map((item, index) => {
if (indexObj[item[0]]) {
indexObj[item[0]] = [...indexObj[item[0]], item[1]]
} else {
indexObj[item[0]] = [item[1]]
}
})
sortArr = groupArr(Object.keys(indexObj).sort(), [], sortArr)
if (sortArr) {
return getArr(indexObj, sortArr)
} else {
return false
}
}
function getArr(indexObj, sortArr) {
let arr = []
sortArr.map((item, index) => {
if (arr.length) {
if (indexObj[arr[arr.length - 1][1]]) {
if (index != sortArr.length - 1) {
if (indexObj[item].includes(Number(item) + 1) && indexObj[Number(item) + 1]) {
arr.push([Number(item), Number(item) + 1])
} else {
arr = []
}
} else {
if (indexObj[Number(item)].includes(arr[0][0])) {
arr.push([Number(item), arr[0][0]])
} else {
arr = []
}
}
}
} else {
if (indexObj[item].includes(Number(item) + 1)) {
arr.push([Number(item), Number(item) + 1])
}
}
})
if (arr.length) {
return arr
} else {
return false
}
}
function groupArr(arr, sarr, sortArr) {
let newarr = sarr || []
if (newarr.length) {
if (Number(newarr[newarr.length - 1]) + 1 === Number(arr[0])) {
newarr.push(arr.shift())
if (arr.length === 0) {
return newarr
}
} else {
return false
}
} else {
newarr.push(arr.shift())
}
if (arr.length > 0) {
groupArr(arr, newarr, sortArr)
}
return newarr
}
// 5
// 1
let res = fn(inputArr)
console.log('res', res);
class Bus {
constructor() {
this.task = {}
}
listen(name, cb) {
this.task[name] = cb
}
listenMore(name, cb) {
if (name.length != cb.length) {
return new Error('多重监听参数如([],[])且[]长度应一致')
} else {
name.map((item, index) => {
this.task[item] = cb[index]
})
}
}
trigger(...name) {
name && name.map(item => {
if (this.task[item]) {
this.task[item]()
this.unListen(item)
} else {
console.log(`${item}该函数未监听`);
// throw new Error(`${item}该函数未监听`)
}
})
}
unListen(name) {
this.task[name] = null
}
}
const bus = new Bus()
bus.listen('testEvent', (...argv) => {
console.log('event callback')
})
bus.trigger('testEvent', 1, 2)
// TODO:2、3
可以算是一次周赛了
在一个微信群里看到链接的,花了两个小时刷了一下前四道题,其中第二道颇有难度,需要组合拓扑排序和并查集分组,有点力扣周赛hard题的感觉。
附代码,由于没有构建多少test cases,所以下面如有错误请帮忙指出。
type CompletionResult = {
mp:number;
w:number;
d:number;
l:number;
p:number;
}
// 第一题分割字符串后直接用HashMap分组
const s1 = (str:string)=>{
const ret = Array.from(str.split("\n").map(v=>v.split(";")).reduce((map,[a,b,r])=>{
if(!map.has(a)) map.set(a,{mp:0,w:0,d:0,l:0,p:0})
if(!map.has(b)) map.set(b,{mp:0,w:0,d:0,l:0,p:0})
const oldA = map.get(a)!
const oldB = map.get(b)!
oldA.mp++
oldB.mp++
if(r=='draw') {
oldA.d++
oldB.d++
oldA.p++
oldB.p++
}else if(r=='win'){
oldA.w++
oldB.l++
oldA.p+=3
}else{
oldA.l++
oldB.w++
oldB.p+=3
}
return map
},new Map<string,CompletionResult>()))
.sort((a,b)=>b[1].p-a[1].p)
.map(([name,{mp,w,d,l,p}])=>{
return `${name.padEnd(32)}| ${mp} | ${w} | ${d} | ${l} | ${p}`
}).join("\n")
return `${"Team".padEnd(32)}| MP | W | D | L | P\n` + ret
}
console.log("第一题:\n"+s1(`Allegoric Alaskans;Blithering Badgers;win
Devastating Donkeys;Courageous Californians;draw
Devastating Donkeys;Allegoric Alaskans;win
Courageous Californians;Blithering Badgers;loss
Blithering Badgers;Devastating Donkeys;loss
Allegoric Alaskans;Courageous Californians;win`))
type Q2Item = {
id:number
before?:number
after?:number
first?:boolean
last?:boolean
}
// 第二题运用到拓扑排序+并查集分组
const s2 = (arr:Q2Item[])=>{
const map = new Map(arr.map(({id})=>[id,{id,afters:[] as number[]}]))
let firstId:null|number = null
let lastId:null|number = null
const uSet = new Map<number,number>()
for(let {id,before,after,first,last} of arr){
uSet.set(id,id)
const node = map.get(id)!
if(before!=null) {
if(!map.has(before)) throw new Error(`node ${before} is not exist`)
const pre = map.get(before)!
pre.afters.push(id)
}
if(after!=null) node.afters.push(after)
if(first==true && last==true){
if(arr.length>1) throw new Error('error')
return [id]
}
if(first==true){
if(firstId!=null) throw new Error(`node ${id} is the first one!`)
firstId = id
}
if(last==true){
if(lastId!=null) throw new Error(`node ${id} is the last one!`)
lastId = id
}
}
const visited = new Map<number,boolean|null>()
const ret:number[] = []
const getParent = (id:number):number=>
uSet.get(id)==id? id:getParent(uSet.get(id)!)
const merge = (a:number,b:number)=>{
uSet.set(uSet.get(a)!,uSet.get(b)!)
}
const dfs = (id:number)=>{
const node = map.get(id)!
if(visited.get(id)==true) return;
if(visited.get(id)==false) throw new Error('cycle dependecies')
visited.set(id,false)
for(let i of node.afters){
merge(id,i)
if(visited.get(i)==false) throw new Error('cycle dependecies')
if(!visited.has(i)) dfs(i)
}
visited.set(id,true)
ret.push(id)
}
for(let {id} of arr) dfs(id)
const result = new Map<number,number[]>()
for(let id of ret){
const k = getParent(id)
if(!result.has(k)) result.set(k,[])
const lst = result.get(k)!
lst.push(id)
}
let firstNode:number[]|null = null
let lastNode:number[]|null = null
if(firstId!=null){
const f = getParent(firstId)
firstNode = result.get(f)!
result.delete(f)
if(firstNode[0]!==firstId)
throw new Error(`node ${firstId} must be the first one1`)
}
if(lastId!=null){
const f = getParent(lastId)
lastNode = result.get(f)!
result.delete(f)
if(lastNode[lastNode.length-1]!==lastId)
throw new Error(`node ${lastId} must be the last one1!`)
}
const returnArr = Array.from(result).map(v=>v[1]).flat()
if(firstNode!=null) returnArr.unshift(...firstNode)
if(lastNode!=null) returnArr.push(...lastNode)
return returnArr
}
console.log("第二题:\n"+s2([
{id: 1},
{id: 7, after: 8}, // 这里 after 的意思是自己要排在 id 为 8 元素后面
{id: 2, before: 1}, // 这里 before 的意思是自己要排在 id 为 1 的元素前面
{id: 3, after: 1}, // 这里 after 的意思是自己要排在 id 为 1 元素后面
{id: 5, first: true},
{id: 6, last: true},
{id: 8},
{id: 9},
]).join("->"))
type Q3Item = {
id:number
name:string
parentId?:number
}
type TreeNode = {
id:number
name:string
children?:Array<TreeNode>
}
// 先建好所有节点,再一次性循环填充children
const s3 = (arr:Q3Item[])=>{
const nodeMap = new Map<number,TreeNode>(arr.map(({id,name})=>[id,{id,name}]))
let root:TreeNode|null = null
for(let {id,parentId} of arr){
const node = nodeMap.get(id)!
if(parentId==null){
if(!root) root = node
else throw new Error('root exists!')
}else{
const parent = nodeMap.get(parentId)
if(!parent) throw new Error('parent is not exist!')
if(parent.children==null) parent.children = []
parent.children.push(node)
}
}
return root
}
console.log("第三题:\n"+JSON.stringify(s3([
{id:1, name: 'i1'},
{id:2, name:'i2', parentId: 1},
{id:4, name:'i4', parentId: 3},
{id:3, name:'i3', parentId: 2},
{id:8, name:'i8', parentId: 3}
]),null,2))
// 由图构建有环双链表,由于题目保证有效且有环
// 所以从任意一点出发即可,通过DFS遍历到所有节点结束
const s4 = (arr:[number,number][])=>{
const map = new Map<number,number[]>()
for(let i=0;i<arr.length;i++){
const [l,r] = arr[i]
if(!map.has(l)) map.set(l,[])
if(!map.has(r)) map.set(r,[])
map.get(l)!.push(i)
map.get(r)!.push(i)
}
const dfs = (i:number,path:Set<number>):number[]|null=>{
if(path.size==arr.length) return Array.from(path)
const lst = map.get(i)
if(lst==null) return null
for(let k of lst){
if(path.has(k)) continue;
const next = arr[k][0]==i?arr[k][1]:arr[k][0]
const ret = dfs(next,new Set(path).add(k))
if(ret!=null) return ret
}
return null
}
const ret = dfs(arr[0][0],new Set([0]))
if(ret==null) return null
const lst:[number,number][] = [[arr[0][1],arr[0][0]]]
for(let i=1;i<ret.length;i++){
const [_,preR] = lst[lst.length-1]
const [l,r] = arr[ret[i]]
lst.push(preR==l?[l,r]:[r,l])
}
return lst.map(v=>v.join(""))
}
console.log("第四题:\n"+
s4([[1, 2], [5, 3], [3, 1], [1, 2], [2, 4], [1, 6], [2, 3], [3, 4], [5, 6]]))
Recommend Projects
-
React
A declarative, efficient, and flexible JavaScript library for building user interfaces.
-
Vue.js
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
-
Typescript
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
-
TensorFlow
An Open Source Machine Learning Framework for Everyone
-
Django
The Web framework for perfectionists with deadlines.
-
Laravel
A PHP framework for web artisans
-
D3
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
-
Recommend Topics
-
javascript
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
-
web
Some thing interesting about web. New door for the world.
-
server
A server is a program made to process requests and deliver data to clients.
-
Machine learning
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
-
Visualization
Some thing interesting about visualization, use data art
-
Game
Some thing interesting about game, make everyone happy.
Recommend Org
-
Facebook
We are working to build community through open source technology. NB: members must have two-factor auth.
-
Microsoft
Open source projects and samples from Microsoft.
-
Google
Google ❤️ Open Source for everyone.
-
Alibaba
Alibaba Open Source for everyone
-
D3
Data-Driven Documents codes.
-
Tencent
China tencent open source team.