This post contains some programs that I have personally written to solve elementary problems. I am sharing these just so that people can see different ways of solving the same problem. Also, I claim that the methods used are very simple and natural.
Disclaimer:-
Please don't send me comments/scraps/mails giving me links where you have found the same logic. Its just that I have thought about these solutions without aid from any external source(internet, book or someone else). It may exactly/partially mimic what you have seen somewhere else or what you have thought of yourself. If that is the case, then just skip reading this post.
----------------------------------------------------------------------------------------------------------------------------------------
Q. Given a string, print all the unique permutations of the string in lexicographic order.
Ans. The methods that I have detailed below is special in that it prints "unique permutations".
Algorithm:-
1. Maintain an integer array which stores the number of occurrences of each character in the input string( hash the input string). It should be such that arr[character] gives the number of occurrences of character in the input string.
2. Allot the first character which has at least one occurrence. Then recursively permute the other part.
3. In the next iteration, make sure you choose a different character to allot. Even if the previous character you allotted occurred more than once in the input string, do not allot this once again (this is the key to ensure you get only unique permutations).
Steps 1 and 3 are the crucial steps. Step 1 makes sure that the permutations are in lexicographic order and Step 2 makes sure that only unique permutations are generated. Download the code from here.
----------------------------------------------------------------------------------------------------------------------------------------
Q. Given a sentence reverse the order of words in it. For example-
Input - who is the person over there
Output - there over person the is who
Ans. This is an all-time favourite question for On-Spot-Programming question paper setters. There are quite a few things you can do to solve this problem.
1. From the end of the string, come back to find a space. From there, go forwards printing all the characters till the occurrence of the next space. Do that until you reach the beginning of the string.
2. Put a \0 in wherever there is a space and do a printf("%s ",ptr) every time you find a a \0.
3. Take input as a sequence of words. Print the words in reverse order.
4. Reverse the string. Later on, reverse each word in it.
All the above methods are simple and equally efficient. Though this is an oft repeated question, often I find people struggling with this, purely because of silly mistakes. I thought of a way that is safe and easy to reproduce too. I do it recursively and that is what is special here.
Steps:-
1. Form the first word. If the breaking character is a space, then do a recursive call.
2. Keep doing step 1 until you get a newline character. Now start printing the words.
Download the code here.
----------------------------------------------------------------------------------------------------------------------------------------
Q. Write a program to simulate a simple Snake as seen in mobiles.
Ans. I have coded this particular program on Turbo C. It is easily reproducible on other compilers only if you know the corresponding functions.
What is special this time??? - I have not used the graphics library at all.
Download the code here. If you have any issues executing it, please let me know.
Disclaimer:-
Please don't send me comments/scraps/mails giving me links where you have found the same logic. Its just that I have thought about these solutions without aid from any external source(internet, book or someone else). It may exactly/partially mimic what you have seen somewhere else or what you have thought of yourself. If that is the case, then just skip reading this post.
----------------------------------------------------------------------------------------------------------------------------------------
Q. Given a string, print all the unique permutations of the string in lexicographic order.
Ans. The methods that I have detailed below is special in that it prints "unique permutations".
Algorithm:-
1. Maintain an integer array which stores the number of occurrences of each character in the input string( hash the input string). It should be such that arr[character] gives the number of occurrences of character in the input string.
2. Allot the first character which has at least one occurrence. Then recursively permute the other part.
3. In the next iteration, make sure you choose a different character to allot. Even if the previous character you allotted occurred more than once in the input string, do not allot this once again (this is the key to ensure you get only unique permutations).
Steps 1 and 3 are the crucial steps. Step 1 makes sure that the permutations are in lexicographic order and Step 2 makes sure that only unique permutations are generated. Download the code from here.
----------------------------------------------------------------------------------------------------------------------------------------
Q. Given a sentence reverse the order of words in it. For example-
Input - who is the person over there
Output - there over person the is who
Ans. This is an all-time favourite question for On-Spot-Programming question paper setters. There are quite a few things you can do to solve this problem.
1. From the end of the string, come back to find a space. From there, go forwards printing all the characters till the occurrence of the next space. Do that until you reach the beginning of the string.
2. Put a \0 in wherever there is a space and do a printf("%s ",ptr) every time you find a a \0.
3. Take input as a sequence of words. Print the words in reverse order.
4. Reverse the string. Later on, reverse each word in it.
All the above methods are simple and equally efficient. Though this is an oft repeated question, often I find people struggling with this, purely because of silly mistakes. I thought of a way that is safe and easy to reproduce too. I do it recursively and that is what is special here.
Steps:-
1. Form the first word. If the breaking character is a space, then do a recursive call.
2. Keep doing step 1 until you get a newline character. Now start printing the words.
Download the code here.
----------------------------------------------------------------------------------------------------------------------------------------
Q. Write a program to simulate a simple Snake as seen in mobiles.
Ans. I have coded this particular program on Turbo C. It is easily reproducible on other compilers only if you know the corresponding functions.
What is special this time??? - I have not used the graphics library at all.
Download the code here. If you have any issues executing it, please let me know.
0 comments:
Post a Comment