Dsxv's blog

Interview Question Directed Graph — Doubt
By Dsxv, history, 4 years ago, In English

Hi Everyone!

I haven't been active lately because of interviews going on. Recently I appeared for Amazon Interview for Internship and there was a problem that I still have doubts with:

Problem

I confirmed with the interviewer that there is a formation of the cycle in this, he told me that cycle formation is possible and whenever it happens you have to break the chain there since you don't want to repeat the same elements

As you can see the graph is not an unweighted DAG, Hence, the problem became finding acyclic longest chain in a directed cyclic graph.

I wasn't able to come with a clear solution (O(n)) because it didn't feel right that how I can take care of cases with a cycle using maybe topological sort? So I wanted to ask what is the best possible complexity answer for this.

Thanks!

UPD: The problem might not even be of a graph, I have mentioned the original problem in the exact words as by the interviewer, not that you have to follow the graph approach, I just want to find any possible views on this.

UPD2: Got selected anyway lol :p

  • Vote: I like it
  • +17
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +2 Vote: I do not like it

There are only 26 vertices, so it may be possible to do a DFS for each vertex, using each edge at most once.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I don't think there are 26 vertices, all the strings can act as a vertex

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      take all the letters as a vertex, and connect all the starting and ending letters of each string with an edge equal to the length of that string.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
        ← Rev. 2   Vote: I like it +5 Vote: I do not like it

        So according to you, the maximum length is going to be 26, but there can be a simple example that can falsify that.

        Edit: sorry didn't read it perfectly but what is the purpose of weighing the edge as length of the string.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          Max number of vertices will be 26, edges will be of the order n, If I'm wrong can you please state the example.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Okay, I understand now, but how is this gonna simplify the question in any way, since we are just compressing into 26 vertices, there can be cases of multiple edges that need to be handled, if possible can you perhaps share a sample code. That would be very helpful, Thanks!

            → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    What about something like {abc, cba, abdc, cbda}, you will start at 'a' then you won't be able to visit 'a' again after vising 'c'

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes, I never said to not repeat the vertex, you should never repeat an edge (Like in an Euler Tour).

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I think we can do dp of some sort like in this problem

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It mentions there that it doesn't contain any directed cycle tho :p

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Considering every string as a vertex you can check before adding any edge if cycle will be formed or not after adding this edge, you shouldn't add edge if cycle is formed

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I am sorry, but then isn't our answer going to depend on the flow of dfs? Or is it independent of that?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          No, it won't be dependent, as i mentioned before this problem will be converted to this problem. You can watch this video for more clarifications.

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            the video doesn't clarify how the directed cyclic graph case is handled. Just for the record, solving for DAG is pretty straightforward so I don't have a problem with that.

            → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

If this was an interview question, then in the interviews, they often don't tell the complete problem to the candidate, and allow the candidate to ask questions and interact like —

What are the constraints of problem or questions like these.

Now, this might seem senseless, but, did you ask, that "what should I do (What value shall I return), in case the answer becomes infinite" ?

I guess, you yourself converted it into — "Find longest acyclic chain in the graph". Maybe, the formal problem was never, what you think.

I would have responded with — "For some graphs, the answer will be infinite, so Mr Interviewer, could you please tell me, what shall I return in that case?"

And, if it is not infinite, then answer will be max path length in an un-directed graph. And, to check, whether answer will be infinite or not, I can "detect if a cycle exists in the given graph"

If you did ask these questions, and the problem still translates to what you described above, then yes, its tricky ( But I still believe, that this might not be the case ).

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sorry for giving less info because I wanted to focus on the question. Yes I did, let me update my problem statement with that too.

    UPD: I most certainly realized it will get messy if I am going to solve this specific problem, that's why I spent almost 5 minutes confirming if this is what he wants. And he said that it can be done in O(n).

    → Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Somehow, the comment got posted twice, ignore

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Dsxv (previous revision, new revision, compare).

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

You can solve this problem using SCC and dynamic programming . See in the given graph there may be some scc which means you can reach to every other node in that scc . so count all the nodes in the scc and compress it into a single node .
After that apply dynamic programming .(which is not hard now) Here is the link to a similar problem.
I hope I understood your problem correctly .

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    I might be wrong, but I think you can repeat your path in this problem, just that coins will be added only once. This means SCC's value can be taken as a single value, however, in my problem you have to choose which path in SCC you have to take or if you should loop inside.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem is very much similar to the problem that came in the google kickstart round-H 2020... you may refer to that problem for a better solution.. link to the problem

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Sorry, the graph seems undirected in this case.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by Dsxv (previous revision, new revision, compare).

→ Reply