Question: Given an integer N, find the prime numbers in that range from 1 to N. Input: N = 25 Output: 2, 3, 5, 7, 11, 13, 17, 19, 23 Today let us discuss about a very common but very interesting problem “To find prime numbers in first N Natural numbers “. I will be taking here a very specific approach of first giving definition of prime numbers , using that definition to derive the algorithm, and then using different properties or results that can be further applied to our…
Others


Question: Given an unsigned Integer, you need to reverse its bits. There are several methods of reversing the bits of an unsigned integer. Here, we devise an algorithm using the XOR swap trick. Hint: How do you swap the ith bit with the jth bit? Try to figure out if you could use the XOR operation to do it. The XOR swap trick: Reversing bits could be done by swapping the n/2 least significant bits with its most significant bits. The trick is to implement a function called swapBits(i, j),…

Question: Given an Integer, you need to determine if it is a palindrome or not. You should not use any extra space in the process. Input: 121 Output: Palindrome At the first go, the problems seems very easy to solve. We just need to reverse the number and check if it remains the same. Right? Don’t be deceived by this problem which seems too easy. Also note the restriction of doing it without extra space. We also need to think of a generic solution that is not language/platform specific. First,…

Question: What is a Pointer? What are its limitations? What are its benefits? How do we use it? What all operation we can perform using it? In this article we are going to discover answers to all these questions. Pointer is a variable that contain the address of another variable and that variable can be a structure, array or basic data type. The basic syntax to define the pointer is as follows: Datatype * identifier; Datatype is the data type of the variable whose address we are going to store…

Question: Given a string, find the length of the longest substring without repeating characters. Input: “abcabcbb” Output: “abc” Input: “bbbb” Output: “b” The longest substring without repeating letters for “abcabcbb” is “abc”, which the length is 3. For “bbbbb” the longest substring is “b”, with the length of 1. We definitely have the bruteforce method, where we find each string and then compare. But we want to speed up the process. How can we can look up if a character had existed in the substring instantaneously? The answer is using…

Question: You are given a function foo() that represents a biased coin. When foo() is called, it returns 0 with 60% probability, and 1 with 40% probability. Write a new function that returns 0 and 1 with 50% probability each. Your function should use only foo(), no other library method. We know foo() returns 0 with 60% probability. How can we ensure that 0 and 1 are returned with 50% probability? If we can somehow get two cases with equal probability, then we are done. We call foo() two times.…

In C, a structure cannot have static members, but in C++ a structure can have static members. For example, following program causes compilation error in C, but works in C++. Feel free to add your opinion.

Symbol Tables can be implemented in many ways and here are some of them. Unordered Array Implementation With this method, just maintaining an array is enough. It needs O(n) time for searching, insertion and deletion in the worst case. Ordered [Sorted] Array Implementation In this we maintain a sorted array of keys and values. Store in sorted order by key keys[i] = ith largest key values[i] = value associated with ith largest key Since the elements are sorted and stored in arrays, we can use simple binary search for finding…

Since childhood, we have all used a dictionary, and many of us have used a word processor (say Microsoft WORD) which comes with a spell checker. The spell checker is also a dictionary but limited. There are many real time examples for dictionaries and few of them are: Spelling checker The data dictionary found in database management applications Symbol tables generated by loaders, assemblers, and compilers Routing tables in networking companies (DNS Lookup) In computer science, we generally use the term symbol table rather than dictionary, when referring to the…

Insertion sort is the most generic example of a sorting algorithm, and the one which is used by one of the most naive users. Often we must have also used this algorithm in our real life examples unknowingly. One of the favorite example is: This is a very common scenario and we must have used it. Suppose you get a hand of cards. Our general approach is that we start scanning the cards from starting and if we find a card out of place, we remove it from there and…