There is a stream of n (idKey, value) pairs arriving in an arbitrary order, where idKey is an integer between 1 and n and value is a string. No two pairs have the same id.
Design a stream that returns the values in increasing order of their IDs by returning a chunk (list) of values after each insertion. The concatenation of all the chunks should result in a list of the sorted values.
Implement the OrderedStream class:
OrderedStream(int n) Constructs the stream to take n values.String[] insert(int idKey, String value) Inserts the pair (idKey, value) into the stream, then returns the largest possible chunk of currently inserted values that appear next in the order.Example:
Input [ "OrderedStream ", "insert ", "insert ", "insert ", "insert ", "insert "] [[5], [3, "ccccc "], [1, "aaaaa "], [2, "bbbbb "], [5, "eeeee "], [4, "ddddd "]] Output [null, [], [ "aaaaa "], [ "bbbbb ", "ccccc "], [], [ "ddddd ", "eeeee "]]
Explanation // Note that the values ordered by ID is [ "aaaaa ", "bbbbb ", "ccccc ", "ddddd ", "eeeee "]. OrderedStream os = new OrderedStream(5); os.insert(3, "ccccc "); // Inserts (3, "ccccc "), returns []. os.insert(1, "aaaaa "); // Inserts (1, "aaaaa "), returns [ "aaaaa "]. os.insert(2, "bbbbb "); // Inserts (2, "bbbbb "), returns [ "bbbbb ", "ccccc "]. os.insert(5, "eeeee "); // Inserts (5, "eeeee "), returns []. os.insert(4, "ddddd "); // Inserts (4, "ddddd "), returns [ "ddddd ", "eeeee "]. // Concatentating all the chunks returned: // [] + [ "aaaaa "] + [ "bbbbb ", "ccccc "] + [] + [ "ddddd ", "eeeee "] = [ "aaaaa ", "bbbbb ", "ccccc ", "ddddd ", "eeeee "] // The resulting order is the same as the order above.
Constraints:
1 <= n <= 10001 <= id <= nvalue.length == 5value consists only of lowercase letters.insert will have a unique id.n calls will be made to insert.program main
use :: ordered_stream_mod
implicit none
type(ordered_stream) :: os
integer :: i
character(len=6) :: value
! Example 1
os = ordered_stream(5)
print '(A)', os%insert(3, 'ccccc ')
print '(A)', os%insert(1, 'aaaaa ')
print '(A)', os%insert(2, 'bbbbb ')
print '(A)', os%insert(5, 'eeeee ')
print '(A)', os%insert(4, 'ddddd ')
do i = 1, 5
write (unit=*, fmt='(*(g0))') os%insert(i, '')
end do
! Example 2
os = ordered_stream(4)
print '(A)', os%insert(2, 'bbbbb ')
print '(A)', os%insert(3, 'ccccc ')
print '(A)', os%insert(1, 'aaaaa ')
print '(A)', os%insert(4, 'ddddd ')
do i = 1, 4
write (unit=*, fmt='(*(g0))') os%insert(i, '')
end do
! Example 3
os = ordered_stream(3)
print '(A)', os%insert(1, 'aaaaa ')
print '(A)', os%insert(2, 'bbbbb ')
print '(A)', os%insert(3, 'ccccc ')
do i = 1, 3
write (unit=*, fmt='(*(g0))') os%insert(i, '')
end do
contains
function insert(this, id_key, value) result(chunk)
class(ordered_stream), intent(inout) :: this
integer, intent(in) :: id_key
character(len=*), intent(in) :: value
character(len=:), allocatable :: chunk(:)
if (size(this%values) < id_key) then
allocate(character(len=len(value)) :: chunk(0))
else
allocate(character(len=len(value)) :: chunk(1))
chunk(1) = value
end if
this%values(id_key) = value
do i = id_key - 1, 1, -1
if (this%values(i) > this%values(id_key)) then
exit
end if
chunk(1) = this%values(i)
end do
return
end function insert
end program main
module ordered_stream_mod
implicit none
private
public :: ordered_stream
type, public :: ordered_stream
private
integer :: n
character(len=:), allocatable :: values(:)
contains
procedure :: insert => insert
end type ordered_stream
contains
subroutine insert(this, id_key, value)
class(ordered_stream), intent(inout) :: this
integer, intent(in) :: id_key
character(len=*), intent(in) :: value
if (size(this%values) < id_key) then
allocate(character(len=len(value)) :: this%values(id_key))
end if
this%values(id_key) = value
do i = id_key - 1, 1, -1
if (this%values(i) > this%values(id_key)) then
exit
end if
this%values(i) = this%values(id_key)
end do
return
end subroutine insert
end module ordered_stream_modtemp.f95:2:11:
2 | use :: ordered_stream_mod
| 1
Fatal Error: Cannot open module file ‘ordered_stream_mod.mod’ for reading at (1): No such file or directory
compilation terminated.
module ordered_stream
implicit none
type :: ordered_stream
integer :: n
integer, allocatable :: keys(:)
character(len=5), allocatable :: values(:)
contains
procedure :: insert
end type
contains
function insert(this, id_key, value) result(chunk)
class(ordered_stream), intent(inout) :: this
integer, intent(in) :: id_key
character(len=*), intent(in) :: value
integer :: i
character(len=5), allocatable :: chunk(:)
! Check if the key is already in the stream
do i = 1, this%n
if (this%keys(i) == id_key) then
! If the key is already in the stream, update the value
this%values(i) = value
return
end if
end do
! If the key is not in the stream, insert it
this%n = this%n + 1
allocate(this%keys(this%n))
allocate(this%values(this%n))
this%keys(this%n) = id_key
this%values(this%n) = value
! Sort the keys and values
call sort(this%keys, this%values)
! Return the largest possible chunk of currently inserted values
! that appear next in the order
chunk = this%values(this%n - 1)
do i = this%n - 2, 1, -1
if (this%keys(i) == this%keys(i + 1) - 1) then
chunk = [chunk, this%values(i)]
else
exit
end if
end do
end function
subroutine sort(keys, values)
integer, intent(inout) :: keys(:)
character(len=*), intent(inout) :: values(:)
integer :: i, j
integer :: temp
character(len=5) :: temp_value
do i = 1, size(keys) - 1
do j = i + 1, size(keys)
if (keys(i) > keys(j)) then
temp = keys(i)
keys(i) = keys(j)
keys(j) = temp
temp_value = values(i)
values(i) = values(j)
values(j) = temp_value
end if
end do
end do
end subroutine
end module
program main
use ordered_stream
implicit none
type(ordered_stream) :: os
integer :: id_key, i
character(len=5) :: value
character(len=5), allocatable :: chunk(:)
! Examples
os = ordered_stream(5)
id_key = 3
value = "ccccc "
chunk = os%insert(id_key, value)
write (*,*) chunk
id_key = 1
value = "aaaaa "
chunk = os%insert(id_key, value)
write (*,*) chunk
id_key = 2
value = "bbbbb "
chunk = os%insert(id_key, value)
write (*,*) chunk
id_key = 5
value = "eeeee "
chunk = os%insert(id_key, value)
write (*,*) chunk
id_key = 4
value = "ddddd "
chunk = os%insert(id_key, value)
write (*,*) chunk
! Test cases
do i = 1, 10
os = ordered_stream(5)
id_key = i
value = "value " // char(ichar('a') + i - 1)
chunk = os%insert(id_key, value)
write (*,*) chunk
end do
end program
temp.f95:4:26:
4 | type :: ordered_stream
| 1
Error: MODULE attribute of ‘ordered_stream’ conflicts with PROCEDURE attribute at (1)
temp.f95:10:7:
10 | end type
| 1
Error: Expecting END MODULE statement at (1)
temp.f95:12:8:
12 | contains
| 1
Error: Unexpected CONTAINS statement in CONTAINS section at (1)
temp.f95:15:30:
1 | module ordered_stream
| 2
......
15 | class(ordered_stream), intent(inout) :: this
| 1
Error: Type name ‘ordered_stream’ at (1) conflicts with previously declared entity at (2), which has the same name
temp.f95:22:24:
22 | do i = 1, this%n
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:23:22:
23 | if (this%keys(i) == id_key) then
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:25:22:
25 | this%values(i) = value
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:27:15:
27 | end if
| 1
Error: Expecting END FUNCTION statement at (1)
temp.f95:28:11:
28 | end do
| 1
Error: Expecting END FUNCTION statement at (1)
temp.f95:31:14:
31 | this%n = this%n + 1
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:32:23:
32 | allocate(this%keys(this%n))
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:33:23:
33 | allocate(this%values(this%n))
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:34:14:
34 | this%keys(this%n) = id_key
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:35:14:
35 | this%values(this%n) = value
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:38:24:
38 | call sort(this%keys, this%values)
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:42:22:
42 | chunk = this%values(this%n - 1)
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:43:21:
43 | do i = this%n - 2, 1, -1
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:44:22:
44 | if (this%keys(i) == this%keys(i + 1) - 1) then
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:45:38:
45 | chunk = [chunk, this%values(i)]
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:46:16:
46 | else
| 1
Error: Unexpected ELSE statement at (1)
temp.f95:47:20:
47 | exit
| 1
Error: EXIT statement at (1) is not within a construct
temp.f95:48:15:
48 | end if
| 1
Error: Expecting END FUNCTION statement at (1)
temp.f95:49:11:
49 | end do
| 1
Error: Expecting END FUNCTION statement at (1)
temp.f95:14:24:
14 | function insert(this, id_key, value) result(chunk)
| 1
Error: Symbol ‘this’ at (1) has no IMPLICIT type
temp.f95:78:9:
78 | use ordered_stream
| 1
Fatal Error: Cannot open module file ‘ordered_stream.mod’ for reading at (1): No such file or directory
compilation terminated.
def count_good_triplets(arr, a, b, c):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if abs(arr[i] - arr[j]) <= a:
for k in range(j+1, len(arr)):
if abs(arr[j] - arr[k]) <= b and abs(arr[i] - arr[k]) <= c:
count += 1
return count
The algorithm iterates through the array with three nested loops. The outer loop iterates through all the elements in the array with index i. The second loop starts from i+1 and goes till the last element in the array with index j. The third loop starts from j+1 and iterates till the last element in the array with index k.
Inside the innermost loop, we check if the absolute difference between arr[i] and arr[j] is less than or equal to a. If it is, proceed to calculate the absolute difference between arr[j] and arr[k] and check if it is less than or equal to b, as well as the absolute difference between arr[i] and arr[k] to check if it is less than or equal to c. If all three conditions are true, increment the count by 1.
Return the count after all nested loops are completed.
int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
int count = 0;
for (int i = 0; i < arr.size(); i++) {
for (int j = i + 1; j < arr.size(); j++) {
if (abs(arr[i] - arr[j]) <= a) {
for (int k = j + 1; k < arr.size(); k++) {
if (abs(arr[j] - arr[k]) <= b && abs(arr[i] - arr[k]) <= c) {
count++;
}
}
}
}
}
return count;
}
The algorithm iterates through the array with three nested loops. The outer loop iterates through all the elements in the array with index i. The second loop starts from i+1 and goes till the last element in the array with index j. The third loop starts from j+1 and iterates till the last element in the array with index k.
Inside the innermost loop, we check if the absolute difference between arr[i] and arr[j] is less than or equal to a. If it is, proceed to calculate the absolute difference between arr[j] and arr[k] and check if it is less than or equal to b, as well as the absolute difference between arr[i] and arr[k] to check if it is less than or equal to c. If all three conditions are true, increment the count by 1.
Return the count after all nested loops are completed.