package com;
// 注意: 题目有四道, 请认真仔细读题,
// 如果有不理解的地方, 请联系 HR 或面试官,
// 如果有不会的, 请留空, 不要求做完, 不要盲目答题.
import java.util.*;
import java.util.concurrent.*;
import java.util.function.Function;
import java.util.function.Supplier;
/**
* Q1: 加权随机函数生成器
* <p>
* 给定一个正整数数组 input, 构造一个加权随机类实例,
* 该实例的 {@link #next()} 方法被调用时, 随机返回一个该数组的下标, 下标 i 被返回的概率
* 为该下标对应的元素的值 / 所有元素之和.
* <p>
* 要求: {@link #next()} 方法的时间复杂度不超过 O(log(N))
*/
class WeightedRandom {
private int sum;
private Random random;
private TreeMap<Integer, Integer> treeMap = new TreeMap<>();
public WeightedRandom(int[] input) {
//init
int len = input.length;
for (int i = 0; i < len; i++) {
sum += input[i];
//current sum, index
treeMap.put(sum, i);
}
random = new Random();
}
public int next() {
// use treemap, search target key in O(log(N))
final Map.Entry<Integer, Integer> higherEntry = treeMap.higherEntry(random.nextInt(sum));
return higherEntry.getValue();
}
}
/**
* Q2: 字符跳动
* <p>
* 给定一个由不重复的小写字母组成的字符串，通过一系列跳动指令变换成一个新的字符串。
* 跳动指令有：
* * Move(移动)，简写：M，例如：M:7 表示将字符串向右移动7位。
* * eXchange(交换)，简写：X，例如：X:a/c 表示将字符串中的 a c 位置交换。
* * IndexChange(按位置交换)，简写：I，例如：I:2/4 表示将位置2和位置4的字符交换，位置的索引从0开始计数。
* 示例：
* 给定初始字符串为：wosjgncxyakdbefh
* 给定如下指令：
* M:3 则变换后的新字符串为：efhwosjgncxyakdb
* I:7/2 则变换后的新字符串为：efgwosjhncxyakdb
* X:o/h 则变换后的新字符串为：efgwhsjoncxyakdb
* 因此给定初始字符串：wosjgncxyakdbefh，在经过指令 M:3,I:7/2,X:o/h 的变换后得到新的字符串：efgwhsjoncxyakdb。
*/
class CharDance {
private String OP_TMP = "-";
/**
* 题目1：
* 给定一个随机的初始字符串: src，给定一组随机的指令: ops，(src 和 ops 一定是合法的)，求经过转换后得到的新字符串。
* 思路
* 1、根据指令前缀做不同的操作，将操作结果返回
* 2、封装不同的指令操作方法
*/
public String transfer(String src, String ops) {
//src ops is valid, dont'check here
final String[] opsArr = ops.split(",");
String result = src;
for (String op : opsArr) {
final String[] operator = op.split(":");
String opt = operator[0];
String opv = operator[1];
switch (opt) {
case "M":
result = opM(result, opv);
break;
case "I":
result = opI(result, opv);
break;
case "X":
result = opX(result, opv);
break;
default:
break;
}
}
return result;
}
/**
* 题目2：
* 将上一次转换后得到的新字符串作为初始字符串，使用相同的跳动指令集再进行转换，如此重复执行 count 次，求得到的最终字符串是什么？
* 注意: count 足够大, 比如可能超过 2^32.
*/
public String transferMultipleTimes(String src, String ops, long count) {
List<String> resutList = new ArrayList<>();
long period = 0;
for (long i = 0; i < count; i++) {
src = transfer(src, ops);
if (resutList.contains(src)) {
period = i;
break;
}
resutList.add(src);
}
if (period > 0) {
return resutList.get((int) ((count - 1) % period));
}
return src;
}
/**
* 例如：M:7 表示将字符串向右移动7位。
*
* @param src
* @param opv
* @return
*/
private String opM(String src, String opv) {
final int index = src.length();
int move = Integer.parseInt(opv) % index;
if (move == 0) {
return src;
}
int moveIndex = index - move;
final String prefix = src.substring(0, moveIndex);
final String moveStr = src.substring(moveIndex);
return moveStr + prefix;
}
/**
* 例如：I:2/4 表示将位置2和位置4的字符交换，位置的索引从0开始计数。
*
* @param src
* @param opv
* @return
*/
private String opI(String src, String opv) {
String[] split = opv.split("/");
int firstIdx = Integer.parseInt(split[0]);
int secondIdx = Integer.parseInt(split[1]);
if (firstIdx == secondIdx) {
return src;
}
final char[] chars = src.toCharArray();
//exchange char
char firstCh = chars[firstIdx];
chars[firstIdx] = chars[secondIdx];
chars[secondIdx] = firstCh;
return new String(chars);
}
/**
* 例如：X:a/c 表示将字符串中的 a c 位置交换。
*
* @param src
* @param opv
* @return
*/
private String opX(String src, String opv) {
String[] split = opv.split("/");
String firstChar = split[0];
String secondChar = split[1];
//not exist repeat char
// if (firstChar.equals(secondChar)) {
// return src;
// }
src = src.replaceAll(firstChar, OP_TMP);
src = src.replaceAll(secondChar, firstChar);
src = src.replaceAll(OP_TMP, secondChar);
return src;
}
}
/**
* Q3: 并发任务控制器
* <p>
* 注意: 不可使用 java 提供的线程池相关接口
*/
class AsyncWorker {
private volatile int capacity;
private volatile int RUNNING = 0;
BlockingQueue<Runnable> workQueue = new LinkedBlockingQueue<>();
private final HashSet<Worker> workers = new HashSet<Worker>();
Map<Integer, Integer> map = new HashMap<Integer,Integer>();
/**
* 构造函数
*
* @param capacity 最大并发数量
*/
public AsyncWorker(int capacity) {
// show me your code
this.capacity = capacity;
}
/**
* 任务提交函数: 当前正在执行的任务数小于 capacity 时, 立即异步执行, 否则
* 等到任意一个任务执行完成后立即执行.
*
* @param task 任务函数
* @param <T> 返回值类型
* @return 返回由 Future 包装的任务函数的返回值, 其状态应该和 task 的执行结果一致
*/
public <T> Future<T> submit(Callable<T> task) {
if (task == null) throw new NullPointerException();
RunnableFuture<T> ftask = newTaskFor(task);
execute(ftask);
return ftask;
// show me your code
}
protected <T> RunnableFuture<T> newTaskFor(Callable<T> callable) {
return new FutureTask<T>(callable);
}
private <T> void execute(RunnableFuture<T> ftask){
if (RUNNING < capacity) {
if (addWorker(ftask))
return;
}
addWorker(ftask);
return;
}
private boolean addWorker(Runnable firstTask) {
for (; ; ) {
if (RUNNING >= capacity)
return false;
RUNNING++;
break;
}
boolean workerStarted = false;
boolean workerAdded = false;
Worker w = null;
try {
w = new Worker(firstTask);
final Thread t = w.thread;
if (t != null) {
try {
workers.add(w);
workerAdded = true;
} finally {
}
if (workerAdded) {
t.start();
workerStarted = true;
}
}
} finally {
}
return workerStarted;
}
private final class Worker
implements Runnable
{
/**
* This class will never be serialized, but we provide a
* serialVersionUID to suppress a javac warning.
*/
private static final long serialVersionUID = 6138294804551838833L;
/** Thread this worker is running in. Null if factory fails. */
final Thread thread;
/** Initial task to run. Possibly null. */
Runnable firstTask;
/** Per-thread task counter */
volatile long completedTasks;
/**
* Creates with given first task and thread from ThreadFactory.
* @param firstTask the first task (null if none)
*/
Worker(Runnable firstTask) {
this.firstTask = firstTask;
this.thread = new Thread(this);
}
/** Delegates main run loop to outer runWorker */
public void run() {
runWorker(this);
}
}
final void runWorker(Worker w) {
Thread wt = Thread.currentThread();
Runnable task = w.firstTask;
w.firstTask = null;
boolean completedAbruptly = true;
try {
while (task != null || (task = getTask()) != null) {
try {
Throwable thrown = null;
try {
task.run();
} catch (RuntimeException x) {
thrown = x; throw x;
} catch (Error x) {
thrown = x; throw x;
} catch (Throwable x) {
thrown = x; throw new Error(x);
} finally {
}
} finally {
task = null;
w.completedTasks++;
}
}
completedAbruptly = false;
} finally {
workers.remove(w);
RUNNING--;
}
}
private Runnable getTask() {
boolean timedOut = false; // Did the last poll() time out?
for (;;) {
try {
Runnable r = workQueue.take();
if (r != null)
return r;
timedOut = true;
} catch (InterruptedException retry) {
timedOut = false;
}
}
}
}
/* ----------------- 以下是测试用例 -----------------*/
class TestWeightedRandom {
public static void testWeightedRandom(Function<int[], WeightedRandom> factory) {
//0--4--6--7--10--13
// 4 -2 - 1- 3 - 3
int[] input = {4, 2, 1, 3, 3};
WeightedRandom random = factory.apply(input);
int[] count = new int[input.length];
for (int i = 0; i < 10000; i++) {
int v = random.next();
if (v < 0 || v >= input.length) {
throw new RuntimeException("invalid random value: " + v);
}
count[v]++;
}
int sum = Arrays.stream(input).sum();
for (int i = 0; i < input.length; i++) {
double expectedWeight = (double) input[i] / (double) sum;
double realWeight = (double) count[i] / 10000D;
if (Math.abs(expectedWeight - realWeight) > 0.01) {
throw new RuntimeException(
"invalid weight " + realWeight + " for index " + i + ", expected is " + expectedWeight
);
}
}
}
}
class TestCharDance {
public static void testCharDance(Supplier<CharDance> factory) {
CharDance charDance = factory.get();
String src = "wosjgncxyakdbefh";
String ops = "M:3,I:7/2,X:o/h";
String dst = "efgwhsjoncxyakdb";
String realDst = charDance.transfer(src, ops);
if (!dst.equals(realDst)) {
throw new RuntimeException("invalid transfer result " + realDst + ", expected is " + dst);
}
String dst100 = src;
for (int i = 0; i < 127; i++) {
dst100 = charDance.transfer(dst100, ops);
}
String realDst100 = charDance.transferMultipleTimes(src, ops, 127);
if (!dst100.equals(realDst100)) {
throw new RuntimeException("invalid transfer result " + realDst100 + " after 100 times, expected is " + dst100);
}
}
}
class TestAsyncWorker {
private static AsyncWorker worker;
private static List<Task> tasks;
public static void testAsyncWorker(Function<Integer, AsyncWorker> factory) {
worker = factory.apply(2);
tasks = new ArrayList<>();
runTask(1, 100, 100, false);
runTask(2, 200, 200, true);
runTask(3, 300, 400, false);
runTask(4, 400, 600, true);
runTask(5, 100, 500, false);
runTask(6, 200, 700, true);
runTask(7, 100, 700, false);
runTask(8, 200, 900, false);
for (Task task : tasks) {
check(task);
}
}
private static void runTask(int id, int delay, int expectedDelay, boolean fail) {
Task task = new Task();
task.id = id;
task.expectedDelay = expectedDelay;
task.fail = fail;
long now = System.currentTimeMillis();
task.value =
worker.submit(() -> {
try {
Thread.sleep(delay);
} catch (InterruptedException ignored) {
}
long realDelay = System.currentTimeMillis() - now;
if (fail) {
throw new RuntimeException(String.valueOf(realDelay));
} else {
return (int) realDelay;
}
});
tasks.add(task);
}
private static class Task {
private int id;
private int expectedDelay;
private boolean fail;
private Future<Integer> value;
}
private static void check(Task task) {
int realDelay;
boolean realFail = false;
try {
realDelay = task.value.get();
} catch (Exception e) {
realDelay = Integer.parseInt(e.getCause().getMessage());
realFail = true;
}
if (realFail != task.fail) {
throw new RuntimeException(
"status of task " +
task.id +
" should be " +
(task.fail ? "failed" : "succeeded") +
", rather than " +
(realFail ? "failed" : "succeeded")
);
}
// 忽略延时误差
if (realDelay / 100 != task.expectedDelay / 100) {
throw new RuntimeException(
"delay of task " + task.id + " should be " + task.expectedDelay + ", rather than " + realDelay
);
}
}
}
public class ShowMeBug {
public static void main(String[] args) {
TestWeightedRandom.testWeightedRandom(WeightedRandom::new);
TestCharDance.testCharDance(CharDance::new);
TestAsyncWorker.testAsyncWorker(AsyncWorker::new);
}
}
标签：src,task,String,答题,int,宠物,SAAS,private,new From： https://www.cnblogs.com/quyf/p/17050864.html