这题就好像一组火车时刻表，问能不能从某站到某站

I am given an array of Transactions in a ledger. A Transaction object has three things.

• Sender (which means who started this transaction)
• Receiver (means who is the destination of transaction)
• Timestamp (at what time this transaction was executed)
  

Now I need to write a method findIfTransactionIsValid() which will have the array of all transactions, one sender, one receiver. A transaction is valid is following cases:

• if sender and receiver are same
• The timestamp should be increasing (what I mean here is if A -> B happens at Time 2 and B-> C happens at Time 1, then A->C is not a valid transaction, however if B -> C happens at Time 3 then A --> C is a valid transaction)
  

Example:
Transaction
{
  Sender -> Receiver (Timestamp)
}

Example: [T is timestamp here]

1. A -> B (T=0)
   
2. B -> C (T=1)
   
3. C -> F (T=0)

复制代码

findIfTransactionIsValid(A, C) -> this should return true
findIfTransactionIsValid(B, F) -> false (time is backwards)

步惊云 发表于 2019-2-20 10:33
没什么太多想法, bfs吧. node上存到下一个node的不同时间.

差不多算single source (shortest) path那种 ...

这题随着时间的变化，edges会发生变化。觉得bfs和dfs都可以。针对楼顶的问题，
- 需要对每个node的edges用时间进行排序。方便搜索哪些边可以走
- 如果有环visited过了就不必再计算了。

问题的followup会有很多种。见过的面经里有的是：

从点A到点Z最早的到达时间，应该是dijkstra。

能到达点Z的最晚从A点出发时间。我的想法是每个node的edges用时间倒序。从A的最晚的时间开始DFS。每个node需要记录哪些边已经走过以避免重复计算。这样如果A最晚的不行，倒数第二晚的再计算就不必计算已经测试过的边了。

不知还有无其它followups。

可能还有：从点A开始必须经过点C有没有到达点Z的可能