注册一亩三分地论坛，查看更多干货！
您需要 登录 才可以下载或查看附件。没有帐号？注册账号
x
Next-capital在线面试，分成三轮技术面(back-to-back)，总共持续了接近3小时，先是HR简单简单介绍了一下他们公司，然后在HackerRank平台上分享屏幕面试。
可以自己选择Java, python或者javascript语言编写，但不能选C++，他们公司不用C++。
第一轮，就一个题，按照保龄球的评分标准计算总分，比较有特点的是面试官注重test-driven development，先写测试用例再写实现的代码。
每次先写简单一些的test case，然后按照这个test case写出相应的实现代码，不需要一次性考虑所有情况。在满足这个test case的基础上再设计更复杂、特殊情况的test case，再完善实现代码。
Build an implementation to score a game of bowling, using test-driven development.
A game of bowling has 10 frames. Each frame has 2 rolls, except the 10th frame, which can have a bonus third roll depending on the first or second roll.
The goal is to knock down all 10 pins in each frame. Bowling a strike means all 10 pins are knocked down in the first roll of the frame. A spare means it took 2 rolls to knock down all 10.
Bowling a strike gives you 10 points + the next 2 rolls as a bonus.
Bowling a spare gives you 10 points + the next roll as a bonus.
There are no bonuses for strikes or spares in the 10th frame.
Sample game:
[
'3', '4',
'X', '0',
'8', '1',
'5', '/',
'6', '2',
'X', '0',
'X', '0',
'7', '1',
'1', '/',
'6', '/', 'X'
]
Notes:
The game is an array of strings, always of length 21 (all possible rolls).
Strikes are indicated with 'X'.
Spares are indicated with '/'.
以下是代码，面试时先给出了大部分框架，要自己写出核心函数和测试用例：
import java.lang.annotation.*;
import java.lang.reflect.*;
import java.io.*;
import java.util.*;
import java.math.*;
import java.util.regex.*;
@Target(ElementType.METHOD)
@Retention(RetentionPolicy.RUNTIME)
@interface Test {}
public class BowlingScorer {
// Given a frame and array of scores, determines if a strike occurred
private boolean wasAStrike(int frame, String[] scores) {
return "X" == scores[(2*frame)-2];
}
// Given a frame and array of scores, determines if a spare occurred
private boolean wasASpare(int frame, String[] scores) {
return "/" == scores[(2*frame)-1];
}
// Given a frame and array of scores, returns the score for the rolls within that frame
private int getFrameScore(int frame, String[] scores) {
if (wasAStrike(frame, scores) || wasASpare(frame, scores)) {
return 10;
} else {
return Integer.parseInt(scores[(2*frame)-1], 10) + Integer.parseInt(scores[(2*frame)-2], 10);
}
}
// Given a frame and array of scores, return the score for the first roll of that frame
private int getFirstRoll(int frame, String[] scores) {
if (wasAStrike(frame, scores)) {
return 10;
} else {
return Integer.parseInt(scores[(2*frame)-2], 10);
}
}
// Given a frame and array of scores, returns the cumulative score up to the frame.
// The array contains 1 score for each roll - it should be of length 21.
public int getScore(int frame, String[] scores) {
int i, sum=0;
for (i=1; i<=frame; i++){
if (wasAStrike(i, scores) && i<10){
sum+=10;
if (!wasAStrike(i+1, scores)){
sum+=getFrameScore(i+1, scores);
} else { // next frame is a strike
// for the 9th frame, it would be different
if (i==9){
if (scores[18]=="X"){
sum+=10;
if (scores[19]=="X"){
sum+=10;
} else {
sum+=Integer.valueOf(scores[19]); // the scores[19] cannot be '/' if scores[18]=='X'
}
} else {
sum+=getFrameScore(10, scores);
}
continue;
}
sum+=10;
sum+=getFirstRoll(i+2, scores);
}
} else if (wasASpare(i, scores) && i<10){
sum+=10;
sum+=getFirstRoll(i+1, scores);
} else if (i<10){
sum+=getFrameScore(i, scores);
} else { //i==10
if (!wasAStrike(10, scores) && !wasASpare(10, scores) ){
sum+=getFrameScore(10, scores);
} else if (wasAStrike(10, scores)){
sum+=10;
if (scores[19]=="X"){
sum+=10;
} else if (scores[20]=="/"){
sum+=10;
return sum;
}
else sum+=Integer.valueOf(scores[19]); // it cannot be "/" for scores[19]
if (scores[20]=="X"){
sum+=10;
} else sum+=Integer.valueOf(scores[20]);
} else if (wasASpare(10, scores)){
sum+=10;
if (scores[20]=="X"){
sum+=10;
} else if (scores[20]=="/"){
sum+=10;
} else {
sum+=Integer.valueOf(scores[20]);
}
}
}
// System.out.println("line "+i+" sum:"+sum);
}
return sum;
}
@Test
public static void itShouldReturnZeroForAllGutterBalls() {
runTest(
1,
new String[] {"0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0"},
0
);
}
@Test
public static void itShouldHaveMoreTests() {
runTest(
10,
new String[] {"3", "4", "X", "0", "8", "1", "5", "/", "6", "2", "X", "0", "X", "0", "7", "1", "1", "/", "6", "/", "X"},
148
);
};
@Test
public static void itShouldHave10thTest() {
runTest(
10,
new String[] {"3", "4", "X", "0", "8", "1", "5", "/", "6", "2", "X", "0", "X", "0", "7", "1", "1", "/", "X", "X", "6"},
158
);
};
@Test
public static void itShouldHave10thTest2() {
runTest(
10,
new String[] {"0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "/", "4", "3", "X"},
21
);
};
@Test
public static void itShouldHave10thTest3() {
runTest(
10,
new String[] {"0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "X", "0", "X", "3", "X"},
46
);
};
@Test
public static void itShouldHave10thTest4() {
runTest(
10,
new String[] {"0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "5", "/", "4", "/", "1"},
25
);
};
@Test
public static void itShouldHave10thTest5() {
runTest(
10,
new String[] {"0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "5", "/", "X", "3", "/"},
40
);
};
@Test
public static void itShouldHave10thTest6() {
runTest(
10,
new String[] {"0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "0", "X", "0", "3", "2", "0"},
20
);
};
@Test
public static void itShouldHave10thTest7() {
runTest(
10,
new String[] {"X", "0", "X", "0","X", "0", "X", "0","X", "0", "X", "0", "X", "0","X", "0", "X", "0","X", "X", "X"},
300
);
};
// IGNORE EVERYTHING BELOW THIS LINE
private static Method currentTest;
public static void runTest(int frame, String[] scores, int expectedScore) {
int score = new BowlingScorer().getScore(frame, scores);
if (score != expectedScore) {
System.out.println(currentTest.getName());
System.out.println(" Input: " + Arrays.toString(scores));
System.out.println(" Output: " + score);
System.out.println(" Expected: " + expectedScore);
System.out.println();
}
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String countString = in.nextLine().trim();
if (countString.equals("candidate")) {
for (Method test : BowlingScorer.class.getDeclaredMethods()) {
for (Annotation annotation : test.getAnnotations()) {
if (annotation instanceof Test) {
try {
BowlingScorer.currentTest = test;
test.invoke(null);
} catch(IllegalAccessException e) {
// Don't care
} catch(InvocationTargetException e) {
System.out.println(currentTest.getName() + " threw an exception\n");
System.err.println(currentTest.getName());
e.getCause().printStackTrace();
System.err.println();
} finally {
break;
}
}
}
}
System.out.println("Done");
} else {
int count = Integer.parseInt(countString);
String[] scores = new String[count];
for (int i = 0; i < count; i++) {
scores[i] = in.nextLine().trim();
}
int score = new BowlingScorer().getScore(10, scores);
System.out.println(score);
}
}
}
第二轮，两个题，先写代码然后面试官让简单分析一下复杂度。
Sliders
You are provided with a function called "slide" that takes an array of Slider instances. An instance of a Slider has a value property, which is an integer.
Your task is to write the implementation of the function. Your implementation should modify the array in place, and result in Sliders with a value of zero being at the end of the array, and Sliders with a non-zero value being at the start of the array, with their original relative order preserved.
Your implementation should use O(1) auxiliary space.
Add your own test cases to the provided harness. You can write tests first if you prefer.
Example
Say an array has instances of Slider with values of (in order):
[1, 0, 3, 2, 0, 4]
After calling the slide function with the array, the array should have instances of Slider with values of (in order):
[1, 3, 2, 4, 0, 0]
代码：
import java.util.*;
public class Solution {
// Do not modify
public static class Slider {
private final int value;
public Slider(int value) {
this.value = value;
}
public int getValue() {
return value;
}
@Override
public String toString() {
return Integer.toString(value);
}
}
public static void slide(Slider[] array) {
// Implement me
int pos1=0, pos2;
Slider tmp;
pos2=0;
while (pos1<array.length){
if (array[pos1].getValue()==0){
while (pos2<array.length && array[pos2].getValue()==0) pos2++;
if (pos2>=array.length) return;
tmp=array[pos2];
array[pos2]=array[pos1];
array[pos1]=tmp;
pos1++;
} else {
pos1++;
pos2++;
}
}
}
public static Test[] getTests() {
return new Test[] {
// Example test
// These arrays of integers will automatically be converted
// to and from instances of Slider for you
new Test(
new int[] { 1, 2, 3 }, // Initial values of the Slider instances
new int[] { 1, 2, 3 } // Expected values of the Slider instances
),
// Add more tests here by following the above example
new Test(
new int[] { 1, 2, 3 }, // Initial values of the Slider instances
new int[] { 1, 2, 3 } // Expected values of the Slider instances
),
new Test(
new int[] { 0 }, // Initial values of the Slider instances
new int[] { 0 } // Expected values of the Slider instances
),
new Test(
new int[] { 0, 0, 0, 0, 0 }, // Initial values of the Slider instances
new int[] { 0, 0, 0, 0, 0 } // Expected values of the Slider instances
),
new Test(
new int[] { 0, 1, 0, 3, 0, 4, 0 }, // Initial values of the Slider instances
new int[] { 1, 3, 4, 0, 0, 0, 0 } // Expected values of the Slider instances
),
new Test(
new int[] { 0, 1, 0, 3, 0, 4, 3, 4, 10, 0, 0, 0, 9 }, // Initial values of the Slider instances
new int[] { 1, 3, 4,3,4,10, 9, 0,0,0,0,0,0 } // Expected values of the Slider instances
)
};
}
//
// IGNORE EVERYTHING BELOW
//
private static class Test {
private int[] initialValues;
private int[] expectedValues;
public Test(int[] initialValues, int[] expectedValues) {
this.initialValues = initialValues;
this.expectedValues = expectedValues;
}
public int[] get您好！
本帖隐藏的内容需要积分高于 188 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式 游客，您好！ 本帖隐藏的内容需要积分高于 188 才可浏览 您当前积分为 0。 VIP即刻解锁阅读权限 或 查看其他获取积分的方式
rightHalf[i] = strings[mid + i];
}
return new String[][]{ leftHalf, rightHalf };
}
static String[] merge(String[] left, String[] right) {
if (left.length == 0) {
return right;
} else if (right.length == 0) {
return left;
} else if (left[0].compareTo(right[0]) < 0) {
String[][] arrays = pluckFirst(left);
String[] firstLeft = arrays[0];
String[] newLeft = arrays[1];
return concatArrays(firstLeft, merge(newLeft, right));
} else {
String[][] arrays = pluckFirst(right);
String[] firstRight = arrays[0];
String[] newRight = arrays[1];
return concatArrays(firstRight, merge(left, newRight));
}
}
static String[][] pluckFirst(String[] strings) {
String[] first;
first = new String[1];
first[0] = strings[0];
String[] rest;
if (strings.length > 1) {
rest = new String[strings.length - 1];
for(int i = 1; i < strings.length; i++) {
rest[i-1] = strings[i];
}
} else {
rest = new String[0];
}
return new String[][]{first, rest};
}
static String[] concatArrays(String[] first, String[] second) {
int length = first.length + second.length;
String[] result = new String[length];
for(int i = 0; i < first.length; i++) {
result[i] = first[i];
}
for(int i = 0; i < second.length; i++) {
int index = first.length + i;
result[index] = second[i];
}
return result;
}
static String[] rejiggerArray(String[] strings) {
String[] output = mergeSort(strings);
List<String> resultList = new LinkedList<String>();
for (int i = 1; i < output.length-1; i++) {
// System.out.println("The "+i+"-th string:"+ output[i]);
char[] chars = output[i].toCharArray();
List<Character> charList = new ArrayList<Character>();
for(int j = 0; j < chars.length; j++) {
if (j == 0) {
charList.add(chars[0]);
continue;
}
if(chars.length % j != 0) {
charList.add(chars[j]);
}
}
StringBuilder result = new StringBuilder(charList.size());
for (Character c : charList) {
result.append(c);
}
resultList.add(result.toString());
}
return resultList.toArray(new String[resultList.size()]);
}
public static void main(String[] args) throws IOException {
Scanner in = new Scanner(System.in);
final String fileName = System.getenv("OUTPUT_PATH");
BufferedWriter bw = new BufferedWriter(new FileWriter(fileName));
String[] res;
int _strings_size = 0;
_strings_size = Integer.parseInt(in.nextLine().trim());
String[] _strings = new String[_strings_size];
String _strings_item;
for(int _strings_i = 0; _strings_i < _strings_size; _strings_i++) {
try {
_strings_item = in.nextLine();
} catch (Exception e) {
_strings_item = null;
}
if (_strings_item.equals("%")) {
_strings_item = "";
}
_strings[_strings_i] = _strings_item;
}
res = rejiggerArray(_strings);
for(int res_i=0; res_i < res.length; res_i++) {
if (res[res_i].equals("")) {
res[res_i] = "%";
}
bw.write(String.valueOf(res[res_i]));
bw.newLine();
}
bw.close();
}
}
|
狗仔卡
提升卡
置顶卡
关贴卡
开贴卡
变色卡
千斤顶
楼主
