HRT SWE summer intern 11月底新鲜OA

刚做完 HRT SWE summer 2023 intern的OA，2个小时4题，其中第三题是filesystem with unit test的题目，其余三个都是single function的题。
看来还是刷题刷的不够，从没刷过unit test的题，遇到第三题就卡住没写出来，其余三题都过了。

• 第一题是地里出现的HRT的高频题，也是leetcode上的原题： Leetcode 67: Add Binary String。（这题就不贴图了）
• 第二题是diamond cipher，给你一个2n*n的table，要你返回经过diamond cipher变换之后的table。我读了好久的题目才看懂该怎么变化。。。看懂题意之后找找规律，重点看新的table的每一行出现在原来table的哪些位置，最后直接按行算出新的table，并不算太难。
• 第三题是根据
  您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  使用VIP即刻解锁阅读权限或查看其他获取积分的方式

  游客，您好！
  本帖隐藏的内容需要积分高于 188 才可浏览
  您当前积分为 0。
  VIP即刻解锁阅读权限 或 查看其他获取积分的方式
  
  queries取到的最小值数组。最直观的解法是把matrix构造出来，然后暴力更新matrix和搜取最小值，但是这样会超时。优化了好久，在最后还剩两分钟的时候终于通过了所有的test cases。
  

AK82 发表于 2022-12-02 15:41:26
请问最后一题可以怎么优化呀，想半天想不出来，只会暴力解法

不要建表，直接return i+1 * j+1

乱七八糟的Leo 发表于 2022-12-2 23:48
不要建表，直接return i+1 * j+1

说的没错，首先是不要建表。然后对于行和列各维护一个数组: [1,2,3,...,num_row], [1,2,3,...,num_col]。deactive行和列的时候从数组里删掉对应的行和列。取最小值的时候直接去行列数组的第一位相乘，得到的就是最小值了。

匿名用户 发表于 2022-12-3 13:15
第四题的code，但凡再多一个for循环都会tle。。。
请大家多多指教~

请问给的test case没有重复deactivate嘛？因为remove如果尝试删除已经不在的elem会报错的

欢迎讨论，若有好心人，给点米吧~~谢谢！

感謝你的分享，很有用的資訊

请问最后一题可以怎么优化呀，想半天想不出来，只会暴力解法

第四题的code，但凡再多一个for循环都会tle。。。
请大家多多指教~

请问投的是core还是Algo呀？  谢谢~

匿名用户 发表于 2022-12-3 13:10
说的没错，首先是不要建表。然后对于行和列各维护一个数组: [1,2,3,...,num_row], [1,2,3,...,num_col]。 ...

真的如此，好厉害～

谢谢楼主分享～