nikoo28

A sorting algorithm is said to be stable if two objects with equal keys appear in the same order in sorted output as they appear in the input unsorted array. Some sorting algorithms are stable by nature like Insertion sort, Merge Sort, Bubble Sort, etc. And some sorting algorithms are not, like Heap Sort, Quick Sort, etc. However, any given sorting algorithm which is not stable can be modified to be stable. There can be sorting algorithm specific ways to make it stable, but in general, any comparison based sorting …

Question: Find the duplicate characters in a string? Input: floccinaucinihilipilification Output: a ,c ,f ,i ,l ,n ,o The idea for this problem would be:- Create a character array for the number of characters possible. Take 256 for all the ASCII characters as well. Traverse the array and print the characters that have a count greater than 1. Here is the source code for the same-

Question: Find the number of words in a given string? Input: This is a sample    statement       and I need to         find   the number of words. Output: 14 According to the problem, we are given a string and it contain words separated by spaces, next lines or tab spaces. So, the basic idea for the problem would be to traverse the string and increment a counter whenever we see the end of a word.

Question: Write a program to swap 2 numbers? Input: a = 4, b = 19 Output: a = 19, b = 4 We will try to discuss the different ways to swap 2 numbers. To understand how swapping works, please visit this post. Method 1 : Using a temporary variable Method 2 : Without a temporary variable Method 3: Using multiplication and division IMP: It is necessary here that numbers should be non-zero Method 4: Using Bitwise XOR (^) Method 5: Swapping in single line using arithmetic operator Method 6: …

Question: Write a program to swap 2 numbers? Input: a = 4, b = 19 Output: a = 19, b = 4 Swapping 2 numbers is one of the most basic tasks while programming. But sometimes, we tend to make error in it. For instance look at this code. The output of the above program is:- What happened? The values were changed inside the function but the changes did not reflect when returning. This is because when we call the function swapIntegers(int, int), only the value of the integers is …

Question: Given a sorted array of n integers that has been rotated an unknown number of times, give a O(log (n)) solution that finds an element in the array? Input: arr [] = {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14}. Find 5 . Output: 8 (the index of 5 in the array) We can solve this problem in only one scan of the array as well. Please read Method 1 if you have not done so, as this forms the base of this problem. To …

We have been discussing the time complexities of each of the algorithm that we have discussed. Let us try to analyze, how these time complexities are calculated. O(1) Time complexity of a function (or set of statements) is considered as O(1) if it doesn’t contain loop, recursion and call to any other non-constant time function. For example swap() function(which interchanges two numbers) has O(1) time complexity. A loop or recursion that runs a constant number of times is also considered as O(1). For example the following loop is O(1). O(n) …

Question: Given a sequence of integers, find the median of the integers? Input: arr [] = {15, 23, 4, 16, 8, 42}. Find median. Output: 15 Since the question does not specify anything we cannot assume that the given array is a sorted one. The definition of median is the (n/2)th element of a sorted sequence of integers. This definition makes our approach simpler. All we need to do is sort the integers and then return the (n/2)th element. Here is the code for above approach. I use quick sort …

A Programming Contest is a delightful playground for the exploration of intelligence of programmers. To start solving problems in contests, first of all, you have to fix your aim. Some contestants want to increase the number of problems solved by them and the other contestants want to solve less problems but with more efficiency. Choose any of the two categories and then start. If you are a beginner, first try to find the easier problems.Try to solve them within short time. At first, you may need more and more time …

Question: Given a sorted array of n integers that has been rotated an unknown number of times, give a O(log (n)) solution that finds an element in the array? Input: arr [] = {15, 16, 19, 20, 25, 1, 3, 4, 5, 7, 10, 14}. Find 5 . Output: 8 (the index of 5 in the array) Let us assume that the given array is arr[]. The basic approach for this problem will be:- Find the pivot element. That means after which all elements are in ascending order. This basically …