Given a table elements with the following structure:
create table elements ( v integer not null )write an SQL query that returns the sum of the numbers in column v.
For example, given:
v --- 2 10 20 10your query should return 42.
insert into elements values (10); insert into elements values (37);
function result: +----+ | 42 | +----+
function result: +----+ | 47 | +----+
insert into elements values (10); insert into elements values (37);
function result: +----+ | 42 | +----+
function result: +----+ | 47 | +----+
The solution obtained perfect score.
function result: +----+ | 42 | +----+
function result: +----+ | 55 | +----+
function result: +----+ | 45 | +----+
function result: +----+ | 12 | +----+
function result: +----+ | 10 | +----+
function result: +----+ | 76 | +----+
function result: +----+ | 31 | +----+
function result: +-----+ | 167 | +-----+
function result: +-------+ | -1000 | +-------+
function result: +-------+ | 11800 | +-------+
function result: +---------+ | 1810000 | +---------+
A non-empty array A consisting of N integers and sorted in a non-decreasing order (i.e. A[0] ≤ A[1] ≤ ... ≤ A[N−1]) is given. The leader of this array is the value that occurs in more than half of the elements of A.
You are given an implementation of a function:
class Solution { public int solution(int[] A); }
that, given a non-empty array A consisting of N integers, sorted in a non-decreasing order, returns the leader of array A. The function should return −1 if array A does not contain a leader.
For example, given array A consisting of ten elements such that:
A[0] = 2 A[1] = 2 A[2] = 2 A[3] = 2 A[4] = 2 A[5] = 3 A[6] = 4 A[7] = 4 A[8] = 4 A[9] = 6the function should return −1, because the value that occurs most frequently in the array, 2, occurs five times, and 5 is not more than half of 10.
Given array A consisting of five elements such that:
A[0] = 1 A[1] = 1 A[2] = 1 A[3] = 1 A[4] = 50the function should return 1.
The attached code is still incorrect for some inputs. Despite the error(s), the code may produce a correct answer for the example test cases. The goal of the exercise is to find and fix the bug(s) in the implementation. You can modify at most three lines.
Assume that:
- N is an integer within the range [1..100,000];
- each element of array A is an integer within the range [0..2,147,483,647];
- array A is sorted in non-decreasing order.
In your solution, focus on correctness. The performance of your solution will not be the focus of the assessment.
| 1 | import java.util.*; |
| 2 | class Solution { |
| 3 | int solution(int[] A) { |
| 4 | int n = A.length; |
| 5 | int[] L = new int[n + 1]; |
| 6 | L[0] = -1; |
| 7 | for (int i = 0; i < n; i++) { |
| 8 | L[i + 1] = A[i]; |
| 9 | } |
| 10 | int count = 0; |
| 11 | int pos = (n + 1) / 2; |
| 12 | int candidate = L[pos]; |
| 13 | for (int i = 1; i <= n; i++) { |
| 14 | if (L[i] == candidate) |
| 15 | count = count + 1; |
| 16 | } |
| 17 | if (count > pos) |
| 18 | return candidate; |
| 19 | return (-1); |
| 20 | } |
| 21 | } |
| 1 | import java.util.*; |
| 2 | class Solution { |
| 3 | int solution(int[] A) { |
| 4 | int n = A.length; |
| 5 | int[] L = new int[n + 1]; |
| 6 | L[0] = -1; |
| 7 | for (int i = 0; i < n; i++) { |
| 8 | L[i + 1] = A[i]; |
| 9 | } |
| 10 | int count = 0; |
| 11 | int pos = (n + 1) / 2; |
| 12 | int candidate = L[pos]; |
| 13 | for (int i = 1; i <= n; i++) { |
| 14 | if (L[i] == candidate) |
| 15 | count = count + 1; |
| 16 | } |
| 17 | - if (count > pos) |
| + if (2 * count > n) | |
| 18 | return candidate; |
| 19 | return (-1); |
| 20 | } |
| 21 | } |
| 1 | import java.util.*; |
| 2 | class Solution { |
| 3 | int solution(int[] A) { |
| 4 | int n = A.length; |
| 5 | int[] L = new int[n + 1]; |
| 6 | L[0] = -1; |
| 7 | for (int i = 0; i < n; i++) { |
| 8 | L[i + 1] = A[i]; |
| 9 | } |
| 10 | int count = 0; |
| 11 | int pos = (n + 1) / 2; |
| 12 | int candidate = L[pos]; |
| 13 | for (int i = 1; i <= n; i++) { |
| 14 | if (L[i] == candidate) |
| 15 | count = count + 1; |
| 16 | } |
| 17 | - if (count > pos) |
| + if (2 * count > n) | |
| 18 | return candidate; |
| 19 | return (-1); |
| 20 | } |
| 21 | } |
| 1 | import java.util.*; |
| 2 | class Solution { |
| 3 | int solution(int[] A) { |
| 4 | int n = A.length; |
| 5 | int[] L = new int[n + 1]; |
| 6 | L[0] = -1; |
| 7 | for (int i = 0; i < n; i++) { |
| 8 | L[i + 1] = A[i]; |
| 9 | } |
| 10 | int count = 0; |
| 11 | int pos = (n + 1) / 2; |
| 12 | int candidate = L[pos]; |
| 13 | for (int i = 1; i <= n; i++) { |
| 14 | if (L[i] == candidate) |
| 15 | count = count + 1; |
| 16 | } |
| 17 | - if (count > pos) |
| + if (2 * count > n) | |
| 18 | return candidate; |
| 19 | return (-1); |
| 20 | } |
| 21 | } |
The solution obtained perfect score.
Integer V lies strictly between integers U and W if U < V < W or if U > V > W.
A non-empty array A consisting of N integers is given. A pair of indices (P, Q), where 0 ≤ P < Q < N, is said to have adjacent values if no value in the array lies strictly between values A[P] and A[Q].
For example, in array A such that:
A[0] = 0 A[1] = 3 A[2] = 3 A[3] = 7 A[4] = 5 A[5] = 3 A[6] = 11 A[7] = 1the following pairs of indices have adjacent values:
(0, 7), (1, 2), (1, 4), (1, 5), (1, 7), (2, 4), (2, 5), (2, 7), (3, 4), (3, 6), (4, 5), (5, 7).For example, indices 4 and 5 have adjacent values because there is no value in array A that lies strictly between A[4] = 5 and A[5] = 3; the only such value could be the number 4, and it is not present in the array.
Given two indices P and Q, their distance is defined as abs(A[P] − A[Q]), where abs(X) = X for X ≥ 0, and abs(X) = −X for X < 0. For example, the distance between indices 4 and 5 is 2 because (A[4] − A[5]) = (5 − 3) = 2.
Write a function:
def solution(A)
that, given a non-empty array A consisting of N integers, returns the minimum distance between indices of this array that have adjacent values. The function should return −1 if the minimum distance is greater than 100,000,000. The function should return −2 if no adjacent indices exist.
For example, given array A such that:
A[0] = 0 A[1] = 3 A[2] = 3 A[3] = 7 A[4] = 5 A[5] = 3 A[6] = 11 A[7] = 1the function should return 0 because:
- indices 1 and 2 are adjacent, because the array does not contain any value that lies strictly between A[1] = 3 and A[2] = 3;
- the distance between these indices is (A[1] − A[2]) = (3 − 3) = 0;
- no other pair of adjacent indices that has smaller distance exists.
Write an efficient algorithm for the following assumptions:
- N is an integer within the range [1..40,000];
- each element of array A is an integer within the range [−2,147,483,648..2,147,483,647].
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
N = len(A)
if N < 2:
return -2
res = abs(A[1]-A[0])
for i in range(N):
has_next_val = False
next_val = -1
for j in range(N):
if j != i and A[j] >= A[i]:
if not has_next_val:
has_next_val = True
next_val = A[j]
else:
next_val = min(next_val, A[j])
if not has_next_val:
continue
res = min(res, next_val-A[i])
if res > 100000000:
return -1
return res
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
N = len(A)
if N < 2:
return -2
res = abs(A[1]-A[0])
for i in range(N):
has_next_val = False
next_val = -1
for j in range(N):
if j != i and A[j] >= A[i]:
if not has_next_val:
has_next_val = True
next_val = A[j]
else:
next_val = min(next_val, A[j])
if not has_next_val:
continue
res = min(res, next_val-A[i])
if res > 100000000:
return -1
return res
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
N = len(A)
if N < 2:
return -2
res = abs(A[1]-A[0])
for i in range(N):
has_next_val = False
next_val = -1
for j in range(N):
if j != i and A[j] >= A[i]:
if not has_next_val:
has_next_val = True
next_val = A[j]
else:
next_val = min(next_val, A[j])
if not has_next_val:
continue
res = min(res, next_val-A[i])
if res > 100000000:
return -1
return res
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
N = len(A)
if N < 2:
return -2
res = abs(A[1]-A[0])
for i in range(N):
has_next_val = False
next_val = -1
for j in range(N):
if j != i and A[j] >= A[i]:
if not has_next_val:
has_next_val = True
next_val = A[j]
else:
next_val = min(next_val, A[j])
if not has_next_val:
continue
res = min(res, next_val-A[i])
if res > 100000000:
return -1
return res
# you can write to stdout for debugging purposes, e.g.
# print("this is a debug message")
def solution(A):
N = len(A)
if N < 2:
return -2
res = abs(A[1]-A[0])
for i in range(N):
has_next_val = False
next_val = -1
for j in range(N):
if j != i and A[j] >= A[i]:
if not has_next_val:
has_next_val = True
next_val = A[j]
else:
next_val = min(next_val, A[j])
if not has_next_val:
continue
res = min(res, next_val-A[i])
if res > 100000000:
return -1
return res
The following issues have been detected: timeout errors.
medium chaotic sequence; length=1K
running time: 0.296 sec., time limit: 0.144 sec.
medium chaotic sequence; length=2K
running time: 1.072 sec., time limit: 0.160 sec.
medium chaotic sequence; length=3K + [1,5,10]
running time: 2.376 sec., time limit: 0.160 sec.
large chaotic sequence; length=10K + [1,5,10]
Killed. Hard limit reached: 6.000 sec.
large chaotic sequence; length=20K + [1,5,10]
Killed. Hard limit reached: 6.000 sec.
large chaotic sequence; length=40K + [1,5,10]
Killed. Hard limit reached: 6.000 sec.