You can use this restaurant website template on your portfolio project. So learn coding by watching this food website restaurant template HTML CSS tutorial.
For ease of understanding we view the permutations as a tree:
Proceeding from the root in any path in this tree will yield one permutation. We will write a recursive function that will loop through all the paths of this tree once. We don’t really need to build the tree with the adjacency matrix, the picture is provided for easy understanding.
Suppose our function name is generate(idx)
. idx means now we want to put a number in idxth position. Look at the following pseudocode, followed by my explanation:
In line 5 I have executed a loop from 0 to n. In line 6 we see if the number i has already been taken or not. If not taken then recursively idx+1 by placing i in the idx th position
I am solving the problem for the rest of the positions.
The interesting thing is to recursively generate(idx+1)
After solving for this we make taken[i] <- false. Because after placing the i-th number in the idx position, I will recursively solve by dropping i from that position and placing i+1 in the same position.
The general idea of backtracking is:
1. Select one of the possible options in each function call.
2. Try to find the solution recursively from the remaining options.
3. Discard the selected option and try again with another one.
Now your job is to convert the pseudocode into real code. If you can do this, you can easily solve other similar problems. For example, if you are asked to generate all kinds of permutations with a string “abcd”, you can easily do the same. But if the string contains this character more than once (eg “abbcdd”) then it will be a bit of a hassle, seeing the same permutation being generated over and over again. To avoid this you need to set a flag to stop solving recursively by putting the same character in the same position multiple times.
That’s it for now, in the next part we’ll look at some of the problems that can be solved with backtracking.
Floyd’s cycle finding algorithm
You are given a linked list, you have to say whether there are any bikes in the linked list. This is a very common interview question, we will learn how to solve this problem with Floyd’s Cycle Finding Algorithm.
The linked list of the picture shows that there is a bicycle of length 7.
The easiest way to detect cycles is to use a dictionary or hashmap. Proceed one cell at a time from the first node and save each node in the dictionary. If you go to a node and see that the node is already in the dictionary, then you must understand that the linked list is cyclic. The time complexity and memory complexity of this algorithm are both O(n).
Memory complexity is O(1)
It can be deduced using Floyd’s algorithm.
Suppose we have two pointers, one called the turtle pointer which we call T
(Tortoise) will mark, another name is rabbit pointer which we will mark with H (Hare). Initially both pointers will be at the root node of the linked list.
A hare moves two houses per second but a tortoise moves only one house. Then after 1 second the position of both pointers will be:
After another 1 second T will be at node 12, H will be at node 90. By simulating a few steps manually in this way, you will see that both pointers meet at node number 28.
Two pointers joining the same node means that the linked-list must have a cycle. H if there is no bicycle
The pointer would move forward to the end of the linked list.
Now how do we find the first node of the cycle?
The distance from the root node to the first node of the cycle
k=distance from the first node of the cycle to the meeting point of the hare and the tortoise
Now if turtle total cT
Rabbit if cH
The total distance traveled by the rabbit when the tortoise meets the bar cycle is:
Since the speed of the hare is twice that of the tortoise we can say:
This can be turned around and written as:
is the length of the cycle, i.e. m+k is a multiple of the length of the cycle. And that means if you m+k from the first node of the cycle
If you exceed the length, you will return to the first node. Understanding this is the most important part of this algorithm.
Now if you m from the meeting point
Go home only then you will come back to the first node of the cycle, because the distance from the first node to the meeting point is k. But you don’t know the value of m or k, so how can m move forward? There is a very easy and fun way to do that. You must remember that the distance from the root node to the first node of the cycle is also m.
Suppose the rabbit is no more, but a new turtle pointer T2 has appeared at the root node, and T
That previous meeting point is there. Now if the two pointers move forward one room where they meet is the first node of the cycle!
This is Floyd’s cycle detection algorithm. The time complexity is still O(n) (why?) but the memory complexity becomes O(1).
Let’s look at a C++ code:
This algorithm has many uses besides detecting cycles in linked lists. Such as detecting the cycle of a mathematical function or pseudo-random number generator.
uva 350 pseudo random numbers problem to check whether you understand the algorithm.
solve problems in Online Juz without competing, if you talk to many senior software engineers, you will see that even if they are not competing, they solve problems sometimes just to keep their heads sharp. Your friend has solved 300 problems in codeforces, you don’t need to be disappointed seeing that you haven’t done even 10 yet, just move forward at your own pace and always try to learn. In the end, life is not a competition, in a software company you have to cooperate with everyone, not a competition. Again like to contest without looking but don’t underestimate the algorithm.
You must Join our Facebook Group and Subscribe YouTube Channel
All Links in Below:
Join Our FreeWebsiteCreate Facebook Group to get an instant update for projects, templates, design resources, and solutions.
Join Our YouTube Channel & Subscribe with Bell Icon for New Video:
Join Our Official Facebook Page For the Latest updates All Code Projects are Free:
Visit our service page to get premium services.
You must Join our Facebook Group and Subscribe YouTube Channel