aonecoding
BAN USER- 2of 2 votes
AnswersGiven a binary tree, find the closest LEAF node to the target.
- aonecoding in United States| Report Duplicate | Flag | PURGE
Amazon Software Engineer - 7of 7 votes
AnswersGive an array A of n integers where 1 <= a[i] <= K.
- aonecoding in United States
Find out the length of the shortest sequence that can be constructed out of numbers 1, 2, .. k that is NOT a subsequence of A.
eg. A = [4, 2, 1, 2, 3, 3, 2, 4, 1], K = 4
All single digits appears. Each of the 16 double digit sequences, (1,1), (1, 2), (1, 3), (1, 4), (2, 1), (2, 2) ... appears. Because (1, 1, 2) doesn't appear, return 3.| Report Duplicate | Flag | PURGE
Google Solutions Engineer - 1of 1 vote
AnswerGiven an undirected graph represented as a list of edges, find out the number of connected component.
- aonecoding in United States| Report Duplicate | Flag | PURGE
Twitter Software Engineer - 2of 2 votes
AnswersGive m balls and n bins. Find out how many ways to assign balls to bins. Notice the buckets has no order. Like (1,2,3) and (3,2,1) are considered the same.
- aonecoding in United States
eg, m = 3, n = 2, return 2. (1, 2) and (3, 0)| Report Duplicate | Flag | PURGE
Amazon Software Developer - 2of 2 votes
AnswersGive an positive integer n, find out the smallest integer m, such that all digits in m multiply equals to n. For example, n = 36, return 49. n = 72, return 89. You can assume there is no overflow.
- aonecoding in United States| Report Duplicate | Flag | PURGE
Microsoft Software Engineer - 2of 2 votes
AnswersYahoo Sunnyvale onsite
- aonecoding in United States
A string s3 consists of multiple repetitions of s1.
Given s1 and another string s2, find if s2 is a substring of s3.
s3 = s1 + s1 + … + s1 = n * s1, where n is a positive integer 0.
For example
s1 = “aabc”, s2 = “caa” => true
s1 = “aabc”, s2 = “cab” => false
s1 = “aabc”, s2 = “caabcaa” => true| Report Duplicate | Flag | PURGE
Yahoo Software Engineer Algorithm - 5of 5 votes
AnswersCongrats on aonecode member A.P. for signing the offer with FB! Thanks for sharing the experience with us.
- aonecoding in United States
phone:
postorder tree traversal recursive -> iterative
add two binary number
on-site:
1 ring buffer
2 merge intervals
3 Leetcode alien dictionary
4.sort list of words| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
AnswersAirbnb: Design webbrowser back button
- aonecoding in United States
Your web browser supports will support three actions: back, forward and open. The init webpage is “about:blank”.
Given a sequence of commands. Return the result page.| Report Duplicate | Flag | PURGE
Airbnb Software Engineer Algorithm - 2of 2 votes
AnswersApril Google Interview 3/4
- aonecoding in Korea
Maze
N,M array
Level 1 0,0 to N-1,M-1 => Path exsits?
Level 2 if path exists then print path
Level 3 if path exists then print min cost path
Level 4 O(nm log mn) using Priority Queue.| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 6of 6 votes
AnswersFB On-site 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 | PURGE
Facebook Software Engineer Algorithm - 2of 2 votes
AnswersDropbox
- 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 | PURGE
Dropbox Software Engineer Algorithm - 2of 2 votes
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 | PURGE
Facebook Software Engineer Algorithm - 4of 4 votes
AnswersFeb On-site Google
- aonecoding in United States
DP Problem. Given the length and width of a matrix, get the number of paths from bottom-left to bottom right.
You may only walk into those 3 directions ➡ (right) ↗ (upper-right) ↘ (lower-right) at each point.
Follow-up: optimize 2d DP to 1d DP of linear extra space.
Follow-up: 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 | PURGE
Google Software Engineer Algorithm - 3of 3 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 | PURGE
Uber Software Engineer Algorithm - 2of 2 votes
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% ;
Follow-up:
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 | PURGE
Google Software Engineer Algorithm - 3of 3 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 | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersDesign 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);
Follow-up:
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 | PURGE
Dropbox Software Engineer Algorithm - 2of 4 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 | PURGE
Google Software Engineer Algorithm - 3of 3 votes
Answers/**
- aonecoding in United States
* Google
* Given a list of non-negative 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 | PURGE
Google Software Engineer Algorithm - 2of 2 votes
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 | PURGE
Twitter Software Engineer Algorithm - 3of 3 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 top-tier 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 | PURGE
Dropbox Software Engineer - 3of 3 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 ONE-TO-ONE 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 top-tier companies after weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!| Report Duplicate | Flag | PURGE
Microsoft Software Engineer Algorithm - 2of 4 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 pre-processing the dictionary. Key: letter; Value: frequency. Begin with combinations of most frequent letters first)| Report Duplicate | Flag | PURGE
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 | PURGE
Linkedin Software Engineer Algorithm - 2of 2 votes
AnswerFacebook
- aonecoding in United States
-Phone: LC304 & longest arithmetic sequence. Return the sequence.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 4of 4 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 | PURGE
Wish Solutions Engineer Algorithm - 2of 2 votes
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 non-repetitive 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 | PURGE
Airbnb 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。
Follow-up:
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 | PURGE
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 | PURGE
Google 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://s3-us-west-2.amazonaws.com/aonecode/techblog/50cfcdd1d61f1bd6002cf4d3b4a61deb-min.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 | PURGE
Twitter Software Engineer SQL - 0of 0 votes
AnswersI. Closest K nodes to a target in BST? (Do it in O(n)?)
- aonecoding in United States
II. Nested List sum?| Report Duplicate | Flag | PURGE
Linkedin Software Engineer Algorithm - 0of 0 votes
AnswerSolve the 24 Game
- aonecoding in United States| Report Duplicate | Flag | PURGE
Twitter Software Engineer Algorithm - 3of 3 votes
AnswersRound4
- aonecoding in United States
Starting from num = 0, add 2^i (where i can be any non-negative 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 | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersRound1
- aonecoding in United States
Find if two people in a family tree are blood-related.
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 | PURGE
Google 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].)
Follow-up:
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 | PURGE
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 | PURGE
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.
Follow-up:
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 | PURGE
Google Software Engineer Algorithm - 2of 2 votes
AnswersGoogle on-site 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).
Follow-up: Given multiple non-overlapped rectangles on the 2D grid, uniformly select a random point from the rectangles.| Report Duplicate | Flag | PURGE
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).
Follow-up: If primeSum(N) is frequently called, how to optimize it.
II. OODesign Parking Lot| Report Duplicate | Flag | PURGE
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 non-negative.
Implement query(i, j).
2. Flatten nested linked list
3. POI search design
4. LC238 & LC279| Report Duplicate | Flag | PURGE
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 | PURGE
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.
Follow-up: What if the log comes from a data stream.
Follow-up: If the machine has 4GB RAM, is there going to be a problem?| Report Duplicate | Flag | PURGE
Apple Backend Developer Algorithm - 2of 2 votes
Answers4/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 | PURGE
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. Follow-up: Optimize the solution.| Report Duplicate | Flag | PURGE
Uber Software Engineer Algorithm - 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 | PURGE
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 | PURGE
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 | PURGE
Facebook Software Engineer Algorithm - 3of 3 votes
Answers1 year exp. Interviewed at Cambridge, MA
- aonecoding in United States
Round1
LC304. Follow-up: 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.
Follow-up: decode with utf-16. 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 | PURGE
Google Software Engineer Algorithm - 3of 3 votes
AnswersGoogle full-time 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 | PURGE
Google Software Engineer Algorithm - 5of 5 votes
AnswersGoogle On-site 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.
Follow-up
In addition, implement
void multiply_to_all(int x)
The same required to run in O(1) time| Report Duplicate | Flag | PURGE
Google Software Engineer Algorithm - 1of 1 vote
AnswersImplement circular buffer with read & write functions
- aonecoding in United States| Report Duplicate | Flag | PURGE
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, non-distributed 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 | PURGE
Facebook Software Engineer - 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 | PURGE
Google SDE1 Algorithm - 2of 2 votes
AnswersApple On-site 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 co-existed 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 | PURGE
Apple SDE-3 design - 1of 1 vote
AnswersApple On-site 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 | PURGE
Apple SDE-3 Algorithm - 1of 1 vote
AnswersApple On-site 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 | PURGE
Apple SDE-3 Algorithm - -1of 3 votes
AnswersAmazon SDE 2 On-site (4 of 4 Rounds)
- aonecoding in United States
Assume that there is an e-book 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 | PURGE
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 | PURGE
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 Challenge-qpan.
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 | PURGE
VMWare Inc Software Engineer Algorithm - 7of 7 votes
AnswersFacebook Senior Engineer On-site 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 + component-wise design on download manager| Report Duplicate | Flag | PURGE
Facebook Software Engineer Algorithm - 6of 6 votes
Answers5th Round
- aonecoding in United States
Open-ended 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 | PURGE
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
Follow-up 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 | PURGE
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]
Follow-up:
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 single-pass(go through each array only once)?| Report Duplicate | Flag | PURGE
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
Follow-up:
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 | PURGE
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
Follow-up:
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 | PURGE
Google Software Engineer Algorithm - 0of 6 votes
AnswersCreate an iterator class that stores a list of the built-in 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 | PURGE
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 non-overlap 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 | PURGE
Facebook 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 | PURGE
Facebook Software Engineer Algorithm - 6of 6 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 | PURGE
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 | PURGE
Google Software Engineer Algorithm - 6of 6 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 | PURGE
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 | PURGE
Uber Software Engineer Algorithm - 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 | PURGE
Google Software Engineer Algorithm
- 1 Answer 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 | PURGE - 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 | PURGE
public class MultiplicationQueries {
int[] array;
int[] zeroToLeft;
int[] product;
public MultiplicationQueries(int[] a) {
array = a;
if(array.length > 0) {
zeroToLeft = new int[array.length];
product = new int[array.length];
zeroToLeft[0] = array[0] == 0 ? 0: -1;
product[0] = array[0] == 0 ? 0: array[0];
}
for(int i = 1; i < array.length; i++) {
zeroToLeft[i] = array[i] == 0 ? i: zeroToLeft[i - 1];
product[i] = array[i] == 0 ? 0: array[i - 1] == 0 ? array[i]: array[i] * product[i - 1];
}
}
public int query(int i, int j) {
if(i > j || i >= array.length || j >= array.length || i < 0 || j < 0) return -1;
if(i == j) return array[i];
return zeroToLeft[j] >= i ? 0: (i == 0 || array[i - 1] == 0) ? product[j]: product[j] / product[i - 1];
}
}
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
Since query(i, j) gets frequently called, it should run as fast as possible, ideally in O(1) time.
I. When there is 0 between i and j, the query returns 0.
To quickly find out 0 between i and j, initial another array to keep track of at the current index i, where is the closest 0 to the left of i (including i).
II. To get the product of any given range without zero in between, build an array of cumulative products from the first positive number in the non-zero part up to current idx i. So that if there is no zero in between, query(i, j) equals to product[j] / product[i - 1] (O(1) time).
e.g. For A = [2, 2, 3, 4, 0, 4, 5, 6]
product array P = [2, 4, 12, 48 ,0, 4, 20 ,120]
query(1, 3) = P[3] / P[1 - 1] = 48 / 2 = 24
Remember to discuss with the interviewer if the product can get integer overflow
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!
Any routing algorithm will solve this problem, such as BFS Dijrsktra's etc.
It's still a challenging problem under the time limit in an interview since it involves first parsing the input string into a graph structure and then run the routing algorithm.
public int minCost(String flights, String from, String to, int k) {
if(from == to) return 0;
if(flights.isEmpty()) return -1;
int[][] edges = parseString(flights,from, to);
Map<Integer, Integer> minCostSet = new HashMap<>();
minCostSet.put(0, 0);
Queue<Integer> prev = new ArrayDeque<>(); //previous level of nodes
prev.add(0);
while(k >= 0 && !prev.isEmpty()) { //BFS
Queue<Integer> current = new ArrayDeque<>();
for(int source: prev) {
for(int destination = 0; destination < edges.length; destination++) {
if(edges[source][destination] > 0) {
int minCost = minCostSet.containsKey(destination) ? minCostSet.get(destination) : Integer.MAX_VALUE;
int newCost = Math.min(minCost, minCostSet.get(source) + edges[source][destination]);
if (minCost > newCost) {
minCostSet.put(destination, newCost);
current.add(destination);
}
}
}
}
prev = current;
k--;
}
return minCostSet.containsKey(edges.length - 1) ? minCostSet.get(edges.length - 1): -1;
}
private int[][] parseString(String flights, String start, String end) {
Map<String, Integer> map = new HashMap<>();
List<int[]> edges = new ArrayList<>();
String[] f = flights.split(",");
map.put(start, 0);
map.put(end, -1);
for(int i = 0; i < f.length; i+=2) {
int idx = f[i].indexOf('-');
String src = f[i].substring(0, idx);
String des = f[i].substring(idx + 2);
if(!map.containsKey(src)) {
map.put(src, map.size() - 1);
}
if(!map.containsKey(des)){
map.put(des, map.size() - 1);
}
if(map.get(src) != -1) { //exclude flights that departs from the ultimate destination
edges.add(new int[]{map.get(src), map.get(des), Integer.parseInt(f[i + 1])});
}
}
int n = map.size();
int[][] graph = new int[n][n];
for(int[] edge: edges) {
if(edge[1] == -1) edge[1] = n - 1;
graph[edge[0]][edge[1]] = edge[2];
}
return graph;
}
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 Round 4
//input a 4X13 matrix with 4 suits and 13 ranks of cards. set cards[suit][rank] to 1 if this card in hand.
public static boolean handClear(int[][] cards, int hand) {
if(hand == 0) return true;
for(int rank = 12; rank >= 0; rank--) {
for(int suit = 0; suit < 4; suit++) {
if(cards[suit][rank] == 1) { //if cards[suit][rank] in hand
cards[suit][rank] = 0; hand--;
int smallerRank = rank == 0 ? 12: rank - 1; // look for straight flush that end with this card
// watch for Ace as a special case that ***QKA and A23*** both valid
if(cards[suit][smallerRank] == 1) {
cards[suit][smallerRank] = 0; hand--;
int r = smallerRank - 1;
for(; r >= 0 && cards[suit][r] == 1; r--) { //try playing the straight flush found
cards[suit][r] = 0; hand--;
if(handClear(cards, hand)) return true;
}
r++;
for(; r <= smallerRank; r++) { //backtrack if play did not work
cards[suit][r] = 1; hand++;
}
}
//look for 3/4 of a kind for cards[suit][rand]
int n = cards[0][rank] + cards[1][rank] + cards[2][rank] + cards[3][rank];
if(n == 3 || n == 2) {
int tmp1 = cards[(suit + 1) % 4][rank],
tmp2 = cards[(suit + 2) % 4][rank],
tmp3 = cards[(suit + 3) % 4][rank];
cards[(suit + 1) % 4][rank] = 0; //try playing the 3/4 of a kind
cards[(suit + 2) % 4][rank] = 0;
cards[(suit + 3) % 4][rank] = 0;
hand -= n;
if(handClear(cards, hand)) return true;
cards[(suit + 1) % 4][rank] = tmp1; //backtrack if play did not work
cards[(suit + 2) % 4][rank] = tmp2;
cards[(suit + 3) % 4][rank] = tmp3;
hand += n;
}
cards[suit][rank] = 1; hand++;
}
}
}
return false;
}
Looking for interview experience sharing and mentor?
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 Code),
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
For the first problem a hash set of {IPs} may simply solve it.
However in the follow-ups as the amount of data cumulates, if the IPs are stored as strings, 4GB is becomes absolutely insufficient, since there are over 4 billion IPs out there and each ip as a string takes at least 9 bytes.
Even if convert ip to integer(8B), it wouldn't be enough.
An approach is to go with bit set. Then each ip takes only 1 bit. Have a bit set to store whether an ip occurs and another set to store whether an ip repeats.
This takes 2 * 2^32 bit = ~1GB -> fits in RAM.
public class IPFilter {
long[] map; //mark all ip that showed up
long[] repeatedIP; //mark all ips that repeatedly showed up
public IPFilter() {
//there's 2^32 IP in total.
// each long integer is identifies 64 IPs.
// Need 2^32 / 2^6 long integers in the bit map
int size = 1 << (32 - 6);
map = new long[size];
repeatedIP = new long[size];
}
public void addToMap(List<String> IPs) {
for(String ip: IPs) {
long decimal = IPToLong(ip);
int idx = (int)(decimal / 64);
int res = (int)(decimal % 64);
if((map[idx] >> res) == 1) { //repeated ip
repeatedIP[idx] |= (1 << res);
} else { //first occurred ip
map[idx] |= (1 << res);
}
}
}
private long IPToLong(String ipAddress) { //convert ip (base 256) to decimal
String[] ipAddressInArray = ipAddress.split("\\.");
long result = 0;
for (int i = 0; i < ipAddressInArray.length; i++) {
int power = 3 - i;
int ip = Integer.parseInt(ipAddressInArray[i]);
result += ip * Math.pow(256, power);
}
return result;
}
}
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 2/5: The number of minutes in a day is constant. Create an array of size 60*24 minutes in a day. Mark true on meeting schedules.
public boolean meetingOverlap(int[][] meetings) {
boolean[] schedule = new boolean[24 * 60];
for(int[] time:meetings) {
for(int i = time[0]; i <= time[1]; i++) {
if(schedule[i]) return true;
schedule[i] = true;
}
}
return false;
}
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!
4/5 is a graph problem - similar to finding the number of connected components in graph.
DFS solution:
In this graph every node has at most 2 edges. Every position (x, y) has 2 nodes. If it's a '/' in (x, y) and current node is upper half of (x,y), the next two nodes to search is right half of (x - 1, y) and lower half of (x, y - 1).
Other than DFS, union find and BFS will work as well.
public int segmentCount(char[][] m) {
int len = m[0].length;
boolean[] upperHalf = new boolean[m.length * len];
boolean[] lowerHalf = new boolean[m.length * len];
int count = 0;
for(int i = 0; i < m.length; i++) {
for(int j = 0; j < len; j++) {
if(!upperHalf[i*len + j]) {
count++;
dfs(m, upperHalf, lowerHalf, i, j, 0);
}
if(!lowerHalf[i*len + j]) {
count++;
dfs(m, upperHalf, lowerHalf, i, j, 1);
}
}
}
return count;
}
//upper:0, lower:1, left:2, right:3
private void dfs(char[][] m, boolean[] upperHalf, boolean[] lowerHalf, int x, int y, int position) {
if(x < 0 || x == m.length || y == m[0].length || y < 0) {
return;
}
if((position == 2 && m[x][y] == '\\') || (position == 3 && m[x][y] == '/')) position = 1;
if((position == 2 && m[x][y] == '/') || position == 3 && m[x][y] == '\\') position = 0;
int id = x * m[0].length + y;
if((position == 0 && upperHalf[id]) || (position == 1 && lowerHalf[id])) { //if visited
return;
}
if(position == 0) upperHalf[id] = true;
else lowerHalf[id] = true;
if(position == 0 && m[x][y] == '\\') {
dfs(m, upperHalf, lowerHalf, x, y + 1, 2); //go right
dfs(m, upperHalf, lowerHalf, x - 1, y, 1); //go up
}
if(position == 0 && m[x][y] == '/') {
dfs(m, upperHalf, lowerHalf, x, y - 1, 3); //go left
dfs(m, upperHalf, lowerHalf, x - 1, y, 1); //go up
}
if(position == 1 && m[x][y] == '\\') {
dfs(m, upperHalf, lowerHalf, x, y - 1, 3); //go left
dfs(m, upperHalf, lowerHalf, x + 1, y, 0); //go down
}
if(position == 1 && m[x][y] == '/') {
dfs(m, upperHalf, lowerHalf, x, y + 1, 2); //go right
dfs(m, upperHalf, lowerHalf, x + 1, y, 0); //go down
}
}
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 targeting 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 boolean match(String str, String pattern) {
int occurLower = 0, occurUpper = 0;
char prev = '\0';
int i = 0, j = 0;
while(j < pattern.length()) {
char c = i == str.length() ? '\0': str.charAt(i);
if (occurUpper == 0 || prev == pattern.charAt(j) || (c != prev && occurLower <= 0)) {
String range = j + 1 < pattern.length() && pattern.charAt(j + 1) == '{' ?
pattern.substring(j + 2, pattern.indexOf('}', j + 2)): "";
int[] r = getRange(range);
occurLower = prev == pattern.charAt(j) ? occurLower + r[0] : r[0];
occurUpper = prev == pattern.charAt(j) ? occurUpper + r[1] : r[1];
prev = pattern.charAt(j);
j = range.isEmpty() ? j + 1: pattern.indexOf('}', j + 2) + 1;
}
if (c == prev) {
occurLower--;
occurUpper--;
i++;
} else if (occurLower > 0) {
return false;
}
}
while(i < str.length()) {
if(str.charAt(i) != prev || occurUpper == 0) return false;
else {
occurUpper--;
i++;
}
}
return true;
}
private int[] getRange(String b) {
if(b.isEmpty()) return new int[]{1,1};
int comma = b.indexOf(',');
return new int[]{
Integer.parseInt(b.substring(0, comma)),
Integer.parseInt(b.substring(comma + 1)) - 1
};
}
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
ONE TO ONE real-time coaching 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 4.1
public TreeNode solve(TreeNode root) {
TreeNode[] res = treetoDLL(root);
if(res == null) return null;
res[0].left = res[1]; //make linked list circular
res[1].right = res[0];
return res[0]; //return a node in the chain
}
public TreeNode[] treetoDLL(TreeNode root) { //recursion to create linked list in place
if(root == null) return null;
TreeNode[] prev = treetoDLL(root.left);
TreeNode[] next = treetoDLL(root.right);
TreeNode[] res = new TreeNode[] {root, root};
if(prev != null) {
prev[1].right = root;
root.left = prev[1];
res[0] = prev[0];
}
if(next != null) {
next[0].left = root;
root.right = next[0];
res[1] = next[1];
}
return res;
}
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
ONE TO ONE real-time coaching 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 static int divide(int dividend, int divisor) {
//if(divisor == 0) throw new Exception();
int sign = 1;
//figure out the sign of the result
if((dividend < 0 && divisor > 0)
|| (dividend > 0 && divisor < 0)) {
sign = -1;
}
if(dividend < 0) dividend = -dividend;
if(divisor < 0) divisor = -divisor;
int n = 1; //get the range of result [n, 2n], where n is doubled every round
while(dividend > (n << 1) * divisor) {
n <<= 1;
}
//now it's known that the result is between [n, 2n]
//so in the dividend has a sum of more than n and less than 2n divisors in total
//to figure out exactly how many divisors sum up to the dividend,
// break down the problem to result = n + divide(dividend - n * divisor, divisor)
// next round the dividend becomes (dividend - n * divisor) with n added to the result.
// proceed to figure out the range [x, 2x] of result for the new dividend, where x can be n/2, n/4, n/8...
// whenever the x is found, add x to the result and deduce x * divisor from the dividend
// util n is 0 or dividend is 0
//If written in math, the formula looks like dividend = ([T/F]* n + [T/F]* n/2 + [T/F]* n/ 4 + [T/F]* n/ 8...) * divisor
//The quotient will be ([T/F]* n + [T/F]* n/2 + [T/F]* n/ 4 + [T/F]* n/ 8...), [T/F] depends on (dividend - n * divisor) >= 0
int result = 0;
while(n > 0 && dividend > 0) {
if(dividend - n * divisor >= 0) {
dividend -= n * divisor;
result += n;
}
n >>= 1;
}
return result * sign;
}
Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
ONE TO ONE real-time coaching 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!
Candidate's solution to 1.1
int diameterOfBinaryTree(TreeNode* root) {
maxDown(root);
return maxLen;
}
int maxDown(TreeNode* r) {
if (!r) return 0;
int maxL = maxDown(r->left), maxR = maxDown(r->right);
maxLen = max(maxLen, maxL+maxR);
return max(maxL, maxR) + 1;
}
int maxLen = 0;
Solution to 1.2
public static List<int[]> maxOverlap(int[][] intervals) { //input [[start1, end1], [start2, end2]...]
int[] starts = new int[intervals.length];
int[] ends = new int[intervals.length];
for(int i=0; i<intervals.length; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
Arrays.sort(starts);
Arrays.sort(ends);
int rooms = 0;
int endsItr = 0;
int mark = 1;
for(int i=0; i<starts.length; i++) {
if (starts[i] < ends[endsItr]) {
rooms++;
mark = endsItr; //mark where the first max overlap zone appears
} else {
endsItr++;
}
}
List<int[]> points = new ArrayList<>(); //result
while(mark <= ends.length - rooms) {
if(ends[mark] > starts[mark + rooms - 1]) {
points.add(new int[]{starts[mark + rooms - 1], ends[mark]});
}
mark++;
}
//optional: convert non-overlap intervals in 'points' to collection of numbers if necessary
return points;
}
Solution to 1st Question in Round2 blog.csdn.net/taoqick/article/details/21814849
- aonecoding July 11, 2017Looking for interview experience sharing and coaching?
Visit A++ Coding Bootcamp at aonecode.com.
Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Simulating rain
Break down the 1 meter walkway to 100 centimeters. Originally the whole centimeter is dry
so left = 0, right=0.01(meter); When the rain drop falls between on centimeter i (covers 0.4 centimeters of i)and centimeter i+1( 0.6 centimeters of i + 1), push the right boundary of centimeter[i] to the left by centimeter[i].right - 0.004. Same thing push the left boundary of centimeter[i] + 1 to 0.006.
Whenever a centimeter gets to left >= right, increment the fully wet centimeter count (wetCnt) by 1. When wetCnt hits 100, the whole meter is covered in rain.
public class RainDrop {
static class Interval {
double left = 0, right = 0.01;
boolean isWet() {
return left >= right;
}
}
public static void main(String[] args) {
simulateRainDrop();
}
public static void simulateRainDrop() {
Interval[] sidewalk = new Interval[100];
for (int i = 0; i < 100; i++) {
sidewalk[i] = new Interval();
}
int cnt = 0, wetCnt = 0;
while (wetCnt < 100) {
++cnt;
double p = Math.random();
double left = p - 0.005;
double right = p + 0.005;
if (left >= 0) {
int idx = (int) (left / 0.01);
if (!sidewalk[idx].isWet()) {
double iright = left - idx * 0.01; //update seg[i].right with left bound of rain
if (iright < sidewalk[idx].right) {
sidewalk[idx].right = iright;
if (sidewalk[idx].isWet())
++wetCnt;
}
}
}
if (right <= 1) {
int idx = (int) (right / 0.01);
if (!sidewalk[idx].isWet()) {
double ileft = right - idx * 0.01;//update seg[i + 1].left with right bound of rain
if (ileft > sidewalk[idx].left) {
sidewalk[idx].left = ileft;
if (sidewalk[idx].isWet())
++wetCnt;
}
}
}
}
System.out.println(cnt);
}
}
Looking for interview experience sharing and coaching?
Visit A++ Coding Bootcamp at aonecode.com.
Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
Solution:
append and get are naturally done in constant time with ArrayList. To achieve add_to_all in constant time, have an extra variable 'addition' to store the added number. For any incoming number x to append, append(x - addition) instead. The get() method returns get(index) + addition.
Followup:
We could do the same thing for the multiply to all. keep track of the current multiplication factor and append the new number x by append(x / factor). However this brings the data type into double which is lousy.
A way around that is have another array divisor to keep track of the current factor when a new number x is appended at index i. Append x as it is. But later when x is requested, return x * factor / divisor.get(i).
Don't forget that every time the factor changes - such as when it doubles, the addition will be doubled as well.
import java.util.List;
import java.util.ArrayList;
public class Collection {
List<Integer> collection = new ArrayList<>();
List<Integer> divisors = new ArrayList<>();
int factor = 1;
int addition = 0;
public void append(int x) {
collection.add(x - addition);
divisors.add(factor);
}
public int get(int index) {
if(index >= collection.size()) throw new RuntimeException();
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) {
addition *= x;
factor *= x;
}
}
Looking for interview experience sharing and coaching?
Visit A++ Coding Bootcamp at aonecode.com.
Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
public class CircularBuffer<T> {
private T[] buffer;
private int tail;
private int head;
@SuppressWarnings("unchecked")
public CircularBuffer(int n) {
buffer = (T[]) new Object[n];
tail = 0;
head = 0;
}
public void add(T toAdd) {
if (head != (tail - 1)) {
buffer[head++] = toAdd;
} else {
//throw new BufferOverflowException();
}
head = head % buffer.length;
}
public T get() {
T t = null;
int adjTail = tail > head ? tail - buffer.length : tail;
if (adjTail < head) {
t = (T) buffer[tail++];
tail = tail % buffer.length;
} else {
//throw new BufferUnderflowException();
}
return t;
}
public String toString() {
return "CircularBuffer(size=" + buffer.length + ", head=" + head + ", tail=" + tail + ")";
}
}
Looking for interview experience sharing and coaching?
Visit A++ Coding Bootcamp at aonecode.com.
Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Feel free to email us aonecoding@gmail.com with any questions. Thanks!
public static int divide(int dividend, int divisor) {
if(divisor == 0) throw new RuntimeException();
int sign = 1;
//figure out the sign of the result
if((dividend < 0 && divisor > 0)
|| (dividend > 0 && divisor < 0)) {
sign = -1;
}
if(dividend < 0) dividend = -dividend;
if(divisor < 0) divisor = -divisor;
int n = 1; //get the range of result [n, 2n], where n is doubled every round
while(dividend > (n << 1) * divisor) {
n <<= 1;
}
//now it's known that the result is between [n, 2n]
//so in the dividend has a sum of more than n and less than 2n divisors in total
//to figure out exactly how many divisors sum up to the dividend,
// break down the problem to result = n + divide(dividend - n * divisor, divisor)
// next round the dividend becomes (dividend - n * divisor) with n added to the result.
// proceed to figure out the range [x, 2x] of result for the new dividend, where x can be n/2, n/4, n/8...
// whenever the x is found, add x to the result and deduce x * divisor from the dividend
// util n is 0 or dividend is 0
//If written in math, the formula looks like dividend = ([T/F]* n + [T/F]* n/2 + [T/F]* n/ 4 + [T/F]* n/ 8...) * divisor
//The quotient will be ([T/F]* n + [T/F]* n/2 + [T/F]* n/ 4 + [T/F]* n/ 8...), [T/F] depends on (dividend - n * divisor) >= 0
int result = 0;
while(n > 0 && dividend > 0) {
if(dividend - n * divisor >= 0) {
dividend -= n * divisor;
result += n;
}
n >>= 1;
}
return result * sign;
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy, String and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amz, Yahoo and other top companies after weeks of training.
Welcome to email us aonecoding@gmail.com with any questions. Thanks for reading.
Solution by the interviewee:
public int findBlockCount(List<Node> pointers, Node head)
{
HashMap<Node, Integer> map = new HashMap();
for(Node n:pointers)
{
map.put(n, 1);
}
int block = 0;
boolean newblock = true;
Node itr = head;
while(itr!=null)
{
if(map.containsKey(itr))
{
if(newblock)
{
block++;
newblock = false;
}
}else
{
newblock = true;
}
itr = itr->next;
}
return block;
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us aonecoding@gmail.com with any questions. Thanks for reading.
Backtracking for all the combinations to solve this problem.
public class StringToSingleChar {
public static void main(String[] args) {
StringToSingleChar t = new StringToSingleChar("ABACABB");
System.out.println(t.pathLen());
}
List<Character> str;
public StringToSingleChar(String s) {
str = new ArrayList<>();
for(char c: s.toCharArray()) {
str.add(c);
}
}
public int pathLen() {
if(str.size() == 0) return -1;
if(str.size() == 1) return 0;
if(invalidToConvert()) return -1;
for(int i = 0; i < str.size() - 1; i++) {
char curr = str.get(i), next = str.get(i + 1);
if(curr != next) {
//backtracking, try to convert any two adjacent chars in str
str.set(i, convert(curr, next));
str.remove(i + 1);
int steps = pathLen();
if(steps >= 0) return steps + 1;
//recover the str after the recursive calls
str.set(i, curr);
str.add(i + 1, next);
}
}
return -1;
}
//check if given string is invalid like "AAAAA..." or "BBBBB..." or "CCCCC..."
private boolean invalidToConvert() {
for(int i = 0; i < str.size() - 1; i++) {
if(str.get(i) != str.get(i + 1)) return false;
}
return true;
}
private char convert(char a, char b) {
if(a != 'C' && b != 'C') return 'C';
if(a != 'B' && b != 'B') return 'B';
return 'A';
}
}
def pow(x, n):
if n == 0:
return 1
neg = False
if n < 0:
neg = True
n = -n
pow = 1
while n > 1:
if n % 2 == 1:
pow *= x
n /= 2 # x^n = (x ^ 2) ^ (n / 2)
x *= x
return 1/(pow * x ) if neg else pow * x
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us aonecoding@gmail.com with any questions. Thanks for reading.
public int largestProduct3(int[] array) {
Arrays.sort(array);
int n = array.length;
int maxProduct;
//case> pick the last 3 numbers(when the array has only negative, or only positive numbers)
maxProduct = array[n - 1] * array[n - 2] * array[n - 3];
//case> pick 2 numbers from the left end and 1 number from the right end
maxProduct = Math.max(maxProduct, array[0] * array[1] * array[n - 1]);
return maxProduct;
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Given by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us aonecoding@gmail.com with any questions. Thanks for reading.
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greedy and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us aonecoding@gmail.com with any questions. Thanks!
public boolean validForSharing(List<SharedParagraph> sharedParagraphs, Book book) {
if(sharedParagraphs.isEmpty()) return true;
//sort sharedParagraphs
Collections.sort(sharedParagraphs, new Comparator<SharedParagraph>(){
public int compare(SharedParagraph i1, SharedParagraph i2){
if(i1.start!=i2.start)
return i1.start-i2.start;
else
return i1.end-i2.end;
}
});
SharedParagraph pre = sharedParagraphs.get(0);
int totalShared = 0, start = 0, end = 0;
for(int i=0; i<sharedParagraph.size(); i++){
SharedParagraph curr = sharedParagraphs.get(i);
if(curr.start >= end) {
totalShared += end - start;
start = curr.start;
end = curr.end;
} else {
end = Math.max(curr.end, end);
}
}
totalShared += end - start;
return result <= book.size() / 10;
}
Interviewer's solution to the 4th question
public int minUniqueSum(int[] A) {
int n = A.length;
int sum = A[0];
int prev = A[0];
for( int i = 1; i < n; i++ ) {
int curr = A[i];
if( prev >= curr ) {
curr = prev+1;
}
sum += curr;
prev = curr;
}
return sum;
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greed and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us aonecoding@gmail.com with any questions. Thanks for reading.
interviewer's solution to 1st problem
public class CreateBinarySearchTree {
private TreeNode root;
public CreateBinarySearchTree() {
}
//create a BST on order of elements in the array
public CreateBinarySearchTree(int[] a) {
this();
for (int i : a) {
add(i);
}
}
private static class TreeNode {
TreeNode left;
int item;
TreeNode right;
TreeNode(TreeNode left, int item, TreeNode right) {
this.left = left;
this.right = right;
this.item = item;
}
}
public void add(int item) {
if (root == null) {
root = new TreeNode(null, item, null);
return;
}
TreeNode node = root;
while (true) {
if (item < node.item) {
if (node.left == null) {
node.left = new TreeNode(null, item, null);
break;
}
node = node.left;
} else {
if (node.right == null) {
node.right = new TreeNode(null, item, null);
break;
}
node = node.right;
}
}
}
public String toString() {
return toString(root);
}
private String toString(TreeNode node) {
if (node == null) {
return null;
}
return "[" + toString(node.left) + "," + node.item + "," + toString(node.right) + "]";
}
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greed and other advanced algo problems),
and mock interviews.
Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us aonecoding@gmail.com with any questions. Thanks for reading.
Hi Nidhi,
Thanks for the inquiry. A few of our mentors are experienced backend data engineers. They can definitely guide you on the data architecture/warehousing area of the interviews. Please feel free to write to us aonecoding@gmail.com with any further questions.
Thanks!
All the algo questions were seen except the Random Max Index. Optimal solution is O(n) in time (single pass)and constant extra space.
Generate random max index
Given an array of integers, randomly return an index of the maximum value seen by far.
e.g.
Given [11,30,2,30,30,30,6,2,62, 62]
Having iterated up to the at element index 5 (where the last 30 is), randomly give an index among [1, 3, 4, 5] which are indices of 30 - the max value by far. Each index should have a ¼ chance to get picked.
Having iterated through the entire array, randomly give an index between 8 and 9 which are indices of the max value 62.
Solution:
public void sampleIdx(int[] array){
if(array == null || array.length == 0){
return;
}
Random rnd = new Random();
int res = 0, max = Integer.MIN_VALUE, count = 0;
for(int i = 0; i < array.length; i++){
if(max < array[i]){
max = array[i];
res = i;
count = 1;
}else if(max == array[i]){
count++;
int idx = rnd.nextInt(count); //(0, k - 1)
if(idx == 0){
res = i;
System.out.print(“A max value index up to the ”+i +”th element is ” + res;
);
}
}
}
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greed and other advanced algo problems),
and mock interviews.
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. Thanks for reading.
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
Taught by experienced engineers/interviewers from FB, Google and Uber,
our ONE TO ONE courses cover everything in an interview including
latest interview questions sorted by companies,
SYSTEM DESIGN Courses (highly recommended for people interviewing with FLAG)
ALGORITHMS (conquer DP, Graph, Greed and other advanced algo problems),
and mock interviews.
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. Thanks for reading.
Interviewee's solution
#include <iostream>
#include <vector>
using namespace std;
void printLargerSmaller(const vector<int> &v) {
int n = v.size();
vector<int>leftMax(n, INT_MIN);
for(int i=1;i<n; ++i) leftMax = max(leftMax[i-1], v[i-1]);
int rightMin =INT_MAX;
for(int i=n-1;i>=0; i--) {
if(i<n-1)rightMin = min(rightMin, v[i+1]);
if(v >leftMax && v < rightMin) cout << v << " ";
}
}
int main() {
vector<int>v = {3,4,7,1,8,12};
printLargerSmaller(v);
return 0;
}
Looking for interview experience sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com.
We provide ONE TO ONE courses that cover everything in an interview including
the latest interview questions categorized by companies,
algorithms,
SYSTEM DESIGN Courses(highly recommended for people interviewing with FLAG)
and 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. Thanks for reading.
Interviewee's solution:
#include <iostream>
#include <string>
#include <vector>
using namespace std;
long factorial(long n){
long fact = 1;
for (long i = 1; i<= n; ++i)
fact *= i;
return fact;
}
void DFS(const string &s1, int m, int i,
const string&s2, int n, int j,
string path,vector<string> &ret){
if(i==m &&j==n) {
ret.push_back(path);
return;
}
if(i < m) DFS(s1, m, i+1, s2, n, j, path+s1, ret);
if(j < n) DFS(s1, m, i, s2, n, j+1, path+s2[j], ret);
}
vector<string> combineTowStrings(const string &s1,const string &s2) {
int m =s1.length(), n = s2.length();
long count =factorial(m+n)/factorial(n)/factorial(m);
cout <<"count:" << count << endl;
vector<string> ret;
DFS(s1, m, 0, s2,n, 0, "", ret);
return ret;
}
int main() {
vector<string> ret = combineTowStrings("AB","CDF");
cout <<ret.size() << endl;
for(string &s: ret) cout << s << endl;
return 0;
}
Looking for interview questions sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding,
algorithms,
system design
and 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. Thanks for reading.
Solution:
Iterate through the two lists twice. First time get the difference in length. Second time get the sum at every digit (allow a node to have 2 digits). And then iterate through the new result array once to deal with the carry.
public ListNode add(ListNode head1, ListNode head2) {
if(head1 == null || head2 == null) {
return head1 == null? head2: head1;
}
int diff = 0; //get the difference in lengths of the two lists
ListNode p1 = head1, p2 = head2;
while(p1 != null && p2 != null) {
p1 = p1.next;
p2 = p2.next;
}
ListNode longer = p1 == null? head2: head1;
ListNode shorter = p1 == null? head1: head2;
while(p1 != null) {
p1 = p1.next;
diff++;
}
while(p2 != null) {
p2 = p2.next;
diff++;
}
ListNode dump = new ListNode(0); //create a dummy head for the result list
ListNode curr= dump;
while(diff > 0) { //create the longer part of the longer list
diff--;
curr.next = new ListNode(longer.val);
longer = longer.next;
curr = curr.next;
}
while(longer != null) { //add the two lists
curr.next = new ListNode(longer.val + shorter.val);
curr = curr.next;
longer = longer.next;
shorter = shorter.next;
}
curr = dump;
ListNode carry = dump;
while(curr != null) { //carry always points at the number smaller than 9
if(curr.val < 9) { //when a carry is found at current node, add 1 to carry and change anything after carry and before curr to 0
carry = curr;
} else if(curr.val > 9){
carry.val++;
carry = carry.next;
while(carry != curr) {
carry.val = 0;
carry = carry.next;
}
curr.val %= 10;
}
curr = curr.next;
}
return dump.val == 0 ? dump.next: dump;
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
If the array is sorted, simply run a binary search of log(n) time.
Otherwise, the best run time has to be linear.
Sum Solution (might get integer overflow):
1) Get the sum of all numbers n * (n + 1) / 2
2) Subtract all the numbers in array from sum and you will get the missing number.
int getMissingNo (int a[], int n)
{
int i, total;
total = (n+1)*(n+2)/2;
for ( i = 0; i< n; i++)
total -= a[i];
return total;
}
Bit Manipulation Solution:
1) XOR all the array elements, let the result of XOR be X1.
2) XOR all numbers from 1 to n, let XOR be X2.
3) XOR of X1 and X2 gives the missing number.
int getMissingNo(int a[], int n)
{
int i;
int x1 = a[0];
int x2 = 1;
for (i = 1; i< n; i++)
x1 = x1^a[i];
for ( i = 2; i <= n+1; i++)
x2 = x2^i;
return (x1^x2);
}
Trivial solution in linear time.
Optimal solution - since the array is sorted, find the numbers that occur at index n/4, 2n/4, 3n/4 and binary search for the left and right boundaries of the numbers. if rightBound - leftBound > n/4 then the number shows up more than n/4 times.
public void findNums(int[] array) {
if(array.length == 0) return;
int[] factors = new int[] {1, 2, 3}; //search for the left and right bound on the numbers that show up at index n/4, n/2 and 3n/4;
int N = array.length;
int number = array[0] - 1;
for(int factor: factors) {
int current = array[N * factor / 4];
if(number == current) continue;
int leftBound = binarySearch(array, N * (factor - 1) / 4, N * factor / 4, current, -1);
int rightBound = binarySearch(array, N * factor / 4, N - 1, current, 1);
if(rightBound - leftBound >= N / 4) {
number = current;
System.out.print(current + " ");
}
}
}
int binarySearch(int[] array, int start, int end, int num, int direction) {
if(start > end) {
return -1;
}
while(start <= end) {
int mid = (start + end) / 2;
if(array[mid] == num) {
if(mid + direction < 0 || mid + direction > end) {
return mid;
}
if(direction < 0) {
if(array[mid - 1] != num) {
return mid;
}
end = mid - 1;
} else {
if (array[mid + 1] != num) {
return mid;
}
start = mid + 1;
}
} else {
if(direction < 0) {
start = mid + 1;
} else {
end = mid - 1;
}
}
}
return -1;
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
This is a recent LinkedIn on-site question. It's a variant of another question that many have come across before - randomly select a linked list node based on the weights.
The open and follow-up questions are super trivial. Only the extra requirement takes a little probability trick.
public Integer random(int[] array, int[] freq) {
int totalFreq = 0;
Integer selected = null;
Random rand = new Random();
for(int i = 0; i < array.length; i++) {
int r = rand.nextInt() * (totalFreq + freq[i]);
if(r >= totalFreq) {
selected = array[i];
totalFreq += freq[i];
}
}
return selected;
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
For a record to be rewardable, 'A' cannot show up more than once.
So we ignore 'A' at the place and consider only the combination and arrangement for 'O' and 'L'.
We create a 2D array arr[i][j] where arr[i][0] is the number of strings with length i and ending letter 'O'; arr[i][1] is the number of strings with length i and ending letter 'L'
int count(int n) {
int[][] arr = new int[n+1][2];
arr[0] = new int[]{0, 1};
arr[1] = new int[]{1, 1};
for (int i = 2; i <= n; i++) {
arr[i % 2][0] = arr[(i-1) % 2][0] + arr[(i-1) % 2][1]; // the ith letter is O
arr[i % 2][1] = arr[(i-1) % 2][0] + arr[(i-2) % 2][0]; // the ith letter is L
}
int opt = arr[n][0] + arr[n][1]; // case when there is no "A"
for (int i = 0; i < n; i++) { // consider all the cases with one A, there are i letters to the left of A and n-i-1 letter to the right of A
opt += ( arr[i][0] + arr[i][1] ) * ( arr[n-i-1][0] + arr[n-i-1][1] );
}
return opt;
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
public class RoundRobinIterator {
List<Iterator> iterators;
int index; //current element
int size;
public RoundRobinIterator(List<Iterator> iter) {
iterators = iter;
size = iterators.size();
index = 0;
if(size > 0) locateNext();
}
public Object next() {
locateNext();
if(size == 0) return null;
return iterators.get(index).next();
}
public boolean hasNext() { // tradeoff - O(1) or O(n) ?
if(size == 0) return false;
return true;
}
private void locateNext() {
if(iterators.get(index).hasNext()) {
index = (index + 1) % size;
}
while(size > 0 && !iterators.get(index).hasNext()) {
Iterator tmp = iterators.get(index);
iterators.set(index, iterators.get(size - 1));
iterators.set(size - 1, tmp);
size--;
if(index == size) index = 0;
}
}
}
public class RoundRobinIterator {
List<Iterator> iterators;
int index; //current element
int size;
public RoundRobinIterator(List<Iterator> iter) {
iterators = iter;
size = iterators.size();
index = 0;
if(size > 0) locateNext();
}
public Object next() {
locateNext();
if(size == 0) return null;
return iterators.get(index).next();
}
public boolean hasNext() { // tradeoff - O(1) or O(n) ?
if(size == 0) return false;
return true;
}
private void locateNext() {
if(iterators.get(index).hasNext()) {
index = (index + 1) % size;
}
while(size > 0 && !iterators.get(index).hasNext()) {
Iterator tmp = iterators.get(index);
iterators.set(index, iterators.get(size - 1));
iterators.set(size - 1, tmp);
size--;
if(index == size) index = 0;
}
}
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
def maxWeightMeetingSchedule(meetings):
meetings.sort(key = lambda x: x.endTime)
maxWeight = [0] * (len(meetings) + 1)
for k in range(1, len(maxWeight)):
j = k - 1
while j >= 0 and meetings[j].endTime > meetings[k - 1].startTime:
j = j - 1
case1 = meetings[k - 1].weight + maxWeight[j + 1] #attend meeting k
case2 = maxWeight[k - 1] # not attend meeting k
maxWeight[k] = max(case1, case2)
return maxWeight[len(meetings)]
Sorting-free optimal solution. O(n) time. Use a priority queue to solve the problem. Perfectly dealt with the cases when at rank 10 there are multiple cities with the same number of orders.
import java.util.*;
class CityOrder {
private String city;
int orderCount;
public CityOrder(String city) {
this.city = city;
orderCount = 1;
}
}
public class TopNOrderCities {
private PriorityQueue<CityOrder> topN = new PriorityQueue<>((o1, o2) -> (o1.orderCount - o2.orderCount)); //keep top n cities with most orders in here
private Set<CityOrder> minOrderInTopNCities = new HashSet<>();
private Map<String, CityOrder> cityOrderMap = new HashMap<>();
public TopNOrderCities(int n, String[] orders) {
for(String city: orders) {
CityOrder cityOrder;
if(!cityOrderMap.containsKey(city)) {
cityOrder = new CityOrder(city);
cityOrderMap.put(city, cityOrder);
if(topN.size() < n) {
topN.add(cityOrder);
cityOrderMap.put(city, cityOrder);
} else if(topN.peek().orderCount == 1) {
minOrderInTopNCities.add(cityOrder);
}
} else {
cityOrder = cityOrderMap.get(city);
}
CityOrder min = topN.peek();
if(cityOrder.orderCount == min.orderCount) {
minOrderInTopNCities.add(cityOrder);
} else if(cityOrder.orderCount == min.orderCount + 1) {
if(minOrderInTopNCities.contains(cityOrder)) {
minOrderInTopNCities.remove(cityOrder);
topN.add(cityOrder);
}
CityOrder temp;
if(topN.size() == n + 1) {
temp = topN.poll();
if(topN.peek().orderCount == cityOrder.orderCount) {
minOrderInTopNCities = new HashSet<>();
} else {
minOrderInTopNCities.add(temp);
}
}
if(topN.peek().orderCount == cityOrder.orderCount) {
minOrderInTopNCities = new HashSet<>();
}
min = topN.poll();
if(cityOrder.orderCount == topN.peek().orderCount && minOrderInTopNCities.contains(cityOrder)) {
minOrderInTopNCities.remove(cityOrder);
topN.add(cityOrder);
}
}
}
}
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
Concise Backtracking Solution (Depth First Search)
Return -1 if there is no such subset.
public int lengthOfNSum(int[] array, int n) {
return lengthOfNSumRec(array, n, 0);
}
private int lengthOfNSumRec(int[] array, int n, int start) {
if(n < 0) {
return -1;
}
if(n == 0) {
return 0;
}
for(int i = start; i < array.length; i++) {
int len = lengthOfNSumRec(array, n - array[i], i + 1);
if(len >= 0) {
return len + 1;
}
}
return -1;
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
Looking for interview questions sharing and mentors?
Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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 aonecoding@gmail.com with any questions. Thanks for reading.
Solution:
This question is actually asking for implementation of a TRIE that keeps track of the frequency of terms.
The search() method will return all the words with the input prefix which takes a lot of time. You may adjust it according to the interviewer's demand so that perhaps only the top 10 frequent keywords get returned.
import java.util.List;
import java.util.ArrayList;
class TrieNode {
char letter;
TrieNode previousLetter;
TrieNode[] nextLetters;
int frequency;
boolean isEndOfWord;
public TrieNode(char letter, TrieNode previousLetter) {
this.letter = letter;
this.previousLetter = previousLetter;
}
}
class Trie {
private TrieNode root;
class WordFrequency{ //keeps track of the frequency to rank the words
String word;
int frequency;
WordFrequency(String w, int f) {
word = w;
frequency = f;
}
}
public Trie(int sizeCharSet) {
root = new TrieNode('&', null);
root.nextLetters = new TrieNode[sizeCharSet]; //sort by freq in descending order
}
public boolean insert(String word) { //if the word is new return true, else false;
TrieNode current = root;
current.frequency++; //root.frequency stores how many words in total are in the Trie
for(int i = 0; i < word.length(); i++) {
int letter = word.charAt(i) - 'a';
if(current.nextLetters[letter] == null) { //initialize children
current.nextLetters[letter] = new TrieNode(word.charAt(i), current);
}
current.nextLetters[letter].frequency++;
current = current.nextLetters[letter];
}
if(current.isEndOfWord) {
return false;
}
else {
return true;
}
}
public List<WordFrequency> search(String prefix) { //returns a list of words with the given prefix
List<WordFrequency> autoCompletion = new ArrayList<>();
TrieNode current = root;
for(char c: prefix.toCharArray()) {
if(current.nextLetters[c - 'a'] == null) {
return autoCompletion;
} else {
current = current.nextLetters[c - 'a'];
}
}
List<WordFrequency> surfix = new ArrayList<>();
depthFirstSearch(current, surfix, new StringBuilder());
for(WordFrequency wf: surfix) {
wf.word = prefix + wf.word;
autoCompletion.add(wf);
}
//you may rank the autoCompletion by frequency according to the requirement in the follow-up question
return autoCompletion;
}
private void depthFirstSearch(TrieNode current, List<WordFrequency> surfix, StringBuilder str) {
if(current == null) return;
str.append(current.letter);
if(current.isEndOfWord && str.length() > 0) surfix.add(new WordFrequency(str.toString(), current.frequency)); //word found
for(TrieNode nextLetter: current.nextLetters) {
depthFirstSearch(nextLetter, surfix, str);
}
str.deleteCharAt(str.length() - 1);
}
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
public static int mergeSegments(int[][] segments) {
if(segments.length == 0) return 0;
TreeMap<Integer, Integer> map = new TreeMap<>();
for(int[] s: segments) {
int start, end;
Integer sKey = map.floorKey(s[0]);
if(sKey == null || map.get(sKey) < s[0]) {
start = s[0];
end = s[1];
} else {
start = sKey;
end = Math.max(s[1], map.get(sKey));
}
Integer next = map.higherKey(start);
while(next != null && map.get(next) <= end) {
end = Math.max(map.get(next), end);
map.remove(next);
next = map.higherKey(next);
}
map.put(start, end);
}
int sum = 0;
for(Map.Entry<Integer, Integer> entry: map.entrySet()) {
sum += entry.getValue() - entry.getKey();
}
return sum;
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
This problem can be solved with TWO POINTERS that make a sliding window and a map to store occurrence of the distinct characters in the window.
public static String longestSubstringWithKDistinctChars(String s, int k) {
int left = 0, right = 0; //create a window for substring(left, right + 1)
Map<Character, Integer> distinctChars = new HashMap<>(); // store occurrence of chars in the window
String max = ""; // the output
while(right < s.length()) {
char c = s.charAt(right);
distinctChars.put(c, distinctChars.getOrDefault(c, 0) + 1);
right++;
if(distinctChars.size() == k) { //if window size == k, compare length of current substring with max
if(right - left + 1 > max.length()) {
max = s.substring(left, right + 1); //if current substring is longer, replace max with current
}
}
while(distinctChars.size() == k + 1) { //if window size > k, discard the char on the left
char toRemove = s.charAt(left);
if(distinctChars.get(toRemove) == 1) {
distinctChars.remove(toRemove);
} else {
distinctChars.put(toRemove, distinctChars.get(toRemove) - 1);
}
left++;
}
}
return max;
}
This solution assumes that we only keep substrings with exactly 5 characters. So if the input string has less than k distinct characters, the return is "".
- aonecoding February 04, 2017Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
Typical Dynamic Programming
public void printSums(int c1, int c2, int c3) {
Set<Integer> sums = new HashSet<>();
sums.add(0);
for(int sum = 1; sum <= 1000; sum++) {
if(sums.contains(sum - c1) || sums.contains(sum - c2) || sums.contains(sum - c3)) {
System.out.println(sum);
sums.add(sum);
}
}
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
public static List<String> comments(String codes) {
List<String> comments = new ArrayList<>();
if(codes == null) return comments;
int i = 0, n = codes.length();
while(i < n) {
char c = codes.charAt(i);
//ignore anything quoted
if(c == '\'' || c == '"') {
i++;
while(codes.charAt(i) != c) {
//when come across a "\\", escape the next char
if(codes.charAt(i) == '\\') i++;
i++;
}
}
// '/' is a sign for the start of a comment section
else if(c=='/'){
StringBuilder comment = new StringBuilder();
char type = codes.charAt(++i);
i++;
if(type == '*') {
// this type /* */ of comment,ends with "*/"
while(codes.charAt(i) != '*' || codes.charAt(i + 1) != '/') {
comment.append(codes.charAt(i));
i++;
}
} else {
// this type // of comment,end with "\\n" or when i == n (at the end of codes)
while (i < n && ( codes.charAt(i) != '\\' || i + 1 == n || codes.charAt(i + 1) != 'n')) {
char a = codes.charAt(i);
if(a == '\\') {
//corner case: "\\\\n"
//find a "\\" and if next char is not ‘n’, then escape next char
comment.append(codes.charAt(i + 1));
i++;
}
comment.append(a);
i++;
}
}
comments.add(comment.toString());
i++;
}
i++;
}
return comments;
}
This is a 'merge set' question. Given a graph, figure out which nodes belong to the same connected component and put them into a set.
Since the input comes in as an edge set, UNION FIND will be a good way to solve this.
Initially every node sources to itself. As we read the statement X = Y, we point the source of Y to the source of X so that they join the same set. After all connected components are sorted out. We check the unequal statements X != Y. If any of the X, Y pairs do share the same source, then X != Y contradicts with the equal statements.
public class CheckStatements {
public boolean validStatements(char[][] equal, char[][] unequal) {
int[] sets = new int[26];
for(int i = 0; i < 26; i++) {
sets[i] = i;
}
for(char[] pair: equal) {
mergeSets(sets, pair[0] - 'A', pair[1] - 'A');
}
for(int i = 0; i < 26; i++) {
findSrc(sets, i);
}
for(char[] pair: unequal) {
if(sets[pair[0] - 'A'] == sets[pair[1] - 'A']) return false;
}
return true;
}
private int findSrc(int[] sets, int i) {
int src = i;
while(src != sets[src]) {
src = sets[src];
}
int tmp;
while (i != sets[i]) {
tmp = sets[i];
sets[i] = src;
i = tmp;
}
return src;
}
private void mergeSets(int[] sets, int a, int b) {
int srcA = findSrc(sets, a);
int srcB = findSrc(sets, b);
sets[srcB] = srcA;
}
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
@ artur.ghandilyan :
Nope dude. The solution works with or without the character ',' in the strings. In fact the choice of SEPARATOR does NOT matter at all. Please read the code more carefully or at least provide one counter case.
Your method works exactly the same as mine, only with different parameter naming.
Replacing the while loop with find() won't make any difference other than shortening the code by one line.
Typical topological sort that can be solved with DFS
Assume packages are nodes like this:
public List<Integer> installPackages(List<Node> packages) {
if(packages == null || packages.isEmpty()) return new LinkedList<Integer>();
int n = packages.size();
int[] parentsCount = new int[n];
for(Node package: packages) {
for(Node child: package.children) {
parentsCount[child.label]++;
}
}
List<Integer> sequence = new LinkedList<>(); //output to return
for(Node package: packages) {
dfs(sequence, parentsCount, package);
}
return sequence;
}
private void dfs(List<Integer> sequence, int[] parentsCount, Node package) {
if(parentsCount[package.label] == 0) {
sequence.add(package.label); //install package
parentsCount[package.label] --;
for(Node child: package.children) {
parentsCount[child.label]-- ;
dfs(sequence, parentsCount, child);
}
}
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
public static int getPathLength(String s) {
String[] lines = s.split("\n");
int i = 0, len = s.length(), res = 0;
Stack<Integer> stack = new Stack<Integer>();
Stack<Boolean> added = new Stack<Boolean>();
stack.push(0);
added.push(true);
int prevSpaces = -1;
for(i = 0; i < len; i++) {
int spaces = lines[i].trim().length() - lines[i].length();
if(spaces < prevSpaces) {
while (spaces < prevSpaces) {
stack.pop();
added.pop();
prevSpaces--;
}
}
if(lines[i].contains(".")) {
if(isPic(lines[i]) && !added.peek()) {//0 , //true //prev = 1 ,sp = 0 //res = 4
res += stack.peek();
added.pop();
added.push(true);
}
} else {
if(spaces <= prevSpaces) {
stack.pop();
added.pop();
} else prevSpaces++;
stack.push(stack.peek() + lines[i].trim().length() + 1);
added.push(false);
}
}
return res;
}
public static boolean isPic(String f) {
String appendix = f.substring(f.length() - 4);
if(appendix.equals(".gif") || appendix.equals(".jpg") || appendix.equals(".png")) return true;
return false;
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
//encoding
static char SEPARATOR = ‘,’;
public static String serialize(List<String> strs) {
if(strs == null) return null;
StringBuilder ret = new StringBuilder();
for(String str: strs) {
ret.append(str.length());
ret.append(SEPARATOR);
ret.append(str);
}
return ret.toString();
}
//decoding
public static List<String> deserialize(String s) {
if(s == null) return null;
List<String> strs = new ArrayList<String>();
int i = 0, n = s.length();
while(i < n) {
int j = i;
while(s.charAt(j) != SEPARATOR) {
j++;
}
int len = Integer.parseInt(s.substring(i, j));
i = j + len + 1;
if(len == 0) strs.add(“”);
else strs.add(s.substring(j + 1, i));
}
return strs;
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
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.
@artur.ghandilyan:
Nope dude. The solution works with or without the character ',' in the strings. In fact the choice of SEPARATOR does NOT matter at all. Please read the code more carefully or at least provide one counter case.
Your method works exactly the same as mine, only with different parameter naming.
Replacing the while loop with find() won't make any difference other than shortening the code by one line.
Repinfo@strivashikaranupay.com, Associate at Adap.tv
Are you searching the strong and the most powerful Mantra for your husband? Consult our vashikaran specialist now. He provides ...
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 ...
Repracheljenkins771, #Green Grass Thing at None
Hello Everyone, My name is Rachel Jenkins, and I am a Hindi and English educator from London in the United ...
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 IIT-D
Are you facing love life and married life problem. Contact vashikaran specialist right now. He will guide your solution with ...
Rep
Repsherykasper, Accountant at A9
Bonjour, je travaille dans une entreprise en tant que caissier. J'habite à Maysville mais je suis en fait d ...
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? Pal-A-Roo’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. Pal-A-Roo’s Child Development Center is a family-owned 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 ...
RepHi, I am a Graphic designer from Madison. I have been working in cretor for the last 2 years. Before ...
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 ...
Repbilliejeckley, SEO at Flipkart
Spent 2002-2008 testing the market for spit-takes in Los Angeles, CA. Spent 2001-2004 deploying how to get boyfriend back by ...
Repmethali0001, Front-end 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 ...
Repmarybritt, Android Engineer at Centro
I am Mary from Wilmington. I am working as a Graphic Designer in Super Enterprises. I also write articles and ...
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 one-stop destination for all your home improvement and handyman needs.We take care of residential & commercial ...
Repsuganpdhchejara921, Problem Setter at TP
Are you facing love life and married life problem. Contact vashikaran specialist right now. He will guide your solution with ...
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!
I. At first find found all primes <= N (sieve of Eratosthenes). Getting the sum will be easy then.
Follow-up:
Cache the sums for any given N to save time. {N:SUM}
Optimization: Don't have to store sums for every N.
When N = 7, N = 8, N = 9, N = 10, the prime sum remains 17.
For N between 11 to 12, the prime sum is 28.
For N between 13 to 16, the sum is 41.
Use a BST structure as the cache. For N = 16, cache:
{2:3, 4:6, 6:11, 10:17, 12:28, 16:41}
For a given N, call cache.ceilingKey(N) to find the bucket for N.
N/log(n) * log(N)
Complexity
Time:
sieve of Eratosthenes takes O(NloglogN) time.
Insert an element into BST takes O(logN), there are N/logN primes in total to be added.
So building the cache takes logN * N / LogN = O(N) time
requesting primeSum(N) takes O(logN)
Space:
sieve of Eratosthenes takes O(N) extra space which will later be release after the cache is created.
Cache: O(N/logN)
- aonecoding July 28, 2017