Questions tagged [arrays]
A sequential random-access data structure whose size can typically not be changed after creation.
-2
votes
0answers
17 views
computer science question 2 java [on hold]
Write a method createMines that creates and returns a 10x10 array of boolean. Set 10 random entries in the table to true. The rest of the entries should be false.
-2
votes
0answers
26 views
Computer Science Question 1 java [on hold]
Write a void method, showMap, that takes a 2-dimensional array of boolean as a parameter and prints the array in the following tabular format: if the corresponding entry is true, then an 'X' is ...
0
votes
1answer
29 views
Applying minimax tree to this array [closed]
Please tell me how I should apply minimax algorithm to the array
$$ 15, 12, 14, 16, 11, 13$$
and make a tree?(I understand how minimax algorithm works but I can't apply it to an array)
1
vote
2answers
29 views
Find the minimum N such that the sum of beauty of all numbers from 1 to N is at least X
The beauty of a number is defined as follows :-
...
1
vote
0answers
23 views
Recurrence Relation for Column Major Form of multidimensional array
A two dimensional array is stored in column major form in memory if the elements are stored in the following sequence $$A[0][0] A[1][0] A[2][0]...A[n_1-1][0] ... A[0][1] A[1][1] ... A[n_1-1][1] .... A[...
0
votes
0answers
28 views
Given a list of arrays, find all pairs of arrays that share a single element [closed]
I need to find a fast algorithm to perform this task. Possible O(n log n) or even O(n).
For example, giving following 5 arrays:
$\begin{bmatrix}10,7,5,5,7\end{bmatrix}$
$\begin{bmatrix}1,7,5,2,2\end{...
3
votes
2answers
68 views
Is it possible to solve this problem in less than n^2 time without using additional space?
Here's the problem:
Given an array array containing integers, maximize array[i] + array [j] + |i - j| where i and j both range ...
2
votes
1answer
37 views
Find four sets where each element from those four appears in at least two of those four sets
I have a list of sorted arrays ("sets") of integers $A_1..A_n$ where each element is unique w.r.t. the other elements in the same array:
$A_i = \{x_{i,1}..x_{i,c_i}\}$
$x_{i,p} < x_{i,p+1}$
$A_i$ ...
0
votes
1answer
22 views
Algorithm to generate repetitive sequence of fixed length
I am trying to create an algorithm to generate test cases. Each test case is an array of $n$ natural integers which are randomly generated using a pseudo-random function. The bound for $n$ is $0 < ...
1
vote
0answers
38 views
Array subset division with equal sums
Today I stumbled upon a problem which looked like the partition problem but certainly is different.
Given array of positive integers, guaranteed to not be divisible into two continious subsets of ...
3
votes
1answer
82 views
Find the smallest element greater than current element
my question is that given a list of integers (lets say A), for each element A[i], find the smallest element A[j] which could satisfy A[i] < A[j] and i < j. Return -1 if there is no such element.
...
0
votes
1answer
15 views
How to count stores in cache analysis of matrix multiplication
I'm trying to understand cache misses/iter and came across this that I couldn't understand or reason out.
For ijk iteration, my slides say that there are 2 loads and 0 stores.
...
2
votes
1answer
80 views
How to find efficiently the minimum modification to avoid close consecutive numbers?
I have an array of sorted numbers:
arr = [-0.1, 0.0, 0.5, 0.8, 1.2]
I want the difference (dist below) between consecutive ...
1
vote
0answers
55 views
How does prefix summing the count histogram in counting sort result in an array of output indices?
My implementation of counting sort is based on the description I found here. I've also included my code in this REPL, but here it is:
...
0
votes
0answers
20 views
Finding periods of a string
I have been given a string $S$ (indexed from 1) and an array $B$ defined by $B[j]=\max(k<j, S[1,k]=S[j-k+1,j])$ for all $1 \leq j \leq len(S)$.
I am supposed to find a relation between $B$ and the ...
0
votes
1answer
31 views
How to compare an element with other elements within an array efficiently for a condition
I need to compare each index with one another and associated array value as well.
For example,
...
1
vote
1answer
24 views
How would you identify the size of a circular turing tape?
Came across this interesting problem in one of my interviews. Suppose you have a circular turing tape, i.e. simply a circular array. You do not know the size i.e. the number of cells available in that ...
2
votes
0answers
55 views
Sort arrays $A$ and $B$ of the same elements using only comparisons between an element of $A$ and one of $B$
Premise: Let $A := [ k(1), k(2), ..., k(n) ]$ and $B:=[ l(1), l(2), ..., l(n) ]$ be two Arrays where $k$ and $l$ are permutations. (What I'm trying to express: $A$ and $B$ contain the same elements in ...
2
votes
1answer
44 views
Maximum number of segments with no intersection [duplicate]
This is an interview question.
Suppose you have an array of n segments, when each segment is a pair of two integers: start point and end point. For example: ...
4
votes
3answers
88 views
Sum of unique elements in all sub-arrays of an array
Given an array $A$, sum the number of unique elements for each sub-array of $A$. If $A = \{1, 2, 1, 3\}$ the desired sum is $18$.
Subarrays:
...
0
votes
1answer
35 views
Strengths and limitations of arrays [closed]
What are the strengths and limitations of arrays? What considerations go into choosing an array over another data structure, or vice-versa?
0
votes
1answer
38 views
Comparison between: Maximum Absolute Difference & Min Steps in Infinite Grid
There are two questions that I am trying to draw a comparison between:
...
1
vote
1answer
48 views
Algorithmic Design to Undo Rotation of Array
An array $A$ of $n$ distinct, ascending integers is rotated to the right by $k$ positions, resulting in the array $A_{k}$.
That is, the element at index $i$ in $A$ is moved to index $(i+k)\mod n$ in $...
1
vote
2answers
62 views
FInding the combination with the least number of elements from and array of integers, given an integer sum
I'm doing and assignment where the problem is to find the combination with the least number of elements form an array of integers, given an integer sum. I have solved this using a gready algorithm ...
1
vote
2answers
61 views
What does the “0 ≤ K < N-1” expression means?
Given the following statement:
"A nonempty array A consisting of N integers is given. Any integer K,
such that 0 ≤ K < N-1, splits array A into two non-empty parts"
What does the 0 ≤ K < ...
1
vote
2answers
19 views
Generate Evenly Distributed Pattern Based on Weights
I have an array of items $A = \{A_i\}, i \in I $ with integer weights $W_i, i \in I$. I need to build a function $f: I \rightarrow A $, that produces evenly distributed patterns of array elements ...
2
votes
1answer
81 views
what is actually a circular array and representation
There are two ways to implement a circular array either take a new array of size 2N where N is the size of the initial array and copy initial array twice into that ...
2
votes
1answer
32 views
Sorting Algorithm which prevents strings with at least one identical char from being next to each other
Imagine this Table:
All combinations represented in the table (1,2 ; 1,3 ; 1,4 ; etc.) are stored as strings in an array with a total of (n^2-n)/2 elements (combinations).
I'm looking for an ...
2
votes
1answer
153 views
Maximum Equal Sum K Subsequences
Given an array we need to find maximum equal sum $K$ subsequences, i.e. we want the sum to be maximized such that there are exactly $K$ non-overlapping subsequences each having the same sum.
Example:
...
3
votes
1answer
173 views
Average-case complexity of linear search where half of the elements in the array are duplicates
I know that for an array of size n distinct elements, the Average Case complexity for linear search is as follows:
A(n) = $\frac{n + 1}{2}$
However, I am having trouble coming up with the Average ...
0
votes
1answer
55 views
1
vote
2answers
784 views
How is the formula for calculation in row/column major obtianed?
In my book, this formula is given for calculation of address of row major order's element $[I,J]$:
Address of $[I,J]$th element in row major order $= B + W[n(I-L_r)+ [J-L_c]]$
where B denotes base ...
2
votes
0answers
38 views
Abstract Data Type
I have been studying data structures. In that I have come across topics like Array being defined as Power set of cross product of set of objects and set of natural number and list being defined as ...
0
votes
2answers
88 views
1D Peak-finding problem, how to derive the formula?
I couldn't find a good answer to how this formula was derived for the divide and conquer algorithm in a 1D Peak-Finding problem.
About the problem
Basically, there's an array of numbers and we want ...
2
votes
1answer
47 views
Selecting a subtree in an array representation of a binary tree
Consider a zero-indexed array representation of a binary tree (as in a binary heap), where
0 is the root
The left child of i is ...
1
vote
1answer
77 views
Calculate the minimum absolute difference between the maximum and minimum number from the triplet of 3 arrays
Question is:
Calculate the minimum absolute difference between the maximum and minimum number from the triplet a, b, c such that a, b, c belongs arrays A, B, C respectively.
There is another ...
-4
votes
1answer
27 views
Construct an array from a binary tree
I am looking for a suggestion. I know it is possible to construct a binary tree from an array. I want to know that vice verse is true? Is it possible to construct an array from a binary tree? If yes ...
4
votes
1answer
71 views
Proof of correctness of reversal algorithm for array rotation
We are given an array A of size n and we have to rotate it in left direction by d positions. So e.g. if A = {1, 2, 3, 4, 5, 6, 7} then for ...
2
votes
0answers
39 views
Counting subarrays where each number either doesn't occur or occurs odd number of times
We have given array $V$ of $N$ integers, we want to count the number of subarrays of the array such that each elements in the subarray either doesn't occur at all, or it occurs odd number of times.
...
7
votes
1answer
446 views
Applicative-order languages don't support constant time array writes? If not, why not?
I'm reading Steven Skiena's "The Algorithm Design Manual", and in one of his War Stories on page 155 he states:
Efficiency is a great challenge in Mathematica, due to its applicative
model of ...
1
vote
3answers
59 views
Algorithm to compute maximum of blocks
We have $n$ numbers lying on a circle, where $n$ is even. We want to compute the maximum of any $n/2$ consecutive numbers (so, we should get $n$ values in total).
One algorithm is to compute the ...
2
votes
1answer
32 views
Can this Arrow-Ring puzzle be encoded as an integer programming problem?
I would like to write a solver for these kind of Arrow-Ring puzzles. However, I can't encode all the constraints correctly.
I noticed that Sudoku can be solved using integer programming and I am ...
1
vote
1answer
196 views
Median of two sorted arrays of different size in logarithmic time?
The solution given in Cormen is as follows:
Reading this solution, the first doubt that comes in my mind is what if the median lies in array B. According to this solution, we are applying binary ...
1
vote
1answer
68 views
Finding duplicate in immutable array in linear time and constant space
We have a array of $N$+1 integers. The integers range from 1 to $N$. The array contains at least one duplicate. Our goal is to find one of the duplicate entries. We have the constraint that we cannot ...
2
votes
1answer
67 views
Summing two array using FFT: time complexity analysis
This is the problem :
Given two arrays of $n$ elements A and B, let's define their sum as
$$ A + B = \{ a + b \mid a \in A \text{ and } b \in B \}. $$
Calculate $A + A$ in optimal time given ...
3
votes
1answer
43 views
Why are linked lists considered O(1) for in-middle insertion/deletion whereas dynamic arrays are considered O(n)?
I am struggling to understand why linked lists seem to be accepted to have better big-O performance than arrays for in-middle insertion/deletion. The performance differences between lists and arrays ...
3
votes
2answers
326 views
Find the kth smallest element in an unsorted array of non-negative integers
I need to find the kth smallest element in an unsorted array of non-negative integer.
kth smallest element is the minimum possible n such that there are at least kth elements <= n.
The rub here ...
1
vote
0answers
20 views
How to chose the condition for expand in hash-table?
How can I chose the condition for expanding of the array in chain-hashing if I want that given some cell (that contains elements) , the number of cells that I need to move about them is O(1) until the ...
0
votes
1answer
43 views
Finding the smallest positive missing number in array of integers contains negative and duplicates number
I found this solution but I don't understand it. Can anyone explain the idea behind it ?
the solution:
A O(n) time and O(1) extra space solution:
The idea is similar to this post. We use array ...
2
votes
2answers
642 views
Given an array of integers and a value k, find the length of the longest subarray with max-gap no more than k
I'm struggling with this problem: you are given an array $A$ of $n$ integers and a number $k \in \mathbb{N} : k \neq 0$. The problem asks to find an algorithm that runs in $\Theta(n)$ that returns the ...
