Arrays

Let us suppose you are given an array of integers. The special thing about this array is that all numbers are repeated twice except one. Find the single non-repeating number. Example 1:Input: [2, 1, 1]Output: 2 Example 2:Input: [4, 5, 5, 2, 2]Output: 4 Problem statement: You are given an array of all positive integers. All the integers are repeated exactly twice except one. We need to find that number with a linear time complexity and using the minimum space possible. Brute Force Method: When tackling such problems, it is …

Question: Given an array A, find the sum of maximum sum of two non-overlapping subarrays, with lengths L and M.In other words, return the largest V for which V = (A[i] + A[i+1] …. A[i+L-1]) + (A[j] + A[j+1] …. A[j+M-1])Input: A = {3, 8, 1, 3, 2, 1, 8, 9, 0}; L = 3, M = 2Output: 29 The problem statement is quite clear. We need to find 2 contiguous sub-arrays from an array Add the elements of both these arrays The sum should be the maximum possible sum …

Question: Given a zero-indexed array ‘A’ of length ‘N’ which contains all integers from 0 to N-1. Find and return the longest length of set S, where S[i] = {A[i], A[A[i]], A[A[A[i]]], …} subjected to a particular condition. Suppose the first element in S starts with the selection of element A[i] of index = i, the next element in S should be A[A[i]], and then A[A[A[i]]],.. and so on. By that analogy, we stop adding elements as soon as we get a duplicate. Input: A = {5, 4, 0, 3, …

Question: Let us suppose we have a two dimensional plane where the the length of lines determine the height of a container. We need to determine the maximum capacity of water this kind of an arrangement can hold. The heights are represented by an array. Input: [1, 8, 6, 2, 5, 4, 8, 3, 7] Output: 49 Let us try to visualize the problem at hand diagrammatically. Let the array be represented as: If we try to pour water from the top in the entire arrangement you can visualize that …

Question: Given an array, there is a largest element N. Check if that number is at least twice than all the other elements in the array. Return the index if it is, else return -1Input: {3, 6, 1, 0}Output: -1 6 is the largest integer, and for every other number in the array x,6 is more than twice as big as x. The index of value 6 is 1, so we return 1. Let us try to make one more exampleInput: nums = [1, 2, 3, 4] Output: -1Explanation: 4 …

Question: There is an array A[N] of N numbers. You have to compose an array Output[N] such that each element in Output[i] will tell the next greater element to the right in the original array. If there is no greater number to the right, then the output array should contain -1 in that position.Array 1: {4, 6, 5, 4, 3, 4, 9, 8, 1} Output: {6, 9, 9, 9, 4, 9, -1, -1, -1} Let us try to understand the problem statement. We are given an input array that has …

Question: Given an unsorted array of integers and a number ‘k’. Return the kth largest element in the array.Input: arr = {3,2,1,5,6,4}, k = 2Output: 5 Given an unsorted array of integers, you need to determine the kth largest element. By taking a first glance at the problem we can be sure of one thing. If the array is already sorted in ascending order, we can simply return the element at arr[size – k]. This would give us the kth largest element. This is because the 2nd largest element is …

Question: Given an integer N, convert it into a string of words. Input: N = 345 Output: three hundred forty five This is one of the most common problems that we come across in out daily lives. We need to input a number from the user and print it in words. First, we perform a number of checks on the input string. If it is in any way invalid, the result is the empty string (“”). Next, we take note of whether or not the string begins with a ‘-‘. …

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 …