去哪儿2018秋招笔试编程题

题目

1、日本旅行

题目描述：

楚乔、宇文玥和燕洵在日本旅行，经过了几天的游玩之后，钱包里出现了大量硬币，楚乔决定用钱包里的硬币为宇文玥和燕洵在自动贩卖机买水。楚乔的钱包里有1元、5元、10元、50元、100元和500元硬币各C1,C5,C10,C50,C100,C500枚。现在要用这些硬币来到自动贩卖机买价格为A的饮料，假设自动贩卖机所需的硬币金额必须是刚刚好，不能多也不能少，最少需要多少枚硬币？

限制条件

0<= C1,C5,C10,C50,C100,C500<=1000000000

0<=A<=1000000000

依次输入 C1,C5,C10,C50,C100,C500和A，以空格分隔，输出最少所需硬币数，如果该金额不能由所给硬币凑出，则返回NOWAY

输入

依次输入 C1,C5,C10,C50,C100,C500和A，以空格分隔

输出

输出最少所需硬币数，如果该金额不能由所给硬币凑出，则返回NOWAY

样例输入

3 2 1 3 0 2 620

样例输出

6

2、带权的DAG节点排序

题目描述：

DAG 即 Directed Acyclic Graph, 有向无环图. 用DAG可以描述一些有依赖关系的任务组, 而这些任务还有另外一个属性, 即都有一个权重, 标示这个任务的重要性.

我们需要你来实现一个算法, 对DAG里面的节点进行排序, 保证排序不违背DAG的依赖关系, 即一个任务A如果排在任务B前面, 那么在DAG中不能存在由B 到A的路径. 另外一个要求就是, 让权重大的任务尽量优先执行.

输入

在第一行给定 DAG的节点数n和边数e.

后面n行, 每一行是 节点的 标号和权重, seq weight.

最后e行, 每一行是对于边的描述, s t.

输出

排序好的节点标号, 在一行内输出, 空格隔开.

样例输入

4 4

1 2

2 3

3 5

4 4

1 2

1 3

2 4

3 4

样例输出

1 3 2 4

题目描述：

LRU全称是Least Recently Used, LRU Cache的核心设计思想是, 如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小。 在cache大小固定的情况下, 如果cache满了, 会把最近最久没有访问的元素删掉.

实现程序禁用各种语言基础库中的LinkedHashMap.

输入

在第一行给定cache的大小 m, 对cache执行读写操作的次数n.

从第二行开始, 有n行操作命令.

操作有两种情况, put和get.

put命令格式是 put key value, 表示向cache写入数据.

get命令格式是 get key, 标示从cache读取数据.

输出

对于n行命令中的每一行get 命令.

如果对于数据存在, 就把value在单独一行打印出来.

如果不存在, 就在单独一行打印null. 

样例输入

3 5

put a b

put x y

put d kkk

put zzz lll

get a

样例输出

null

Hint

直接在输入的时候进行判断即可