Cryptic Studio 家OA,题目不多质量不错,可看可学

原帖地址:一亩三分地

这个公司的OA题好像从来不会变,他们家OA面经其实之前在地里被发过了(http://www.1point3acres.com/bbs/forum.php?mod=viewthreadtid=139479highlight=cryptic),不过版面有点不清晰,我就把重要的再发一遍好了。第二题想看更多的 test case 可以点那个链接看。

OA里只有两道题,难度中等,要求5小时做出来,但是事实长代码写的顺手的话不需要那么久。我第一道题花了半个多小时,第二道题一个半小时,这都是包括debug的时间。
之前看网上大家聊起的说5个小时做不完,有点被吓到,但是其实不难。我昨天提交的,今天上午就通知过了,现已安排phone interview下下周,结束后再来发面经给大家!
(如果5个小时写不出,那其实还需要训练自己的码能力)

1. Write a function that accepts a string of digits and a target value as input parameters. This function should output the two input values followed by a string with +’s and *’s between the digits so the result of evaluating the mathematical expression is the target value. Pay attention to operator precedence. Note there may be more than one answer, it doesn’t matter which one you print.

Examples:
“1231231234”,11353 -> “12*3+1+23*123*4″
“3456237490”,1185 -> “3*4*56+2+3*7+490″
“3456237490”,9191 -> “no solution”

挺简单的回溯,对每个字符后面可能存在:不操作,插入+,插入* 一共三种情况,操作完算一算。
需要注意一下溢出的情况,除此之外没啥别的

2. Write a function “void link(char **tiles)” that accepts a list of ’tiles’ in the provided format below. It should link the tiles together sequentially in the order they are given, and print out the current count and arrangement of tiles at each step exactly as shown in the example output below, including the note about how far the tile had to be rotated.

A tile is a 2-by-2 square split into quadrants, where each quadrant has a number from 0 to 9. After the first tile, a tile can be legally placed if at least two of its quadrants match quadrants on adjacent tiles horizontally or vertically. A tile cannot be legally placed in a location if it would have fewer than two matching quadrants or has any quadrants that do not match horizontally or vertically. Tiles can be rotated, and tiles can be placed in offset positions as demonstrated with tile 9 in the third example. The inputs are always designed so there is only one place a tile will fit.

看上去难其实非常简单,每个tile测试一下能放哪里就好了,测试过程中需要旋转一下(旋转的函数相当简单吧),放好了就停止搜索,然后打印一下当前的board

Examples:
char *tiles1[] = {
“11”, // 1
“23”,
“”,
“44”, // 2
“11”,
“”,
“16”, // 3
“36”,
“”,
“51”, // 4
“71”,
“”,
“46”, // 5
“26”,
“”,
“14”, // 6
“68”,
0};

link(tiles1) prints:

6 tiles
link 1
11
23

link 2
44
11
11
23

link 3
44
11
1116
2336

link 4
44
5111
711116
2336

link 5 // note this tile had to be rotated 180 degrees clockwise
44
5111
71111662
233664

link 6 // note this tile had to be rotated 270 degrees clockwise
4448
511116
71111662
233664