Misc

Question: You are given two axis-aligned rectangles. You have to determine if these rectangles overlap each other or not. Rectangle 1 : P1 (x, y), P2 (x,y) Rectangle 2 : P3 (x,y), P4 (x,y) In this problem statement, we are given co-ordinates for 2 rectangles and we have to determine if they overlap or not. In a way we can say that our use case looks like this. At the first glance, the problem seems to look very complicated. If you are coming up with a complicated set of conditionals,…

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,…

Here we shall discuss some high level Bit hacks that if used cleverly can really speed up your program execution time. We discussed some of the basic hacks in this post:- Low level bit hacks you must know. Please go through the post to get a little understanding of how the things work. Smart learners are anyways welcome to proceed. ;-) BIT HACK 6: Turn off the rightmost 1-bit. Now it finally gets more interesting!!! Bit hacks #1 – #5 were kind of boring to be honest. This bit hack…

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.

Question: Find sum of digits in a given number. Input: 65536 Output: 25 Method 1 (Iterative): In this code sample by using modulus operator(%), we extract the individual digits of given number then we add them together Method 2 (recursive):

Question: Write a program to count the number of bits that are 1(set bits) in a given integer. Input: 8 (1000) 11 (1011) Output: For 8 – 1 set bit For 11 – 3 set bits This question can be done in a very long way where we first convert the integer to its binary form and store its result in a character array. Traversing that character array would give the number of set bits. But that will not be an efficient way. We will use bit manipulation to solve…

The general way to print any statement would be like:- But in this example we are using at least one semicolon(;). Our target is to print something on the screen without using even a single semi colon(;) . This is sort of a fun problem rather than an actual concept. It may seem to be impossible at once but we can utilize the fact that the statements inside an if condition is always executed and its result is used to determine the block to be executed. We can do something…

The term Space Complexity is misused for Auxiliary Space at many places. Following are the correct definitions of Auxiliary Space and Space Complexity. Auxiliary Space is the extra space or temporary space used by an algorithm. Space Complexity of an algorithm is total space taken by the algorithm with respect to the input size. Space complexity includes both Auxiliary space and space used by input. We can also say that the way in which the amount of storage space required by an algorithm varies with the size of the problem…