做了 6年 backend
地点在 Aachen, Germany
职位是SDE2
Procedure
Screening
- Online coding round on codility
- Recurter round
- Chime round {video conferencing }
上门 : 20-30 min Behavioural {including project discussion} + 20-30 min Technical
- Behavioural and Design {Teammate}
- Behavioural {Hiring Manager}
- Lunch
- Behavioural & DS & Algo {Video conferencing}
- Behavioural & DS & Algo {Bar Raiser- Other hiring Manager}
- Behavioural & DS & Algo {Other team colleague }
说下OA
Point of Lattice:
/**
* I'm assuming you mean that she moves in a straight line from A to B and then turns 90 degrees, and that the lattice is a Cartesian grid with the y axis pointing up and the x axis pointing right.
* Let (dx,dy) = (Bx,By)-(Ax,Ay), the vector from point A to point B.
* We can rotate this by 90 degrees to give (dy,-dx).
* After hanna turns right at B, she will head out along that rotated vector toward (Bx+dy,By-dx)
* Since she is moving in a straight line, her vector from B will follow (t.dy,-t.dx), and will hit another lattice point when both of those components are integers, i.e...
* She will hit another lattice point at: (Bx + dy/GCD(|dx|,|dy|), By - dx/GCD(|dx|,|dy|) )
*
* @param AX
* @param AY
* @param BX
* @param BY
* @return
*/
public String solution(int AX, int AY, int BX, int BY) {
int dx = BX - AX;
int dy = BY - AY;
int gcd = getGCD(Math.abs(dx), Math.abs(dy));
int x = BX + dy / gcd;
int y = BY - dx / gcd;
return "" + x + "," + y;
}
//GCD O(log(ab))
private int getGCD(int a, int b) {
if (b == 0)
return a;
return getGCD(b, a % b);
}
Bug fix
int binaryPeriod(int n) {
int[] d = new int[30];
int l = 0;
int p;
while (n > 0) {
d[l] = n % 2;
n /= 2;
l++;
}
for (p = 1; p <= l / 2; ++p) { // mistake 1+l
int i;
boolean ok = true;
for (i = 0; i < l - p; ++i) {
if (d[i] != d[i + p]) {
ok = false;
break;
}
}
if (ok) {
return p; //this find the smallest
}
}
return -1;
}
猎头店面
- why you looking for change,
- what you like to do.
- Would you relocate etc
店面
- Lots of behavioural question and project discussion
- Code: Similar to Word break problem {https://leetcode.com/problems/word-break/} . Instead, here we need to return the words as well.
我的解法:
public static List<String> wordBreakBack(String input, Set<String> dict) {
if (input == null || input.length() == 0)
return Collections.EMPTY_LIST;
LinkedList<String> vw = new LinkedList<>();
wordBreakBack(input, vw, dict);
return vw;
}
//IAM
static boolean wordBreakBack(String input, LinkedList<String> vw, Set<String> dict) {
if (input.isEmpty())
return true;
for (int i = 1; i <= input.length(); i++) {
String currentPrefix = input.substring(0, i);
if (dict.contains(currentPrefix)) {
vw.add(currentPrefix);
String remaining = input.substring(i);
if (wordBreakBack(remaining, vw, dict)) {
return true;
} else {
vw.removeLast();
}
}
}
return false;
}
Onsite : Face to Face 45 min to 1 hr
Face to Face 1: Behavioural and Design {Teammate)
- Lots of Behavioural question
- Project Deep discussion
- Design a Monitoring System for machine failure in a factory
Face to Face 2: Behavioural {Hiring Manager}
- Full hour discussion on behavioural questions. There were 10 questions at least. Full mind twist
Lunch
Face to Face 3: . Behavioural & DS & Algo {Video conferencing}
- Lots of Behavioural question
- Project discussion
- My involvement in project etc
- https://leetcode.com/problems/sliding-window-maximum/ with twist.
- Your api recieve order from a streaming process contains {id, quentity}
- The order rate of coming could be 1 to 100.
- You need to design an api to tell the maximum quentity to process in K time.
- Note: Sliding window maximum is for order rate 1.
- You need to extend this solution to work for a) streaming data 2) Order rate more than 1 {means more than 1 element can be drop at a moment from the window}
Face to Face 4: . Behavioural & DS & Algo {Bar Raiser- Other hiring Manager}
- Lots of Behavioural question
- https://leetcode.com/problems/integer-to-english-words/ Extend your solution to any length
class IntegerToEnglishWords2 {
private static final String[] LESS_THAN_20 = {"", "One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten", "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
private static final String[] TENS = {"", "Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
private static final String[] THOUSANDS = {"", "Thousand", "Million", "Billion"};
public static String numberToWords(int num) {
if (num == 0) return "Zero";
int i = 0;
StringBuilder words = new StringBuilder();
while (num > 0) {
if (num % 1000 != 0)
words.insert(0, numberToWordsLessThanOneThousand(num % 1000) + THOUSANDS[i] + " ");
num /= 1000;
i++;
}
return words.toString().trim();
}
private static String numberToWordsLessThanOneThousand(int num) {
if (num == 0)
return "";
else if (num < 20)
return LESS_THAN_20[num] + " ";
else if (num < 100)
return TENS[num / 10] + " " + numberToWordsLessThanOneThousand(num % 10);
else
return LESS_THAN_20[num / 100] + " Hundred " + numberToWordsLessThanOneThousand(num % 100);
}
}
Face to Face 5: . Behavioural & DS & Algo {Other team colleague }
- Lots of Behavioural question
- Given memory usage of process with start, end and memory usage of this process. Find the interval where the memory usage is maximum.
Input:
[4,8,19], [1,5,8], [2,8,10], [20,30,10]
Output:
[4,5] with 37 {[4,8,19], [2,8,10], [1,5,8] }
Input:
[4,8,19], [1,5,8], [2,8,10], [20,30,80]
Output:
[20,30] with 80 {[20,30,80] }
我的解法
public class PeakMemoryUsage {
public static void main(String[] args) {
boolean test = test(new int[][]{{4, 8, 19}, {1, 5, 8}, {2, 8, 10}, {20, 30, 10}}, new int[]{4, 5, 37})
&& test(new int[][]{{4, 8, 19}, {1, 5, 8}, {2, 8, 10}, {20, 30, 80}}, new int[]{20, 30, 80});
System.out.println("Tests :" + (test ? "Passed" : "Failed"));
}
private static boolean test(int[][] intervals, int[] expected) {
System.out.println("\nIntervals :" + GenericPrinter.toString(intervals));
System.out.println("Expected :" + GenericPrinter.toString(expected));
int[] obtained = peakMemoryUsage(intervals);
System.out.println("Obtained :" + GenericPrinter.toString(obtained));
return GenericPrinter.equalsValues(expected, obtained);
}
/**
* Algorithm:
* <p>
* Sort start times with an nlogn sorting algorithm and store it.
* Sort end times with an nlogn sorting algorithm and store it.
* <p>
* We traverse sorted start times and add to an accumulator,
* but after traversing one start time, we traverse as many end times as needed to "catch up"
* to the start time and we subtract that from the accumulator. Take the max of accumulator vs the current max at each traversal.
*
* @param intervals
* @return
*/
private static int[] peakMemoryUsage(int[][] intervals) {
if (null == intervals || intervals.length == 0)
return new int[0];
int n = intervals.length;
class Interval {
int id;
int memoryUsage;
int interval;
public Interval(int id, int memoryUsage, int interval) {
this.id = id;
this.memoryUsage = memoryUsage;
this.interval = interval;
}
}
//contains start time and its id
List<Interval> start = new ArrayList<>(n);
List<Interval> end = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
start.add(new Interval(i, intervals[i][2], intervals[i][0]));
end.add(new Interval(i, intervals[i][2], intervals[i][1]));
}
//Sort start times .
start.sort(Comparator.comparingInt(o -> o.interval));
//Sort end times .
end.sort(Comparator.comparingInt(o -> o.interval));
int maxMemory = 0;
int currentMemory = 0;
int si = -1;
int ei = -1;
int i = 0;
int j = 0;
while (i < n && j < n) {
int s = start.get(i).interval;
int e = end.get(j).interval;
if (s <= e) {
currentMemory += start.get(i).memoryUsage;
i++;
} else {
currentMemory -= end.get(j).memoryUsage;
j++;
}
if (currentMemory > maxMemory) {
maxMemory = currentMemory;
si = s;
ei = e;
}
}
return new int[]{si, ei, maxMemory};
}
}