Given an array of positive integers. All numbers occur even number of times except one number which occurs odd number of times. Find the number in O(n) time & constant space.
Example:
I/P = [1, 2, 3, 2, 3, 1, 3]
O/P = 3
Approach: Take xor of all the elements. The number of terms occurring even number of times get cancelled due to property of xor that a ^ a = 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include<iostream>
using...
Sunday, 28 August 2016
Range Sum Query - Immutable
Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
Example:
Given nums = [-2, 0, 3, -5, 2, -1]
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.
Approach: Compute the sum till...
Friday, 26 August 2016
Largest Number
Given a list of non-negative integers, return the largest number that can be formed by their arrangement.
Eg. For the list [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.
Approach: We need sorting but in the modified way since if we have the number 9, 80 in the list then the...
Week 4 Assignment Solution
This post provides solution to the fourth assignment of the online course Software Testing offered by MHRD. The answers to each questions are marked in red. Explanation for numerical problems are given below each problem.
You can download the pdf version of the solution here.
Which statement below BEST describes non-functional testing?
The process of testing an integrated system...
Thursday, 25 August 2016
Majority Element in a Sorted Array
Write an algorithm to find if a given integer x appears more than n/2 times in a sorted array of n integers. See this for a similar problem on Majority Element.
Approach: Use binary search to find the first occurrence of x in the array.
TC = O(log(n))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include...
Wednesday, 24 August 2016
Majority Element
Majority Element: A majority element in an array A[] of size n is an element that appears more than n/2 times (and hence there is at most one such element).
Idea : To find the majority element using Moore's Voting Algorithm
Basic idea of the algorithm is if we cancel out each occurrence of an element e with all the other elements that are different from e then e will exist till end...
Two Sum Zero
An array of integers is given, both +ve and -ve. You need to find the two elements such that their sum is closest to zero.
Approach : Using the approach given in the 2 Sum post.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include...
Monday, 22 August 2016
3Sum Closest
Given an array A of n integers, find three integers in A such that the sum is closest to a given value. Return the sum of the three integers. You may assume that each input would have exactly one solution.
It is a modified version of the problem 3 Sum
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 +...
Sunday, 21 August 2016
Anti Diagonals
Give a N*N square matrix, return an array of its anti-diagonals.
Input:
1 2 3
4 5 6
7 8 9
Output :
[
[1],
[2, 4],
[3, 5, 7],
[6, 8],
[9]
]
Approach : The point to observe here is that the sum of i (row number) and j (column number) is constant for each anti-diagonal.
For example:
Diagonal 1 has i + j = 0
Diagonal 2 has i + j = 1
and so on.
So define s = i + j
Loop with s from...
