Karat
Last updated
Last updated
------------------------------------------------------------------------------------
收集了网上大部分OA题目，大部分都不难。含python解答，自己跑了test都没问题。 https://drive.google.com/file/d/ ... zc/view?usp=sharing
文件最后有一些SQL的OA，没写。 有用请加米！
------------------------------------------------------------------------------------
第一次发帖分享家具厂Karat OA
System design老5道： https://leetcode.com/discuss/int ... based-system-design 补充： a) strong vs eventual consistent: 1) 社交网络latency 20 ms； 2）web log analysis 3）Banking b) Google doc round robin: 每个doc 被分到一个server，而不是每个user c) question 4 换成FB 好友数显示，一张user table一张friendship table，每一对friends只存一条而不是换个顺序存两条，怎么scale 2 Coding a) LC 811，统计domain/subdomain数 b) longest common substring https://www.lintcode.com/problem/79/ 区别是题面把字符串换成browsing history，相应字符变成history里的每个url，而且要求输出最长连续的common history，而不是最长长度。 难度不大，但是时间比较紧
------------------------------------------------------------------------------------
总共3题，130分钟 1、N People 2、Jimmy Garden 以下内容需要积分高于 188 您已经可以浏览 3、Array A consisting of N distinct integers
------------------------------------------------------------------------------------
通过Karat的店面，一个估计是中东的大哥。
先是一堆sys design concept 的选择题和讨论题，都不难，有点工作经验都能答出来。
最后coding找单词，题目如下，求加米！
/* After catching your classroom students cheating before, you realize your students are getting craftier and hiding words in 2D grids of letters. The word may start anywhere in the grid, and consecutive letters can be either immediately below or immediately to the right of the previous letter. Given a grid and a word, write a function that returns the location of the word in the grid as a list of coordinates. If there are multiple matches, return any one. grid1 = [ ['c', 'c', 'x', 't', 'i', 'b'], ['c', 'c', 'a', 't', 'n', 'i'], ['a', 'c', 'n', 'n', 't', 't'], ['t', 'c', 's', 'i', 'p', 't'], ['a', 'o', 'o', 'o', 'a', 'a'], ['o', 'a', 'a', 'a', 'o', 'o'], ['k', 'a', 'i', 'c', 'k', 'i'], ] word1 = "catnip" word2 = "cccc" word3 = "s" word4 = "bit" word5 = "aoi" word6 = "ki" word7 = "aaa" word8 = "ooo" grid2 = [['a']] word9 = "a" find_word_location(grid1, word1) => [ (1, 1), (1, 2), (1, 3), (2, 3), (3, 3), (3, 4) ] find_word_location(grid1, word2) => [(0, 1), (1, 1), (2, 1), (3, 1)] OR [(0, 0), (1, 0), (1, 1), (2, 1)] OR [(0, 0), (0, 1), (1, 1), (2, 1)] OR [(1, 0), (1, 1), (2, 1), (3, 1)] find_word_location(grid1, word3) => [(3, 2)] find_word_location(grid1, word4) => [(0, 5), (1, 5), (2, 5)] find_word_location(grid1, word5) => [(4, 5), (5, 5), (6, 5)] find_word_location(grid1, word6) => [(6, 4), (6, 5)] find_word_location(grid1, word7) => [(5, 1), (5, 2), (5, 3)] find_word_location(grid1, word8) => [(4, 1), (4, 2), (4, 3)] find_word_location(grid2, word9) => [(0, 0)] Complexity analysis variables: r = number of rows c = number of columns w = length of the word */
------------------------------------------------------------------------------------
karat，面试官比较冷漠。。 开始是设计五小题，地里都有。 代码题我感觉还是有点难度对于我（lc只刷了100来道题），还好最后做出来了。 编程题如下： /** You're developing a system for scheduling advising meetings with students in a Computer Science program. Each meeting should be scheduled when a student has completed 50% of their academic program. Each course at our university has at most one prerequisite that must be taken first. No two courses share a prerequisite. There is only one path through the program. 以下内容需要积分高于 188 您已经可以浏览 Write a function that takes a list of (prerequisite, course) pairs, and returns the name of the course that the student will be taking when they are halfway through their program. (If a track has an even number of courses, and therefore has two "middle" courses, you should return the first one.) Sample input 1: (arbitrarily ordered) prereqs_courses1 = [ ["Foundations of Computer Science", "Operating Systems"], ["Data Structures", "Algorithms"], ["Computer Networks", "Computer Architecture"], ["Algorithms", "Foundations of Computer Science"], ["Computer Architecture", "Data Structures"], ["Software Design", "Computer Networks"] ] In this case, the order of the courses in the program is: Software Design Computer Networks Computer Architecture Data Structures Algorithms Foundations of Computer Science Operating Systems Sample output 1: "Data Structures" Sample input 2: prereqs_courses2 = [ ["Algorithms", "Foundations of Computer Science"], ["Data Structures", "Algorithms"], ["Foundations of Computer Science", "Logic"], ["Logic", "Compilers"], ["Compilers", "Distributed Systems"], ] Sample output 2: "Foundations of Computer Science" Sample input 3: prereqs_courses3 = [ ["Data Structures", "Algorithms"], ] Sample output 3: "Data Structures" Complexity analysis variables: n: number of pairs in the input / import java.io.; import java.util.*; public class Solution { public static void main(String[] argv) { String[][] prereqsCourses1 = { {"Foundations of Computer Science", "Operating Systems"}, {"Data Structures", "Algorithms"}, {"Computer Networks", "Computer Architecture"}, {"Algorithms", "Foundations of Computer Science"}, {"Computer Architecture", "Data Structures"}, {"Software Design", "Computer Networks"} }; String[][] prereqsCourses2 = { {"Algorithms", "Foundations of Computer Science"}, {"Data Structures", "Algorithms"}, {"Foundations of Computer Science", "Logic"}, {"Logic", "Compilers"}, {"Compilers", "Distributed Systems"}, }; String[][] prereqsCourses3 = { {"Data Structures", "Algorithms"} }; System.out.println(findHalfway(prereqsCourses3)); } public static String findHalfway (String[][] courses) { } } 答案：（recruiter反馈我的解法是optimal solution）
public static String findHalfway (String[][] courses) { LinkedList lst = new LinkedList<>(); int x = courses.length; // assume there is always records. //"Data Structures" -> "Algorithms" -> "Foundations of Computer Science" -> "Operating Systems" Map ba = new HashMap<>(); Map ab = new HashMap<>(); for(int i=0; i
------------------------------------------------------------------------------------
wayfair白嫖的oa，十个工作日内写完。
第一道题：特别简单的一道，给两个array，让return一个string。arr1代表next position，arr2代表每个position对应的char。从0开始，不停寻找arr1里的next position，然后回到0的时候把过程中记录的arr2 的char组成string return。说起来有点费劲，反正绝对简单。
第二道题：https://stackoverflow.com/questi ... ees-in-a-forest-usi 跟这里基本一致，给一个array代表一排树的高度，然后切一棵树来满足排列是高低相间。问有多少种切法。类似wiggle array。应该是mid难度吧。
第三道题：蠡口气留疤，hard难度但是代码可以很短。
------------------------------------------------------------------------------------
三道题都在地里1. N people , k-th assigned letter S[K]那道题 2. 利口 忆旧凌肆 3. Checkers board game 三道过了给的test cases 但是第三道自己想的一种case不对 不知道能不能过 求大米！谢谢大家了！
------------------------------------------------------------------------------------
OA 两部分，System Design和Coding System Design
要求实现Facebook的total count of current friends功能。给了两个表。- 可以join然后count
Google Doc每个server只能handle一个document，一个document可以有很多人使用。目前是用round robin的load balancing，有什么问题。- 有的server可能会成为hot spot，可以用connection based load balancing
给了几个scenario，问应该用strong还是eventual consistency。- latency低的或者不要求实时准确的可以用eventual
假设系统在document sign了之后会发自动的notification。给了两个信息，一个是database记录doc是什么时候被sign的，一个是log记录有哪些doc id发了邮件。问现在系统有bug，怎么发现哪些doc有问题没发出邮件。- 根据时间从DB里取所有的id在减去log里的
给了一张图，问throughput是多少。- 选处理能力最少的那个bottleneck Coding 是 https://www.jianshu.com/p/fdbcba5fe5bc 里的“2. 返回空闲时间段”那题。 可以把所有人的时间放进一个list里，根据开始时间排序。然后从前往后比，如果有空就记录下来，如果重叠就记录住当前的最大的会议结束时间。用这个会议结束时间再比后面的开始时间。 帖子里是把时间段merge之后再取空白时间，方法差不多。 目前生死未卜，求好运，求大米看面经 补充内容 (2022-01-19 07:35 +8:00): ============================= 1/18号更新： 刚收到消息，OA过了进下一轮
------------------------------------------------------------------------------------
Questions:
I do not remember the exact wording of the the questions, but can give a general idea from what I remember. Roughly 5 or 6 different scenario based questions were asked revolving around system design concepts. I can roughly recall the following:
For the following scenarios, which would be better - Strong consistency/Eventual consistency. Explain reasons why. About 3 scenarios were given, one of which was a Banking application.
The interview gave a scenario for Google docs and multiple users can access the same document, and google docs uses a Round Robin load balancing approach. Do you see any issues with using such an approach.
One question was related to finding the max throughput of a system. It was sort of like a graph diagram, with various about 6 stages labeled A to F, and the throughput they operate on. I was asked to calculate the max throuhput of the system.
One question was related to a scenario where they were using a relational database, and two tables were provided with a foreign key reference. They wanted to see how we can scale such a system (I believe they were looking for data partitioning/sharding techniques that we could apply.)
Another scenario was something like that there was a bug on an application, and you ended up having a lot of failed requests. You have a database that stores all IDs that are there, and you also have large log files from about 500 different production servers that log the IDs of the successful requests. How would you come up with a solution to find the IDs that were missing/
Overall, a good understanding of core system design concepts such as load balancing,caching, map-reduce, throughput, etc. should be helpful to answer these questions.
------------------------------------------------------------------------------------
http://202.79.172.224/id/863003
Karat这个面试系统先给你五个scenario-based的system design问题，还挺有趣的，很多点值得斟酌讨论。不知有没有大牛来侃一侃。
We have a photo sharing app where users can upload photos and share a link to other users; And we have a scalable server pool to distribute photo workloads by user name alphabetically, from a to z, to each of the server in the pool. Assuming the pool can scale automatically if more user signing up, what's the problem of this design?
A single-process program is creating a single thread for every new video stream running on a single machine. A bug is found to cause the single-process to crash when processing more than 10 video streams at the same time. During livesite, we don't have time to push a bug fix; Assuming you're the on-call SRE, what immediate actions would you take to mitigate the issue.
I have an internet-connected vending machine system. Each vending machine reports its stocking information at 1AM every day to a server machine, so that we can decide if we should re-stock them. What's the problem of this design?
I have a mobile app to analyze a completed GO game, to provide suggestions to improve player's GO skills. There are two implementation options: 1) Analyze the GO game locally in the mobile app; 2) Send the game to a server and get back the analysis report to the mobile client. What's advantage and disadvantage of each approach?
We have a photo sharing app where users can upload photos and share a link to other users. What kind of attributes would you consider to project and determine the total capacity of the storage we need.
------------------------------------------------------------------------------------
昨天刚面完的WayFair家具厂电面，Karat代面。今早7点收到拒信with detailed feedback。
Part 1 20min还是经典的那五个system design快问快答。最后会以incorrect/basic/intermediate给你打分。这部分要求你在快速读完长篇小作文叙述后，立马给出精简而且准确的答案才行。不然这部分也不好过。每题没有讨论的余地。说是open anwser，其实感觉不是。。
Part 2 给的新题，没遇到过去6个月里面经题包括这个总结里的题(https://www.jianshu.com/p/fdbcba5fe5bc)
题目是给一个List>，里面内容是[<用户名>, <电影名>, <评分>], 比如["小明", "哈利波特", "5"], 然后给你一个人名和这rating list，让你返回推荐这人看的movie list。满足的推荐条件有2个： 1是这人没看过这个movie，2是另外2个人有4或者5对这个movie的打分(打分在1-5)区间。 题目不难，但是代码量其实不是特别少。lz最后用了几分钟搞明白了题目，然后开始写，最后25min就写完了这一题。最后评价说有logic错误，hard to read.....orz...说我写的慢 coding感觉karat不会给你交流打分的，你只要把题目跟他赶紧问清楚了，就开始写，但是要求代码简洁、可读性强，完成度高。30min他家expect你做完2题，不然基本给你挂。
overral，面试体验感觉一般。加上前面一家练手公司，目前两家电面都给我挂了。。。唉，马上就该上大厂面试了。。不知道是不是我太菜还是现在就是面试要求上去了，要求完美才给过。。 攒攒人品，希望下面大厂的面试能顺利啊。 在职刷题真的太累了。
----------------------------------------------------------------------------------------
------------------------------------------------------------------------------------