RSS Feed
Twitter
Orkut
Question 1:-
Write a function
Write a function
int distinct(int A[], int N);
that,
given a zero-indexed array A consisting of N integers, returns the number of
distinct values in array A.
Assume
that:
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [−1,000,000..1,000,000].
each element of array A is an integer within the range [−1,000,000..1,000,000].
For
example, given array A consisting of six elements such that:
A[0] = 2 A[1] = 1 A[2] = 1
A[3] = 2 A[4] = 3 A[5] = 1
A[3] = 2 A[4] = 3 A[5] = 1
the
function should return 3, because there are 3 distinct values appearing in
array A, namely 1, 2 and 3.
Complexity:
expected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements
of input arrays can be modified.
Question 2:-
A
non-empty zero-indexed array A consisting of N non-negative integers is given.
This array defines a number M as follows:
M = pm2(A[0]) + pm2(A[1]) + ... + pm2(A[N−1])
pm2(N) = (−2)N
pm2(N) = (−2)N
For
example, array A such that
A[0] = 5 A[1] = 4 A[2] = 7
defines
number −144, because
pm2(A[0]) + pm2(A[1]) + pm2(A[2]) =
pm2(5) + pm2(4) + pm2(7) =
(-32) + (16) + (-128) = -144
pm2(5) + pm2(4) + pm2(7) =
(-32) + (16) + (-128) = -144
Write a
function
int sum_of_powers_of_minus_two(int A[], int N);
that
given a non-empty zero-index array A consisting of N non-negative integers
returns the number M defined by this array in the above manner. The function
should return −1 if the absolute value of the result exceeds 10,000,000.
Assume
that:
N is an integer within the range [0..100,000];
each element of array A is an integer within the range [0..1,000,000,000].
each element of array A is an integer within the range [0..1,000,000,000].
For
example, given array array A such that
A[0] = 5 A[1] = 4 A[2] = 7
the
function should return −144, as explained in the example above.
Complexity:
expected worst-case time complexity is O(N*log(N));
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
expected worst-case space complexity is O(N), beyond input storage (not counting the storage required for input arguments).
Elements
of input arrays can be modified.
Question 3 :-
Write a
function:
int symmetryPoint(char *S);
that,
given a string S, returns the index (counting from 0) of a character such that
the substring to the left of that character is a reversal of the substring to
its right. The function should return −1 if no such index exists.
Note:
reversing an empty string (i.e. a string whose length is zero) gives an empty
string.
For
example, given a string:
"racecar"
the
function should return 3, because the substring to the left of the character
"e" at index 3 is "rac", and the one to the right is
"car".
Given a
string:
"x"
the
function should return 0, because both substrings are empty.
Assume
that:
the length of S is within the range [0..2,000,000].
Complexity:
expected worst-case time complexity is O(length(S));
expected worst-case space complexity is O(1) (not counting the storage required for input arguments).
expected worst-case space complexity is O(1) (not counting the storage required for input arguments).
Question 4:-
A non-negative integer N is given. The maximal
binary ones stretch of N is the length of the longest sequence of consecutive
bits set to 1 in the binary representation of N. For example, consider N =
114067. Its binary representation is 11011110110010011. Its maximal binary ones
stretch is equal to 4.
Write a function
int max_binary_ones_stretch(int N);
that, given a non-negative integer N, returns the maximal binary ones stretch of N.
Assume that:
N is an integer within the range [0..2,147,483,647].
For example, given N = 114067, the function should return 4, as explained above.
Complexity:
expected worst-case time complexity is O(log(N));
expected worst-case space complexity is O(1).
Write a function
int max_binary_ones_stretch(int N);
that, given a non-negative integer N, returns the maximal binary ones stretch of N.
Assume that:
N is an integer within the range [0..2,147,483,647].
For example, given N = 114067, the function should return 4, as explained above.
Complexity:
expected worst-case time complexity is O(log(N));
expected worst-case space complexity is O(1).
Question 5:-
A positive integer N is
given. Write a function:
int
factorial_digits_sum(int N);
that returns the sum of
the values of the digits in a decimal representation of N! (factorial of N,
i.e. 1 * 2 * ... * N).
For example, given N =
14, the function should return 45, because N! = 87178291200 and the sum of the
values of its digits equals:
8 + 7
+ 1 + 7 + 8 + 2 + 9 + 1 + 2 + 0 + 0 = 45.
The function should
return −1 if the result exceeds 100,000,000.
Assume that:
N is an integer within the range [1..2,000].
Complexity:
expected worst-case time complexity is O(N2);
expected worst-case space complexity is O(N).
expected worst-case space complexity is O(N).
Question 6:-
A prefix of a string S
is any leading contiguous part of S. For example, the string
"codility" has the following prefixes: "", "c",
"co", "cod", "codi", "codil",
"codili", "codilit" and "codility". A prefix of S
is called proper if it is shorter than S.
A suffix of a string S
is any trailing contigous part of S. For example, the string
"codility" has the following suffixes: "", "y",
"ty", "ity", "lity", "ility",
"dility", "odility" and "codility". A suffix of S
is called proper if it is shorter than S.
Write a function:
int
max_prefix_suffix(char *S);
that, given a string S
consisting of N characters, returns the length of the longest string that is
both a proper prefix of S and a proper suffix of S. The function should return
−1 if no such string exists.
For example, given S =
"abbabba" the function should return 4 because:
proper prefixes of S are: "", "a", "ab",
"abb", "abba", "abbab", "abbabb";
proper prefixes of S are: "", "a", "ba", "bba", "abba", "babba", "bbabba";
string "abba" is both a proper prefix and a proper suffix of S;
this is the longest such string.
proper prefixes of S are: "", "a", "ba", "bba", "abba", "babba", "bbabba";
string "abba" is both a proper prefix and a proper suffix of S;
this is the longest such string.
Complexity:
expected worst-case time complexity is O(N);
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).
expected worst-case space complexity is O(N) (not counting the storage required for input arguments).
Question 7:-
binary gap within a
positive integer N is any maximal sequence of consecutive zeros that is
surrounded by ones at both ends in the binary representation of N.
For example, number 9
has binary representation 1001 and contains a binary gap of length 2. The
number 529 has binary representation 1000010001) and contains two binary gaps:
one of length 4 and one of length 3. The number 20 has binary representation
10100 and contains one binary gap of length 1. The number 15 has binary
representation 1111 and has no binary gaps.
Write a function
int
binary_gap(int N);
that, given a positive
integer N, returns the length of its longest binary gap. The function should
return 0 if N doesn't contain a binary gap.
Assume that:
N is an integer within the range [1..2,147,483,647].
For example, given N =
1041 the function should return 5, because N has binary representation
10000010001 and so its longest binary gap is of length 5.
Complexity:
expected worst-case time complexity is O(log(N));
expected worst-case space complexity is O(1).
expected worst-case space complexity is O(1).
Question 8:-
A zero-indexed array A
consisting of N integers is given. It contains daily prices of a stock share
for a period of N consecutive days. If a single share was bought on day P and
sold on day Q, where 0 ≤ P ≤ Q < N, then the profit of such transaction is
equal to A[Q] − A[P], provided that A[Q] ≥ A[P]. Otherwise, the transaction
brings loss of A[P] − A[Q].
For example, consider
the following array A consisting of six elements such that:
A[0] = 23171 A[1]
= 21011 A[2] = 21123
A[3] = 21366 A[4]
= 21013 A[5] = 21367
If a share was bought on
day 0 and sold on day 2, a loss of 2048 would occur because A[2] − A[0] = 21123
− 23171 = −2048. If a share was bought on day 4 and sold on day 5, a profit of
354 would occur because A[5] − A[4] = 21367 − 21013 = 354. Maximum possible
profit was 356. It would occur if a share was bought on day 1 and sold on day
5.
Write a function,
int
maxProfit(int A[], int N);
that, given a
zero-indexed array A consisting of N integers containing daily prices of a
stock share for a period of N consecutive days, returns the maximum possible
profit from one transaction during this period. The function should return 0 if
it was impossible to gain any profit.
Assume that:
· N is an integer within the range [0..1,000,000];
· each element of array A is an integer within the
range [0..1,000,000,000].
For example, given array
A consisting of six elements such that:
A[0] = 23171 A[1]
= 21011 A[2] = 21123
A[3] = 21366 A[4]
= 21013 A[5] = 21367
the function should
return 356, as explained above.
Complexity:
· expected worst-case time complexity is O(N);
· expected worst-case space complexity is O(1),
beyond input storage (not counting the storage required for input arguments).
Elements of input arrays
can be modified.
Question 9:-
A non-empty zero-indexed
array A consisting of N non-negative integers is given. Its binarian is defined as
binarian(A)
|
=
|
pow2(A[0]) + pow2(A[1]) + ... +
pow2(A[N−1])
|
pow2(K)
|
=
|
2K
|
For example, the
binarian of array A such that
A[0] = 1
A[1] = 5 A[2] = 4
is equal to 50:
binarian(A)
|
=
|
pow2(A[0]) + pow2(A[1]) +
pow2(A[2])
|
=
|
pow2(1) + pow2(5) + pow2(4)
|
|
=
|
2 + 32 + 16
|
|
=
|
50
|
Write a function
int
min_binarian_equivalent(int A[], int N);
that given an array A
consisting of N non−negative integers returns the length of the shortest array
that has the same binarian as array A.
Assume that:
· N is an integer within the range [1..100,000];
· each element of array A is an integer within the
range [0..10,000].
For example, given array
A such that
A[0] = 1
A[1] = 0 A[2] = 2
A[3] = 0 A[4] = 0 A[5] = 2
the function should
return 3 because:
· the binarian of A is equal to 13,
· array B such that B[0] = 3 B[1] = 2 B[2] = 0 also has binarian equal to 13,
· no shorter array has binarian equal to 13.
Complexity:
· expected worst-case time complexity is
O(N*log(N));
· expected worst-case space complexity is O(N),
beyond input storage (not counting the storage required for input arguments).
Elements of input arrays
can be modified.
Question 10 :-
Every element in an array of integers points to a relative
location from the current element. Precisely, if A[k]
= m, the jump from k should land at k+A[k]=k+m.
Write a function
int arrayJmp(int[] A);
that returns the number of jumps until the pointer jumps
out of the array when starting from the firstelement.
For example:
A[0]=2, A[1]=3, A[2]=1, A[3]=1, A[4]=3
The pointer's 1st jump is from 0 to 2, 2nd jump from 2 to
3, 3rd jump from 3 to 4, 4th jump from 4 to 7, but 7 is out of the array. The
number of jumps until the pointer jumps out of the array is 4.
Return -1 if the sequence of jumps never ends.
