Wish Interview Question for Solutions Engineers


Country: United States
Interview Type: In-Person




Comment hidden because of low score. Click to expand.
3
of 3 vote

Looking for interview experience sharing and coaching?

Visit AONECODE.COM for private lessons by FB, Google and Uber engineers

Our ONE TO ONE class offers

SYSTEM DESIGN Courses (highly recommended for candidates of FB, LinkedIn, Amazon, Google & Uber etc.)
ALGORITHMS (conquer DP, Greedy, Graph, Advanced Algos & Clean Coding),
latest interview questions sorted by companies,
mock interviews.

Our students got hired from G, U, FB, Amazon, LinkedIn and other top-tier companies after weeks of training.

Feel free to email us aonecoding@gmail.com with any questions. Thanks!

public static int rankWays(int n) {
int[] base = new int[2]; // start from case for 0 participants
base[1] = 1;

for(int p = 2; p <= n; p++) {
int[] ways = new int[p + 1]; //index is row number, value is count of ways
for(int r = 1; r < base.length; r++) {
ways[r + 1] += base[r] * (r + 1);
ways[r] += base[r] * r;
}
base = ways;
}
int sum = 0;
for(int x: base) sum += x;
return sum;
}

With N participants [p1, p2, p3... pN], one ranking could be:
1st place: p1
2nd place: p2, p3
...
xth place: pN

In this case, if one more player pL joins the game. The new player pL can be placed into

pL can be here as new 1st place
1st place p1 pL can be here tied with 1st place
pL can be here as new 2nd place
2nd place p2, p3 pL can be here tied 2nd place
... ...
xth place pN pL can be here tied last place
pL can be here as new last

So for every rank combination of N people, adding 1 more player creates rowNumber * 2 + 1 ways of ranking.
So if we keep track of the row numbers of all previous combinations of ranking,
a ranking with R rows is gonna derive into R + 1 more cases (with R + 1 row numbers) plus R more cases (with R row numbers).

To print all possible combinations:
public static List<List<List<Integer>>> rankCombinations(int n) {
List<List<List<Integer>>> base = new ArrayList<>();
base.add(new ArrayList<>());
base.get(0).add(new ArrayList<>());
base.get(0).get(0).add(1);
for(int p = 2; p <= n; p++) {
List<List<List<Integer>>> combinations = new ArrayList<>();
for(List<List<Integer>> comb: base) {
for(int i = 0; i <= comb.size(); i++) {
List<Integer> rank = new ArrayList<>();
rank.add(p);
List<List<Integer>> newComb = new ArrayList<>(comb);
newComb.add(i, rank);
combinations.add(newComb);
}

for(int i = 0; i < comb.size(); i++) {
List<List<Integer>> newComb = deepcopy(comb);
newComb.get(i).add(p);
combinations.add(newComb);
}
}
base = combinations;
}
//print all ranking combinations. multi players in a same sublist makes a tie.
for(List<List<Integer>> ranks: base) System.out.println(ranks);
return base;
}

private static List<List<Integer>> deepcopy(List<List<Integer>> ls) {
List<List<Integer>> copy = new ArrayList<>();
for(List<Integer> sublist: ls) {
copy.add(new ArrayList<Integer>(sublist));
}
return copy;
}

- aonecoding November 03, 2017 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More