Code Monkey home page Code Monkey logo

interview's People

Contributors

sskyy avatar

Stargazers

 avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar  avatar

Watchers

 avatar  avatar

interview'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 photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo 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.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google ❤️ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.