Puzzle

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