aonecoding
 1of 1 vote
AnswerFB Onsite March
 aonecoding in United States
Q: Find number of Islands.
XXXOO
OOOXX
XXOOX
Return 3 islands.
1 1 1OO
OOO2 2
3 3OO 2
Followup: If the board is too big to fit in memory, how to get the number? Report Duplicate  Flag
Facebook Software Engineer Algorithm  2of 2 votes
AnswerFind the median of a very big array of integer. Only iterator of array is given
 aonecoding in United States Report Duplicate  Flag
Airbnb Software Engineer Algorithm  1of 1 vote
AnswersGoogle
 aonecoding in United States
Given two lowercase strings, S1 and S2, sort S1 in same order as S2.
If a character in S1 doesn't exist in S2, put them at the end. If S1 is "program" and S2 is "grapo", then return "grrapom". Report Duplicate  Flag
Google Software Engineer Algorithm  2of 2 votes
AnswersTwitter
 aonecoding in United States
Count number of each character in a string and print out the counts from highest to lowest. Report Duplicate  Flag
Twitter Software Engineer Algorithm  2of 2 votes
AnswerSearch for a target value from a sorted array with unknown size.
 aonecoding in United States Report Duplicate  Flag
Yelp Software Engineer Algorithm  1of 1 vote
AnswersAdobe (phone)
 aonecoding in United States
Return the value of the item k away from the end of a linked list Report Duplicate  Flag
Adobe Software Engineer Algorithm  2of 2 votes
AnswerFind a byte array in a byte file.
 aonecoding in United States
For e.g.
finding arr = bytearray([3,4,5,3]) in byte file ([24,3,4,5,3,4,5,3,9, 255,...])
output: 1, 4, ...
since arr is found at idx 1, 4, ... Report Duplicate  Flag
Dropbox Software Engineer Algorithm  2of 2 votes
AnswersJet.com
 aonecoding in United States
Print a matrix in zigzag traversal (diagonally).
For matrix
1 2 3 4 5 6
7 8 9 10 11 12
13 14 15 16 17 18
19 20 21 22 23 24
Print
1 2 7 13 8 3 4 9 14 19 20 15 10 5 6 11 16 21 22 17 12 18 23 24 Report Duplicate  Flag
Jet Software Engineer Algorithm  1of 1 vote
AnswerDropbox
 aonecoding in United States
Grid Illumination: Given an NxN grid with an array of lamp coordinates.
Each lamp provides illumination to every square on their x axis,
every square on their y axis, and every square that lies in their diagonal
(think of a Queen in chess).
Given an array of query coordinates,
determine whether that point is illuminated or not. The catch is when checking a query all lamps adjacent to, or on,… Report Duplicate  Flag
Dropbox Software Engineer Algorithm  1of 1 vote
AnswersMarch 2018 Phone Interview FB
 aonecoding in United States
Calculate a moving average that considers the last N values.
Circular Queue (Interviewer didn't agree with the linked list queue that I suggested at first. Said the pointers took space) Report Duplicate  Flag
Facebook Software Engineer Algorithm  2of 2 votes
AnswersFeb Onsite Google
 aonecoding in United States
DP Problem. Given the length and width of a matrix, get the number of paths from bottomleft to bottom right.
You may only walk into those 3 directions ➡ (right) ↗ (upperright) ↘ (lowerright) at each point.
Followup: optimize 2d DP to 1d DP of linear extra space.
Followup: what if some cells are blocked
System Design
Availability test/debug on distributed system. Discussed and drafted about failover, replication, NoSQL etc.
Interviewer seemed to be expecting more but time ran out. Report Duplicate  Flag
Google Software Engineer Algorithm  2of 2 votes
AnswersFeb Onsite Google
 aonecoding in United States
Print all numbers satisfying the expression 2^i * 5^i (where i, j are integers i >= 0 and j >= 0) in increasing order up to a given bound N.
2^i stands for power(2, i). Report Duplicate  Flag
Google Software Engineer Algorithm  2of 2 votes
AnswersConvert a string with digits into a literal representation of the number like: 1001 to one thousand one
 aonecoding in United States Report Duplicate  Flag
Uber Software Engineer Algorithm  2of 2 votes
AnswersDecompress string  string (s) followed by {n} denotes s repeating n times
 aonecoding in United States
"a(b(c){2}){2}d" decompresses to "abccbccd"
"((x){3}(y){2}z){2}" decompresses to "xxxyyzxxxyyz" Report Duplicate  Flag
Google Software Engineer Algorithm  1of 1 vote
AnswerGoogle
 aonecoding in United States
1st round
Given a box with N balls in it, each ball having a weight, randomly choose pick one out base on the weight.
Input ball1> 5kg, ball2 > 10kg and ball3 > 35kg,
then Prob(ball1 chosen) = 10%, Prob(ball2) = 20%,
Prob(ball3) = 70% ;
Followup:
Select a ball randomly based on weights. Once a ball is chosen, remove it. Next time select from the remaining balls. Go on until there is nothing left in the box. Report Duplicate  Flag
Google Software Engineer Algorithm  2of 2 votes
AnswersFind whether string S is periodic.
 aonecoding in United States
Periodic indicates S = nP.
e.g.
S = "ababab", then n = 3, and P = "ab"
S = "xxxxxx", then n = 1, and P = "x"
S = "aabbaaabba", then n = 2, and P = "aabba"
follow up:
Given string S, find out the P (repetitive pattern) of S. Report Duplicate  Flag
Google Software Engineer Algorithm  1of 1 vote
AnswerDesign a hit counter which counts the number of hits received in the past 5 minutes.
 aonecoding in United States
Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.
Example:
HitCounter counter = new HitCounter();
// hit at timestamp 1.
counter.hit(1);
// hit at timestamp 2.
counter.hit(2);
// hit at timestamp 3.
counter.hit(3);
// get hits at timestamp 4, should return 3.
counter.getHits(4);
// hit at timestamp 300.
counter.hit(300);
// get hits at timestamp 300, should return 4.
counter.getHits(300);
// get hits at timestamp 301, should return 3.
counter.getHits(301);
Followup:
Due to latency, several hits arrive roughly at the same time and the order of timestamps is not guaranteed chronological.
Follow up 2:
What if the number of hits per second could be very large? Does your design scale? Report Duplicate  Flag
Dropbox Software Engineer Algorithm  1of 3 votes
AnswersRound3 Google
 aonecoding in United States
For N light bulbs , implement two methods
I. isOn(int i)  find if the ith bulb is on or off.
II. toggle(int i, int j)  i <= j. Switch state (switch on if it's off, turn off if it's on) of every bulb in range i to j.
All bulbs are off initially. Report Duplicate  Flag
Google Software Engineer Algorithm  2of 2 votes
Answers/**
 aonecoding in United States
* Google
* Given a list of nonnegative numbers and a target integer k,
* write a function to check if the array has a continuous subarray of size at least 2 that sums up to the multiple of k, that is, sums up to n*k where n is also an integer.
**/ Report Duplicate  Flag
Google Software Engineer Algorithm  3of 3 votes
AnswersAmazon
 aonecoding in United States
Given an ArrayList of Nodes, with each Node having an ID and a parent ID, determine whether the List is given in preorder. Report Duplicate  Flag
Amazon Software Engineer Algorithm  2of 2 votes
AnswersGoogle
 aonecoding in United States
Given an array a[] and an integer k, a[i] means flower at position a[i] will blossom at day i. Find the first day that there are k slots between two blooming flowers. Report Duplicate  Flag
Google Software Engineer Algorithm  1of 1 vote
AnswersGoogle
 aonecoding in United States
Given a string that represents time like "15:31", find the next time that is formed by the numbers in the string(a number can be used more than once). For "15:31", the answer should be "15:33". Report Duplicate  Flag
Google Software Engineer Algorithm  1of 1 vote
AnswerTwitter
 aonecoding in United States
Create a simple stack which takes a list of elements.
Each element contains a stack operator (push, pop, inc) and a value to either push/pop or two values, n and m,
which increment the bottom n values by m.
Then print the topmost value of the stack after every operation. If the stack is empty, print "empty" Report Duplicate  Flag
Twitter Software Engineer Algorithm  2of 2 votes
AnswersDropBox Dec 2017
 aonecoding in United States
Congrats to Brian landing @DropBox
Round 3：
Develop an web crawler API, find all subsites reachable from a given URL.
Given this method  vector<string> getURLs(string url);
Comparison of DFS vs BFS in the scenario
Follow up：
Support multithearding.
Round 4：
Build an ID allocator. Max ID value is given as MAX. Allocate IDs from 0 to MAX.
Must be able to handle when an ID gets released.
Must be able to handle exceptions.
Followup: Improve time/space efficiency.
Optimal approach:
Segment tree + bit map.
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
ONE TO ONE realtime coaching on SYSTEM DESIGN, ALGORITHMS, and mock interviews.
Feel free to email us aonecoding@gmail.com with any questions. Thanks! Report Duplicate  Flag
Dropbox Software Engineer Algorithm  2of 2 votes
AnswersDropBox Dec 2017
 aonecoding in United States
Congrats to Brian landing @DropBox
Dropbox always has the most responsive HR and gives review on the interview within a week. The canteen is also one of the best in Bay Area.
Phone：
LC: game of life
What if the board is huge?
Store in disk
with bitmap
Load into memory, process and write to disk row by row
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Members get hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
Onsite：
Round 1：
Given an array of byte and a file name, find if the array of byte is in file.
Solution: Rolling hash
Round 2：
Given an Iterator of some photo with IDs, find the top K most hit photo IDs.
Follow up: What if the input is from a stream? When iterator reaches the end, moments later new hits can be added to the iterator. Modify code for this scenario.
Lunch was great.
Then came a demo round. Discussed Dropbox Paper Report Duplicate  Flag
Dropbox Software Engineer  2of 2 votes
AnswersCongrats on aonecode.com member V.S. on the offer from Microsoft and thanks for sharing with us the experience.
 aonecoding in United States
Coding Question 1  Find all the paths between two nodes
Coding question 2 : Max sum in adjacent sub array
Design Question  Design a ticketing System
Design Question 2  Design a system which allows multiple agents to read different data from same tables. Latency should be low. Algorithm should rank agents through some logic and assigned work according to that so that each agents are reading different set of rows from same table. Scale it for 20 million active agents .
Follow up  If Data Sharding is allowed, what will be the Shard Id and how the partition will look like? How your system will respond if there are agents which are also writing at same time. Consistency should be given high preference over availability.
Looking for coaching on interview prep?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
Customized course covers
System Design (for candidates of FB, LinkedIn, AMZ, Google & Uber etc)
Algorithms (DP, Greedy, Graph etc. every aspect you need in a coding interview & Clean Coding)
Interview questions sorted by companies
Mock Interviews
Our members got into G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks! Report Duplicate  Flag
Microsoft Software Engineer Algorithm  1of 3 votes
AnswerCongrats to aonecode's member F.L.
 aonecoding in United States
Got offers from  Youtube(G), LinkedIn, Airbnb, Square, Wish, Blend and NextDoor!
Thanks for sharing the interview experience with us.
Youtube Interview
 Phone: Find anagrams of string A from string B (sliding window)
 Phone: Find if two frames in a screen are equal. Frames may overlap. (equal method)
Onsite:
 LC41 first missing positive
 LC499+LC505 The maze
 LC161 one edit distance
 Similar to hangman but make guesses based on a dictionary.
Assume a dictionary has words  {house, morse, jesus} and ‘morse’ is the answer. If your first guess is ‘house’, output will be ‘_o_se’, which indicates 3 letters are correct. (Here the arrangement of letters does not matter. Your guess can be ‘co’ and if answer is ‘ok’ then the output is gonna be ‘_o’ which indicates letter ‘o’ in answer. )
Try to get the answer with minimum guesses.
(Interviewer expects preprocessing the dictionary. Key: letter; Value: frequency. Begin with combinations of most frequent letters first) Report Duplicate  Flag
Google Software Engineer Algorithm  1of 3 votes
AnswerCongrats to F.L.
 aonecoding in United States
Got offers from  Youtube(G), LinkedIn, Airbnb, Square, Wish, Blend and NextDoor!
Thanks for sharing the interview experience with us.
LinkedIn
Phone:
 Questions from LC tagged LinkedIn.
Onsite:
 Get sqrt(x). Output a floored integer if result is not a perfect square. sqrt(18) = 4
 Implement BST, insert, delete, search.
 Design a dashboard for service logs stats (sort and aggregate). Scale from 1 to more machines. Discuss async and realtime as different scenarios. Report Duplicate  Flag
Linkedin Software Engineer Algorithm  2of 2 votes
AnswerFacebook
 aonecoding in United States
Phone: LC304 & longest arithmetic sequence. Return the sequence. Report Duplicate  Flag
Facebook Software Engineer Algorithm  3of 3 votes
AnswerWish Interview
 aonecoding in United States
Phone: Two sum, Three sum, N sum(recursion)
Onsite:
Implement merge sort (recursion&iteration)
Merge two sorted arrays: one of length m+n, the other n; store the result in the longer array
Given a number print diamond:
Given 1
Pirnt 1
Given 3
Print
1
121
1
Given 5
Print
1
121
12321
121
1
 Rank N people in a game. There may be a tie among participants. How many possible ways of ranking there is.
 Design: Define a bot as an IP that hits the web app over M times in the past T seconds (not necessarily hits on the same page. Also take into account different API calls.) How to design a bot detector layer and where to place it in the system. Report Duplicate  Flag
Wish Solutions Engineer Algorithm  1of 1 vote
AnswerAirbnb Online Assessment Paginate List
 aonecoding in United States
5
13
1,28,310.6,SF
4,5,204.1,SF
20,7,203.2,Oakland
6,8,202.2,SF
6,10,199.1,SF
1,16,190.4,SF
6,29,185.2,SF
7,20,180.1,SF
6,21,162.1,SF
2,18,161.2,SF
2,30,149.1,SF
3,76,146.2,SF
2,14,141.1,San Jose
Here is a sample input. It’s a list generated by user search.
(1,28,100.3,Paris) corresponds to (Host ID, List ID, Points, City).
5 in the first row tells each page at most keeps 5 records.
13 in the second row is the number of records in the list.
Please paginate the list for Airbnb by requirement:
1. When possible, two records with same host ID shouldn’t be in a page.
2. But if no more records with nonrepetitive host ID can be found, fill up the page with the given input order (ordered by Points).
Expected output:
1,28,310.6,SF
4,5,204.1,SF
20,7,203.2,Oakland
6,8,202.2,SF
7,20,180.1,SF
6,10,199.1,SF
1,16,190.4,SF
2,18,161.2,SF
3,76,146.2,SF
6,29,185.2,SF  6 repeats in page bec no more unique host ID available
6,21,162.1,SF
2,30,149.1,SF
2,14,141.1,San Jose Report Duplicate  Flag
Airbnb Software Engineer Algorithm  2of 2 votes
AnswersFind the indices of all anagrams of a given word in a another word.
 aonecoding in United States
For example: Find the indices of all the anagrams of AB in ABCDBACDAB (Answer: 0, 4, 8) Report Duplicate  Flag
Amazon Software Engineer Algorithm  2of 2 votes
AnswerAmazon OA2
 aonecoding in United States
Implement a round robin scheduler.
Each process has an arrival time Atime[i], execute time Etime[i].
Q is the maximum time that a process gets executed in its turn. If the process isn't finished after q, it waits till the next round.
Output average wait time for the processes. Report Duplicate  Flag
Amazon Software Engineer Algorithm  1of 1 vote
Answerscreate a class of integer collection,
 aonecoding in United States
3 APIs:
append(int x),
get(int idx),
add_to_all(int x)，
in O(1) time。
Followup:
implement
multiply_to_all(int x)
e.g.
insert(1)
insert(2)
add_to_all(5)
insert(3)
get(0) > returns 6
get(2) > return 3
multiply_to_all(10)
insert(4)
get(1) > returns 70
get(2) > returns 30
get(3) > returns 4 Report Duplicate  Flag
Google Software Engineer Algorithm  0of 0 votes
AnswersLonely Pixel
 aonecoding in United States
Given an N x M image with black pixels and white pixels, if a pixel is the only one in its color throughout its entire row and column, then it is a lonely pixel. Find the number of lonely pixels in black from the image. (O(NM)) Report Duplicate  Flag
Google Software Engineer Algorithm  1of 1 vote
AnswerTweet Recommendation
 aonecoding in United States
Twitter Interview Online Test
On Twitter, millions of tweets are posted on a daily basis. Help Twitter write a simple ranking algorithm to find the best of all tweets. It works as follows: A good tweet receives many “likes” from people on Twitter, either from people you follow, or people you do now follow. A tweet is more relevant to you if people you follow also liked the tweet. If enough people you follow have liked that tweet, we recommend that tweet to you.
Your task is to complete the function
getRecommendedTweets(followGraph_edges, likeGraph_edges, targetUser, minLikeThreshold), which returns a list of tweet IDs in sorted order that should be recommended for a certain user. It takes 4 parameters:
followGroup_edges stores follow relationships as an array of tuple of integers.
For example, followGraph_edges = Array{(A, B), (A, C), (B, C)} represents 3 follow relationships:
A follows B
A follows C
B follows C
likeGraph_edges stores like relationships, also in an array of tuple of integers.
For example, likeGraph_edges = Array{(A, T1), (B, T2), (A, T2)} means:
A liked tweet T1
B liked tweet T2
A liked tweet T2
targetUser is the user ID for which we generate recommended tweets
minLikeThreshold is the minimum number of likes a tweet mush receive from people you follow to be recommended
For example, if minLikeThreshold = 4, only tweets that received at least 4 likes from people you follow should be recommended
Note: If you cannot find a single tweet that meets our requirement, simply return an empty list. You may also use any functions provided by the standard library. Report Duplicate  Flag
Twitter Software Engineer Algorithm  1of 1 vote
AnswersEmployees Per Department
 aonecoding in United States
Twitter Interview Online Test SQL
A company uses 2 data tables, Employee and Department, to store data about its employees and departments.
Table Name: Employee
Attributes:
ID Integer,
NAME String,
SALARY Integer,
DEPT_ID Integer
Table Name: Department
Attributes:
DEPT_ID Integer,
Name String,
LOCATION String
View sample tables:
https://s3uswest2.amazonaws.com/aonecode/techblog/50cfcdd1d61f1bd6002cf4d3b4a61debmin.jpeg
Write a query to print the respective Department Name and number of employees for all departments in the Department table (even unstaffed ones).
Sort your result in descending order of employees per department; if two or more departments have the same number of employees, then sort those departments alphabetically by Department Name. Report Duplicate  Flag
Twitter Software Engineer SQL  2of 2 votes
AnswersHacking Time
 aonecoding in United States
Twitter Interview Online Test
Alice and Bob are avid Twitter users and tweet to each other every day. One day, Alice decides to send Bob a secret message by encrypting it and tweeting it publicly to Bob. They had anticipated a scenario like this, and exchanged a shared secret key some time in the past. Unfortunately, Alice isn’t very familiar with encryption algorithms, so she decides to make her own. Her encryption algorithm works as follows:
1. Choose a key entirely composed of digits 0  9, for example: 12345.
2. Iterate each letter of the plaintext message and rotate the letter forward a number of times equal to the corresponding digit in the key. If the rotation of the letter passes Z, start back at A.
3. If the message is longer than the key, loop back to the first digit of the key again, as many times as needed.
4. If a nonalphabetical character is encountered, leave it as it is and don’t move to the next digit in the key.
5. Characters should maintain their upper or lowercase orientation after rotation.
Here is an example message and its encrypted output using Alice’s algorithm:
Original message: Hi, this is an example
Example Key: 4071321
Encrypted message: Li, ailu jw facntll
Where H was rotated forward 4 letters to L, i rotated 0 to i, t rotated forward 7 letters to a, etc.
Satisfied with the security of her algorithm, Alice tweets the following ciphertext to Bob:
Otjfvknou kskgnl, K mbxg iurtsvcnb ksgq hoz atv. Vje xcxtyqrl vt ujg smewfv vrmcxvtg rwqr ju vhm ytsf elwepuqyez. Atvt hrqgse, Cnikg
Uh oh! Unfortunately for Alice and Bob, you are “Eve”, the world’s greatest hacker. You’ve been intercepting Alice’s messages for some time now, and know she always ends her messages with the signature “Your friend, Alice”. You job is now as follows:
Determine the key Alice is using.
Using this key, write a function to decrypt any future communications from Alice. This method should take the encrypted string as an input and return the original unencrypted string. Report Duplicate  Flag
Twitter Software Engineer Algorithm  1of 1 vote
AnswerIII. Square root of a number?
 aonecoding in United States
IV. Expression operators? Add signs (+, , *, /) to a string to form target
V. Top trending posts in last 5m, 1H, 1Day? Report Duplicate  Flag
Linkedin Software Engineer Algorithm  0of 0 votes
AnswerI. Closest K nodes to a target in BST? (Do it in O(n)?)
 aonecoding in United States
II. Nested List sum? Report Duplicate  Flag
Linkedin Software Engineer Algorithm  0of 0 votes
AnswerSolve the 24 Game
 aonecoding in United States Report Duplicate  Flag
Twitter Software Engineer Algorithm  3of 3 votes
AnswersRound4
 aonecoding in United States
Starting from num = 0, add 2^i (where i can be any nonnegative integer) to num until num == N. Print all paths of how num turns from 0 to N.
For example if N = 4,
Paths printed are [0,1,2,3,4], [0,1,2,4], [0,1,3,4], [0,2,4], [0,2,3,4], [0,4].
[0,2,4] is made from 0 + 2^1 + 2^1. [0,1,3,4] from 0 + 2^0 + 2^1 + 2^0 Report Duplicate  Flag
Google Software Engineer Algorithm  2of 2 votes
AnswersRound3
 aonecoding in United States
For N light bulbs, implement two methods
I. isOn(int i)  find if the ith bulb is on or off.
II. toggle(int start, int end) Report Duplicate  Flag
Google Software Engineer Algorithm  2of 2 votes
AnswersRound1
 aonecoding in United States
Find if two people in a family tree are bloodrelated.
Round2
Given some nodes in a singly linked list, how many groups of consecutively connected nodes there is.
For linked list
0>1>2>3>4>5>6,
given nodes 1, 3, 5, 6
there are 3 groups [1], [3], and [5, 6]. Report Duplicate  Flag
Google Software Engineer Algorithm  4of 4 votes
AnswersGiven a sorted array A, find how many subsets of A satisfies MIN(subset) + MAX(subset) < K.
 aonecoding in United States Report Duplicate  Flag
Facebook Software Engineer Algorithm  1of 1 vote
AnswersRound 5:
 aonecoding in United States
Given a set of synonyms such as (fast, quick), (fast, speedy), (learn, study), decides if two sentences were synonymous.
(The sentences were structurally the same and has the same number of words in them.
The synonymous relation [fast ~ quick] and [fast ~ speedy] does not necessarily mean [quick ~ speedy].)
Followup:
If the synonymous relation passes down so that [fast ~ quick] and [fast ~ speedy] implies [quick ~ speedy], decide if two sentences were synonymous. Report Duplicate  Flag
Google Software Engineer Algorithm  1of 1 vote
AnswersRound 4:
 aonecoding in United States
Implement a class Employment with these 3 methods: assignManager(p1, p2): assign p1 as p2's manager. beColleague(p1, p2): make p1 and p2 peer colleagues. isManager((p1, p2): decide if p1 is the manager of p2. Report Duplicate  Flag
Google Software Engineer Algorithm  2of 2 votes
AnswersRound 3
 aonecoding in United States
Given a matrix of 0s and 1s where 0 is wall and 1 is pathway, print the shortest path from the first row to the last row.
Can walk to the left, top, right, bottom at any given spot.
Followup:
If every pathway takes a cost (positive integer) to get through, print the minimum cost path from the first row to the last row. Report Duplicate  Flag
Google Software Engineer Algorithm  1of 1 vote
AnswersGoogle onsite June
 aonecoding in United States
Round 1
Leetcode 10
Round 2
Select a random point uniformly within a rectangle, (The side of rectangle is parallel to the x/ y grid).
Followup: Given multiple nonoverlapped rectangles on the 2D grid, uniformly select a random point from the rectangles. Report Duplicate  Flag
Google Software Engineer Algorithm  2of 2 votes
AnswersPhone Interview Amazon, Seattle
 aonecoding in United States
I. Get the sum of all prime numbers up to N. primeSum(N).
Followup: If primeSum(N) is frequently called, how to optimize it.
II. OODesign Parking Lot Report Duplicate  Flag
Amazon Software Engineer Algorithm  2of 2 votes
AnswersApple Map Team
 aonecoding in United States
1. Given an array A and some queries, query(i, j) returns the result of Ai*...*Aj, in other words the multiplication from Ai to Aj.
The numbers in A are nonnegative.
Implement query(i, j).
2. Flatten nested linked list
3. POI search design
4. LC238 & LC279 Report Duplicate  Flag
Apple Software Engineer Algorithm  1of 1 vote
AnswersAirbnb Interview
 aonecoding in United States
Min cost of flight from start to end if allowed at most k transfers.
Given all the flights in a string:
A>B,100,
B>C,100,
A>C,500,
If k = 1，from A to C the best route is A>B>C at the cost of 200. Report Duplicate  Flag
Airbnb Algorithm  3of 3 votes
AnswersApple phone interview
 aonecoding in United States
Given an API to find all IPv4 addresses in a log file, find all IPs that occurred only once.
Followup: What if the log comes from a data stream.
Followup: If the machine has 4GB RAM, is there going to be a problem? Report Duplicate  Flag
Apple Backend Developer Algorithm  2of 2 votes
Answer4/5 Round at Uber
 aonecoding in United States
Coding: Given a 2D array of either '\' or '/', find out how many pieces this rectangle is divided into graphically.
For a 2X2 matrix with
/\
\/
The matrix split into 5 pieces  the diamond in middle and the four corners. Return 5 as the answer.
5/5 Round at Uber
Design Excel. Report Duplicate  Flag
Uber Software Engineer Algorithm  1of 1 vote
Answers2/5 Round at Uber
 aonecoding in United States
Bar raiser  Behavioral questions. Coding: Find if a set of meetings overlap. Meeting has a starttime and an endtime with accuracy to minute. All meetings take place in the same day. Do this in O(n) time.
3/5 Round at Uber
Coding: Subset sum. Followup: Optimize the solution. Report Duplicate  Flag
Uber Software Engineer Algorithm  0of 0 votes
Answers1/5 Round at Uber
 aonecoding in United States
Manager : Behavioral questions. Basic system design concepts. Publish/subscribe model. Discussion on Uber architecture. Report Duplicate  Flag
Uber Software Engineer System Design  2of 2 votes
AnswerUber
 aonecoding in United States
1. Mirror Binary Tree
2. String pattern matching
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(String str, String pattern)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa","a{1,3}") → true
isMatch("aaa","a{1,3}") → false
isMatch("ab","a{1,3}b{1,3}") → true
isMatch("abc","a{1,3}b{1,3}c") → true
isMatch("abbc","a{1,3}b{1,2}c") → false
isMatch("acbac","a{1,3}b{1,3}c") → false
isMatch("abcc","a{1,3}b{1,3}cc{1,3}") → true
In pattern string, a char followed by {lower, upper} means that the char occur lower to upper(exclusive) times. e.g. a{1, 3} > a occurs 1 or 2 times. Report Duplicate  Flag
Uber Software Engineer Algorithm  3of 3 votes
Answers3.1 design: design fb inbox search —> just focus on the post
 aonecoding in United States
4.1 binary tree to circular double linked list.
4.2 two arrays, find the common elements of two sorted array. if one array is small, the other is very big. Report Duplicate  Flag
Facebook Software Engineer Algorithm  2of 2 votes
Answers2.1 career discussion
 aonecoding in United States
2.2 divide two numbers with no / or % Report Duplicate  Flag
Facebook Software Engineer Algorithm  4of 4 votes
Answers1/4 round of FB onsite interview, Master Degree, Hired
 aonecoding in United States
1.1 diameter of tree
1.2 find the point which have the maximum overlap of intervals Report Duplicate  Flag
Facebook Software Engineer Algorithm  3of 3 votes
Answers1 year exp. Interviewed at Cambridge, MA
 aonecoding in United States
Round1
LC304. Followup: given a char stream instead a string as the input, get the longest substring with at most K distinct characters.
Round2
Find out the area of a number of squares on a plane, an advanced version of LC223.
Had no clue on that problem at all so the interviewer kindly gave another one LC305.
Round3
Similar to LC393 but the interviewer made a slightly different rule for encoding.
Followup: decode with utf16. It took quite a while for me to understand the rules.
Round4
Card game rule: the hand is drawn from a pack of cards (no jokers).
Play cards ONLY when they are
1. 3 of a kind ('AAA' ) or 4 of a kind('AAAA’).
2. a straight flush of 3 or more cards('JQK' or 'A23456...' in the same suit).
Find out whether the player is able to play the whole hand given.
e.g. [Spade A, Spade K, Spade Q, Diamond Q, Heart Q] return false.
[Spade A, Spade K, Spade Q, Diamond Q, Heart Q, Club Q] return true. Report Duplicate  Flag
Google Software Engineer Algorithm  5of 7 votes
AnswersMaster Degree 2 year exp
 aonecoding in United States
1st Round.
Behavioral  most challenging project.
Tech  bit manipulation
2nd Round. A matrix has 0s and 1s only.. All the 1s in every row are to the of 0s. Find out the leftmost 1 in the entire matrix.
3rd Round.
A dp problem.
Find out how many ways you can make change of N cents given coins of values [a1, a2, a3...], each type of coin got infinite supplies.
Arrangement of coins don't matter.
4th Round.
Design news feed.
A user wrote a post with the basic user info, pictures and time etc (I even drafted a basic UI on whiteboard).
How to obtain these information and store them.
If a new feature with a button is added. How to maintain availability of old service to users who did not update the app.
Did not dive further into scaling.
5th Round.
User groups  If I made a certain post visible to a user group, how to store the post? how to push the post to the chosen group. If there are new friends who aren't assigned to any group just yet, how to treat them as if they were in the same 'unassigned' group?
DB sharding is involved.s Report Duplicate  Flag
Facebook Software Engineer System Design  2of 2 votes
AnswersFind the length of longest arithmetic progression in array.
 aonecoding in United States
For example, in the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is 1, 3, 5, and 7 Report Duplicate  Flag
Facebook Software Engineer Algorithm  3of 3 votes
AnswersGoogle fulltime phD candidate w/ work experience.
 aonecoding in United States
Q1. On a 1 meter walkroad, randomly generate rain. The raindrop is 1 centimeter wide.
Simulate how raindrops cover the 1 meter [0~1] road. How many drops does it take to fully cover the 1meter?
Q2. Find out the maximum number of isosceles triangles you can make from a plane of points(cannot reuse points)
Q3.Longest holiday  Every city has a different days of holidays every week. You may only travel to another city at the weekends. What is the max days of holiday you can get this year.
Q4.
Design merchandising product data storage service Report Duplicate  Flag
Google Software Engineer Algorithm  5of 5 votes
AnswersGoogle Onsite in May
 aonecoding in United States
Create a class with a collection of integers.
Enable 3 APIs:
void append(int x),
int get(int idx),
void add_to_all(int x)，//add x to all numbers in collection
These methods should run in O(1) time.
Followup
In addition, implement
void multiply_to_all(int x)
The same required to run in O(1) time Report Duplicate  Flag
Google Software Engineer Algorithm  1of 1 vote
AnswersImplement circular buffer with read & write functions
 aonecoding in United States Report Duplicate  Flag
Facebook Software Engineer Data Structures  1of 1 vote
AnswersCoding III
 aonecoding in United States
Implement int divide(int a, int b) without division or mod operation.
## Round IV
Behavioral Questions + Project Walk Through + Coding (Validate BST)
## System Design V
Design memcache to enable read, write and delete (single server, nondistributed infrastructure).
Which data structure to go with?
Eviction rules?
How to minimize segmentation?
How to handle concurrency?
## Extra
After two weeks they called me to an extra round of system design.
How to store social graphs?
How to handle concurrent read/write requests(read heavy) on one server. Report Duplicate  Flag
Facebook Software Engineer  0of 0 votes
AnswersCoding I
 aonecoding in United States
Flatten a linked list.
Each node in the list carries a piece of data and a pointer. The data could be in a normal data type such as an integer, or a pointer that points to another list node.
The interviewer gave no specification on how the list node class was defined. You may look at each list node as if it has two pointers  one of them points to the next node; the other points to the ‘data’ which could be either a node or an integer. There also needs to be a function to tell you about the node data is actual data or a pointer.
I solved the problem with recursion. During the process, any nodes that don’t carry an integer get removed. Report Duplicate  Flag
Facebook Software Engineer Algorithm  3of 3 votes
AnswersFB onsite two weeks ago last round of coding . (This problem is also in the internal question bank of G.)
 aonecoding in United States
There is a robot in a room. The initial location of the robot is unknown. The shape or area of the room is unknown.
You have a remote that could walk the robot into any of the four directions  up, left, down or right.
Here is the move method: boolean move(int direction), direction: 0, 1, 2, 3. If the robot hits the wall, the method returns false.
Otherwise returns true and the robot moves on to the direction given.
Find out the area of the room.
e.g.
X
XXX X
XXXXX 'X' marks the floor plan of the room.
A room like such has an area of 10. Report Duplicate  Flag
Facebook Software Engineer Algorithm  1of 1 vote
AnswersLast Monday phone interview of G.
 aonecoding in United States
Given a vector/list of doubly linked list pointers (a pointer is the directed linkage of two nodes), count how many independent blocks of linked lists there are for the pointers given. Report Duplicate  Flag
Google SDE1 Algorithm  2of 2 votes
AnswersApple Onsite at Cupertino
 aonecoding in United States
Team Data Warehousing
Questions on Hadoop, Hive and Spark
I. Given a table with 1B of user ID and product IDs that the users bought, and another table with product ID mapped with product name. We are trying to find the paired products that are often purchased together by the same user, such as wine and bottle opener, chips and beer … How to find the top 100 of these coexisted pairs of products. If going with hadoop, where is the bottleneck and how to optimize?
II. Someone put distribute Random()*ID in a Hive script to prevent data skew. What would be the problem here? Report Duplicate  Flag
Apple SDE3 design  1of 1 vote
AnswersApple Onsite at Cupertino
 aonecoding in United States
Team Data Warehousing
III. Given three letters ABC, where AB>C, AC>B, BC>A (sequence doesn’t matter). Get the length of the path to convert from a given string to a single character.
For example, “ABACB” goes to “ACCB” (based on AB >C, convert s[1] and s[2] to C)
“ACCB” goes to “BCB” (based on AC>B)
“BCB” goes to “AB”
“AB” goes to “C”
So it takes 4 steps to change the given string into a single character.
If a given string cannot be resized to 1 character, such as “AAA” or "ABACABB", return 1. Report Duplicate  Flag
Apple SDE3 Algorithm  0of 0 votes
AnswersApple Onsite at Cupertino
 aonecoding in United States
Team Data Warehousing
There were 6.5 rounds in total, that 0.5 on package negotiation with the HR and the remaining rounds with 2 managers and 4 engineers.
Only three pure coding questions were asked.
I. Use a stack to sort given data.
II. Given an array with positive integers only, find the MIN integer that is missing from the array. Report Duplicate  Flag
Apple SDE3 Algorithm  0of 2 votes
AnswersAmazon SDE 2 Onsite (1 of 4 Rounds)
 aonecoding in United States
In a file system stored a large amount of user’s browsing data, including the urls that the user visited. Design a function that outputs the longest common path of all the urls.
Having finished the code, I was asked to analyze the complexity. Report Duplicate  Flag
Amazon Software Engineer Algorithm  2of 2 votes
AnswersAmazon SDE 2 Onsite (4 of 4 Rounds)
 aonecoding in United States
Assume that there is an ebook application. For every book the sharable part of the book content cannot exceed 10% of the whole book. Design a module to decide whether the current part of content is sharable.
The description given is vague. I had to push him with questions to give the details.
At first I thought the problem was about strStr. But then the interviewer said that even if there are two paragraphs of the book content with the exact same texts, as long as they are not in the same place, they would be considered different content.
I then realized it’s a question about merging segments  have a helper to find each pair of start and end point of the input content (given multiple separated paragraphs). Then merge the intervals and see if they combined exceed 10% of the entire book.
The interviewer approved my solution and ask me to code it.
Overall I feel like that the Amazon SDE II Interview doesn’t focus on just algorithm. It’s more about problem solving in practice and then implement the only core function on whiteboard. Report Duplicate  Flag
Amazon Software Engineer  1of 1 vote
AnswersVMWare Standard Online Screen
 aonecoding in United States
3rd Question Given an array of strings and a long description about the formatting of IPv6 and IPv4 (it took me more than 5 minutes to read the description). Write a function to find if a string is IPv4 or IPv6 address or neither.
4th Question Given an integer array, whenever a duplicate number is found, you may increment it (++). Find the minimum sum of the numbers in the array by keep incrementing the dups until all the numbers are unique. Report Duplicate  Flag
VMWare Inc Software Engineer Algorithm  2of 2 votes
AnswerVMWare Standard Online Screen
 aonecoding in United States
The Online Assessment was called something like Life Cycle Challengeqpan.
There are 4 questions in total given 60 minutes. The problem description was unexpectedly long that it takes 5 minutes just to read a question.
1st Question Design a function to create BST. Given an integer array, insert the integers into the binary search tree and print all the steps taken.
2nd Question Given an integer, print the index of all the positions in which the binary bit is 1 in order. Report Duplicate  Flag
VMWare Inc Software Engineer Algorithm  5of 5 votes
AnswersFacebook Senior Engineer Onsite 2017
 aonecoding in United States
1st Round
Question 1: Binary tree to doubly linked list.
Question 2: Read 4 (Given the read4 API, read an entire file)
2nd Round
Culture fit. No coding.
3rd Round
Question: System Design POI (Point of Interest. Given a point, find things within a radius).
Lunch
4th Round
Question 1: Decode way
Question 2: Random max index
5th Round
Question: System design + componentwise design on download manager Report Duplicate  Flag
Facebook Software Engineer Algorithm  5of 5 votes
Answers5th Round
 aonecoding in United States
Openended question What happens when you type a url in the browser and hit enter?
Second question Given an array of integers, print all the numbers that meet the following requirement  when the number is greater than every number on its left and smaller than every number on the right. Report Duplicate  Flag
Google Software Engineer Algorithm  2of 4 votes
Answerinterviewed by senior engineer
 aonecoding in United States
Question Given two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters
Followup If s1 has a length of m and s2 has a length of n, how many ways the strings could be merged. Figure out the formula F(m, n) = ? Report Duplicate  Flag
Google Software Engineer Algorithm  0of 2 votes
AnswersHow to randomly select a number in an array?
 aonecoding in United States
array: [15, 2, 4, 5, 1, 2, 0]
Followup:
Given a second array freq where freq[i] represents the occurrence of the ith number in array, how to randomly select a number in array based on the frequency.
Extra requirement:
Could you complete the selection in a singlepass(go through each array only once)? Report Duplicate  Flag
Linkedin Software Engineer Algorithm  1of 5 votes
AnswersIn school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
 aonecoding in United States
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),
check whether the student qualifies for the reward.
e.g.
@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False
The student does not qualify for reward because "LLA" means he was late for 3 times in a row.
@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True
Followup:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward. Report Duplicate  Flag
Google Software Engineer Algorithm  0of 0 votes
AnswersIn school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
 aonecoding in United States
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time), check whether the student qualifies for the reward.
e.g.
@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False
The student does not qualify for reward because "LLA" means he was late for 3 times in a row.
@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True
Followup:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure the student gets the reward. Report Duplicate  Flag
Google Software Engineer Algorithm  3of 3 votes
AnswersEarly on I prefer to post the interview questions with a simplified description or only present the algorithmic part of it. Because it's hard for our students to memorize the full description of a problem. Therefore often times only the algorithm behind the question is given.
 aonecoding in United States
But somehow a user of this site @concernedCoder gets unhappy with it. So from today on, we will try to recover the original version of the question as much as possible.
We assure you all of the questions we posted are real questions that you have a good chance to come across during a coding interview. Anyone who has experience in a coding interview should be able to see that.
Here is the full description of a recent Amazon OA question. The reason why we are able to provide the full description is because it's the online assessment. But for an onsite interview it's almost impossible to recover the questions perfectly.
Title: Item Recommendations
Amazon wants to recommend items to a customer who has just made a purchase. Amazon's recommendation algorithm is based on item 'connection'.
Two items are 'strongly connected' if a single customer bought both of them. Two items are 'weakly connected' if they are both strongly and weakly connected to some other third item.
Your task is to determine the number of the items strongly and weakly connected to a given item.
You are provided the item id represented as a string, as well as the list of customer purchases represented as an array of strings. Each element in the array consists of a customer id(represented as a string) and an item id (also represented as a string). The two ids are separated by a colon. For example, if they element in the array is "ABJA:Z42G" then that means customer ABJA purchased item Z42G.
Your output consists of an array, where the first element in the array represents the number of items strongly connected to the provided item id and the second element represents the number of items weakly connected to the provided item id.
For example, if you were provided with the following input:
determineRecommendation("ABC",["first:ABC", "first:HIJ", "sec:HIJ", "sec:KLM", "third:NOP", "fourth:ABC", "fourth:QRS", "first"DEF", "fifth:KLM", "fifth:TUV"])
You would return the following array:
[3, 2]
since ABC is strongly connected to 3 items: DEF, HIJ and QRS and is weakly connected to 2 items: KLM and TUV
Although the description is long, the problem is just asking for 'search (with either DFS or BFS) in a graph'. Report Duplicate  Flag
Amazon Software Engineer Algorithm  1of 5 votes
AnswersCreate an iterator class that stores a list of the builtin Iterators.
 aonecoding in United States
Implement the next() and hasNext() methods in a Round Robin pattern (pops next element in a circle).
Example:
Given a list [iterator1,iterator2, iterator3...]
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next() if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
until there is no more element in any of the iterators Report Duplicate  Flag
Google Algorithm  1of 9 votes
AnswersQ: Weighted meeting room
Given a series of meetings, how to schedule them. Cannot attend more than a meeting at the same time. Goal is to find maximum weight subset of mutually nonoverlap meetings.class Meeting: def __init__(self): self.startTime self.endTime self.weight
@concernedCoder
 aonecoding in United States
When you claim the questions as fake, provide evidence. These are no doubt questions asked in the coding interviews of the best companies and they definitely help interviewees to prepare for the interview.
Why do you have a problem with this? Report Duplicate  Flag
Facebook Software Engineer Algorithm  1of 3 votes
AnswerOn google search, how to enable key word auto completion after a few letters typed.
 aonecoding in United States
Followup: How to rank the words if they are weighted by frequency? Report Duplicate  Flag
Google Software Engineer Algorithm  4of 4 votes
Answers# There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room.
 aonecoding in United States
# For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words:
# Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
# For example:
# input = [(1,4), (2,3)]
# > 3
# input = [(4,6), (1,2)]
# > 3
# input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
# > 11 Report Duplicate  Flag
Facebook Software Engineer Algorithm  5of 5 votes
AnswersFind the median of an unsorted array.
 aonecoding in United States
Have to do better than O(nlogn) time.
e.g.
Given [2, 6, 1] return 2
Given [2, 6, 1, 4] return 3 which is sum of the two elements in middle over 2 Report Duplicate  Flag
Facebook Software Engineer Algorithm  5of 5 votes
Answers/**
 aonecoding in United States
Given many coins of 3 different face values, print the combination sums of the coins up to 1000. Must be printed in order.
eg: coins(10, 15, 55)
print:
10
15
20
25
30
.
.
.
1000
*/ Report Duplicate  Flag
Facebook Software Developer Algorithm  2of 4 votes
AnswersFind all comments in the Java (it could be Python or any other language of your choice) codes that’s parsed in as a string.
 aonecoding in United States
You may assume the codes given is valid.
Input is a single string, e.g.
String codes =
“/* file created by aonecode.com\\n” +
“ welcome to the tech blog*/ \\n” +
“//main method\\n” +
“public static void main(String[] args) { \\n“ +
“ System.out.println(“//welcome”); //output\\n” +
“}”
Output is a list of strings
List<String> ret =
[
“ file created by anecode.com\n welcome to the tech blog”,
“main method”,
“output”
] Report Duplicate  Flag
Google Software Engineer Algorithm  4of 4 votes
AnswersQ: If you were given a series of equations e.g. [A = B, B = D, C = D, F = G, E = H, H = C]
 aonecoding in United States
and then another series [A != C, D != H, ..., F != A ]
Check whether the equations combined is valid.
For the example given, your program should return 'invalid', because the first series implies that A = C, which contradicts the statement A != C in the second series. Report Duplicate  Flag
Amazon Software Engineer Algorithm  3of 3 votes
AnswersPrint first pair of mismatching leaves (first pair as in inorder) given two preorder traversal arrays of BSTs.
e.g.For 5 4 8 2 4 6 9 Preorder Sequence as [5,4,2,4,8,6,9] & 5 3 8 2 4 7 9 Preorder Sequence2 as [5,3,2,4,8,7,9] Print “4, 3”.
@Kart
 aonecoding in United States
If you create the inorder sequences for the two trees, you'll be able to see that 4 and 3 comes far before 6 and 7.
In fact, in any of the three wellknown types of tree traversal, there is NO way for a node in the right tree visited prior to the node in the left tree.
@anon
The question gives just enough detail for you to solve it. It does NOT matter if the trees are balanced or same size. It's said in the first sentence that 'find the first nonmatching pair as in the INORDER sequence', which is the ascending sequence in a BST. Report Duplicate  Flag
Facebook Software Engineer Algorithm  3of 3 votes
AnswersRandomly select one of the weighted items from a linked list. (you may only go through the list once)
 aonecoding in United States
e.g.
weight 1.6 > weight 0.2> ... > weight 3.4
randomly select one item based on the weight. The higher the weight is, the more likely to be selected Report Duplicate  Flag
Amazon Software Engineer Algorithm  3of 3 votes
AnswersGiven a list of system packages, some packages cannot be installed until the other packages are installed. Provide a valid sequence to install all of the packages.
 aonecoding in United States
e.g.
a relies on b
b relies on c
then a valid sequence is [c, b, a] Report Duplicate  Flag
Uber Software Engineer Algorithm  3of 5 votes
AnswersPhone screen Q: String encoding and decoding: Design a method that converts a list of strings into a single string which can be later converted back to the list.
 aonecoding in United States Report Duplicate  Flag
Google Software Engineer Programming Skills  3of 5 votes
AnswersQ: Find the absolute paths to all directories with image files, given a file system that looks like this. The subdirectory is one indent over.
 aonecoding in United States/usr /local profile.jpg /bin config.txt dest.png /rbin image.gif /sys /re /tmp pic.jpg ..... ……
 Report Duplicate  Flag
Google Software Engineer Algorithm  2of 4 votes
AnswersQ: List all comments in the given segment of codes. It's pretty tricky since there is a lot of things to be considered, especially the escape characters.
 aonecoding in United States Report Duplicate  Flag
Google Software Engineer Algorithm

0 Answers
Coding Interview Mentoring
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
 aonecoding January 15, 2017
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions. Flag 
0 Answers
Coding Interview Mentoring
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
 aonecoding January 15, 2017
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions. Flag
Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION:
Find the median of a very big array of integer. Only iterator is available
There are 3 common ways to find median of an array.
1. Quick/Merge Sort
2. Quick Select
3. Counting Sort
1 and 2 demands WRITE access to the arrays if the array is too big to fit in memory. However only the iterator (READ) is given.
Since the numbers are integer, the range of possible numbers is [min_int, max_int]. Create a counter array or map to store frequency of numbers in array. Then find median from counter array in O(N).
public static double getMedian(Iterator<Integer> iterator) {
int size = 0;
Map<Integer, Integer> counter = new HashMap<>();
while(iterator.hasNext()) {
size++;
int number = iterator.next();
counter.put(number, counter.getOrDefault(number, 0) + 1);
}
int mid_idx1 = (size  1) / 2, mid_idx2 = size / 2;
int mid1 = Integer.MAX_VALUE, mid2 = Integer.MAX_VALUE;
for(int value = Integer.MIN_VALUE; value < Integer.MAX_VALUE; value++) {
if(counter.containsKey(value)) {
size = counter.get(value);
if(size <= mid_idx1 && mid2 < Integer.MAX_VALUE) { //array has even size
return (mid2 + value) / 2.0;
} else if(size <= mid_idx1) { //array has odd size
return value;
} else if(size == mid_idx2) { //found the first middle number for array with even size
mid2 = value;
}
}
}
return (mid1 + mid2) / 2;
}
More Optimal Solution:
Still this method requires storing the full range of integers, which has high demand for memory ~10G.
Another approach is distributed quick select  divide arrays into trunks that fits in memory. Find median of each trunk by inmemory sorting or quick select.
Next round ignore all numbers less than minimum median or bigger than maximum median. Divide remaining elements into trunks that fits in memory.
This way every round we'd be able to exclude one trunk of numbers and narrow down the search range, until eventually the range is small enough to fitin memory.
Looking for coaching on interview preparation?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. advanced algorithms and clean coding)
Interview questions sorted by companies
Mock Interviews
Ace G, U, FB, Amazon, LinkedIn, MS and other toptier interviews in weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution
public String countingSort(String s1, String s2) {
Map<Character, Integer> map = new HashMap<>();
for(char c: s1.toCharArray()) {
map.put(c, map.getOrDefault(c, 0) + 1);
}
StringBuilder overlaps = new StringBuilder();
StringBuilder nonoverlaps = new StringBuilder();
for(char c: s2.toCharArray()) {
if(map.containsKey(c)) {
int count = map.get(c);
while(count > 0) {
overlaps.append(c);
count;
}
map.put(c, 0);
} else {
nonoverlaps.append(c);
}
}
overlaps.append(nonoverlaps);
return overlaps.toString();
}

aonecoding
April 12, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION:
bucket sort in O(n)
public void sortOccurrences(String s) {
int n = s.length();
Map<Character, Integer> freq = new HashMap<>();
int maxFreq = 0;
for(char c: s.toCharArray()) { //count occurrences of chars
int frequency = freq.getOrDefault(c, 0) + 1;
freq.put(c, frequency);
if(frequency > maxFreq) maxFreq = frequency;
}
List<Character>[] buckets = new List[maxFreq + 1];
for(Map.Entry entry: freq.entrySet()) { //create buckets on occurrences of chars
int i = (int)entry.getValue();
if(buckets[i] == null) {
buckets[i] = new LinkedList<>();
}
buckets[i].add((char)entry.getKey());
}
for(int k = maxFreq; k > 0; k) { //print in descending
if(buckets[k] != null) {
for(char c: buckets[k]) {
System.out.println(c + ":" + k);
}
}
}
}

aonecoding
April 12, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION:
public class KClosestPoints {
public class Point {
public int x;
public int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}
public List<Point> findKClosest(Point[] p, int k) {
PriorityQueue<Point> pq = new PriorityQueue<>(k, new Comparator<Point>() {
@Override
public int compare(Point a, Point b) {
return (b.x * b.x + b.y * b.y)  (a.x * a.x + a.y * a.y);
}
});
for (int i = 0; i < p.length; i++) {
if (i < k)
pq.offer(p[i]);
else {
Point temp = pq.peek();
if ((p[i].x * p[i].x + p[i].y * p[i].y)  (temp.x * temp.x + temp.y * temp.y) < 0) {
pq.poll();
pq.offer(p[i]);
}
}
}
List<Point> x = new ArrayList<>();
while (!pq.isEmpty())
x.add(pq.poll());
return x;
}
}

aonecoding
April 07, 2018 Looking for coaching on interview preparation?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. advanced algorithms and clean coding)
Interview questions sorted by companies
Mock Interviews
Ace G, U, FB, Amazon, LinkedIn, MS and other toptier interviews in weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution: O(n)
first forloop removes all invalid ')'. Second forloop removes all invalid '('
public static String balanceParenthesis(String s) {
StringBuilder str = new StringBuilder(s);
int left = 0;
for(int i = 0; i < str.length(); i++) {
if(str.charAt(i) == '(') {
left++;
} else if(str.charAt(i) == ')') {
if(left > 0) {
left;
} else {
str.deleteCharAt(i);
}
}
}
int right = 0;
for(int i = str.length()  1; i >= 0; i) {
if(str.charAt(i) == ')') {
right++;
} else if(str.charAt(i) == '('){
if(right > 0) right;
else {
str.deleteCharAt(i);
}
}
}
return str.toString();
}

aonecoding
April 07, 2018 Looking for coaching on interview preparation?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. advanced algorithms and clean coding)
Interview questions sorted by companies
Mock Interviews
Ace G, U, FB, Amazon, LinkedIn, MS and other toptier interviews in weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION:
A binary search that looks for the actual size of array and target value at the same time.
public int binarySearch(SizeUnknown array, int target) {
int lo = 0, hi = 1;
while(lo <= hi) {
int mid = (lo + hi) / 2;
try {
if(array.get(mid) == target) {
return mid;
} else if(array.get(mid) > target){
hi = mid  1;
} else {
if(array.get(hi) < target) hi *= 2;
lo = mid + 1;
}
} catch(IndexOutOfBoundsException e) {
hi = mid  1;
}
}
return 1;
}

aonecoding
April 05, 2018 Looking for coaching on interview preparation?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. advanced algorithms and clean coding)
Interview questions sorted by companies
Mock Interviews
Ace G, U, FB, Amazon, LinkedIn, MS and other toptier interviews in weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION:
Seems like there are 3 cases:
1. s1 and s2 share no mutual characters. Then there is no way to further minimize the distance.
2. s1 and s2 share a pair of characters on crossed positions, such as 'b' and 'c' in "aabaaac" and "aacaaab". Then swap 'b' and 'c'.
3. s1 and s2 has no crossed pairs but has the same character on different positions. Then swap to align the character.
//@return the pair of indices in s2 to swap with.
public int[] Swap(String s1, String s2) {
if(s1.length() > s2.length()) {
return Swap(s2, s1);
}
int swap_idx1 = 1, swap_idx2 = 1;
for(int i = 0; i < s1.length(); i++) {
if(s1.charAt(i) != s2.charAt(i)) {
for (int j = i + 1; j < s1.length(); j++) {
if(s1.charAt(i) == s2.charAt(j) && s1.charAt(j) == s2.charAt(i)) {
return new int[]{i, j}; //case 2 found
} else if(s1.charAt(i) == s2.charAt(j) && s1.charAt(j) != s2.charAt(j)) {
swap_idx1 = i;
swap_idx2 = j;
}
}
for(int j = s1.length(); j < s2.length(); j++) {
if(s1.charAt(i) == s2.charAt(j)) {
swap_idx1 = i;
swap_idx2 = j;
}
}
}
}
if(swap_idx1 == 1) return null; //case1
else return new int[]{swap_idx1, swap_idx2};
}

aonecoding
April 01, 2018 Looking for coaching on interview preparation?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. advanced algorithms and clean coding)
Interview questions sorted by companies
Mock Interviews
Ace G, U, FB, Amazon, LinkedIn, MS and other toptier interviews in weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION:
import java.util.List;
import java.util.Map;
import java.util.HashMap;
class TreeNode {
int val;
List<TreeNode> kids;
}
public class HouseRobTree {
public int houseRob(TreeNode root) {
Map<TreeNode, Integer> money_in_tree = new HashMap<>();
return houseRobHelper(root, money_in_tree);
}
private int houseRobHelper(TreeNode root, Map<TreeNode, Integer> money_in_tree) {
if(root == null) return 0;
if(root.kids == null  root.kids.isEmpty()) return root.val;
if(money_in_tree.containsKey(root)) return money_in_tree.get(root);
int max = 0;
for(TreeNode kid: root.kids) {
max = Math.max(max, houseRobHelper(kid, money_in_tree));
if(kid.kids != null) {
for(TreeNode grandKid: kid.kids) {
max = Math.max(max, houseRobHelper(grandKid, money_in_tree) + root.val);
}
}
}
money_in_tree.put(root, max);
return max;
}
}

aonecoding
April 01, 2018 Looking for coaching on interview preparation?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. advanced algorithms and clean coding)
Interview questions sorted by companies
Mock Interviews
Ace G, U, FB, Amazon, LinkedIn, MS and other toptier interviews in weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution
Node kFromEnd(Node head, int k) {
Node fast = head;
k;
while(fast != null && k > 0) {
fast = fast.next;
k;
}
if(fast == null) return null;
Node slow = head;
while(fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}

aonecoding
March 30, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION:
KMP will be one way to do it. Another way will be Rolling Hash.
Since a byte has only 256 different values, it won't be hard to create rolling hash on it. For problems like searching bit series in a binary file or searching bytes in byte file, rolling hash can be easier than KMP.
A rolling hash (also known as rolling checksum) is a hash function where the input is hashed in a window that moves through the input.
class Search:
def __init__(self, prime):
#the prime number controls the scale of hashcodes by (hashcode % prime)
self.prime = prime
#search for a byte array in a byte_file
def find(self, array, byte_file):
length = len(array)
weight = 255 ** (length  1) # weight of the element leaving the window
code = self.hashcode(array)
rolling_hash_code = self.hashcode(byte_file[:length])
if code == rolling_hash_code:
print "target found at [", 0, ":", length, "]"
#start moving the window
for i in range(length, len(byte_file)): #or read file byte after byte(if memory is the bottleneck)
rolling_hash_code = self.rolling_hash(rolling_hash_code, byte_file[i  length], byte_file[i], weight)
if code == rolling_hash_code:
#then compare array with byte_file[i  length: i] to prevent false positive
print "target found at [", i  length + 1, ":", i + 1, "]"
#get hashcode for given byte array
def hashcode(self, array):
code = 0
for byte in array:
code = (code % self.prime * 255) % self.prime + byte
return code % self.prime
#get hashcode for bytes in window
def rolling_hash(self, code, past, current, weight):
code = 255 * (code  (weight % self.prime * past % self.prime) % self.prime) + current
code %= self.prime
return code

aonecoding
March 30, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
/*
North
1 2 3 4 5 6
West 7 8 9 10 11 12 East
13 14 15 16 17 18
19 20 21 22 23 24
South
*/
public void print(int[][] matrix) {
int len = matrix.length, width = matrix[0].length;
int x = 0, y = 0;
boolean goingUp = true;
while(x < len && y < width) {
System.out.print(matrix[x][y] + " ");
if(goingUp) {
if(y > 0 && x < len  1) {//Proceed to top right cell if border isn't met
y = 1;
x += 1;
} else if(x == len  1){ // Hit East border. Move to lower cell and start going down
y += 1;
goingUp = false;
} else { // Hit North border. Move to right cell and start going down
x += 1;
goingUp = false;
}
} else {
if(y < width  1 && x > 0) { //Proceed to bottom left cell if border if border isn't met
y += 1;
x = 1;
} else if(y == width  1) { //Hit South border. Move to the right neighbor and start going up
x += 1;
goingUp = true;
} else { //Hit West border. Move to the lower neighbor and start going up
y += 1;
goingUp = true;
}
}
}
}

aonecoding
March 22, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION
//O(N) time and space for processing the board and lamps
//O(1) for finding if a cell is illuminated
public class GridIllumination {
int N; //board size
Set<Integer> illuminated_x = new HashSet<>();
Set<Integer> illuminated_y = new HashSet<>();
Set<Integer> illuminated_diag0 = new HashSet();
Set<Integer> illuminated_diag1 = new HashSet();
//@param lamps  a list of (x,y) locations of lamps
public GridIllumination(int N, int[][] lamps) {
this.N = N;
for(int[] lamp: lamps) { //this lamp illuminates 4 lines of cells
illuminated_x.add(lamp[0]); //the entire column
illuminated_y.add(lamp[1]); //the entire row
illuminated_diag0.add(lamp[1]  lamp[0]); //diagonal line with a slope of 1
illuminated_diag1.add(lamp[0] + lamp[1]); //diagonal lines with a slope of 1
}
}
public boolean is_illuminated(int x, int y) {
if(illuminated_x.contains(x) 
illuminated_y.contains(y) 
illuminated_diag0.contains(y  x) 
illuminated_diag1.contains(x + y)) {
return true;
}
return false;
}
}

aonecoding
March 21, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
public class MovingAvg {
int[] q; // a circular queue of size N
int head; //queue head
int tail; //queue tail
int size; // queue size
int sum;
public MovingAvg(int N) {
q = new int[N];
}
//@param num  the next number from data stream
//@return  new average with num included and expired number excluded
public double getAverage(int num) {
double avg = 0;
sum += num;
if(size == q.length) {
sum = q[head];
head = (head + 1) % q.length;
} else {
size++;
}
q[tail] = num;
tail = (tail + 1) % q.length;
return 1.0 * sum / size;
}
}

aonecoding
March 17, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
public class MatrixPuzzle {
int column;
int row;
public MatrixPuzzle(int length, int width) {
this.column = length;
this.row = width;
}
//The dp formula will be M[i,j] = M[i  1, j  1] + M[i  1, j] + M[i  1, j + 1]
//Because one could only land on current cell from the 3 cells in the upperleft, left and lowerleft.
//To make the space consumption 1d, cache the numbers in one column of the matrix at a time.
//Followup 2: Just reset pathcounts for blocked cells to 0
public int numberOfPaths() {
int[] paths = new int[row];
paths[row  1] = 1; //start from bottomleft corner
for(int col = 1; col < column; col++) {
int upper_left_value = 0;
for(int r = 0; r < row; r++) {
int left_value = paths[r];
paths[r] += upper_left_value + (r == row  1 ? 0 : paths[r + 1]);
upper_left_value = left_value;
}
}
return paths[row  1]; //exit from bottomright
}
}

aonecoding
March 10, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION
public void output(int N) {
Set<Integer> set = new HashSet<>();
set.add(1);
for(int num = 2; num <= N; num++) {
if((num % 2 == 0 && set.contains(num / 2))  (num % 5 == 0 && set.contains(num / 5))) {
set.add(num);
System.out.println(num);
}
}
}
//What if factors (such as 5 and 2) are not known numbers?
//print all possible numbers by factor1^i * factor2^j * factor3^k * ...
public void outputK(int[] a, int N) { //an array of factors are given
Set<Integer> set = new HashSet<>();
set.add(1);
for(int num = 2; num <= N; num++) {
for(int i = 0; i < a.length; i++) {
if ((num % a[i] == 0 && set.contains(num / a[i]))) {
set.add(num);
System.out.println(num);
break;
}
}
}
}

aonecoding
March 10, 2018 Looking for coaching on interview preparation?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. advanced algorithms and clean coding)
Interview questions sorted by companies
Mock Interviews
Ace G, U, FB, Amazon, LinkedIn, MS and other toptier interviews in weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
//Extra space O(1) Runtime O(nlogn)
List<Integer> getFibonacciNumber(int[] nums) {
List<Integer> fibonacciNumbers = new ArrayList<>();
Arrays.sort(nums);
int fib1 = 1, fib2 = 1;
for(int i = 0; i < nums.length;) {
if(nums[i] < fib2) {
i++;
} else if(nums[i] == fib2) {
fibonacciNumbers.add(nums[i]);
i++;
} else {
int fib3 = fib1 + fib2;
fib1 = fib2;
fib2 = fib3;
}
}
return fibonacciNumbers;
}
//Math Solution: Extra space O(1) Runtime O(n)
List<Integer> getFibonacciNumbers(int[] nums) {
List<Integer> fibonacciNumbers = new ArrayList<>();
for(int n: nums) {
if(isFibonacci(n)) fibonacciNumbers.add(n);
}
return fibonacciNumbers;
}
boolean isFibonacci(int n)
{
// n is Fibonacci if one of 5*n*n + 4 or 5*n*n  4 or both
// is a perfect square
return isPerfectSquare(5*n*n + 4) 
isPerfectSquare(5*n*n  4);
}
boolean isPerfectSquare(int x)
{
int s = (int) Math.sqrt(x);
return (s*s == x);
}

aonecoding
February 15, 2018 Looking for coaching on interview preparation?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. advanced algorithms and clean coding)
Interview questions sorted by companies
Mock Interviews
Ace G, U, FB, Amazon, LinkedIn, MS and other toptier interviews in weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION:
final String[] largeNumbers = new String[] {""," thousand"," million"," billion"," trillion"," quintillion"};//...etc
final String[] digits = new String[] {"", " one", " two", " three", " four", " five", " six"," seven"," eight", " nine"};
final String[] tens = new String[] {"", " ten"," twenty"," thirty"," forty"," fifty"," sixty"," seventy"," eighty"," ninety"};
final String[] teens = new String[] {" ten", " eleven"," twelve", " thirteen", " fourteen", " fifteen", " sixteen", " seventeen"," eighteen"," nineteen"};
String digitsToEnglish(String num) {
if(num.length() == 1) {
return digits[Integer.parseInt(num)];
}
int len = num.length();
StringBuilder english = new StringBuilder();
int largeNumIdx = 0, tripletIdx = 0;
while(tripletIdx < len) {
StringBuilder triplet = new StringBuilder();
if(len > tripletIdx) {
triplet.append(num.charAt(len  1  tripletIdx));
}
if(len > tripletIdx + 1) {
triplet.insert(0, num.charAt(len  1  tripletIdx  1));
}
if(len > tripletIdx + 2) {
triplet.insert(0, num.charAt(len  1  tripletIdx  2));
}
if(Integer.parseInt(triplet.toString()) != 0) {
StringBuilder current = new StringBuilder();
if (triplet.length() == 3 && triplet.charAt(0) != '0') {
//current.append(' ');
current.append(digits[triplet.charAt(0)  '0']);
current.append(' ');
current.append("hundred");
}
if (triplet.length() >= 2 && triplet.charAt(triplet.length()  2) == '1') {
//current.append(' ');
current.append(teens[triplet.charAt(triplet.length()  1)  '0']);
} else {
if (triplet.length() >= 2) {
//current.append(' ');
current.append(tens[triplet.charAt(triplet.length()  2)  '0']);
}
//current.append(' ');
current.append(digits[triplet.charAt(triplet.length()  1)  '0']);
}
//current.append(' ');
current.append(largeNumbers[largeNumIdx]);
english.insert(0, current);
}
largeNumIdx += 1;
tripletIdx += 3;
}
return english.toString();
}

aonecoding
February 15, 2018 Looking for coaching on interview preparation?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. advanced algorithms and clean coding)
Interview questions sorted by companies
Mock Interviews
Ace G, U, FB, Amazon, LinkedIn, MS and other toptier interviews in weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
decompress("((x){3}(y){2}z){2}", 0)
def decompress(s, i):
res = ""
while i < len(s):
if s[i] == '(':
i += 1
word, i, r = decompress(s, i) # word is the decompressed string in (), r is the number of repetitions
res += word * r
elif s[i] == ')':
if i == len(s)  1 or s[i + 1] != '{': # in case of strings like "(a(b))" where {} is omitted
return res, i + 1, 1
else:
close = s.find("}", i)
return res, close + 1, int(s[i + 2: close])
else:
res += s[i]
i += 1
return res

aonecoding
February 13, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION:
Twoway BFS, similar to 'WordLadder'.
s1Derives and s2Derives are the words reachable by swapping characters in s1 and s2 in any random way. If s1and s2 are anagrams, for sure s1Derives and s2Derives would join at some point. Find out all possible derivatives 'nextLevel' of s1/s2. Then find out all derivatives of words in 'nextLevel'......until the earliest joint of s1Derives and s2Derives occurs. Return the number of levels gone through.
int minNumberOfSwaps(String s1,String s2) {
//if(!isAnagram(s1, s2)) return Integer.MAX_VALUE; //assume s1 and s2 are anagrams
int step = 0;
Set<String> s1Derives = new HashSet<>();
Set<String> s2Derives = new HashSet<>();
s1Derives.add(s1);
s2Derives.add(s2);
Set<String> visited = new HashSet<>();
int len = s1.length();
while(!containsSameString(s1Derives, s2Derives)) {
Set<String> set = step % 2 == 0 ? s1Derives: s2Derives;
Set<String> nextLevel = new HashSet<>();
for(String s: set) {
for (int i = 0; i < len; i++) {
for (int j = i; j < len; j++) {
if(s.charAt(i) != s.charAt(j)) {
char[] charArray = swap(s.toCharArray(), i, j);
String derived = new String(charArray);
if(!visited.contains(new String(derived))) {
nextLevel.add(derived);
visited.add(derived);
}
}
}
}
}
if(step % 2 == 0) s1Derives = nextLevel;
else s2Derives = nextLevel;
step++;
}
return step;
}

aonecoding
February 03, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION 1
public Integer random(int[] weights) {
int totalWeight = 0;
Integer selected = null;
Random rand = new Random();
for(int i = 0; i < weights.length; i++) {
int r = rand.nextInt(totalWeight + weights[i]);
if(r >= totalWeight) {
selected = i;
totalWeight += weights[i];
}
}
return selected;
}
FOLLOWUP
//main
//RandomSelectTree tree = new RandomSelectTree();
//while(tree.n > 0) tree.randomPoll();
//Segment Tree O(nlogn)
public class RandomSelectTree {
int[] tree;
int[] weights;
int n; //number of remaining balls
RandomSelectTree(int[] weights) {
tree = new int[2 * weights.length + 1];
this.weights = weights;
n = weights.length;
buildTree(0, 0, weights.length  1);
}
//build segment tree for weights[]
private void buildTree(int root, int start, int end) {
if(start > end) return;
if(start == end) {
tree[root] = weights[start];
return;
}
int mid = (start + end) / 2;
int leftChild = 2 * root + 1, rightChild = 2 * root + 2;
buildTree(leftChild, start, mid);
buildTree(rightChild, mid + 1, end);
tree[root] = tree[leftChild] + tree[rightChild];
}
public int randomPoll() {
if(n == 0) {
//Exception
}
int rand = new Random().nextInt(tree[0]);
int start = 0, end = weights.length  1, node = 0;
while(start < end) {
//chosen ball is between start to (start + end) / 2
if(rand < tree[node * 2 + 1]) {
node = node * 2 + 1;
end = (start + end) / 2;
} else { //chosen ball between (start + end) / 2 + 1 and end
rand = tree[node * 2 + 1]; //!!! narrow down to remaining range
node = node * 2 + 2;
start = (start + end) / 2 + 1;
}
}
delete(start, node);
return start;
}
//remove ball at idx.
private void delete(int idx, int node) {
n;
while(node > 0) {
tree[node] = weights[idx];
node = (node  1) / 2;
}
tree[0] = weights[idx];
}

aonecoding
January 20, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
//Solution to question O(n)
boolean isPeriod(String s) {
StringBuilder str = new StringBuilder(s + s);
str.deleteCharAt(0);
str.deleteCharAt(str.length()  1);
return strStr(str.toString(), s); //KMP strStr(T, S) to find if T has S in it.
}
//Solution to followup
//This method looks for the repeating pattern in string
private static String getPeriod(String string) { // O(n * n)
//for every possible period size i, check if it's valid
for (int i = 1; i <= string.length() / 2; i++) {
if (string.length() % i == 0) {
String period = string.substring(0, i);
int j = i;
while(j + i < string.length()) {
if (period.equals(string.substring(j, j + i))) {
j = j + i;
if(j == string.length()) { //period valid through entire string
return period;
}
} else {
break;
}
}
}
}
return null; //string is not periodic
}

aonecoding
January 20, 2018 Looking for help on interview preparation?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
Customized course covers
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. every aspect you need in a coding interview and Clean Coding)
Interview questions sorted by companies
Mock Interviews
Our members got into G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION:
Step 1, have a table to store all the visits sorted by time stamp.
or
have a queue to store the visits per second in the past 5 minute.
Followup:
Have two arrays hits[range] and lastupdated[range].
Range = 5 mins = 300 seconds in this case. Any hit within 'range' time from now is valid and should counted.
Index of a hit in the two arrays will be timestamp % 300.
Store the last updated time of a hit. Later if a query for the hit count arrives with a query timestamp, sum up all the valid hits from array 'hits'. Threshold for valid hits: query time  hit last updated time < 300.
public class HitCounter {
int[] times, hits;
int timeRange;
/** Initialize your data structure here. */
public HitCounter(int range) {
times = new int[range];
hits = new int[range];
timeRange = range;
}
/** Record a hit.
@param timestamp  The current timestamp (in seconds granularity). */
public void hit(int timestamp) {
int idx = timestamp % timeRange;
if (times[idx] != timestamp) {
times[idx] = timestamp;
hits[idx] = 1;
} else {
++hits[idx];
}
}
/** Return the number of hits in the past 5 minutes.
@param timestamp  The current timestamp (in seconds granularity). */
public int getHits(int timestamp) {
int res = 0;
for (int i = 0; i < timeRange; ++i) {
if (timestamp  times[i] < timeRange) {
res += hits[i];
}
}
return res;
}
}
Followup2
For writing,
Concurrency update becomes an issue. Add write lock for protection. But this may slowdown the machine badly.
Move hit counters onto a distributed system. Have several machines counting together. Assign userIDs to diff hosts.
Add LB on top to make sure requests get distributed evenly.
Upon reading, sum up counts across all machines. For a readheavy system, add cache.
Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
//Binary Indexed Tree (O(logN) Toggle, O(logN) Get.
public class ToggleBulbs {
int[] bulbs;
public ToggleBulbs(int n) { //n bulbs given
bulbs = new int[n + 1];
}
public boolean isOn(int i) {
//a bulb is on if it's toggled an odd number of times
return read(i) % 2 == 1;
}
// toggle(i, j) is equivalent to
// toggle(i, n  1) and then toggle(j, n  1)
public void toggle(int i,int j) {
toggle(i);
toggle(j + 1);
}
//toggle from ith to the last bulb (a standard update in BITree)
private void toggle(int idx){
int node = idx + 1;
while (node < bulbs.length){
bulbs[node] = (bulbs[node] + 1) % 2;
node += (node & node);
}
}
//get the number of times bulb i toggled (read prefix sum from 0 to i in BITree)
private int read(int idx) {
int node = idx + 1;
int sum = 0;
while (node > 0) {
sum += bulbs[node];
node = (node & node);
}
return sum;
}
}

aonecoding
January 16, 2018 Looking for help on interview preparation?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
Customized course covers
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. every aspect you need in a coding interview and Clean Coding)
Interview questions sorted by companies
Mock Interviews
Our members got into G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
boolean hasFactorKSubArray(int[] arr, int k) {
for(int i = 1; i < arr.length; i++) {
arr[i] += arr[i  1]; //becomes a prefix sum array of arr (can be recovered if necessary)
}
for(int hi = arr.length  1; hi >= 1; hi ) {
for(int lo = 0; lo <= hi  1; lo++) {
if((arr[hi]  lo == 0 ? 0: arr[lo  1]) % k == 0) {
return true;
}
}
}
return false;
}

aonecoding
January 13, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
class Node:
def __init__(self, ID, parent):
self.ID = ID
self.parentID = parent
self.left = None
self.right = None
#function to identify if given is preorder
'''
Create a stack to store nodes in the current path when traversing.
Push node[i] into stack once node[i] is verified to be valid (valid only when parent of node[i] is in stack.
In preorder a parent must show up earlier than its child)
Whenever stack top is not the parent of node[i], pop until parent of node[i] is at stack top. Push node[i].
If all nodes popped but parent of node[i] still not found, then node[i] is not in preorder sequence.
'''
def isPreorder(nodes):
if not nodes:
return True
st = [nodes[0].ID]
i = 1
while i < len(nodes):
if not st:
return False
if st[1] is nodes[i].parentID:
st.append(nodes[i].ID)
i += 1
else:
st.pop()
return True

aonecoding
January 06, 2018 Looking for help on interview preparation?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
Customized course covers
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. every aspect you need in a coding interview and Clean Coding)
Interview questions sorted by companies
Mock Interviews
Our members got into G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
# The question is about identifying any window size k that its numbers at both ends bigger than numbers in between
def bloomDay(a, k): # k must be >= 0
window = [] # elements in window maintain descending order.
firstDay = 10000000
i = 0
while i < len(a):
if not window:
window.append(i)
i += 1
elif i  window[0] <= k:
if a[i] >= a[window[0]]:
window = [i]
i += 1
elif a[i] >= a[window[1]]:
window.pop()
else:
window.append(i)
i += 1
else: #window size == k
if len(window) == 1 or a[window[1]] < a[i]:#valid window with both end numbers biggest
firstDay = min(firstDay, a[i], a[window[0]])
window = [i]
i += 1
else: #a[i] is less than a number in the middle of the window
window.pop(0)
if a[window[1]] <= a[i]:
window.pop()
else:
window.append(i)
i += 1
return firstDay

aonecoding
January 05, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
'''
This is sexagesimal addition.
e.g.
Start from the least significant bit (righthand side).
Check if there is a number bigger than the current digit available.
If yes,
For least significant digit in '15:31', '3' is the next number bigger than '1'.
Then there is no carry to bring forward. Stop adding and return the result '15:33'.
If no,
For example '14:59', nothing is bigger than '9'. Then update this bit with the min number and proceed
to find the number just bigger than the next bit '5'.
It's similar to bringing the carry bit forward in an add operation.
When looking for the number bigger than '5', note that this is a sexagesimal number.
Therefore although '9' is bigger than '5', but it can't be taken since it's over '6'. So set '5' to the min number '1'.
And proceed to the next number '4'.
'4' has a next bigger number '5'. So set it to '5' and the carry stops here.
Result for '14:59' is '15:11".
'''
def nextMoment(time):
result = list(time)
numbers = list(time)
numbers.pop(2)
numbers = sorted(set(numbers))
result[1] = findNextNumber(numbers, time[1], '9')
if result[1] >= time[1]:
return "".join(result)
result[2] = findNextNumber(numbers, time[2], '5')
if result[2] > time[2]:
return "".join(result)
result[1] = findNextNumber(numbers, time[1], '9')
if result[1] > time[1]:
return "".join(result)
result[0] = findNextNumber(numbers, time[0], '5')
if result[0] >= time[0]:
return "".join(result)
return "".join(result)
#find the next available number that's bigger than num.
#if nothing is bigger, then return the smallest number.
def findNextNumber(sorted_arr, num, upper_bound):
idx = sorted_arr.index(num) + 1
if idx >= len(sorted_arr) or sorted_arr[idx] > upper_bound:
return sorted_arr[0]
return sorted_arr[idx]

aonecoding
January 05, 2018 Looking for help on interview preparation?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
Customized course covers
System Design (for candidates of FB, LinkedIn, AMZ, Google and Uber etc)
Algorithms (DP, Greedy, Graph etc. every aspect you need in a coding interview and Clean Coding)
Interview questions sorted by companies
Mock Interviews
Our members got into G, U, FB, Amazon, LinkedIn, MS and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION
The push, pop and inc can all take place in O(1) time
if there is an additional array to maintain the m incremented at each position n.
class Stack:
def __init__(self):
self.nums = []
self.add = []
def push(self,num):
self.nums.append(num)
self.add.append(0)
print num," "
def pop(self):
try:
number_to_add = self.add.pop()
print self.nums.pop() + number_to_add
if self.add:
self.add[1] += number_to_add
except:
print "can't pop from an empty stack"
def inc(self, n, m):
if not self.nums:
print "empty"
if n > 0:
n = min(n, len(self.nums))
self.add[n  1] += m
print self.nums[1] + self.add[1], " "

aonecoding
January 04, 2018 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Sliding window anagram:
public static List<Integer> getAnagrams(String s, String word) {
Map<Character, Integer> letters = new HashMap<>();
int distinct_letters = 0;
for(char c: word.toCharArray()) {
if(!letters.containsKey(c)) distinct_letters++;
letters.put(c, letters.getOrDefault(c, 0) + 1);
}
//search for anagrams with two pointers
List<Integer> res = new ArrayList<>();
int lo = 0, hi = 0;
while(hi < s.length()) {
if(!letters.containsKey(s.charAt(hi))) {
while(lo < hi) {
char c = s.charAt(lo);
if(letters.get(c) == 0) distinct_letters++;
letters.put(c, letters.get(c) + 1);
lo++;
}
hi++;
lo = hi;
} else if(letters.get(s.charAt(hi)) == 0){
while(s.charAt(lo) != s.charAt(hi)) {
char c = s.charAt(lo);
if(letters.get(c) == 0) distinct_letters++;
letters.put(c, letters.get(c) + 1);
lo++;
}
lo++;
} else {
char c = s.charAt(hi);
letters.put(c, letters.get(c)  1);
if(letters.get(c) == 0) distinct_letters;
if(distinct_letters == 0) {
res.add(lo);
}
hi++;
}
}
return res;
}

aonecoding
November 03, 2017 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Get sqrt(x):
int sqrt(int x) {
//check for x >= 0 if necessary
int r = x;
while (r * r > x)
r = (r + x / r) / 2;
return r ;
}
BST Implementation:
class BinarySearchTree {
/* Class containing left and right child of current node and key value*/
class Node {
int key;
Node left, right;
public Node(int item) {
key = item;
left = right = null;
}
}
// Root of BST
Node root;
// Constructor
BinarySearchTree() {
root = null;
}
// This method mainly calls insertRec()
void insert(int key) {
root = insertRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node insertRec(Node root, int key) {
/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = insertRec(root.left, key);
else if (key > root.key)
root.right = insertRec(root.right, key);
/* return the (unchanged) node pointer */
return root;
}
// This method mainly calls InorderRec()
void inorder() {
inorderRec(root);
}
// A utility function to do inorder traversal of BST
void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.println(root.key);
inorderRec(root.right);
}
}
// This method mainly calls deleteRec()
void deleteKey(int key)
{
root = deleteRec(root, key);
}
/* A recursive function to insert a new key in BST */
Node deleteRec(Node root, int key)
{
/* Base Case: If the tree is empty */
if (root == null) return root;
/* Otherwise, recur down the tree */
if (key < root.key)
root.left = deleteRec(root.left, key);
else if (key > root.key)
root.right = deleteRec(root.right, key);
// if key is same as root's key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (root.left == null)
return root.right;
else if (root.right == null)
return root.left;
// node with two children: Get the inorder successor (smallest
// in the right subtree)
root.key = minValue(root.right);
// Delete the inorder successor
root.right = deleteRec(root.right, root.key);
}
return root;
}
}

aonecoding
November 03, 2017 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Get the longest arithmetic progression:
public static int[] llac(int[] array) {
if(array.length == 0) return new int[]{};
int maxLen = 1, //len of longest sequence
end = array[0], //end number of sequence
step = 0;
Map<Integer,Map<Integer, Integer>> index_to_llac = new HashMap<>(); //Map<currentIndex, Map<difference, length>>
for(int current = 1; current < array.length; current++) {
index_to_llac.put(current, new HashMap<>());
for(int prev = 0; prev < current; prev++) {
int diff = array[current]  array[prev];
int length = 2;
if(index_to_llac.containsKey(prev) && index_to_llac.get(prev).containsKey(diff)) {
length = index_to_llac.get(prev).get(diff) + 1;
}
Map<Integer, Integer> diff_to_llac = index_to_llac.get(current);
//if this is a arithmetic progression with [diff] exists before current, add 1 to the length to include current in the progression
//otherwise, [prev, current] forms a progression of size 2
diff_to_llac.put(diff, length);
if(maxLen < length) {
maxLen = length;
end = array[current];
step = diff;
}
}
}
int[] sequence = new int[maxLen];
for(int i = maxLen  1; i >= 0; i) {
sequence[i] = end;
end = step;
}
return sequence;
}

aonecoding
November 03, 2017 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
public static int rankWays(int n) {
int[] base = new int[2]; // start from case for 0 participants
base[1] = 1;
for(int p = 2; p <= n; p++) {
int[] ways = new int[p + 1]; //index is row number, value is count of ways
for(int r = 1; r < base.length; r++) {
ways[r + 1] += base[r] * (r + 1);
ways[r] += base[r] * r;
}
base = ways;
}
int sum = 0;
for(int x: base) sum += x;
return sum;
}
With N participants [p1, p2, p3... pN], one ranking could be:
1st place: p1
2nd place: p2, p3
...
xth place: pN
In this case, if one more player pL joins the game. The new player pL can be placed into
pL can be here as new 1st place
1st place p1 pL can be here tied with 1st place
pL can be here as new 2nd place
2nd place p2, p3 pL can be here tied 2nd place
... ...
xth place pN pL can be here tied last place
pL can be here as new last
So for every rank combination of N people, adding 1 more player creates rowNumber * 2 + 1 ways of ranking.
So if we keep track of the row numbers of all previous combinations of ranking,
a ranking with R rows is gonna derive into R + 1 more cases (with R + 1 row numbers) plus R more cases (with R row numbers).
To print all possible combinations:
public static List<List<List<Integer>>> rankCombinations(int n) {
List<List<List<Integer>>> base = new ArrayList<>();
base.add(new ArrayList<>());
base.get(0).add(new ArrayList<>());
base.get(0).get(0).add(1);
for(int p = 2; p <= n; p++) {
List<List<List<Integer>>> combinations = new ArrayList<>();
for(List<List<Integer>> comb: base) {
for(int i = 0; i <= comb.size(); i++) {
List<Integer> rank = new ArrayList<>();
rank.add(p);
List<List<Integer>> newComb = new ArrayList<>(comb);
newComb.add(i, rank);
combinations.add(newComb);
}
for(int i = 0; i < comb.size(); i++) {
List<List<Integer>> newComb = deepcopy(comb);
newComb.get(i).add(p);
combinations.add(newComb);
}
}
base = combinations;
}
//print all ranking combinations. multi players in a same sublist makes a tie.
for(List<List<Integer>> ranks: base) System.out.println(ranks);
return base;
}
private static List<List<Integer>> deepcopy(List<List<Integer>> ls) {
List<List<Integer>> copy = new ArrayList<>();
for(List<Integer> sublist: ls) {
copy.add(new ArrayList<Integer>(sublist));
}
return copy;
}
Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Candidate’s Solution (Passed all test cases in Airbnb OA)
int paginate(const std::vector<std::string>& addressbook, std::vector<std::string>& results) {
std::list<std::pair<int, int> > curve; // host_id, position in addressbook
int num_entries = addressbook.size(); // already sorted by score.
for (int index = 0; index < num_entries; ++index) {
const std::string& s = addressbook[index];
int host_id = std::stoi(s.substr(0, s.find_first_of(',')));
curve.emplace_back(host_id, index);
}
while (!curve.empty()) {
std::unordered_set<int> uniq_host_ids;
std::vector<decltype(curve)::iterator> hosts;
bool combo = false;
for (auto iter = curve.begin(); iter != curve.end(); ++iter) {
if (uniq_host_ids.find(iter>first) == uniq_host_ids.end()) {
uniq_host_ids.insert(iter>first);
hosts.push_back(iter);
if (hosts.size() == resultsPerPage) {
combo = true;
break;
}
}
}
for (auto& host : hosts) {
results.push_back(addressbook[host>second]);
}
for (auto& host : hosts) {
curve.erase(host);
}
if (combo) {
if (!curve.empty()) results.push_back("");
continue; // enter next loop
}
if (!curve.empty()) {
int num_done = hosts.size();
for (auto iter = curve.begin(); iter != curve.end(); ++iter) {
hosts.push_back(iter);
if (hosts.size() == resultsPerPage) {
combo = true; break;
}
}
int num_hosts = hosts.size();
for (int i = num_done; i < num_hosts; ++i) {
results.push_back(addressbook[hosts[i]>second]);
}
for (int i = num_done; i < num_hosts; ++i) {
curve.erase(hosts[i]);
}
if (combo && !curve.empty()) {
results.push_back("");
}
} // end if condition
} // end while loop
return 0;
}

aonecoding
October 13, 2017 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
public static List<Integer> getAnagrams(String s, String word) {
Map<Character, Integer> letters = new HashMap<>();
int distinct_letters = 0;
for(char c: word.toCharArray()) {
if(!letters.containsKey(c)) distinct_letters++;
letters.put(c, letters.getOrDefault(c, 0) + 1);
}
//search for anagrams with two pointers
List<Integer> res = new ArrayList<>();
int lo = 0, hi = 0;
while(hi < s.length()) {
if(!letters.containsKey(s.charAt(hi))) {
while(lo < hi) {
char c = s.charAt(lo);
if(letters.get(c) == 0) distinct_letters++;
letters.put(c, letters.get(c) + 1);
lo++;
}
hi++;
lo = hi;
} else if(letters.get(s.charAt(hi)) == 0){
while(s.charAt(lo) != s.charAt(hi)) {
char c = s.charAt(lo);
if(letters.get(c) == 0) distinct_letters++;
letters.put(c, letters.get(c) + 1);
lo++;
}
lo++;
} else {
char c = s.charAt(hi);
letters.put(c, letters.get(c)  1);
if(letters.get(c) == 0) distinct_letters;
if(distinct_letters == 0) {
res.add(lo);
}
hi++;
}
}
return res;
}

aonecoding
October 09, 2017 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
import java.util.LinkedList;
import java.util.Queue;
class process {
int arrTime;
int exeTime;
process(int arr, int exe) {
arrTime = arr;
exeTime = exe;
}
}
public class RoundRobinScheduling {
public float Solution(int[] Atime, int[] Etime, int q) {
if (Atime == null  Etime == null  Atime.length != Etime.length)
return 0;
int length = Atime.length;
Queue<process> queue = new LinkedList<process>();
int curTime = 0, waitTime = 0;
int index = 0;
while (!queue.isEmpty()  index < length) {
if (!queue.isEmpty()) {
process cur = queue.poll();
waitTime += curTime  cur.arrTime;
curTime += Math.min(cur.exeTime, q);
for (; index < length && Atime[index] <= curTime; index++)
queue.offer(new process(Atime[index], Etime[index]));
if (cur.exeTime > q)
queue.offer(new process(curTime, cur.exeTime  q));
}
else {
queue.offer(new process(Atime[index], Etime[index]));
curTime = Atime[index++];
}
}
return (float) waitTime / length;
}
}

aonecoding
October 09, 2017 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
public static void main(String[] args) {
System.out.println(lonelyPixelCount(new int[][]{ //1: black, 0: white
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0},
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0},
{0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
}));
}
static int lonelyPixelCount(int[][] picture) {
int m = picture.length, n = picture[0].length;
//First traversal sum up the count of black pixels by column
for(int i = 1; i < m; i++){
for(int j = 0; j < n; j++){
picture[i][j] += picture[i  1][j];
}
}
int result = 0;
//Then traverse row by row from the bottom, count the black pixels in current row.
//If there is only 1 black pixel in current row, verify whether it is also the only in the column.
for(int i = m  1; i >= 0; i) {
int pixel_count_in_row = 0;
boolean only_pixel_in_column = false;
for(int j = n  1; j >= 0; j) {
if(picture[i][j] > 0 && (i == 0  picture[i  1][j] + 1 == picture[i][j])) { //verify if current cell number is a black pixel, by method in blue text above
pixel_count_in_row++;
if((i < m  1 && picture[i + 1][j] == 1)  (i == m  1 && picture[i][j] == 1)) {
only_pixel_in_column = true;
}
}
if(i < m  1) {
//overwrite current cell with the number below it
picture[i][j] = picture[i + 1][j];
}
}
if(pixel_count_in_row == 1 && only_pixel_in_column) {
result++;
}
}
return result;
}

aonecoding
September 22, 2017 Looking for interview experience sharing and coaching?
Visit AONECODE.COM for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other toptier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
import java.util.List;
import java.util.ArrayList;
public class IntegerCollection {
List<Integer> collection = new ArrayList<>();
List<Integer> divisors = new ArrayList<>();
int factor = 1;
int addition = 0;
int set0 = 1;
public void append(int x) {
collection.add(x  addition);
divisors.add(factor);
}
public int get(int index) {
if(index >= collection.size()) throw new RuntimeException();
if(divisors.get(index) <= set0) return addition;
return collection.get(index) * (factor / divisors.get(index)) + addition;
}
public void add_to_all(int x) {
addition += x;
}
public void multiply_to_all(int x) {
if(x == 0) {
addition = 0;
factor = 1;
set0 = collection.size()  1;
} else {
addition *= x;
factor *= x;
}
}
}

aonecoding
September 22, 2017 Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
from collections import defaultdict
def getRecommendedTweets(followGraph_edges, likeGraph_edges, targetUser, minLikeThreshold):
targetUserFollows = {t[1] for t in followGraph_edges if t[0] is targetUser}
recommendedTweets = defaultdict(lambda:0)
for like in likeGraph_edges:
if like[0] in targetUserFollows:
recommendedTweets[like[1]] += 1
return [tweet for tweet in recommendedTweets if recommendedTweets[tweet] >= minLikeThreshold]

aonecoding
September 07, 2017 SELECT
Department.name,
COUNT(Employee.id)
FROM
Department
LEFT JOIN
Employee ON Department.dept_id = Employee.dept_id
GROUP BY
Department.dept_id,
Department.name
ORDER BY
COUNT(Employee.id) DESC,
Department.name
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Step 1 Find the Key
Based on the rotation rules and the piece of decrypted message:
Atvt hrqgse, Cnikg
Your friend, Alice
We get the code
251220825122082
1st character 'Y' + 2 is beyond 'Z'. So start back at 'A'.
2nd character 'o' + 5 is 't'.
3rd character 'u' + 1 is 'v'
etc.
The code is probably periodic on 2512208, more precisely, on a rotation of 2512208 since we do not know where the start of the key is, since "Your friend, Alice" is not at the opening of the text.
To find out the first digit in the key,
Known the length of key is 7 and number of letters before the signature is N.
So the message is encrypted this way:
7 digit key  7 digit key  …  N % 7 of key
7 letters  7 letters  …  N % 7 letters
The final key period in the message prior to signature is incomplete with (N % 7) digits used.
The remaining part of the key period (7  N % 7) goes to the signature"Your friend, Alice".
So the first complete key period in "Your friend, Alice" starts at position (7  N % 7).
In the test case give, there are 92 letters before the signature Your friend, Alice.
N = 92
(7  N % 7) = 6
Therefore the start of key 2512208 is at the 6th index position which is the 8.
So the actual key is 8251220,
Step 2 Recover from Rotation
Once the key is found, what left is just to rotate the encrypted message back.
Assume current letter in the encrypted message is msg[i] and current key digit is key[j],
original letter = msg[i]  key[j] (if original letter underflows ‘a’/’A’, start again from ‘z’/‘Z’).
public String decrypt(String input, int[] key) {
StringBuilder res = new StringBuilder();
int i = 0;
for(char c: input.toCharArray()) {
if(i == key.length) i = 0;
if(Character.isLetter(c)) {
char firstLetter = c <= 'Z' ? 'A' : 'a';
c = (char)(c  key[i]);
if(c < firstLetter) c = (char)(c + 26);
i++;
}
res.append(c);
}
return res.toString();
}
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution to III.
int sqrt(int x) {
if (x == 0)
return x;
int left = 1, right = x;
while (true) {
int mid = (left + right) / 2;
if (mid > x / mid)
right = mid  1;
else if (mid + 1 > x / (mid + 1)) //mid < x / mid
return mid;
else //mid < x / mid
left = mid + 1;
}
}
IV. is on LC
V. Lossy Counting & Sticky Sampling
Solution to Closest K Nodes
vector<int> closestKValues(TreeNode* root, double target, int k) {
vector<int> res;
inorder(root, target, k, res);
return res;
}
void inorder(TreeNode *root, double target, int k, vector<int> &res) {
if (!root) return;
inorder(root>left, target, k, res);
if (res.size() < k) res.push_back(root>val);
else if (abs(root>val  target) < abs(res[0]  target)) {
res.erase(res.begin());
res.push_back(root>val);
} else return;
inorder(root>right, target, k, res);
}
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
@ChrisK
There were two versions of code provided  one for a set with no dupes and the other one for a set with dupes.
It is not counting any cases twice since there is a while loop at the end of dfs() that hops i over any duplicated elements.
I would appreciate it if you read the thing more thoroughly before making assumptions.
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution:
How to combine the 4 given card ranks with operators +, , x and / to reach 24.
Backtrack to print all possible combinations.
public void solve(int[] cards) {
boolean[] played = new boolean[4];
for(int i = 0; i < 4; i++) {
StringBuilder str = new StringBuilder(String.valueOf(cards[i]));
played[i] = true;
solve(cards, played, cards[i],str);
played[i] = false;
}
}
private void solve(int[] cards, boolean[] played, double res, StringBuilder str) {
if(played[0] && played[1] && played[2] && played[3]) {
if(res == 24)
System.out.println(str.toString());
return;
}
for(int i = 0; i < 4; i++) {
int len = str.length();
if(!played[i]) {
played[i] = true;
str.insert(0, '(');
str.append("+" + cards[i] + ")");
solve(cards, played, res + cards[i], str);
str.setCharAt(len + 1, '');
solve(cards, played, res  cards[i], str);
str.deleteCharAt(0);
str.deleteCharAt(str.length()  1);
str.setCharAt(len, '*');
solve(cards, played, res * cards[i], str);
str.setCharAt(len, '/');
solve(cards, played, 1.0 * res / cards[i], str);
str.delete(len, str.length());
played[i] = false;
}
}
}

aonecoding
August 14, 2017 Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution:
I. If it is a writeheavy application, create a Fenwick Tree to store for every toggle(i, j), add 1 to node i and 1 to node j (O(logN)). Upon calling isOn(k), get the cumulative sum (O(logN)) till the kth node. If sum is odd, then bulb is on. Otherwise bulb is off.
II. If it is readheavy, create a bit map that toggles in linear time and reads in constant time.
//Fenwick Tree Solution
public class ToggleBulbs {
int[] sum;
public ToggleBulbs(int n) {
sum = new int[n];
}
public boolean isOn(int i)
{
return read(i)%2==1;
}
public void toggle(int start,int end)
{
update(start,1);
update(end+1,1);
}
private int read(int idx){
int ans = 0;
while (idx > 0){
ans += sum[idx];
idx = (idx & idx);
}
return ans;
}
private void update(int idx ,int val){
while (idx <= sum.length){
sum[idx] += val;
idx += (idx & idx);
}
}
}

aonecoding
August 09, 2017 Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
public void powerOf2Paths(int N) {
List<Integer> path = new ArrayList<>();
path.add(0);
powerOf2PathsHelper(4, 0, path);
}
public void powerOf2PathsHelper(int N, int num, List<Integer> path) {
if(num == N) {
System.out.println(path);
}
for(int i = 0; num + (1 << i) <= N; i++) {
int sum = num + (1 << i);
path.add(sum);
powerOf2PathsHelper(N, sum, path);
path.remove(path.size()  1);
}
}

aonecoding
August 09, 2017 Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
//get the number of connected components in a list
public int numberOfGroups(Set<Node> nodes) {
Set<Node> visited = new HashSet<>();
int cnt = 0;
for(Node node: nodes) {
while(!visited.contains(node)) {
if(nodes.contains(node)){
visited.add(node);
node = node.next;
} else {
cnt++;
break;
}
}
}
return cnt;
}

aonecoding
August 09, 2017 Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates for FLAG & U)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Our students got hired from G, U, FB, Amazon, LinkedIn and other top tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution:
I. If the given arr has unique and distinct elements, it is like the two sum problem then (have two pointers and find out for each j, what's the corresponding i so that arr[i] + arr[j] is just smaller than target K ). The subset count for i to j will be pow(2, j  i).
II. While there are dupes in arr, backtracking is needed to figure out all the subsets possible.
//no dupes
int countSubset(vector<int> & arr, int target) {
int i = arr.size()  1;
while(i >= 0 && arr[i] << 1 >= target) i;
if(i == 1) return 0;
int count = 0, j = i;
while(i >= 0) {
while(j < arr.size()  1 && arr[j + 1] + arr[i] < target) j++;
count += pow(2, j  i);
i;
}
return count;
}
//with dupes
void dfs(vector<int> nums, int idx, int &res, vector<int> &cur, int target)
{
if(idx == nums.size())
{
return;
}
else
{
for(int i = idx; i < nums.size(); i++)
{
cur.push_back(nums);
if((cur.size() == 1 && cur[0] < target)  (cur[0] + cur.back() < target))
{
for(auto it : cur)
{
cout<<it<<" ";
}
cout<<endl;
res++;
dfs(nums, i + 1, res, cur, target);
}
cur.pop_back();
while(i < nums.size()  1 && nums == nums[i + 1])i++;
}
}
}
int countSubset2(vector<int> nums, int target)
{
int res = 0;
vector<int> cur;
dfs(nums, 0, res, cur, target);
return res;
}
int main()
{
vector<int> nums = {2, 2, 3, 5, 7};
cout<<countSubset2(nums, 8)<<endl;
}

aonecoding
August 06, 2017 Hi Fernando,
I interpret the problem this way  making someone my colleague means having him into my team (assigning my manager to him). Since it is a design problem it's openended and your solution would be good as well.
Thanks for the reply!
Replisanielson212, Associate at ASAPInfosystemsPvtLtd
Now I work in freelancing in Search Engine optimization. I like reading nobbles, old stories, love stories. I am happy ...
RepJohnMThomaa, Systems Design Engineer at USAA
Managed a small team writing about dust in Minneapolis, MN. Spent high school summers marketing Online vacuum pump sale New ...
RepDimaOxygen15, Computer Scientist at Headrun Technologies Pvt Ltd
Hi! all my sweets friends My name is Dimo Oxygen! Now I study in Victoria University of Wellington New Zealand ...
RepShaneMMullen, SEO at IITD
Are you facing love life and married life problem. Contact vashikaran specialist right now. He will guide your solution with ...
RepAre you looking a solution for marry your love? Islamic dua to marry someone you love is the effective solution ...
RepDiscover the best online vaporizer store to buy quality vaping accessories at affordable price. Visit NY Vape Shop, specialized in ...
RepMaryHDavis, Employee at ASU
Had a brief career promoting wooden tops in Salisbury, MD. My current pet project is lecturing about human hair in ...
RepPandit Ji is the best vashikaran expert for vashikaran mantra for girlfriend in Mumbai.It is the strongest method to ...
RepLooking for the best day care center Charlotte? PalARoo’s Child Development Center is a family owned child care facility ...
RepAmber Van is registered and fully insured cheap removal company in Bristol.Our featured services includes domestic moves,commercial moves ...
RepHire high professional child development center in Charlotte. PalARoo’s Child Development Center is a familyowned child care facility offering ...
Repriverajenny935, i love my shop piano at xyz
Hello Everyone,My Name is Jenny Rivera .I have been a piano instructor for more than 25 years! I earned ...
Rep
Repsunstaley212, Graphics Programmer at Service Now
Hello Everyone, My name is sun staley and I am from new zealand. I might want to attempt this experience ...
RepAmber Van is the top rated company that offers friendly and professional removals services.Our featured services includes domestic moves ...
RepMartaLopes590, maintenence engineer at xyz
My name is Marta Lopes from Australia. I'm a single parent of one. I've been occupied with demonstrating ...
Repmethali0001, Frontend Software Engineer at Coupon Dunia
I am website designer in India Chandigarh. I done Msc in IT. I open a new small company for designing ...
RepRocioNavarro189, None at Student
Hello Everyone,My name is Rocio Navarro Form Auckland,NZ,and 31 years old.I am searching for a servant ...
RepVirginialdelmonte, Animator at lostlovebackvashikaran
Have you lost your husband love? And you want to control your husband mind with vashikaran mantra. Guru ji is ...
RepAre you wasting time for to search a professional astrologer and specialist to get rid of black magic?Black Magic ...
RepAre you searching the strong and the most powerful Mantra for your husband? Consult our vashikaran specialist now. He provides ...
Reploveastrologyspecialist7, Program Manager at Service Now
Hello Everyone,My name is Asena Kaya from Texas,United States. I am 25 years old.i am in the ...
Repsunita212jain, Android test engineer at Computer Associates
My name is Sunita jain. I am in Chandigarh (India). I am a computer hardware retailer and wholesaler. I also ...
RepHandyman Homes is the onestop destination for all your home improvement and handyman needs.We take care of residential & commercial ...
Open Chat in New Window
Looking for interview experience sharing and coaching?
Visit AONECODE.COM for ONETOONE private lessons by FB, Google and Uber engineers!
SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algorithms & Clean Coding),
latest interview questions sorted by companies,
mock interviews.
Get hired by G, FB, U, Amazon, LinkedIn and other companies after weeks of training.
Email us aonecoding@gmail.com with any questions. Thanks!
SOLUTION:
Q1  DFS to count the number of connected components in graph.
Followup 
What if board is too big?
Consider dividing the board and process each part separately.
Divide into blocks or row by row?
Row by Row. It's hard to deal with the border of blocks.
Union find by each row
What's the memory consumption?
Each time load 1 row of input into memory. Create a union find array for two rows (current row and previous row). Memory = 3 * row.
A tester
 aonecoding April 21, 2018