Interview Questions And Answers 
-
You have to get from point A to point B. You don’t know if you can get there. What would you do?
28,387 Views |
(63 votes, avg: 3.49)
Loading ...
Answers »
Our Sponsors
Our Sponsors
You have to get from point A to point B. You don’t know if you can get there. What would you do?
28,387 Views | (63 votes, avg: 3.49)
Loading ...
The two most common way to tackle problem like this is using Depth-First Search (DFS)and Breadth-First Search (BFS).
In the example above, You drive and drive around until you hope to find the destination. Reach a deadend? Turn around and come back where you came from. It might not be the shortest way, but if you tried every possible road, you’ll know that maybe you can’t get to China from New York (And that’s a DFS!).
Understanding these leads to you more exotic things like A* Search, and it’s a fundamental exploring algorithm. Too many things can be reduced into a graph, and knowing the best way to search a graph will come in handy. DFS is basically a stack-based implementation, while BFS is a queue-based implementation, and each with its strength and weaknesses.
BFS is the better option as that will give the shortest path (if it exists) from A to B (assuming each edge has unit weight assigned).
simple… sit where ur are if u have a phone or comp with net connection.. get the map of that area (from many possible sources,,like google earth..) try to find out if their is land route connecting a and b.. if that fails then call in the experts like offer 10k to some taxi guy.. or a make even greater offer to a tour coordinator, u will find urself at B in no time if that is possible..if all these fail then better try C (it may be better that b)..
what form is the input? thus measure the difference and move in direction which minimizes it…what motion is allowed..otherwise assume..
like block world problem
>>Swarnangsu
What you have said is true ONLY when we are dealing with a graph with a large height. For smaller graphs, DFS cannot be discounted so easily.
@NG
BFS is guaranteed optimal for uniform weight condition (if a solution exists BFS will find it in the best time). DFS cannot guarantee this. however, DFS has the advantage of low very low implementation / memory overhead. however, if the graphs are small, DFS is just as good as BFS, so there really is no point to using DFS unless we begin to implement iterated DFS or some such variant
This is really a question that pertains to life itself. We are born at point A. We want to reach success which is point B.
Utilizing a “learn as you go” approach and applying collected knowledge and data along the way is the best way to proceed. Let’s break this down farther.
Determine the amount of time you have to go from point A to point B. Spend the initial 20% of that time making a 360° search with the largest circumference possible with the in the time you have allowed.
During that time, ask people, look for maps, clues, collect data, and knowledge. At the end of the initial 360° search take an objective look at all the information you have obtained and you calculate the risk of failure you are willing to live with. Create a plan and a strategy based on your assessment of where you believe point B to be. Then you proceed on implementing your plan with predetermined intervals of reassessment and strategy improvements.
This is the best chance you have reaching point B if you don’t know if you can get there.
Hi,
Lets say you’re driving a car, and searching for somethig. Would you prefer DFS or BFS, I would certainly prefer DFS, not turn back after at every crossroad
So it all depends on how you look at the problem
If we are considering BFS and DFS as possible solutions, then we are essentially assuming that we are operating in a fully observable environment. Meaning that we have a map or something like that. And in essence what we are trying to do is find at the very least a route from point A to point B, but preferable the optimal route.
Now this being said, I think that it is quite clear that we can use A* with the straight line distances of current location to point B as a heuristic function.
Because such a heuristic function is both admissible (doesn’t overestimate the cost of reaching the goal) and it is consistent (decreases as you get closer to the goal), we are guaranteed that A* will provide an optimal solution.
Really this solution is just an improvement on what has already been discussed here. I just thought that I would add my 2 cents.
Use google maps,… simple
Men never think to just ask for directions! Get advice from someone who’s already been or tried to get where you want to go. Even if it’s a “place” that no one’s ever been, if you break a problem down into smaller components, there are always people who have done some part of it before you. It’s a matter of having good information and advice before you set out to get where your going as well as to be constantly asking questions and talking to others with who may have pieces of knowledge throughout the journey.
Just look at google map
Setup an new image search facility. Use whichever Search Engine which takes it up, to search for location A and B. Patent Pending!
Why are all you guys thinking straightforwardly, think intelligently, suppose somebody tells me that I have to go from A to J, I’ll go to B first, inquire bout where to go next, based on people’s opinion, then go where most tell me to, then again repeat this exercise, obviously this approach is better then thinking on my own, since i know for a fact i lack the necessary knowledge. this actually is a form of heuristic search found in AI.
Regards
Abhishek Vaid
Even if the two points are in a maze or a labyrinth a DFS is [b]guaranteed[/b] to find you a solution to the problem that whether it is possible to reach or not.
try n make the points coincide instead of you yourself moving to a point.
The problem is I dont know how to get there at point B.. but it is not that i dont know the point SO i will look for a bike , car and will go.
If you know the distance between A & B, you can take that distance as the radius of the circle & A as center of the circle.Start from A to the boundry of the circle & move along the circumference of that circle you will get the point B.
The important point is: are there better looking girls in B than in A. Just kidding :). If you know the distance, I think Subash’ method is good enough. Else use DFS with info seeking and heuristics and of course common sense-no one would expect you to walk through the great wall of china.
Leave an Answer/Comment