aonecoding
 2of 2 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  3of 3 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.
 aonecoding in United Statesclass Meeting: def __init__(self): self.startTime self.endTime self.weight
 Report Duplicate  Flag
Facebook Software Engineer Algorithm  0of 0 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  2of 2 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  1of 1 vote
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  1of 1 vote
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  1of 1 vote
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  2of 2 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  1of 1 vote
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  1of 1 vote
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  1of 1 vote
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  2of 2 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  2of 2 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  1of 1 vote
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
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 class WeightedItem {
Object obj;
double weight;
}
public class WeightedRandomSelect {
public WeightedItem random(List<WeightedItem> items) {
double totalWeight = 0;
WeightedItem selected = null;
Random rand = new Random();
for(WeightedItem item: items) {
double r = rand.nextDouble() * (totalWeight + item.weight);
if(r >= totalWeight) {
selected = item;
totalWeight +=item.weight;
}
}
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.
Typical topological sort that can be solved with DFS
Assume packages are nodes like this:
public List<Integer> installPackages(List<Node> packages) {
if(packages == null  packages.isEmpty()) return new LinkedList<Integer>();
int n = packages.size();
int[] parentsCount = new int[n];
for(Node package: packages) {
for(Node child: package.children) {
parentsCount[child.label]++;
}
}
List<Integer> sequence = new LinkedList<>(); //output to return
for(Node package: packages) {
dfs(sequence, parentsCount, package);
}
return sequence;
}
private void dfs(List<Integer> sequence, int[] parentsCount, Node package) {
if(parentsCount[package.label] == 0) {
sequence.add(package.label); //install package
parentsCount[package.label] ;
for(Node child: package.children) {
parentsCount[child.label] ;
dfs(sequence, parentsCount, child);
}
}
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.
public static int getPathLength(String s) {
String[] lines = s.split("\n");
int i = 0, len = s.length(), res = 0;
Stack<Integer> stack = new Stack<Integer>();
Stack<Boolean> added = new Stack<Boolean>();
stack.push(0);
added.push(true);
int prevSpaces = 1;
for(i = 0; i < len; i++) {
int spaces = lines[i].trim().length()  lines[i].length();
if(spaces < prevSpaces) {
while (spaces < prevSpaces) {
stack.pop();
added.pop();
prevSpaces;
}
}
if(lines[i].contains(".")) {
if(isPic(lines[i]) && !added.peek()) {//0 , //true //prev = 1 ,sp = 0 //res = 4
res += stack.peek();
added.pop();
added.push(true);
}
} else {
if(spaces <= prevSpaces) {
stack.pop();
added.pop();
} else prevSpaces++;
stack.push(stack.peek() + lines[i].trim().length() + 1);
added.push(false);
}
}
return res;
}
public static boolean isPic(String f) {
String appendix = f.substring(f.length()  4);
if(appendix.equals(".gif")  appendix.equals(".jpg")  appendix.equals(".png")) return true;
return false;
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.
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);
//找到引号并忽略引号内的内容
if(c == '\''  c == '"') {
i++;
while(codes.charAt(i) != c) {
//遇到escape标志"\\"就忽略下一个字符
if(codes.charAt(i) == '\\') i++;
i++;
}
}
//找到comment开始的标示'/'
else if(c=='/'){
StringBuilder comment = new StringBuilder();
char type = codes.charAt(++i);
i++;
if(type == '*') {
// 读取/* */这种comment，以遇到"*/"为结束标志
while(codes.charAt(i) != '*'  codes.charAt(i + 1) != '/') {
comment.append(codes.charAt(i));
i++;
}
} else {
// 读取//这种comment,以i == n或遇到"\\n"作为结束条件
while (i < n && ( codes.charAt(i) != '\\'  i + 1 == n  codes.charAt(i + 1) != 'n')) {
char a = codes.charAt(i);
if(a == '\\') {
//corner case: 处理在这种comment里遇到"\\\\n"的情况，escape掉这个换行符
//遇到escape标志"\\"且下一个字符不是‘n’就忽略下一个字符
comment.append(codes.charAt(i + 1));
i++;
}
comment.append(a);
i++;
}
}
comments.add(comment.toString());
i++;
}
i++;
}
return comments;
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.
//encoding
static char SEPARATOR = ‘,’;
public static String serialize(List<String> strs) {
if(strs == null) return null;
StringBuilder ret = new StringBuilder();
for(String str: strs) {
ret.append(str.length());
ret.append(SEPARATOR);
ret.append(str);
}
return ret.toString();
}
//decoding
public static List<String> deserialize(String s) {
if(s == null) return null;
List<String> strs = new ArrayList<String>();
int i = 0, n = s.length();
while(i < n) {
int j = i;
while(s.charAt(j) != SEPARATOR) {
j++;
}
int len = Integer.parseInt(s.substring(i, j));
i = j + len + 1;
if(len == 0) strs.add(“”);
else strs.add(s.substring(j + 1, i));
}
return strs;
}
Looking for interview questions sharing and mentors? Visit A++ Coding Bootcamp at aonecode.com (select english at the top right corner).
We provide ONE TO ONE courses that cover everything in an interview from the latest interview questions, coding, algorithms, system design to mock interviews. All classes are given by experienced engineers/interviewers from FB, Google and Uber. Help you close the gap between school and work. Our students got offers from G, U, FB, Amz, Yahoo and other top companies after a few weeks of training.
Welcome to email us with any questions.
@artur.ghandilyan:
Nope dude. The solution works with or without the character ',' in the strings. In fact the choice of SEPARATOR does NOT matter at all. Please read the code more carefully or at least provide one counter case.
Your method works exactly the same as mine, only with different parameter naming.
Replacing the while loop with find() won't make any difference other than shortening the code by one line.
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);
//omit anything in quotes or escaped
if(c == '\''  c == '"') {
i++;
while(codes.charAt(i) != c) {
//遇到escape标志"\\"就忽略下一个字符
if(codes.charAt(i) == '\\') i++;
i++;
}
}
//find '/' which is the start of any comment
else if(c=='/'){
StringBuilder comment = new StringBuilder();
char type = codes.charAt(++i);
i++;
if(type == '*') {
// read /* */ type of comments
while(codes.charAt(i) != '*'  codes.charAt(i + 1) != '/') {
comment.append(codes.charAt(i));
i++;
}
} else {
// read "//" type of comments
while (i < n && ( codes.charAt(i) != '\\'  i + 1 == n  codes.charAt(i + 1) != 'n')) {
char a = codes.charAt(i);
if(a == '\\') {
//corner cases
comment.append(codes.charAt(i + 1));
i++;
}
comment.append(a);
i++;
}
}
comments.add(comment.toString());
i++;
}
i++;
}
return comments;
}
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.
Open Chat in New Window
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.
 aonecoding February 27, 2017