Coding Interviews
You are given a 2D integer array edges representing a tree with n nodes, numbered from 0 to n - 1, rooted at node 0, where edges[i] = [u_i, v_i] means there is an edge between the nodes v_i and u_i.
You are also given a 0-indexed integer array colors of size n, where colors[i] is the color assigned to node i.
We want to find a node v such that every node in the subtree of v has the same color.
Return the size of such a subtree with the maximum number of nodes possible.
Given a string s and a dictionary of strings wordDict, return true if s can be segmented into a space-separated sequence of one or more dictionary words.
Note that the same word in the dictionary may be reused multiple times in the segmentation.
Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Given an integer n, return the number of prime numbers that are strictly less than n.
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
Given an object, return a valid JSON string of that object. You may assume the object only inludes strings, integers, arrays, objects, booleans, and null. The returned string should not include extra spaces. The order of keys should be the same as the order returned by Object.keys().
Please solve it without using the built-in JSON.stringify method.
Given a function fn, return a curried version of that function.
A curried function is a function that accepts fewer or an equal number of parameters as the original function and returns either another curried function or the same value the original function would have returned.
In practical terms, if you called the original function like sum(1,2,3), you would call the curried version like csum(1)(2)(3), csum(1)(2,3), csum(1,2)(3), or csum(1,2,3). All these methods of calling the curried function should return the same value as the original.
Given an array of asyncronous functions functions and a pool limit n, return an asyncronous function promisePool. It should return a promise that resolves when all the input functions resolve.
Pool limit is defined as the maximum number promises that can be pending at once. promisePool should begin execution of as many functions as possible and continue executing new functions when old promises resolve. promisePool should execute functions[i] then functions[i + 1] then functions[i + 2], etc. When the last promise resolves, promisePool should also resolve.
For example, if n = 1, promisePool will execute one function at a time in series. However, if n = 2, it first executes two functions. When either of the two functions resolve, a 3rd function should be executed (if available), and so on until there are no functions left to execute.
You can assume all functions never reject. It is acceptable for promisePool to return a promise that resolves any value.
You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Write an algorithm to determine if a number n is happy.
A happy number is a number defined by the following process:
Starting with any positive integer, replace the number by the sum of the squares of its digits.
Repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1.
Those numbers for which this process ends in 1 are happy.
Return true if n is a happy number, and false if not.
Given an unsorted array of integers nums, return the length of the longest consecutive elements sequence.
You must write an algorithm that runs in O(n) time.
You are given an n x n 2D matrix representing an image, rotate the image by 90 degrees (clockwise).
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Design a url shortener service (similar to tinyurl).
1. Generate expiring unique short URL from provided URL
2. Redirect users to the correct website when they navigate to the short URL
Sending user notifications is a common requirement in system design. Design a notification service for an organization. The system will use shared services for the underlying messaging implementation (email, sms, push notifications, etc) so the actual messaging implementation does not need to be designed. The system should support a user publishing a notification to a single user or groups of users. Notifications can be triggered manually via a web UI or programmatically via an API. Users should be able to view their past notifications they published. If a user is unable to receive a notification, they should still receive it at the next opportunity and not miss the message. The notification service should scale to billions of notifications per day, with messages delivered within a few seconds, with five 9s uptime.
Design an app like google maps. The app should provide the quickest possible route between two arbitrary locations. It should provide an ETA, estimated time to reach a destination, using current traffic data.
Functional Requirements
1. As users type text in a search box, show the top 10 auto complete results with very low latency
2. Analytics will be collected on what the user types
Design a service with the following functional requirements
1. Users should be able to upload and download files
2. The files should be able to be shared with other users
3. Changes to the files should be pushed to other users with the content on their machine
4. There must be no risk of file corruption
5. Keep track of different versions of the files so they may be rolled back
6. Users should be able to edit files without an internet connection and the changes sync up when a connection becomes available
Design a social network website with the following functional requirements
1. Users should be able to post content with text, images or video 2. Users should be able to follow other users 3. Each user will have a relatively low latency feed which shows content posted by users they follow
Functional Requirements
The ability to set limits on the number of requests allowed within a specific timeframe
Keep performance and fault tolerance in mind
Functional Requirements
Users should be able to query plaintext documents (the twitter posts for this example)
Keep reliability and latency in mind