The array-algorithms tag has no wiki summary.
3
votes
2answers
65 views
Median of medians algorithm: why divide the array into blocks of size 5
In median-of-medians algorithm, we need to divide the array into chunks of size 5. I am wondering how did the inventors of the algorithms came up with the magic number '5' and not, may be, 7, or 9 or ...
-1
votes
3answers
116 views
Clustering: finding groups of close items within a large collection
I have an array of items (~5000 items, each item is an English word) and a distance function between pairs of items. I want to find groups of items within the array where all the items within a group ...
-1
votes
3answers
57 views
Finding Minimum Key and Predecessor in B-Tree
Explain how to find the minimum key stored in a B-tree and how to find the predecessor of a given key stored in a B-tree.
0
votes
1answer
108 views
Intersection of maximum and minimum subarrays
Suppose we have an array of some integers (can be both +ve and -ve).
We find non-empty maximum and minimum subarrays(subarrays have successive elements only) from this.
My claim is that these ...
1
vote
4answers
63 views
Difference between shuffling algorithms
Let's say we're to write a method to produce a shuffled deck of cards. Now to make it very simple, disregard the suits and so we have 52 cards.
One algorithm would be:
Populate an array of 52 ...
0
votes
1answer
38 views
Need to find lowest differences between first line of an array and the rest ones
Well, I've been given a number of pairs of elements (s,h), where s sends an h element on the s-th row of a 2d array.It is not necessary that each line has the same amount of elements, only known that ...
-1
votes
1answer
179 views
implementing Brute Force in c++
I have a problem that deals with optimization of a game that includes 2 players.
So we have an undirected connected graph with a number of edges and some vertices.
Each player has to remove edges and ...
-1
votes
2answers
140 views
Algorithm for finding a sum within an array? [closed]
Say you have some array with elements that you know are all positive, and smaller than a number N.
Can someone give me a general, high-level description of an algorithm to find out whether there is ...
2
votes
2answers
99 views
Associative array lookup cost
Consider two lookup functions:
simple={1,3,5}
function isX(id)
for _,v in ipairs(simple) do
if v==id then return true end
end
return false
end
assoc={[1]=true,[3]=true,[5]=true}
...
0
votes
1answer
213 views
Trouble with my algorithm to solve a boggle board
so I'm relatively new to Java (I'm taking AP java at my school currently) and I am trying to develop a recursive algorithm to solve an n*n board and I feel I am very close but not quite there yet.
I ...
1
vote
1answer
227 views
How can I bubble sort this?
In this program I just wanted to bubble sort the ArrayList words. So far I used the Collections.sort and it has placed all the lines in the text file alphabetically. However, I want to implement a ...
0
votes
1answer
77 views
Meaning of S[3i]S[3i + 1]S[3i + 2] [closed]
I have trouble understanding the following:
We have the String ABRACADABRA. We divide this into groups as example:
S is divided into the group:
S0 = <S[3i]S[3i + 1]S[3i + 2] for i = ...
2
votes
1answer
385 views
Longest Contiguous Subarray with Average Greater than or Equal to k
Consider an array of N integers. Find the longest contiguous subarray so that the average of its elements is greater (or equal) than a given number k.
The obvious answer has O(n^2) complexity. Can we ...
1
vote
1answer
118 views
sublists of a list with possitive sum
I'm trying to find the sublist of a list (with at least one positive integer) with the following 2 properties
1. the sum of it's elements is positive
2. it has the maximum length of all the other sub ...
4
votes
2answers
126 views
Algorithm to find non-dominated pairs
Given are pairs of integers (a1,b1),...,(an,bn). Pair i is "dominated" by pair j if ai < aj and bi < bj. What is an algorithm to quickly determine the list of pairs that are not dominated by any ...
10
votes
2answers
2k views
Given an array [a1b2c3d4] convert to [abcd1234]
Constraints :
O(1) space
O(n) Time
It is not a homework question just a interesting question I came across.
Here are some solutions I could think of but nothing that does it in given ...
0
votes
2answers
120 views
Convert a row and column sorted 2-D array to a sorted 1-D array
Given an 2-D Array of n*n elements:
all rows are sorted
all columns are sorted
For example:
1 5 7
2 6 8
3 9 10
convert it to a 1-D sorted array. Is there a solution better than O(nlog(n)).
2
votes
4answers
382 views
How to find the permutation of a sort in Java
I want to sort an array and find the index of each element in the sorted order.
So for instance if I run this on the array:
[3,2,4]
I'd get:
[1,0,2]
Is there an easy way to do this in Java?
3
votes
1answer
485 views
array: convert index of one dimensional array to a vector index of a multidimensional array
It will be a long question, please, take a deep breath before reading.
I want to understand what would be the fastest algorithm to convert index of one dimensional array to a vector index of a ...
2
votes
4answers
208 views
Given a list of integers, determine if 70% of the values are within 20% of one of the values
I want to check if the list values have some level of "closeness". Is there a good algorithm to do this? Bonus points for the most pythonic way.
Valid
[1,7,8,9]
[3,4,100,101,102,103,104,105]
Not ...
0
votes
2answers
426 views
Double dimension array sorting in O(n) time
I was asked a question in interview for sorting a double dimension array in O(n) time.How is it possible to do it in O(n).Can someone shed some light on it.. Thank you.
Input:
3 5 7 1
4 9 2 0
9 3 6 ...
2
votes
4answers
298 views
Grid Permutation Algorithm - Fixed Row Order
Imagine a 3x3 grid:
[A, B, %]
[C, %, D]
[E, F, G]
The percentages % stand for empty spaces/positions.
The rows can be moved like beads on a string, such that the permutations for the ...
5
votes
3answers
247 views
How to find a 2 unpaired elements in array?
You have an array with n=2k+2 elements where 2 elements haven't pair. Example for 8 elemets array: 1 2 3 47 3 1 2 0. "47" and "0" haven't pair in array. If I have array where only 1 element has't ...
4
votes
4answers
2k views
Can I find the max/min value in an unsorted Array in sub linear time?
Is it possible? If not, given an array of size n, how do I know if its better to just sort the array?
0
votes
2answers
282 views
The fastest algorithm to find the largest span (i,j) such that , ai + ai+1 +…+aj = bi + bi+1 +…+bj in arrays a and b
I encountered this problem while preparing for my exams.
Given two arrays of numbers a1,..., an and b1,....,bn where each number is 0 or 1, the fastest algorithm to find the largest span (i,j) such ...
8
votes
3answers
527 views
Linq get values not shared across multiple lists
What's the most efficient way to write a method that will compare n lists and return all the values that do not appear in all lists, so that
var lists = new List<List<int>> {
...
2
votes
3answers
2k views
Sorting Coordinate Points c++
in an application I measure a lot of 2d coordinates (x,y) of a
pattern. This pattern consists of a set of points on grid with fixed
pitches in x and y direction. These coordinates all have a score for
...
4
votes
4answers
220 views
Suffix Range c++
I am trying to build a Suffix range that is
if I have strings "catalog" "catalyst" "ban" "bany"
then suffix tree will be like
.
/ \
...
3
votes
2answers
940 views
datastructure behind browsing history
Im writing a QML file browser. Now, I want to implement a back and forward function. This function is similar to browser back and forward functionality. Example :
I start in "/home/text/folder1" and ...
-1
votes
2answers
1k views
finding a pair of integers in a sorted array which sum to K
Given a sorted array of integers, how can we find a pair of integers that sum to K?
e.g. array = 1,3,5,6,0, K = 6, the answer is 1 and 5.
Time complexity should be minimized.
2
votes
2answers
140 views
algorithm for searching in ranges
I am given a huge list of objects with attributes x and y. We are required to search for all objects lying between a given upper and lower bound of both the attributes.
I was wondering if there is an ...
-1
votes
1answer
205 views
Array Algorithms
I have one question to ask on Algorithms. I have been asked to write the algorithm on this: Not asking you to write the algo for me, but just let me know the efficient process what I need to do:
...
1
vote
1answer
118 views
sorting a file containing huge amount of data
Consider a file containing N words with one word per line.The file is too big so whole of it connot be read in memory at one time.
My ans:
Divide the file into k chunks.So size of each chunk x = N/k
...
6
votes
2answers
337 views
What's the best algorithm for finding the sum of all items in an arbitrary sub array
I have a problem, and an OK-ish solution. I'm hoping there's a better solution out there.
The problem
I have an array with around 200,000 integers. Given two indices, i1 and i2, I need to calculate ...
0
votes
2answers
170 views
Shortest subsequence with no interval duplicates
Given an unsorted array of N integers and a function getNextIndexOf(int k) that returns the index of the next element whose value is 'k', how would one get at the last element (i.e., index N) with the ...
0
votes
4answers
383 views
how does Float.toString() and Integer.toString() works?
How can i implement an algorithm to convert float or int to string?
I found one link
...
4
votes
3answers
2k views
calcuating the sum of nodes in a single verticle line of a binary tree
For a binary tree i want to get the sum of all nodes that fall in a single verticle line.I want the sum of nodes in each verticle node
A
/ \
B C
/ ...
-2
votes
3answers
137 views
Make an algorithm to find the element which is repeated n times in the 2n array [closed]
Make an algorithm to find the element which is repeated n times in the 2n array
I had implemented with a binary tree,and each node having counter associated with it. The node with max count is ...
0
votes
4answers
185 views
How to find the number of occurences of a number in a sorted Array in O(logn)
I have a sorted Array of Integers. Given a number, how to find the number of occurences of that number in O(logn) even the worst case.
