Algorithms associated with arrays
2
votes
3answers
60 views
Am I interpreting this pseudocode wrong?
I've got this pseudocode:
COMPARE-EXCHANGE(A,i,j)
if A[i] > A[j]
exchange A[i] with A[j]
INSERTION-SORT(A)
for j = 2 to A.length
for i = j-1 downto 1
...
0
votes
0answers
28 views
Is linear prefix average method better than quadratic prefix average method?
I've created a method (based on pseudocode I found online) to compute prefix averages for an array but I'm not sure I've satisfied the requirement.
The requirement is:
Given an array a[1…n] of ...
0
votes
1answer
28 views
using a set of vectors in a root searching algorithm
I am working with a time series in which a simple root searching algorithm is needed to calculate a root by iteration. In order to do this I use the package rootSolve. However, I am having some ...
0
votes
1answer
34 views
Modeling the card game War in Ruby and keep getting an infinite loop. Could someone help me understand what's going wrong in my control flow
I'm new to Ruby and only started a few weeks ago. I'm trying to create an algorithm that simulates how the game is played, but I'm getting stuck in an infinite loop. Something is wrong with my ...
0
votes
3answers
143 views
least frequent common number from a int array
I have to find least common number from an int array , I have written code but it is not working properly ,
Here is my logic,
1. sort the array
2. get min common counter updated
3. get if all are ...
2
votes
2answers
113 views
Find Possible addition combinations in array
What is the best way to approach this problem? I have no idea on how to start. This is not a homework problem, but rather practice for interviews.
'Using the JavaScript language, have the function ...
0
votes
0answers
40 views
ith order statistic with bandwidth constraint
Consider the following: Mary and Larry each have an array, M [1,..., n] and
L[1,..., n] respectively. All of the elements in M and L are distinct. Mary and
Larry are interested in finding the i th ...
2
votes
0answers
103 views
What is the running time of comb sort?
According to me, Comb sort should also run in sub quadratic time just like shell sort. This is because comb sort is to bubble sort just how shell sort is related to insertion sort. Shell sort sorts ...
2
votes
1answer
132 views
Updating a range and keeping track of the maximum value that occurs at every index [closed]
You are given an array, say A[], of N elements, initially all of them are equal to negative infinity.
Now you are asked to perform two types of queries(Total M queries):
Type 1. Given two ...
0
votes
2answers
119 views
Skill set matching algorithm
I was asked this in an interview.
I have been trying to find an elegant algorithm for this problem but haven't been able to do so.
Given a list of people(represented as numbers - id's) with their ...
1
vote
1answer
51 views
Container complexity
Hence I have a std::set<int> and std::list<int>.
I want to have my container sorted.
For set I will have complexity like O(nlogn) for n inserted elements.
For list I will have complexity ...
0
votes
0answers
25 views
Optimize / redesign this java code
folks.
I need help or advice on decision making about a a design pattern (or sort of such) to uuse:
Have an application, running on weblogic via EJBs. Part of application deals with the the very ...
1
vote
3answers
113 views
Divide and Conquer Recursion
I am just trying to understand how the recursion works in this example, and would appreciate it if somebody could break this down for me. I have the following algorithm which basically returns the ...
2
votes
3answers
1k views
Finding a maximum sum contiguous sub array
I am writing a code to find the maximum sum contiguous sub array in C. The logic seems fine according to me, but still the output is not correct. Please look into the code. The algorithm divides a ...
5
votes
2answers
318 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
147 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
892 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
178 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
114 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
62 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
310 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
170 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 ...
3
votes
2answers
133 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
420 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
341 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
86 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
626 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
3answers
157 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
241 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
3k 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
3answers
232 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
670 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
772 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
266 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
485 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
425 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
362 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
4k 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
406 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
655 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>> {
...
3
votes
3answers
4k 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
239 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
1k 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 ...
3
votes
2answers
2k 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
156 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
236 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
140 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
529 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
205 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
521 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
...
