Tagged Questions
An algorithm is a sequence of well-defined steps that defines an abstract solution to a problem. Use this tag when your issue is related to algorithm design.
1
vote
0answers
10 views
Overlaying a supset array onto a subset array (in Javascript)
I have a set of arrays of the form
A= [1,2,3,4,5,6]
B= [7,8,9]
C= [5,6]
D= [9]
I want to "overlay" the supersets on the subsets so that the result set looks like this:
A= [1,2,3,4,5,6] (unchanged, ...
2
votes
1answer
12 views
What's time complexity of this Algorithm for breaking words? (Dynamic Programming)
Word Break(with Dynamic Programming: Top->Down) Given a string s and a dictionary of words dict, add spaces in s to construct a sentence
where each word is a valid dictionary word.
Return ...
-3
votes
0answers
12 views
prove that scheduling with release time and deadline is np-complete
suppose we are given a set of jobs that must be run on a single machine. each job i has a release time ri when it is first available for processing;a deadline di by which it must be completed; and a ...
0
votes
1answer
25 views
how to find weather a graph is tree or not?
i am trying to solve a SPOJ problem is it a tree ? in which i have to check weather a graph is tree or not??
in this problem i am using DFS to detect weather the graph has cycle or not..
my code is..
...
-2
votes
0answers
12 views
Software to display angorythms
Please help me to move this topic to the appropriate site in case if it is needed.
I'm looking for a software or online service that helps me to draw something similar to what is displayed on the ...
0
votes
0answers
26 views
Parsing Hierarchy defined by codes
I'm working on parsing a plain text file with a sort of hierarchical structure.
I know that some sort of recursive descendant algorithm should be able to help with this. But I have no experience on ...
0
votes
0answers
26 views
Efficiency of Breadth First Search
What would be the most efficient way to compute the fewest hops it takes to get from x1, y1 to x2, y2 on an unbounded/infinite chess board? Assume that from x1, y1 we can always generate a set of ...
1
vote
1answer
42 views
How to find the optimal grid placement for least distance between nodes of a network?
If I wanted to display the nodes of a network on a 2D grid, but also I wanted to ensure the least amount of manhattan distance between any two directly connected nodes (where there is a maximum of one ...
0
votes
3answers
60 views
Efficient string concatenation algorithm
This is a follow up question to :
Concatenation by += slower than that by using StringBuilder()
where I found out that string1+=string2 is much slower than string1.append(string2) where string1 is now ...
8
votes
2answers
179 views
Why is Java List traversal slower than file readline?
I had this piece of code:
while((line=br.readLine())!=null)
{
String Words[]= line.split(" ");
outputLine = SomeAlgorithm(Words);
output.write(outputLine);
...
1
vote
1answer
28 views
How to implement Efficient Test for a Point to Be in a Convex Polygon algorithm in C#?
Simple problem - find if a point is inside a convex Polygon. There is algorithm described yet due to be beeng an in Wolfram language and I ve got something wrong. This is what I have:
private static ...
1
vote
1answer
28 views
which is the cost of the average case?
According to my notes,we find the cost of the average case of the quicksort,like that:
We suppose that we are lucky-unlucky alternately.
L: lucky U:Unlucky
Then,these two relations:
...
-1
votes
0answers
30 views
Programmatically determine the associativity of an L1 cache
I searched for similar questions; one was similar but there wasn't a definitive answer.
I can write a C program to determine both the line length and size of a cache but I can't think of a way to ...
3
votes
1answer
36 views
Shortest path between two vertices when exactly one edge weight can be reduced by 50%?
This is an interview question I came across:
You are given a the map of airplanes between the cities in a country, basically a directed graph was given with weights as the cost of planes between the ...
0
votes
1answer
20 views
Using BFS for topological sort
Can Breadth first Search be used for finding topological sorting of vertices and strongly connected components in a graph?
If yes how to do that? and If not why not?
we generally use Depth first ...
0
votes
0answers
18 views
algorithm for catching trends and notify [on hold]
I am trying to create a system that will track our company sales, and it will see the hourly/daily/weekly trends, and if the current check is below or above the trends it could know something is ...
0
votes
0answers
15 views
Optimal Lat/Lon API call Algorithm with Radius as Parameter
Following Question:
There is an API, which gives information within a radius r around a lat/lon coordinate. Because coordinates are rectangular and a circle around a point isn't, there is an optimal ...
google-maps
0
votes
1answer
38 views
“Rotating” a ArrayList<Integer>
I have an ArrayList in the board game-like game I am developing in Java, I format this ArrayList as a square, as so (numbers being indexs);
/*
* |0 |1 |2 |3 |
* |4 |5 |6 |7 |
* |8 |9 |10|11|
* ...
0
votes
2answers
37 views
insertion sort leaves larger number unsorted
I'm trying to sort the following list (which gets inserted to the a array):
10 9 8 7 6 5 4 3 2 1
After the below java code executes I get the following (not sure why the largest number is still ...
0
votes
1answer
25 views
Are there a design pattern to controlling slave jobs or management of slaves from master?
Management or Controller design patern. I have one class doing two different job in structure. Are there a design pattern to refactor it in more maintable way? Or, how should I divide this class in ...
0
votes
2answers
16 views
Algorithm to prevent duplication of field while copying data from text file to excel
I have over 100 text (.txt) files. The data in these files is comma-separated, for example:
good,bad,fine
The aforementioned items are just an example, the data can contain anything from individual ...
0
votes
1answer
14 views
How to get Encryption key if i have data which needs to be encrypted is present and data after encryption is also present using DES
I have a data which is encrypted using DES , it's a 10 character data which is encrypted into 28 character where last character is always = . I have around 10 data samples available. How can i get key ...
2
votes
3answers
58 views
Find missing element from one array comparing from other in single for loop
Is it possible to find out one missing element from one array that is not present in other array using single for loop in Java
e.g. a1 = {2,5,1,9,3,4} , length n+1
a2 = {2,4,1,5,3} , length n
...
0
votes
2answers
19 views
Array sort algorithm on two values. One descending other ascending. Javascript
I have the following array structure in Javascript:
var unsorted = [
{h:50,t:70},
{h:70,t:60},
{h:30,t:10}, // Ideal Value (Best combination of t being the least and h being the ...
-1
votes
1answer
29 views
What is the time complexity of these dependent nested loops? [duplicate]
How to calculate time and space complexity for these algorithms?
I referred many sites but its confusing me. please any one explain me.
1.
for(i=0;i<n;i++)
{
for(j=i;j<n;j++)//this for ...
0
votes
1answer
30 views
Finding similar strings in large datasets
I'm using levenshtein distance to retrieve similar strings from a list. At the moment the list has just a few thousand items, but we'll need to support at least 100k items.
I'm trying to make this ...
1
vote
3answers
43 views
Detecting a cycle and making the summation faster
Let's assume that we're given an array of positive integers, probably of a very large size, and we're given another positive integer, and let's call it k, and another positive integer, which we will ...
0
votes
1answer
61 views
Java Knights Walk Algorithm (Brute Force)
I am trying to write a Knights Walk Algorithm(brute force) using Java. I was able to create a program to move through a 5x5 grid but the program always leaves out 06 cells out of the board. And my ...
1
vote
2answers
100 views
solve Equation a+b+c+d=a*b*c*d [on hold]
Hello i am trying to solve this equation for a programming problem that states that you need to do a complete search algorithm to find this results.
However an O(N^4) algorithm takes a lot of time, ...
0
votes
1answer
22 views
How to get random item by priority from several arrays that could be empty
I have three lists: high, mid, and low (can be also 3 arrays)
I want to choose one items from the three lists by priority chance
E.g. From High 70% chance from mid 20% and from low rest 10%
...
-1
votes
0answers
8 views
How to revese edges in graph when adjacency List representation is used.. and in-place algorithm is needed
by an adjacency-matrix A simply compute the transpose of the matrix AT in time O(V 2). If the
graph is represented by an adjacency-list a single scan through this list is sufficient to construct the ...
0
votes
0answers
15 views
Sample data to run maps routing algorithms [on hold]
I am trying to learn the algorithms that are used in online mapping programs like google maps,bing maps etc. Specifically I am looking to learn/study the algorithms used to compute the routes between ...
0
votes
3answers
43 views
Write algorithm to return top 2 elements in terms of frequency from a long list of elements
I was asked this question during interview. I was not able to solve this. I wonder if anyone has a good idea how to solve it:
If I have a long list of integers, return the integer which top 2 in ...
0
votes
0answers
53 views
Smallest solution to system of linear equations
I need to find the smallest number of steps it takes to get between two points in a grid. If you are positioned at the center, and you can only move in 8 directions to the integer points surrounding ...
-6
votes
0answers
33 views
to count number of distinct words (containing N consonants and M vowels) from a given string [on hold]
I have a problem based on combination and permutation .it goes like this ..we have a long string (1 - 10^5 length) we have to find the number of distinct words ,we can make from this string which has ...
1
vote
1answer
30 views
Data Structure for list of records (name, points) - Efficient Search(by name), Search(by rank based on points) and Update(points)
Please suggest a data structure for representing a list of records in memory. Each record is made up of:
User Name
Points
Rank (based on Points) - optional field - can be either stored in the record ...
3
votes
3answers
37 views
Complexity for finding one of many elements in an array
The question is pretty much what the title says, with a slight variation. If I remember correctly, finding an entry in an array of size 'n' has as the average case the complexity O(n).
I assume that ...
-1
votes
0answers
19 views
Find Diameter of tree using dynamic programming [on hold]
i think we can use BFS at each node of tree and find max distance of node and return to parent 1+maxdistance if only one child ... otherwise 2+ maxdistance1+maxdistance2 if it has two child
3
votes
2answers
76 views
Too many collisions in hash function
I was trying to hash about 64million 64bit unique unsigned integers to 128 million buckets(27bit wide address). I tried Bob Jenkin's HashLittle and Murmur hash(Both these hash functions gives 32bit ...
-2
votes
0answers
15 views
Implementing segment tree for handling rotating queries [duplicate]
Given an array of N integers and we can perform 2 type of operations on this array :
Type 0: Described by 0 Li Ri Xi : In this we have to rotate each value in this range with value equal to Xi.If ...
0
votes
1answer
20 views
Efficient sorting algorithm that puts elements of an array into two in either one of two sections according to some value
I need some reference to some sorting algorithms/ideas that I could adapt to most efficiently split the elements of an array into two sections for instance, if e = 1E10-3
then I want all elements ...
2
votes
2answers
81 views
Is there a O(N) solution to getting top k most occurring string in List<String>? [duplicate]
The problem is: Given a list of strings and an integer k, return the top k most frequently occurring words in descending order based on frequency. This must be done O(N) where N is the length of the ...
2
votes
4answers
65 views
Keeping the order of the array in check in C++
There are a lot of algorithms that do sorting in an efficient way, and I was wondering
if there are efficient ways of outputting the order of the array after sorting.
For instance, let's say we have
...
-1
votes
0answers
30 views
java NZEC(Non Zero Exit Code) [on hold]
When I try to execute the following code to find the prim number by using the SIeve algo, I am getting the NZEC error.
I couldn't figure out the run time issue present in my code which is giving the ...
1
vote
0answers
34 views
nth Convolved fibbonaci numbers of order 6 modulo m
Problem: Find the coefficient of xk in (1−x−x2)-6 modulo m.
Constraints:
k≤264
m≤105, m can be a composite number.
I have 10^5 such queries to process in 2 sec, so O(log k) for each query ...
-1
votes
1answer
61 views
Element rotation in segment tree [on hold]
Given an array A with N numbers(all positive and contain less than
or equal to 4 digits), 2 types of queries are to be supported. There
are total M queries.
Update a range given by ...
0
votes
0answers
17 views
How to optimize assignment of tasks to agents with these constraints?
I have an assignment problem as a part of my Master's Thesis, and I am looking for general direction in solving the same.
So, there is a list of agents, and a list of tasks, with number of tasks ...
1
vote
1answer
37 views
What are the disadvantages of hashing function using multiplication method
There are two basic methods for implementing a hash function that are cited in pretty much every text book and CS courses:
Division method where we simply do k mod m essentially picking m as prime ...
0
votes
0answers
9 views
What is the significance of VIKOR approach..suggest an algorithm
VIKOR is used for decision making. I need to know the significance of VIKOR value comparing with the weight of attributes. Also suggest information about utility measure and regret measure in VIKOR ...
0
votes
0answers
46 views
Improve the running time of Implementation of Dijkstra (C++) [on hold]
I am using a priority_queue ( STL ) to implement the Dijkstra's algo.
while(!Q.empty())
{
u = Q.top().first;
Q.pop();
int size=G[u].size();
for(int i=0; ...
