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.
0
votes
0answers
4 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
2answers
22 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
26 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 ...
0
votes
2answers
60 views
solve Equation a+b+c+d=a*b*c*d
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
0answers
14 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%
...
0
votes
0answers
4 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
9 views
Sample data to run maps routing algorithms
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 ...
google-maps
0
votes
0answers
18 views
An efficient way to find the mean distance between points on a circle
I have the following problem. Consider two sets of points on a circle. In python we can make them as
from __future__ import division
import random
circleA = sorted(random.sample(range(1000),10))
...
0
votes
3answers
36 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 ...
-1
votes
0answers
35 views
Checklist/ to-do list for Google internship interview [on hold]
I know this may not be the best place to ask this questions. But many people here have experienced this, so can get a great answer and it will be valuable for others. I am a College student studying ...
0
votes
0answers
43 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
31 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 ...
0
votes
1answer
19 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 ...
2
votes
3answers
35 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
17 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
1
vote
2answers
54 views
Too many collisions in hash function
I was trying to hash about 64million 64bit unsigned integers to 128 million buckets(27bit wide address). I tried Burtle's HashLittle and Murmur hash(Both these hash functions gives 32bit hashes which ...
-2
votes
0answers
12 views
Implementing segment tree for handling rotating queries
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
19 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
74 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
58 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
20 views
java NZEC(Non Zero Exit Code) [on hold]
What 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
25 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
40 views
Element rotation in segment tree
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
14 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
28 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
8 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
45 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; ...
2
votes
1answer
63 views
Subset sum algorithm a little faster than 2^(n/2) in worst time?
After analyzing the fastest subset sum algorithm which runs in 2^(n/2) time, I noticed a slight optimization that can be done. I'm not sure if it really counts as an optimization and if it does, I'm ...
0
votes
1answer
14 views
Traverse and reconstruct a Ruby object graph efficiently without recursion
I'm probably just trying to do something crazy here, so let me explain my use case first:
I've got an object graph in Ruby, consisting only of the basic JSON types (strings, numbers, arrays, hashes, ...
0
votes
1answer
24 views
Looking at the jQuery source, how do I implement this easing function in pseudocode?
jQuery has an easing function called swing that is used when animating the movement of an object. I'm trying to mentally parse the source but am not adept at reading this code. I'm asking for someone ...
0
votes
0answers
14 views
How to set the words to the baseline with JS? I have an algorithm, but it must be checked up
I have such not a usual question: how can I set the words to the baseline of the text?
smth. like this:
http://gyazo.com/be37dfed30cfe0accd6bef8eee92a5de
Sorry I don't have enough reputation for ...
2
votes
2answers
72 views
Find a best way to search data structure string compare
I have a question which data structure is the best for particular situation.
we have one string "AAAAAAAAAAA", and we want to know this string contain in one data base column or not.
For example ...
3
votes
1answer
53 views
How can I find the recursive relation?
How can I find the recursive relation,that describes the cost of the Quicksort,if we want to partition the subproblems with ratio 9:1?
The algorithm of the Quicksort that I am looking is the ...
0
votes
1answer
57 views
substring algorithm on combining fragments
So the assignment was if I was given a list [jimmy, mybaby] then
I will return [jimmy, mybaby, jimybaby]
But! If I'm given a list like [abc, bca] I will return [abc,bca,abca,abcabc, ..... infinite] ...
0
votes
2answers
82 views
Algorithm for a “map”
Well, I was trying to solve the following problem: Suppose I have a "map of a city." I have a source and a destination. There are streets that are blocked and streets that are free. Wanted to create ...
1
vote
1answer
26 views
Why do these two relations stand?
I want to find the cost of the following algorithm in average case:
Quicksort(A,p,r)
if p<r then
q<- partition(A,p,r)
Quicksort(A,p,q-1)
Quicksort(A,q+1,r)
We ...
0
votes
0answers
39 views
Breaking complex conditions in simple ones
I am creating a share market strategy creator using which we can create condition to enter or exit the market using indicators and operators (Logical, arithmetic, relational). it looks something like ...
0
votes
0answers
28 views
Insert and remove nodes while preserving topological sort?
I want to store a tree, where a node can have any number of children, as array. Each node has an associated value that gets calculated based on the parent value. Therefore, the array must be ...
1
vote
2answers
69 views
Reduce The Boolean Expression Complexity of this method?
This isValid() method has up to 6 attributes that can be set in order to be validated. If a particular attribute isn't set, it doesn't need to be validated. The logic appears to be working just how ...
0
votes
1answer
21 views
Object/Array comparison algorithms to determine commonality/similarity
I am trying to figure out the best approach to determining commonality or similarity between various objects or arrays and would be interested in getting the community's input. I am currently building ...
-4
votes
5answers
78 views
Finding maximum value using for loop in an extern array [on hold]
I need help finding the maximum value using an extern array. I have to use extern because the figure must be keyed into another source file.
First Source file:
int transitTime[][10] =
{
88, 67, ...
2
votes
3answers
43 views
splitting polygon in 2 equal parts
I have convex polygon and I want to get line that is parallel X axis that splits polygon into 2 equal areas.
I've tried to implement following(for X axis):
0. sort all vertices of polygon in ...
-3
votes
0answers
45 views
Finding a node in a three-way connected graph
This looks like an old question and I think I saw it somewhere in the past. Unfortunately I forgot how to do it. Please help me out.
Suppose you want to find a special node in a bunch of connected ...
0
votes
1answer
37 views
Connecting two classes of objects so that the total connection distance is minimal
Imagine a map with n cities randomly placed on it. On the same map, there are also m people, randomly placed on the map. n and m do not have any restrictions (other than being a positive integer of ...
1
vote
1answer
41 views
Lock-free memory reclamation with hazard pointers
Hazard pointers are a technique for safely reclaiming memory in lock-free code without garbage-collection.
The idea is that before accessing an object that can be deleted concurrently, a thread sets ...
0
votes
1answer
52 views
Scalable update of java collections
I have a list of baskets. Each basket contains 30 items. I also have a list of purchase history containing items that was bought on a particular day, regardless of who bought it. The data looks like ...
0
votes
2answers
117 views
Single occurrence of a number
For this question, "Given an array where every element occurs three times, except one element which occurs only once. Find the element that occurs once. "
I tried the code given at ...
1
vote
1answer
39 views
How a 10GB movie running in limited Primary memory?
As far as I know, when we run some program, the process or files stored in secondary memory (Hard Disk) comes to primary memory (RAM) and then only program runs. My question is if, a movie file is ...
0
votes
1answer
15 views
Unix/Linux Alike File Permissions
I am trying to create a function that will derive if the user is authorised to access a certain method based on verifying the permission level with the user type. (Similar to linux file permissions - ...
0
votes
1answer
36 views
How to pack a 3 dim array/ how to map it on a 1 dim array
I have a question concerning the packing of multidimensional arrays. I'm stuck at the moment and maybe somebody can help me out since I think it is a rather trivial task. I'm programing in Fortran, ...
