Programming interview question- Path Finding

  • (2 Pages)
  • +
  • 1
  • 2

16 Replies - 2619 Views - Last Post: 18 July 2015 - 02:05 PM Rate Topic: -----

#1 Dev747   User is offline

  • New D.I.C Head

Reputation: -2
  • View blog
  • Posts: 19
  • Joined: 08-July 15

Programming interview question- Path Finding

Posted 17 July 2015 - 12:56 PM

I recently had a programming interview which required to write code for the following problem and which I was unable to do so. Please help with possible solutions.

Problem :
A person wants to travel from one point to another where A is the source point and D is the destination point. The inputs to the problem consisted of paths to be traversed while traversing from source to destination as follows :
B-->C
A-->B
C-->D
( The input paths are to be considered in these orders only)

The aim is to give correct sequence of paths which is as follows :
A-->B
B-->C
C-->D

The interviewer gave hint that in the correct sequence of paths ( A-->B , B-->C , C-->D ), the end point of the 1st path is the start point of the 2nd path and the end point of the 2nd path is the start point of the 3rd path. To achieve this correct sequence we have to use data structures like multi-dimensional array.

This post has been edited by macosxnerd101: 17 July 2015 - 01:26 PM
Reason for edit:: Renamed title to be more descriptive


Is This A Good Question/Topic? 0
  • +

Replies To: Programming interview question- Path Finding

#2 modi123_1   User is offline

  • Suitor #2
  • member icon



Reputation: 15677
  • View blog
  • Posts: 62,769
  • Joined: 12-June 08

Re: Programming interview question- Path Finding

Posted 17 July 2015 - 12:57 PM

What have you tried or considered?
Was This Post Helpful? 0
  • +
  • -

#3 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12735
  • View blog
  • Posts: 45,923
  • Joined: 27-December 08

Re: Programming interview question- Path Finding

Posted 17 July 2015 - 01:22 PM

It might be worth looking into graph theory and path finding algorithms. Breadth-first and depth-first algorithms are good starting points.

Figuring out how to model a graph is important as well. More on representing graphs and designing a graph data structure.

Of course, in this case, it should be a fairly simple matter of using a HashMap.
Was This Post Helpful? 0
  • +
  • -

#4 SleepingInsomniac25   User is offline

  • New D.I.C Head

Reputation: 14
  • View blog
  • Posts: 46
  • Joined: 15-July 15

Re: Programming interview question- Path Finding

Posted 17 July 2015 - 03:32 PM

I think I know your problem.. Are you using a Scanner for input?
Was This Post Helpful? 0
  • +
  • -

#5 SleepingInsomniac25   User is offline

  • New D.I.C Head

Reputation: 14
  • View blog
  • Posts: 46
  • Joined: 15-July 15

Re: Programming interview question- Path Finding

Posted 17 July 2015 - 06:36 PM

If you are, import "javax.swing.JOptionPane" and then use the "JOptionPane.showInputDialog("whatever string here");" method when assigning variables from user input... That should solve your problem.
Was This Post Helpful? 0
  • +
  • -

#6 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12735
  • View blog
  • Posts: 45,923
  • Joined: 27-December 08

Re: Programming interview question- Path Finding

Posted 17 July 2015 - 06:43 PM

User input really isn't the issue here... It doesn't have anything to do with path finding.
Was This Post Helpful? 0
  • +
  • -

#7 SleepingInsomniac25   User is offline

  • New D.I.C Head

Reputation: 14
  • View blog
  • Posts: 46
  • Joined: 15-July 15

Re: Programming interview question- Path Finding

Posted 17 July 2015 - 06:58 PM

I think it's because(and I'm assuming here that you're using an array to hold the "A --> B", "B --> C", et cetera, paths) the Scanner counts everything after each space as possibly a new input. And, because you have the array position to store the other words, it assumes that you are reading directly from a text file, therefore "confirming" that possibility... And boom, you path is split into three, your output becomes warped, and it's just strangeness after that.

Didn't he say something about the string splitting into three?
Was This Post Helpful? 0
  • +
  • -

#8 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12735
  • View blog
  • Posts: 45,923
  • Joined: 27-December 08

Re: Programming interview question- Path Finding

Posted 17 July 2015 - 07:00 PM

I think you're missing the logic here. If test data was provided, one should be able to hard code it and run the logic. When programming, it is important to separate the logic of the application out from the user interface portion. I'm sure the interviewer isn't concerned about whether the OP can use a Scanner vs. a JOptionPane, but more concerned in that the problem statement is understood.

If I give you a bunch of cities and tell you which ones are adjacent, you need to tell me how to get from the starting city to the ending city. The question asks for an algorithm to do this.
Was This Post Helpful? 0
  • +
  • -

#9 SleepingInsomniac25   User is offline

  • New D.I.C Head

Reputation: 14
  • View blog
  • Posts: 46
  • Joined: 15-July 15

Re: Programming interview question- Path Finding

Posted 17 July 2015 - 07:03 PM

No no, it's not that... I could swear someone mentioned a problem about the string splitting into three, but I guess not... I'm sorry. Could you please remove my posts?
Was This Post Helpful? 0
  • +
  • -

#10 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12735
  • View blog
  • Posts: 45,923
  • Joined: 27-December 08

Re: Programming interview question- Path Finding

Posted 17 July 2015 - 07:14 PM

Sure- the input has to be parsed into a model. But that's still not the primary logic of the problem. Focus on abstracting out the path finding portion of the problem.

We don't remove posts. Don't sweat it though. We all get better by trying to answer questions. :)
Was This Post Helpful? 1
  • +
  • -

#11 horace   User is offline

  • D.I.C Lover
  • member icon

Reputation: 768
  • View blog
  • Posts: 3,832
  • Joined: 25-October 06

Re: Programming interview question- Path Finding

Posted 17 July 2015 - 11:02 PM

if you are still looking for path finding algorithms do a web search for Dijkstra's Algorithm
Was This Post Helpful? 0
  • +
  • -

#12 Dev747   User is offline

  • New D.I.C Head

Reputation: -2
  • View blog
  • Posts: 19
  • Joined: 08-July 15

Re: Programming interview question- Path Finding

Posted 18 July 2015 - 01:57 AM

I have got a simple idea as a solution to above problem from a friend. Please tell if it is right.

We will store the input Paths in 2 dimensional array row-wise as follow :

B C
A B
C D

Then as A is source point we will search 0th position in the array where we can find A. That row will be the 1st path. Now the end point of 1st path is B. Therefore we will search 0th position in the array where we can find B.That row will be the 2nd path Similarly we will find 3rd path. In this way we can find all paths in correct sequence.
Please suggest if this a right approach.

Was This Post Helpful? 0
  • +
  • -

#13 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12735
  • View blog
  • Posts: 45,923
  • Joined: 27-December 08

Re: Programming interview question- Path Finding

Posted 18 July 2015 - 07:12 AM

Right approach but wrong data structure. A multidimensional array is not clean for this task. Look at a HashMap instead.
Was This Post Helpful? 0
  • +
  • -

#14 Dev747   User is offline

  • New D.I.C Head

Reputation: -2
  • View blog
  • Posts: 19
  • Joined: 08-July 15

Re: Programming interview question- Path Finding

Posted 18 July 2015 - 08:09 AM

View Postmacosxnerd101, on 18 July 2015 - 07:12 AM, said:

Right approach but wrong data structure. A multidimensional array is not clean for this task. Look at a HashMap instead.


I don't understand why array will be wrong. It will get the work done. Will ypu please explain in detail.
Was This Post Helpful? 0
  • +
  • -

#15 macosxnerd101   User is online

  • Games, Graphs, and Auctions
  • member icon




Reputation: 12735
  • View blog
  • Posts: 45,923
  • Joined: 27-December 08

Re: Programming interview question- Path Finding

Posted 18 July 2015 - 08:46 AM

The HashMap will handle lookup for you in O(1) time. It also stores the data in a more organized manner. Anytime you're storing data in a table format of some sort using a multidimensional array, you're creating messy and inefficient code. It's the same as using parallel arrays in this case, which are very poor practice.

If this is an interview question, multidimensional arrays would raise major red flags to the interviewer for this problem.
Was This Post Helpful? 0
  • +
  • -

  • (2 Pages)
  • +
  • 1
  • 2