aonecoding
 0of 0 votes
Answer4/5 Round at Uber
 aonecoding in United States
Coding: Given a 2D array of either '\' or '/', find out how many pieces this rectangle is divided into graphically.
For a 2X2 matrix with
/\
\/
The matrix split into 5 pieces  the diamond in middle and the four corners. Return 5 as the answer.
5/5 Round at Uber
Design Excel. Report Duplicate  Flag
Uber Software Engineer Algorithm  0of 0 votes
Answer2/5 Round at Uber
 aonecoding in United States
Bar raiser  Behavioral questions. Coding: Find if a set of meetings overlap. Meeting has a starttime and an endtime with accuracy to minute. All meetings take place in the same day. Do this in O(n) time.
3/5 Round at Uber
Coding: Subset sum. Followup: Optimize the solution. Report Duplicate  Flag
Uber Software Engineer Algorithm  0of 0 votes
Answers1/5 Round at Uber
 aonecoding in United States
Manager : Behavioral questions. Basic system design concepts. Publish/subscribe model. Discussion on Uber architecture. Report Duplicate  Flag
Uber Software Engineer System Design  1of 1 vote
AnswerUber
 aonecoding in United States
1. Mirror Binary Tree
2. String pattern matching
The matching should cover the entire input string (not partial).
The function prototype should be:
bool isMatch(String str, String pattern)
Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa","a{1,3}") → true
isMatch("aaa","a{1,3}") → false
isMatch("ab","a{1,3}b{1,3}") → true
isMatch("abc","a{1,3}b{1,3}c") → true
isMatch("abbc","a{1,3}b{1,2}c") → false
isMatch("acbac","a{1,3}b{1,3}c") → false
isMatch("abcc","a{1,3}b{1,3}cc{1,3}") → true
In pattern string, a char followed by {lower, upper} means that the char occur lower to upper(exclusive) times. e.g. a{1, 3} > a occurs 1 or 2 times. Report Duplicate  Flag
Uber Software Engineer Algorithm  2of 2 votes
Answer3.1 design: design fb inbox search —> just focus on the post
 aonecoding in United States
4.1 binary tree to circular double linked list.
4.2 two arrays, find the common elements of two sorted array. if one array is small, the other is very big. Report Duplicate  Flag
Facebook Software Engineer Algorithm  1of 1 vote
Answers2.1 career discussion
 aonecoding in United States
2.2 divide two numbers with no / or % Report Duplicate  Flag
Facebook Software Engineer Algorithm  2of 2 votes
Answers1/4 round of FB onsite interview, Master Degree, Hired
 aonecoding in United States
1.1 diameter of tree
1.2 find the point which have the maximum overlap of intervals Report Duplicate  Flag
Facebook Software Engineer Algorithm  3of 3 votes
Answers1 year exp. Interviewed at Cambridge, MA
 aonecoding in United States
Round1
LC304. Followup: given a char stream instead a string as the input, get the longest substring with at most K distinct characters.
Round2
Find out the area of a number of squares on a plane, an advanced version of LC223.
Had no clue on that problem at all so the interviewer kindly gave another one LC305.
Round3
Similar to LC393 but the interviewer made a slightly different rule for encoding.
Followup: decode with utf16. It took quite a while for me to understand the rules.
Round4
Card game rule: the hand is drawn from a pack of cards (no jokers).
Play cards ONLY when they are
1. 3 of a kind ('AAA' ) or 4 of a kind('AAAA’).
2. a straight flush of 3 or more cards('JQK' or 'A23456...' in the same suit).
Find out whether the player is able to play the whole hand given.
e.g. [Spade A, Spade K, Spade Q, Diamond Q, Heart Q] return false.
[Spade A, Spade K, Spade Q, Diamond Q, Heart Q, Club Q] return true. Report Duplicate  Flag
Google Software Engineer Algorithm  2of 4 votes
AnswersMaster Degree 2 year exp
 aonecoding in United States
1st Round.
Behavioral  most challenging project.
Tech  bit manipulation
2nd Round. A matrix has 0s and 1s only.. All the 1s in every row are to the of 0s. Find out the leftmost 1 in the entire matrix.
3rd Round.
A dp problem.
Find out how many ways you can make change of N cents given coins of values [a1, a2, a3...], each type of coin got infinite supplies.
Arrangement of coins don't matter.
4th Round.
Design news feed.
A user wrote a post with the basic user info, pictures and time etc (I even drafted a basic UI on whiteboard).
How to obtain these information and store them.
If a new feature with a button is added. How to maintain availability of old service to users who did not update the app.
Did not dive further into scaling.
5th Round.
User groups  If I made a certain post visible to a user group, how to store the post? how to push the post to the chosen group. If there are new friends who aren't assigned to any group just yet, how to treat them as if they were in the same 'unassigned' group?
DB sharding is involved.s Report Duplicate  Flag
Facebook Software Engineer System Design  1of 1 vote
AnswersFind the length of longest arithmetic progression in array.
 aonecoding in United States
For example, in the array {1, 6, 3, 5, 9, 7}, the longest arithmetic sequence is 1, 3, 5, and 7 Report Duplicate  Flag
Facebook Software Engineer Algorithm  2of 2 votes
AnswersGoogle fulltime phD candidate w/ work experience.
 aonecoding in United States
Q1. On a 1 meter walkroad, randomly generate rain. The raindrop is 1 centimeter wide.
Simulate how raindrops cover the 1 meter [0~1] road. How many drops does it take to fully cover the 1meter?
Q2. Find out the maximum number of isosceles triangles you can make from a plane of points(cannot reuse points)
Q3.Longest holiday  Every city has a different days of holidays every week. You may only travel to another city at the weekends. What is the max days of holiday you can get this year.
Q4.
Design merchandising product data storage service Report Duplicate  Flag
Google Software Engineer Algorithm  4of 4 votes
AnswersGoogle Onsite in May
 aonecoding in United States
Create a class with a collection of integers.
Enable 3 APIs:
void append(int x),
int get(int idx),
void add_to_all(int x)，//add x to all numbers in collection
These methods should run in O(1) time.
Followup
In addition, implement
void multiply_to_all(int x)
The same required to run in O(1) time Report Duplicate  Flag
Google Software Engineer Algorithm  0of 0 votes
AnswersImplement circular buffer with read & write functions
 aonecoding in United States Report Duplicate  Flag
Facebook Software Engineer Data Structures  0of 0 votes
AnswersCoding III
 aonecoding in United States
Implement int divide(int a, int b) without division or mod operation.
## Round IV
Behavioral Questions + Project Walk Through + Coding (Validate BST)
## System Design V
Design memcache to enable read, write and delete (single server, nondistributed infrastructure).
Which data structure to go with?
Eviction rules?
How to minimize segmentation?
How to handle concurrency?
## Extra
After two weeks they called me to an extra round of system design.
How to store social graphs?
How to handle concurrent read/write requests(read heavy) on one server. Report Duplicate  Flag
Facebook Software Engineer  0of 0 votes
AnswersCoding I
 aonecoding in United States
Flatten a linked list.
Each node in the list carries a piece of data and a pointer. The data could be in a normal data type such as an integer, or a pointer that points to another list node.
The interviewer gave no specification on how the list node class was defined. You may look at each list node as if it has two pointers  one of them points to the next node; the other points to the ‘data’ which could be either a node or an integer. There also needs to be a function to tell you about the node data is actual data or a pointer.
I solved the problem with recursion. During the process, any nodes that don’t carry an integer get removed. Report Duplicate  Flag
Facebook Software Engineer Algorithm  2of 2 votes
AnswersFB onsite two weeks ago last round of coding . (This problem is also in the internal question bank of G.)
 aonecoding in United States
There is a robot in a room. The initial location of the robot is unknown. The shape or area of the room is unknown.
You have a remote that could walk the robot into any of the four directions  up, left, down or right.
Here is the move method: boolean move(int direction), direction: 0, 1, 2, 3. If the robot hits the wall, the method returns false.
Otherwise returns true and the robot moves on to the direction given.
Find out the area of the room.
e.g.
X
XXX X
XXXXX 'X' marks the floor plan of the room.
A room like such has an area of 10. Report Duplicate  Flag
Facebook Software Engineer Algorithm  0of 0 votes
AnswersLast Monday phone interview of G.
 aonecoding in United States
Given a vector/list of doubly linked list pointers (a pointer is the directed linkage of two nodes), count how many independent blocks of linked lists there are for the pointers given. Report Duplicate  Flag
Google SDE1 Algorithm  0of 0 votes
AnswersApple Onsite at Cupertino
 aonecoding in United States
Team Data Warehousing
Questions on Hadoop, Hive and Spark
I. Given a table with 1B of user ID and product IDs that the users bought, and another table with product ID mapped with product name. We are trying to find the paired products that are often purchased together by the same user, such as wine and bottle opener, chips and beer … How to find the top 100 of these coexisted pairs of products. If going with hadoop, where is the bottleneck and how to optimize?
II. Someone put distribute Random()*ID in a Hive script to prevent data skew. What would be the problem here? Report Duplicate  Flag
Apple SDE3 design  0of 0 votes
AnswersApple Onsite at Cupertino
 aonecoding in United States
Team Data Warehousing
III. Given three letters ABC, where AB>C, AC>B, BC>A (sequence doesn’t matter). Get the length of the path to convert from a given string to a single character.
For example, “ABACB” goes to “ACCB” (based on AB >C, convert s[1] and s[2] to C)
“ACCB” goes to “BCB” (based on AC>B)
“BCB” goes to “AB”
“AB” goes to “C”
So it takes 4 steps to change the given string into a single character.
If a given string cannot be resized to 1 character, such as “AAA” or "ABACABB", return 1. Report Duplicate  Flag
Apple SDE3 Algorithm  0of 0 votes
AnswerApple Onsite at Cupertino
 aonecoding in United States
Team Data Warehousing
There were 6.5 rounds in total, that 0.5 on package negotiation with the HR and the remaining rounds with 2 managers and 4 engineers.
Only three pure coding questions were asked.
I. Use a stack to sort given data.
II. Given an array with positive integers only, find the MIN integer that is missing from the array. Report Duplicate  Flag
Apple SDE3 Algorithm  0of 2 votes
AnswersAmazon SDE 2 Onsite (1 of 4 Rounds)
 aonecoding in United States
In a file system stored a large amount of user’s browsing data, including the urls that the user visited. Design a function that outputs the longest common path of all the urls.
Having finished the code, I was asked to analyze the complexity. Report Duplicate  Flag
Amazon Software Engineer Algorithm  2of 2 votes
AnswersAmazon SDE 2 Onsite (4 of 4 Rounds)
 aonecoding in United States
Assume that there is an ebook application. For every book the sharable part of the book content cannot exceed 10% of the whole book. Design a module to decide whether the current part of content is sharable.
The description given is vague. I had to push him with questions to give the details.
At first I thought the problem was about strStr. But then the interviewer said that even if there are two paragraphs of the book content with the exact same texts, as long as they are not in the same place, they would be considered different content.
I then realized it’s a question about merging segments  have a helper to find each pair of start and end point of the input content (given multiple separated paragraphs). Then merge the intervals and see if they combined exceed 10% of the entire book.
The interviewer approved my solution and ask me to code it.
Overall I feel like that the Amazon SDE II Interview doesn’t focus on just algorithm. It’s more about problem solving in practice and then implement the only core function on whiteboard. Report Duplicate  Flag
Amazon Software Engineer  0of 0 votes
AnswersVMWare Standard Online Screen
 aonecoding in United States
3rd Question Given an array of strings and a long description about the formatting of IPv6 and IPv4 (it took me more than 5 minutes to read the description). Write a function to find if a string is IPv4 or IPv6 address or neither.
4th Question Given an integer array, whenever a duplicate number is found, you may increment it (++). Find the minimum sum of the numbers in the array by keep incrementing the dups until all the numbers are unique. Report Duplicate  Flag
VMWare Inc Software Engineer Algorithm  1of 1 vote
AnswerVMWare Standard Online Screen
 aonecoding in United States
The Online Assessment was called something like Life Cycle Challengeqpan.
There are 4 questions in total given 60 minutes. The problem description was unexpectedly long that it takes 5 minutes just to read a question.
1st Question Design a function to create BST. Given an integer array, insert the integers into the binary search tree and print all the steps taken.
2nd Question Given an integer, print the index of all the positions in which the binary bit is 1 in order. Report Duplicate  Flag
VMWare Inc Software Engineer Algorithm  3of 3 votes
AnswersFacebook Senior Engineer Onsite 2017
 aonecoding in United States
1st Round
Question 1: Binary tree to doubly linked list.
Question 2: Read 4 (Given the read4 API, read an entire file)
2nd Round
Culture fit. No coding.
3rd Round
Question: System Design POI (Point of Interest. Given a point, find things within a radius).
Lunch
4th Round
Question 1: Decode way
Question 2: Random max index
5th Round
Question: System design + componentwise design on download manager Report Duplicate  Flag
Facebook Software Engineer Algorithm  4of 4 votes
Answers5th Round
 aonecoding in United States
Openended question What happens when you type a url in the browser and hit enter?
Second question Given an array of integers, print all the numbers that meet the following requirement  when the number is greater than every number on its left and smaller than every number on the right. Report Duplicate  Flag
Google Software Engineer Algorithm  1of 3 votes
Answerinterviewed by senior engineer
 aonecoding in United States
Question Given two strings s1 and s2, combine the characters in the strings and maintain the sequence of characters
Followup If s1 has a length of m and s2 has a length of n, how many ways the strings could be merged. Figure out the formula F(m, n) = ? Report Duplicate  Flag
Google Software Engineer Algorithm  0of 2 votes
AnswersHow to randomly select a number in an array?
 aonecoding in United States
array: [15, 2, 4, 5, 1, 2, 0]
Followup:
Given a second array freq where freq[i] represents the occurrence of the ith number in array, how to randomly select a number in array based on the frequency.
Extra requirement:
Could you complete the selection in a singlepass(go through each array only once)? Report Duplicate  Flag
Linkedin Software Engineer Algorithm  1of 5 votes
AnswersIn school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
 aonecoding in United States
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time),
check whether the student qualifies for the reward.
e.g.
@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False
The student does not qualify for reward because "LLA" means he was late for 3 times in a row.
@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True
Followup:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure you get the reward. Report Duplicate  Flag
Google Software Engineer Algorithm  0of 0 votes
AnswersIn school a student gets rewarded if he has an attendance record without being absent for more than once or being late for 3 times continuously.
 aonecoding in United States
Given a student's attendance record represented by a string with 3 possible characters 'L'(Late), 'A'(Absent), 'O' (On time), check whether the student qualifies for the reward.
e.g.
@INPUT (String) "OLLAOOOLLO"
@RETURN (Boolean) False
The student does not qualify for reward because "LLA" means he was late for 3 times in a row.
@INPUT (String) "OLLOAOLLO"
@RETURN (Boolean) True
Followup:
If known the length of the attendance string is n, how many possible ways there is to attend school and make sure the student gets the reward. Report Duplicate  Flag
Google Software Engineer Algorithm  2of 2 votes
AnswersEarly on I prefer to post the interview questions with a simplified description or only present the algorithmic part of it. Because it's hard for our students to memorize the full description of a problem. Therefore often times only the algorithm behind the question is given.
 aonecoding in United States
But somehow a user of this site @concernedCoder gets unhappy with it. So from today on, we will try to recover the original version of the question as much as possible.
We assure you all of the questions we posted are real questions that you have a good chance to come across during a coding interview. Anyone who has experience in a coding interview should be able to see that.
Here is the full description of a recent Amazon OA question. The reason why we are able to provide the full description is because it's the online assessment. But for an onsite interview it's almost impossible to recover the questions perfectly.
Title: Item Recommendations
Amazon wants to recommend items to a customer who has just made a purchase. Amazon's recommendation algorithm is based on item 'connection'.
Two items are 'strongly connected' if a single customer bought both of them. Two items are 'weakly connected' if they are both strongly and weakly connected to some other third item.
Your task is to determine the number of the items strongly and weakly connected to a given item.
You are provided the item id represented as a string, as well as the list of customer purchases represented as an array of strings. Each element in the array consists of a customer id(represented as a string) and an item id (also represented as a string). The two ids are separated by a colon. For example, if they element in the array is "ABJA:Z42G" then that means customer ABJA purchased item Z42G.
Your output consists of an array, where the first element in the array represents the number of items strongly connected to the provided item id and the second element represents the number of items weakly connected to the provided item id.
For example, if you were provided with the following input:
determineRecommendation("ABC",["first:ABC", "first:HIJ", "sec:HIJ", "sec:KLM", "third:NOP", "fourth:ABC", "fourth:QRS", "first"DEF", "fifth:KLM", "fifth:TUV"])
You would return the following array:
[3, 2]
since ABC is strongly connected to 3 items: DEF, HIJ and QRS and is weakly connected to 2 items: KLM and TUV
Although the description is long, the problem is just asking for 'search (with either DFS or BFS) in a graph'. Report Duplicate  Flag
Amazon Software Engineer Algorithm  1of 5 votes
AnswersCreate an iterator class that stores a list of the builtin Iterators.
 aonecoding in United States
Implement the next() and hasNext() methods in a Round Robin pattern (pops next element in a circle).
Example:
Given a list [iterator1,iterator2, iterator3...]
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next() if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
when calling RoundIterator.next()
pops iterator1.next if iterator1.hasNext() is true
when calling RoundIterator.next()
pops iterator2.next if iterator2.hasNext() is true
when calling RoundIterator.next()
pops iterator3.next if iterator3.hasNext() is true
...
until there is no more element in any of the iterators Report Duplicate  Flag
Google Algorithm  1of 9 votes
AnswersQ: Weighted meeting room
Given a series of meetings, how to schedule them. Cannot attend more than a meeting at the same time. Goal is to find maximum weight subset of mutually nonoverlap meetings.class Meeting: def __init__(self): self.startTime self.endTime self.weight
@concernedCoder
 aonecoding in United States
When you claim the questions as fake, provide evidence. These are no doubt questions asked in the coding interviews of the best companies and they definitely help interviewees to prepare for the interview.
Why do you have a problem with this? Report Duplicate  Flag
Facebook Software Engineer Algorithm  1of 3 votes
AnswerOn google search, how to enable key word auto completion after a few letters typed.
 aonecoding in United States
Followup: How to rank the words if they are weighted by frequency? Report Duplicate  Flag
Google Software Engineer Algorithm  4of 4 votes
Answers# There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room.
 aonecoding in United States
# For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words:
# Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
# For example:
# input = [(1,4), (2,3)]
# > 3
# input = [(4,6), (1,2)]
# > 3
# input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
# > 11 Report Duplicate  Flag
Facebook Software Engineer Algorithm  5of 5 votes
AnswersFind the median of an unsorted array.
 aonecoding in United States
Have to do better than O(nlogn) time.
e.g.
Given [2, 6, 1] return 2
Given [2, 6, 1, 4] return 3 which is sum of the two elements in middle over 2 Report Duplicate  Flag
Facebook Software Engineer Algorithm  4of 4 votes
Answers/**
 aonecoding in United States
Given many coins of 3 different face values, print the combination sums of the coins up to 1000. Must be printed in order.
eg: coins(10, 15, 55)
print:
10
15
20
25
30
.
.
.
1000
*/ Report Duplicate  Flag
Facebook Software Developer Algorithm  2of 4 votes
AnswersFind all comments in the Java (it could be Python or any other language of your choice) codes that’s parsed in as a string.
 aonecoding in United States
You may assume the codes given is valid.
Input is a single string, e.g.
String codes =
“/* file created by aonecode.com\\n” +
“ welcome to the tech blog*/ \\n” +
“//main method\\n” +
“public static void main(String[] args) { \\n“ +
“ System.out.println(“//welcome”); //output\\n” +
“}”
Output is a list of strings
List<String> ret =
[
“ file created by anecode.com\n welcome to the tech blog”,
“main method”,
“output”
] Report Duplicate  Flag
Google Software Engineer Algorithm  4of 4 votes
AnswersQ: If you were given a series of equations e.g. [A = B, B = D, C = D, F = G, E = H, H = C]
 aonecoding in United States
and then another series [A != C, D != H, ..., F != A ]
Check whether the equations combined is valid.
For the example given, your program should return 'invalid', because the first series implies that A = C, which contradicts the statement A != C in the second series. Report Duplicate  Flag
Amazon Software Engineer Algorithm  3of 3 votes
AnswersPrint first pair of mismatching leaves (first pair as in inorder) given two preorder traversal arrays of BSTs.
e.g.For 5 4 8 2 4 6 9 Preorder Sequence as [5,4,2,4,8,6,9] & 5 3 8 2 4 7 9 Preorder Sequence2 as [5,3,2,4,8,7,9] Print “4, 3”.
@Kart
 aonecoding in United States
If you create the inorder sequences for the two trees, you'll be able to see that 4 and 3 comes far before 6 and 7.
In fact, in any of the three wellknown types of tree traversal, there is NO way for a node in the right tree visited prior to the node in the left tree.
@anon
The question gives just enough detail for you to solve it. It does NOT matter if the trees are balanced or same size. It's said in the first sentence that 'find the first nonmatching pair as in the INORDER sequence', which is the ascending sequence in a BST. Report Duplicate  Flag
Facebook Software Engineer Algorithm  3of 3 votes
AnswersRandomly select one of the weighted items from a linked list. (you may only go through the list once)
 aonecoding in United States
e.g.
weight 1.6 > weight 0.2> ... > weight 3.4
randomly select one item based on the weight. The higher the weight is, the more likely to be selected Report Duplicate  Flag
Amazon Software Engineer Algorithm  3of 3 votes
AnswersGiven a list of system packages, some packages cannot be installed until the other packages are installed. Provide a valid sequence to install all of the packages.
 aonecoding in United States
e.g.
a relies on b
b relies on c
then a valid sequence is [c, b, a] Report Duplicate  Flag
Uber Software Engineer Algorithm  3of 5 votes
AnswersPhone screen Q: String encoding and decoding: Design a method that converts a list of strings into a single string which can be later converted back to the list.
 aonecoding in United States Report Duplicate  Flag
Google Software Engineer Programming Skills  3of 5 votes
AnswersQ: Find the absolute paths to all directories with image files, given a file system that looks like this. The subdirectory is one indent over.
 aonecoding in United States/usr /local profile.jpg /bin config.txt dest.png /rbin image.gif /sys /re /tmp pic.jpg ..... ……
 Report Duplicate  Flag
Google Software Engineer Algorithm  2of 4 votes
AnswersQ: List all comments in the given segment of codes. It's pretty tricky since there is a lot of things to be considered, especially the escape characters.
 aonecoding in United States Report Duplicate  Flag
Google Software Engineer Algorithm

0 Answers
Coding Interview Mentoring
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
 aonecoding January 15, 2017
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions. Flag 
0 Answers
Coding Interview Mentoring
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
 aonecoding January 15, 2017
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions. Flag
Looking for interview experience sharing and coaching?
Visit aonecode.com for 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
}
}

aonecoding
July 20, 2017 Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
Our ONE TO ONE class offers
SYSTEM DESIGN Courses (highly recommended for candidates 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
};
}

aonecoding
July 17, 2017 Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
ONE TO ONE realtime 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;
}

aonecoding
July 15, 2017 Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
ONE TO ONE realtime 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;
}

aonecoding
July 15, 2017 Looking for interview experience sharing and coaching?
Visit aonecode.com for private lessons by FB, Google and Uber engineers
ONE TO ONE realtime 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 nonoverlap intervals in 'points' to collection of numbers if necessary
return points;
}

aonecoding
July 15, 2017 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!
Solution: Dynamic programming with a map of a map.
public static int llac(int[] array) {
if(array.length == 0) return 0;
int max = 1;
Map<Integer,Map<Integer, Integer>> index_to_llac = new HashMap<>(); //Map<currentIndex, Map<difference, length>>
for(int current = 1; current < array.length; current++) {
index_to_llac.put(current, new HashMap<>());
for(int prev = 0; prev < current; prev++) {
int diff = array[current]  array[prev];
int length = 2;
if(index_to_llac.containsKey(prev) && index_to_llac.get(prev).containsKey(diff)) {
length = index_to_llac.get(prev).get(diff) + 1;
}
Map<Integer, Integer> diff_to_llac = index_to_llac.get(current);
//if this is a arithmetic progression with [diff] exists before current, add 1 to the length to include current in the progression
//otherwise, [prev, current] forms a progression of size 2
diff_to_llac.put(diff, length);
max = Math.max(length, max);
}
}
return max;
}

aonecoding
July 05, 2017 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!
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!
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);
}
}

aonecoding
June 22, 2017 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;
}
}

aonecoding
June 15, 2017 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 + ")";
}
}

aonecoding
June 06, 2017 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;
}

aonecoding
June 06, 2017 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!
Having come across a nested list node N. Recursively flatten the node into a plain list. Return the Head and Tail of the flattened list. Make the node before N point to Head. Make Tail.next point to N.next.
public class FlattenLinkedList {
public static Wrapper flatten(ListNode head) {
if(head == null) return null;
ListNode dummy = new ListNode(0);
dummy.next = head;
ListNode node = dummy;
while(node.next != null) {
if(node.next.data != null) {
node = node.next;
} else {
Wrapper flattened = flatten(node.next.list);
if(flattened.tail != null) {
flattened.tail.next = node.next.next; //delete the node with nested list
node.next = flattened.head;
node = flattened.tail;
} else {
node.next = node.next.next;
}
}
}
return new Wrapper(dummy.next, node);
}
}
class ListNode<T> {
ListNode next;
T data; //when data is not null, this node carries actual data
ListNode list; //when data is null, this node carries a nested list
public ListNode(T data) {
this.data = data;
}
public ListNode() {
}
//.....other constructors
}
class Wrapper {
ListNode head;
ListNode tail;
public Wrapper(ListNode h, ListNode t) {
head = h;
tail = t;
}

aonecoding
June 06, 2017 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.
Solution:
The problem is about scanning a graph. So either DFS or BFS will work.
Perceive the room as a 2D grid and the robot initializes at (0, 0).
The thing special about this problem is that the shape of the room is unknown. Therefore it is harder for us to mark the visited places. The normal approach like using a boolean matrix wouldn't work here.
Instead we can go with a map of a set Map<Integer, Set<Integer>>. For any (X, Y) location that exists, store it in the map Map<x, Set<all the Ys in line X>>.
Then backtracking solves the problem. Don't forget to move the robot back to where it was from after each layer of recursion. So it is necessary to have an argument that keeps track of from where the robot comes to the current point.
public class Room {
Robot robot;
//......
//x, y is the current location of the robot
//from is the last step taken
//map<x, set<y>> marks the places visited
public int getArea(int x, int y, int from, Map<Integer, Set<Integer>> room) {
if(room.containsKey(x) && room.get(x).contains(y)) { //if this place was visited
robot.move(moveBack(from)); //turn robot back
return 0; //add 0 to total area
}
//mark current place visited
if(!room.containsKey(x)) room.put(x, new HashSet<>());
room.get(x).add(y);
int area = 1;
if(from != 0 && robot.move(moveBack(0))) {//if robot was not moved to current place from below, move robot down
area += getArea(x, y  1, 0, room);
}
if(from != 1 && robot.move(moveBack(1))) {//if robot didn't come from the right, move it to the right
area += getArea(x + 1, y, 1, room);
}
if(from != 2 && robot.move(moveBack(2))) { //if robot didn't come from above, move it up
area += getArea(x, y + 1, 2, room);
}
if(from != 3 && robot.move(moveBack(3))) { //if robot didn't come from the left, move it to the left
area += getArea(x  1, y, 2, room);
}
//after counting the areas around the current location, walk robot back to where it was from
robot.move(moveBack(from));
return area;
}
private int moveBack(int from) {
if(from == 0) return 2;
if(from == 1) return 3;
if(from == 2) return 0;
return 1;
}
}

aonecoding
May 27, 2017 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;
}

aonecoding
May 27, 2017 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';
}
}

aonecoding
May 10, 2017 Not a typical coding interview question but I like it. When problem solving goes too far we'd like to get back to the real world.
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.
class Photo implements Comparable<Photo> {
String location;
String type;
int year;
int month;
int day;
int hour;
int minute;
int second;
int index; //Convert the given string to a list (one photo as an element). This is the index of the current photo
public Photo(String loc, String t, int y, int m, int d, int h, int mm, int s) {
location = loc;
type = t;
year = y;
month = m;
day = d;
hour = h;
minute = mm;
second =s;
}
public int compareTo(Photo o) {
if(year != o.year) return year  o.year;
if(month != o.month) return month  o.month;
if(day != o.day) return day  o.day;
if(hour != o.hour) return hour  o.hour;
if(minute != o.minute) return minute  o.minute;
return second  o.second;
}
}
public class RenamePhotos {
public String solution(String photos) {
if(photos.isEmpty()) return "";
String[] list = photos.split("\n");
//key: location, value: a list of photos taken at the location
Map<String, List<Photo>> map = new HashMap<>();
for(int i = 0; i < list.length; i++) {
Photo photo = createPhoto(list[i]);
photo.index = i;
if(!map.containsKey(photo.location)) {
map.put(photo.location, new ArrayList<>());
}
map.get(photo.location).add(photo);
}
for(String loc: map.keySet()){
List<Photo> photo_by_datetime = map.get(loc);
Collections.sort(photo_by_datetime);
int size = photo_by_datetime.size();
for(int i = 0; i < size; i++) {
//create new name for current photo
StringBuilder str = new StringBuilder();
str.append(photo_by_datetime.get(i).location);
str.append(padZeros(i, size));
str.append('.');
str.append(photo_by_datetime.get(i).type);
//update list with the new name of this photo
list[photo_by_datetime.get(i).index] = str.toString();
}
}
StringBuilder ret = new StringBuilder();
for(String str: list) { //merge new names into a string
ret.append(str);
ret.append('\n');
}
return ret.substring(ret.length()  1);
}
private String padZeros(int i, int len) {
StringBuilder number = new StringBuilder();
number.append(i);
i = number.length();
while(i < len) {
number.insert(0, '0');
i++;
}
return number.toString();
}
//create an instance of photo for each photo name given
private Photo createPhoto(String photo) {
int i = 0;
String type = photo.substring(photo.indexOf('.') + 1, i = photo.indexOf(','));
String location = photo. substring(i + 1, i = photo.indexOf(i + 1, ','));
int year = Integer.parseInt(photo.substring(i + 1, i = photo.indexOf(i + 1, '')));
int month = Integer.parseInt(photo.substring(i + 1, i = photo.indexOf(i + 1, '')));
int day = Integer.parseInt(photo.substring(i + 1, i = photo.indexOf(i + 1, ' ')));
int hour = Integer.parseInt(photo.substring(i + 1, i = photo.indexOf(i + 1, ':')));
int minute = Integer.parseInt(photo.substring(i + 1, i = photo.indexOf(i + 1, ':')));
int second = Integer.parseInt(photo.substring(i + 1));
return new Photo(location, type, year, month, day, hour, minute, second);
}
}

aonecoding
May 05, 2017 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.starti2.start;
else
return i1.endi2.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;
}

aonecoding
April 23, 2017 The solution takes O( L * log(S)) time and O(log(S)) space, where L is the average length of the urls, S is the size of the url list. Because it was said to be a long list, we trade space for time.
Otherwise if space if more valuable, just compare every character at the same index over the whole url list, which takes O(SL) time in the worst case.
//return the last index of the common prefix of url. To get the common prefix, just call url.substring(last index + 1).
public int longestCommonPrefix(String[] urls) {
//the length of a url will not exceed the limit of max integer
return longestCommonPrefix(urls, 0, urls.length()  1, Integer.MAX_VALUE);
}
//recursive divide and conquer approach. To save time every round deal with half of the remaining url list since the list is assumed to be long
private int longestCommonPrefix(String[] urls, int start, int end) {
if(end < start) return 0;
if(end == start) return urls[start].length()  1;
int prefix1 = urls[start].length()  1, prefix2 = urls[end].length()  1;
if(start < end  1) {
int mid = (start + end) / 2;
prefix1 = longestCommonPrefix(urls, start, mid);
prefix2 = longesetCommonPrefix(urls, mid + 1, end);
}
for(int common = 0; common <= prefix1 && common <= prefix2; i++) {
if(urls[start].charAt(common) != urls[end].charAt(common)) break;
}
return common;
}
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!
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[i1], v[i1]);
int rightMin =INT_MAX;
for(int i=n1;i>=0; i) {
if(i<n1)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;
}

aonecoding
April 13, 2017 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;
}

aonecoding
April 13, 2017 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;
}

aonecoding
April 02, 2017 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);
}

aonecoding
March 28, 2017 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 onsite 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 followup 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[(i1) % 2][0] + arr[(i1) % 2][1]; // the ith letter is O
arr[i % 2][1] = arr[(i1) % 2][0] + arr[(i2) % 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 ni1 letter to the right of A
opt += ( arr[i][0] + arr[i][1] ) * ( arr[ni1][0] + arr[ni1][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.
@bunafish
Thank you for the reply. Since it is an online assessment, there is no way to get response from an interviewer who can give further clarification on the problem. The only example given has included the original item in the strong connection set though. Therefore we have to include ABC in order to get the numbers right.
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.
Here is a way to solve the problem wrapping the Items and Customers nicely in classes. The code could be shorter but less readable with other forms of representation of the graph.
class Item {
String label;
Set<Customer> customers;
public Item(String s) {
customers = new HashSet<>();
label = s;
}
}
class Customer {
String id;
Set<Item> items;
public Customer(String s) {
items = new HashSet<>();
id = s;
}
}
public class ItemRecommendation {
public int[] linkageCount(String obj, String[] purchases) {
Map<String, Item> items = new HashMap<>();
Map<String, Customer> customers = new HashMap<>();
for(String purchase: purchases) {
String[] pair = purchase.split(":");
String customer = pair[0], item = pair[1];
if(!customers.containsKey(customer)) {
customers.put(customer, new Customer(customer));
}
if(!items.containsKey(item)) {
items.put(item, new Item(item));
}
customers.get(customer).items.add(items.get(item));
items.get(item).customers.add(customers.get(customer));
}
Set<String> strongly_connected = new HashSet<>();
Set<String> weakly_connected = new HashSet<>();
for(Customer customer: items.get(obj).customers) {
for(Item item: customer.items) {
strongly_connected.add(item.label);
}
}
for(String item: strongly_connected) {
for(Customer customer: items.get(item).customers) {
for(Item i: customer.items) {
if(!strongly_connected.contains(i.label)) {
weakly_connected.add(i.label);
dfsFindWeakConnetions(items, customers, strongly_connected, weakly_connected, i.label);
}
}
}
}
return new int[] {strongly_connected.size(), weakly_connected.size()}; //result
}
private void dfsFindWeakConnetions(Map<String, Item> items, Map<String, Customer> customers //DFS to search for strongly connected items
, Set<String> strongly_connected, Set<String> weakly_connected, String item) {
for(Customer customer: items.get(item).customers) {
for(Item i: customer.items) {
if(!strongly_connected.contains(i.label) && !weakly_connected.contains(i.label)) {
weakly_connected.add(i.label);
dfsFindWeakConnetions(items, customers, strongly_connected, weakly_connected, i.label);
}
}
}
}
}

aonecoding
March 02, 2017 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.
Here is a way to solve the problem wrapping the Items and Customers nicely in classes. The code could be shorter but less readable with other forms of representation of the graph.
class Item {
String label;
Set<Customer> customers;
public Item(String s) {
customers = new HashSet<>();
label = s;
}
}
class Customer {
String id;
Set<Item> items;
public Customer(String s) {
items = new HashSet<>();
id = s;
}
}
public class ItemRecommendation {
public int[] linkageCount(String obj, String[] purchases) {
Map<String, Item> items = new HashMap<>();
Map<String, Customer> customers = new HashMap<>();
for(String purchase: purchases) {
String[] pair = purchase.split(":");
String customer = pair[0], item = pair[1];
if(!customers.containsKey(customer)) {
customers.put(customer, new Customer(customer));
}
if(!items.containsKey(item)) {
items.put(item, new Item(item));
}
customers.get(customer).items.add(items.get(item));
items.get(item).customers.add(customers.get(customer));
}
Set<String> strongly_connected = new HashSet<>();
Set<String> weakly_connected = new HashSet<>();
for(Customer customer: items.get(obj).customers) {
for(Item item: customer.items) {
strongly_connected.add(item.label);
}
}
for(String item: strongly_connected) {
for(Customer customer: items.get(item).customers) {
for(Item i: customer.items) {
if(!strongly_connected.contains(i.label)) {
weakly_connected.add(i.label);
dfsFindWeakConnetions(items, customers, strongly_connected, weakly_connected, i.label);
}
}
}
}
return new int[] {strongly_connected.size(), weakly_connected.size()}; //result
}
private void dfsFindWeakConnetions(Map<String, Item> items, Map<String, Customer> customers //DFS to search for strongly connected items
, Set<String> strongly_connected, Set<String> weakly_connected, String item) {
for(Customer customer: items.get(item).customers) {
for(Item i: customer.items) {
if(!strongly_connected.contains(i.label) && !weakly_connected.contains(i.label)) {
weakly_connected.add(i.label);
dfsFindWeakConnetions(items, customers, strongly_connected, weakly_connected, i.label);
}
}
}
}
}
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;
}
}
}

aonecoding
February 27, 2017 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;
}
}
}

aonecoding
February 27, 2017 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)]

aonecoding
February 27, 2017 Sortingfree 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 followup 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);
}
}

aonecoding
February 19, 2017 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;
}

aonecoding
February 08, 2017 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, 2017We know that sorting the array would not be feasible if we wanna do better than O(nlogn).
Therefore we go with quick select which on average takes O(n) time. The quick select is similar to a binary quick sort which partially sorts the given array.
public static double median(int[] a) {
int len = a.length;
if(len % 2 == 1) {
return topK(a, len / 2);
} else {
return (topK(a, len / 2  1)+ topK(a, len / 2)) * .5;
}
}
private static int topK(int[] a, int k) {
int l = 0, r = a.length  1;
while(l <= r) {
int pivot = a[l];
int i = l + 1, j = r;
while(i <= j) {
if(a[i] <= pivot) i++;
else if(a[j] > pivot) j;
else {
swap(a, i, j);
i++;
j;
}
}
if(j == k) return pivot;
else if(j < k) l = i;
else {
swap(a, l, j);
r = j  1;
}
}
return a[r];
}
On average the performance of the program above is O(n). However it can get to O(n^2) in the worst case. To learn how to find the best pivot in linear time, join us.
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 reach us with any questions via aonecoding@gmail.com. Thanks for reading.
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.
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);
}
}
}

aonecoding
January 27, 2017 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;
}

aonecoding
January 27, 2017 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.
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. Thanks for reading.
public Wrapper findNext(int[] preorder, Stack<Integer> stack, int index) {
while(index < preorder.length) {
if (stack.isEmpty()  preorder[stack.peek()] > preorder[index]) {
stack.push(index); //push the index
index++;
} else {
return new Wrapper(index ,stack.pop());
}
}
if(stack.isEmpty()) return new Wrapper(index, null);
return new Wrapper(index, stack.pop());
}
class Wrapper {
int index; //index of currently traversed node in the array (as in preorder)
Integer c; //index of the next leave (as in inorder)
Wrapper(int index, Integer c) {
this.index = index;
this.c = c;
}
}
//compare the if the two leaves are equal
public void firstNonMathcingLeaves(int[] o1, int[] o2) {
Stack<Integer> s1 = new Stack<>(), s2 = new Stack<>();
Wrapper w1 = new Wrapper(0, 0), w2 = new Wrapper(0, 0);
while(w1.c != null && w2.c != null && o1[w1.c] == o2[w2.c]) {
w1 = findNext(o1, s1, w1.index);
w2 = findNext(o2, s2, w2.index);
}
if(w1.c == null && w2.c == null) {
System.out.println("same"); return;
}
if(w1.c == null) {
System.out.println(w1.c + " " + o2[w2.c]); return;
}
if(w2.c == null) {
System.out.println(o1[w1.c] + " " + w2.c); return;
} else {
System.out.println(o1[w1.c] + " " + o2[w2.c]);
}
}

aonecoding
January 15, 2017 Open Chat in New Window
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.
 aonecoding July 20, 2017