nikoo28

Here we shall discuss some very low level Bit hacks that can really speed up your program execution time when used effectively. Every now and then we see bit level operators. Bit hacks are ingenious little programming tricks that manipulate integers in a smart and efficient manner. Instead of performing some operation (such as counting the 1 bits in an integer) by looping over individual bits, these programming nuggets do the same with one or two carefully chosen bitwise operations. To get things going I’ll assume that you know what …

Question: You are given a function rand7() – that generates random numbers from 1-7. Write a function rand10() – that uses rand7() to generate random numbers from 1-10. This appear to be one of those probabilistic analysis questions. You should be familiar with the concept of expected value, as it could be extremely helpful in probabilistic analysis. Hint: Assume you could generate a random integer in the range 1 to 49. How would you generate a random integer in the range of 1 to 10? What would you do if …

Question: There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. Solve it without division operator and in O(n). For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Array 1: {4, 3, 2, 1, 2} Output: {12, 16, 24, 48, 24} Since the complexity required is O(n), the obvious O(n2) brute force solution is not good …

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 …

What are enums actually? Enums provide an opportunity to the user to define a shorthand for fixed set of constants like months in a year, gender etc. Enumeration is the list of constant integer values, which means that the enum values can’t be modified. Here we are going to explain Enumeration usage rules and constraints in C language. In C Enums are defined by enum keyword. The enum definition is analogous to the way a structure is defined . Syntax: tagname – It is the name given to the enum …

Question: Given 2 sorted arrays, find the intersection elements between them. Array 1: 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26 Array 2: 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33 Output: 6, 12, 18, 24 Let’s called Array1 as “A” and Array2 as “B”, each with size m and n. The obvious brute-force solution is to scan through each element in A, and for each element in A, scan if that element exist in B. The running time complexity is O(m*n). …

Question: Let us suppose we have an array whose ith element gives the price of a share on the day i. If you were only permitted to buy one share of the stock and sell one share of the stock, design an algorithm to find the best times to buy and sell. When we talk about the best times to sell and buy, we mean that we want the best profit possible. A profit is possible when our buying rate is less than the selling rate. We need to maximize …

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 brute-force 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. …

Question: Given the root pointer to a binary tree, find the left view of the tree. Input: Sample Tree (Pointer to node 1 is given). Output: 1, 2, 4 At a single glance of the problem, we can understand that we need to perform a level order traversal on the tree. This is similar to finding the number of levels in a tree. At the start of each level, we just print the first element. This can be done with the algorithm below:- Time Complexity:- O(n) Space Complexity:- O(n) Ideone …