📣 黑五价提前开抢|VIP一年通行证5折,蓝莓、Offer多多同步特惠
楼主: smilelin
跳转到指定楼层
上一主题 下一主题
收起左侧

[其他] 8月刷题/Mock interview接龙活动(缺米刷题的来)

   关闭
🔗
oo糖罐 2020-8-7 11:38:12 | 只看该作者
全局:
Day 4 三道题

Screen Shot 2020-08-06 at 11.37.40 PM.png (32.04 KB, 下载次数: 0)

Screen Shot 2020-08-06 at 11.37.40 PM.png

评分

参与人数 3大米 +3 收起 理由
082520194610 + 1 给你点个赞!
fnwjkm + 1 给你点个赞!
hand我是好人 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

全局:
8.6 Day6 打卡,今天做了两个OA,只刷了一道hard,也费了不少时间 :(

image.png (43.84 KB, 下载次数: 0)

image.png

评分

参与人数 2大米 +2 收起 理由
mereflora + 1 给你点个赞!
fnwjkm + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
fnwjkm 2020-8-7 11:40:27 | 只看该作者
全局:
8.6 打卡

1. A星算法,非常重要。建议大家去做一做。
2. 标准的BFS。换了一个马甲。
3. O(N) space的做法有Set就可以。O(1) 的做法可以把value -> idx做一个映射,比相对应的位置的值置为负数。

Screen Shot 2020-08-06 at 8.36.42 PM.png (50.73 KB, 下载次数: 0)

Screen Shot 2020-08-06 at 8.36.42 PM.png

评分

参与人数 3大米 +3 收起 理由
yaozheng + 1 给你点个赞!
mereflora + 1 给你点个赞!
082520194610 + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
082520194610 2020-8-7 11:53:50 | 只看该作者
全局:
今天学习了Trie~

211 Add and Search Word - Data Structure Design

/* For data structure design questions like this one, the basic idea is very similar to logger design questions. It is easy to come up with a solution. But the essence of the question is to acknowledge different trade-offs of ds. */

My Notes
Method 1: Brute Force
Create a linked list. To add a word, we append the word to the end of list. To search, we loop the linked list and compare each word in the list to see if it is a good fit.

Add:
Time Complexity: O(1)
Space Complexity: O(N), no extra memory

Search
Time Complexity: O(N * m), where m is the maximum length of word.
Space Complexity: O(1)

Given a word and a pattern, it is not that easy to determine if it is a match.

Method 2: Use a set to store add possible patterns for a word
Example: “dad” , we need to add
d*,* *a*, **d, dad, da*, *ad,d*d
Add:
Time Complexity: O(len)
Space O(2^len * N)
Search
Time Complexity: O(1)
Space O(1)

The short come of this method is that I think it is not really storing the words. It is designed solely to faster searching process.

Method 3: Trie

Add: O(word length)
Search: O(word length) - O(M*N)
Memory: O(n*word length*26(alphabetic a))

———————————————————————
Solution

Method 1: HashMap<Integer Word Length, Set<String>>
Time Complexity: O(M*N), where M represents length of the word, N represents number of strings at the length



Method 2: Trie
Trie implementation is pretty straightforward, it's basically nested hashmaps. At each step, one has to verify, if the child node to add is already present. If yes, just go one step down. If not, add it into the trie and then go one step down.

https://leetcode.com/problems/ad ... and-clean-Java-code

With backtracking

Class TrieNode里面 TrieNode(){}要是public TrieNode(){}

——————————————————————————————————
Related Questions
There are two main types of trie interview questions:
* Standard Trie. Design a structure to dynamically add and search strings, for example
    * Add and Search Word.

    * Word Search II.

    * Design Search Autocomplete System.

* Bitwise Trie. Design a structure to dynamically add binary strings and compute maximum/minimum XOR/AND/etc, for example
    * Maximum XOR of Two Number in an Array.

评分

参与人数 3大米 +3 收起 理由
URNOTJANET + 1 给你点个赞!
yaozheng + 1 给你点个赞!
mereflora + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
mereflora 2020-8-7 11:54:22 | 只看该作者
全局:
今天复习了之前做过的backtracking的几道题(combinations, permutations, generate parentheses),做了Letter Combinations of a Phone Number, Palindrome Permutation II, Palindrome Partitioning。

8-6-leetcode.png (135.99 KB, 下载次数: 0)

8-6-leetcode.png

评分

参与人数 2大米 +3 收起 理由
URNOTJANET + 1 给你点个赞!
yaozheng + 2 很有用的信息!

查看全部评分

回复

使用道具 举报

🔗
yaozheng 2020-8-7 11:57:51 | 只看该作者
全局:
8.6

评分

参与人数 2大米 +2 收起 理由
LyanW + 1 给你点个赞!
URNOTJANET + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
URNOTJANET 2020-8-7 11:59:30 | 只看该作者
全局:
8.6 每日一题 Find All Duplicates in an Array
这个题感觉很容易想到 O(n) 解法吧,一个 hashset 判断是否重复添加元素即可。如果限定不能使用hashset可能还有点挑战(等于自己写个hash table?)
另外今天把求职公司的单子差不多列出来了,之后就要开始广撒网的日子辽

评分

参与人数 2大米 +2 收起 理由
gyzdmgqy + 1 给你点个赞!
LyanW + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

全局:
交作业啦~今天其实做了5题。Leetcode上3题可以截图。
Lintcode上两道backpack不知道为啥只能显示当前做的submission history,而不能显示总的history。
我就只上了LeetCode的图

image.png (81.78 KB, 下载次数: 3)

image.png

评分

参与人数 4大米 +4 收起 理由
yoyoliang + 1 给你点个赞!
99887766 + 1 给你点个赞!
gyzdmgqy + 1 给你点个赞!
LyanW + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
LyanW 2020-8-7 12:01:01 | 只看该作者
全局:
八月day4

昨晚半夜睡不着,又爬起来刷了三道,加上今天一共四道题
two sum
remove duplicates
single number
move zeros

睡不好真的很影响脑子……
求加米,感谢

Screen Shot 2020-08-06 at 10.57.18 PM.png (220.52 KB, 下载次数: 2)

Screen Shot 2020-08-06 at 10.57.18 PM.png

评分

参与人数 3大米 +3 收起 理由
andrewsun + 1 给你点个赞!
zhxy222td + 1 给你点个赞!
gyzdmgqy + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

🔗
gyzdmgqy 2020-8-7 12:18:37 | 只看该作者
全局:

刷题打卡第6天
6.ZigZag Conversion 这是一道medium题,关键是想明白采用哪种算法,一种是类似仿真,同步build每一行的string,另外一种是直接计算出每一行的string.然后要处理第一行和最后一行的corner case. 另外我个人漏了考虑输入长度为1的特殊情况。

8. String to Integer (atoi) 这是一道medium题,想明白按照顺序处理string,先把空格都处理掉,然后正负号,然后找到第一个数值和最后一个数值,然后转换,转换的时候检查有没有越界。

4. Median of Two Sorted Arrays 今天刷了一道Hard题 到达到O(log(m+n))就需要binary search, 不能通过遍历或者insertion的算法,关键想明白什么是median以及如何判定收敛,核心思路是在两个array上找到两个cut,分别将所有数分成左右两部分,左边的最大值小于右边的最小值,然后对四个边界值求解中位数。corner case也花了一些时间处理,关键是想明白如何会发生corner case(数组越界)然后引入math.inf和-math.inf进行一般化处理就能实现。

Capture.PNG (24.71 KB, 下载次数: 2)

Capture.PNG

评分

参与人数 3大米 +3 收起 理由
jerryzzf + 1 给你点个赞!
andrewsun + 1 给你点个赞!
zhxy222td + 1 给你点个赞!

查看全部评分

回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表