Questions tagged [algorithm]

An algorithm is a sequence of well-defined steps that define an abstract solution to a problem. Use this tag when your issue is related to algorithm design.

Filter by
Sorted by
Tagged with
57
votes
3answers
3k views

Analyzing Minesweeper Probabilities

Calculating probabilities in Minesweeper might sound like an easy task, but I've seen so many probability calculators that's either incorrect, horribly slow, or with ugly code (or all of them) so I ...
42
votes
2answers
39k views

Balanced parentheses

Given an expression string exp, write a program to examine whether the pairs and the orders of "{","}","(",")","[","]" are correct in exp. For example,...
10
votes
1answer
4k views

Z-Algorithm for pattern matching in strings

I was trying to refactor the following Python code (keeping the same time-complexity) which is an implementation of Z-Algorithm for pattern matching in strings. ...
32
votes
5answers
58k views

Brute Force Algorithm in C

This is a simple brute force algorithm that I have programmed in C. All the program does is print out every possible combination of the given alphabet for the ...
34
votes
3answers
1k views

Advanced and Detailed Minesweeper Probabilities

In an earlier question, I showed my code for calculating the mine probability for each and every field in a Minesweeper board. But it doesn't stop there. In that very same Minesweeper Analyze project, ...
56
votes
9answers
13k views

Project Euler problem 1 in Python - Multiples of 3 and 5

I'd like suggestions for optimizing this brute force solution to problem 1. The algorithm currently checks every integer between 3 and 1000. I'd like to cut as many unnecessary calls to ...
10
votes
1answer
14k views

K-Mean with Numpy

I have implemented the K-Mean clustering Algorithm in Numpy: ...
15
votes
3answers
3k views

N-Queens - Brute force - bit by bit

A discussion in The 2nd Monitor made me realize I had never 'solved' the N-Queens problem. Additionally, as I read up on it, I realized that the 64-squares in a chess board would work well if ...
10
votes
3answers
719 views

More imitation of Enumerable in VBA

I was inspired by Me How's question to see how far I could push an imitation of .Net's Enumerable Class. The new functions can obviously handle Collections, but can also handle any collection-type ...
7
votes
3answers
14k views

Optimizing Manhattan-distance method for N-by-N puzzles

By N-by-N puzzles I mean f.e. a 3x3 sliding puzzle with one blank space (so a 8-puzzle) or a 4x4 sliding puzzle (so a 15-puzzle). When I try to solve certain puzzles some take no time but others take ...
5
votes
2answers
878 views

Matrix of articles and authors from large JSON dataset

Given the following JSON data containing 4 articles by 4 different authors: ...
8
votes
2answers
1k views

Selection Sort Algorithm (Python)

Selection Sort The selection sort algorithm sorts a list by finding the minimum element from the right unsorted part of the list and putting it at the left sorted part of the list. The ...
6
votes
2answers
2k views

Stack implementation using vectors and templates with no overflow version 1.1

I have modified my code as per the suggestion given by some of the developers. Let me know if there are any further concerns or scope for improvements. Original Version ...
6
votes
1answer
405 views

Efficiently counting rooms from a floorplan

Note this was the wrong version of the code. The updated version is here: Efficiently counting rooms from a floorplan (version 2) My apologies! Update Final version 3 with test harness here: ...
3
votes
3answers
447 views

Calculating number of unharmed leaves

I recently came across this problem that asks you to print the number of leaves not eaten by the caterpillars: As we all know caterpillars love to eat leaves. Usually, a caterpillar sits on leaf, ...
2
votes
1answer
1k views

NBA*: Very efficient bidirectional heuristic search algorithm in Java - follow-up

This post elaborates on NBA*: Very efficient bidirectional heuristic search algorithm in Java. I have made the following changes: Added an explicit type for representing digraph paths: ...
11
votes
5answers
3k views

Efficiently counting rooms from a floorplan (version 2)

This is version 2 of Efficiently counting rooms from a floorplan. I had accidentally pasted in the wrong version of the code. Update Final version (version 3) of the code with updated test harness ...
11
votes
3answers
12k views

Bubble sort algorithm in Python

I'm starting to implement basic sorting algorithms. Criticisms on the implementation is welcome. ...
5
votes
2answers
199 views

Stack implementation using vectors with no overflow version 1.0

This is an implementation of a stack where I have used vectors. Can anyone please review it and let me know how I can improve this code and overall coding practice? ...
5
votes
4answers
2k views

Project Euler #5 - Lowest common multiple of 1 through 20

This is my code. All comments welcome. Last time run it only took 335 milliseconds: ...
4
votes
2answers
89 views

Two dimensional gaussian image generator in C

This is a follow-up question for Image Processing Median Filter in C. I am attempting to create a two dimensional gaussian image like below in C. The formula is as follows. The experimental ...
4
votes
0answers
2k views

Generic sliding window

The code implements fully generic sliding window with linear complexity. It should usually be paired with transforming iterator to reach full potential. Sliding window is a grouping of elements by ...
3
votes
2answers
1k views

Premium palindromic primes

Challenge: Write a program which determines the largest prime palindrome less than 1000. The answer is 929, and my program correctly finds and prints this, but actually ended up being more complex ...
3
votes
4answers
2k views

Sieve of Eratosthenes: making it quicker

I was thinking about doing problem 23 of Project Euler. It includes the difficulty where you have to factorize primes. I had already done that in problems I solved earlier, but it was only necessary ...
2
votes
1answer
751 views

Fast Prime Sieve (Python Implementation)

A modified version of the prime sieve. I actually doubt it could be implemented any faster, but I might be wrong: ...
213
votes
4answers
23k views

Calculate SHA1 hash from binary and verify with a provided hash

I applied for a job and they asked me to write code with the following requirements: Get a "toolbar offer" description from http..update.utorrent.com/installoffer.php?offer=conduit. Parse the ...
56
votes
3answers
67k views

Dynamic programming knapsack solution

I wrote a solution to the Knapsack problem in Python, using a bottom-up dynamic programming algorithm. It correctly computes the optimal value, given a list of items with values and weights, and a ...
32
votes
7answers
66k views

Check for balanced parentheses

Given an expression string exp, write a program to examine whether the pairs and the orders of "{","}","(",")","[","]" are correct in exp. For example,...
14
votes
4answers
2k views

Shell Sort, Insertion Sort, Bubble Sort, Selection Sort Algorithms (Python)

There is a follow-up question available: shell-sort-insertion-sort-bubble-sort-selection-sort-algorithms-python. Selection Sort The selection sort algorithm sorts a list (array) by finding the ...
27
votes
2answers
3k views

Sudoku using 'exact cover' solver

1. Introduction This is a solution to Weekend Challenge #3: a Sudoku solver in Python. It works by translating a Sudoku puzzle into an exact cover problem, and then solving the exact cover problem ...
16
votes
2answers
344 views

Minimising the triangle

A triangle needs a good foundation. Every row in the triangle is derived from the sum of the two values below it. However, there can be no repeated values, if a value shows up more than once the ...
12
votes
1answer
2k views

Extended stable marriage challenge

I've written a solution for the stable marriage problem in the case that the number of men is not equal to the number of women. My problem is not that I can't prove my code is right. The problem is I ...
7
votes
1answer
134 views

Classic merge sort (part 2)

(Initial discussion from Classic merge sort, since it is new code, I start a new thread) Post my code below, my major question is, I have to create another array ...
6
votes
2answers
746 views

4 sum challenge (part 2)

This is a continued discussion from (4 sum challenge) by return count only. Problem Given four lists A, B, C, D of integer values, compute how many tuples (i, j, k, l) there are such that A[...
6
votes
1answer
152 views

Generalizing std::minmax_element

In the following answer, @Incomputable basically dared me to implement a generalization of std::minmax_element. Have you thought about creating a search function ...
5
votes
4answers
1k views

Encryption algorithm for an app

I have created an encryption algorithm for this app I am currently in the process of developing. I was wondering if my code looks "sharp", concise, and most importantly, succinct. I was also wondering ...
4
votes
1answer
134 views

Group duplicate files

Here is my source code which group duplicate files together, written in Python 2.7. Any advice on smarter ideas to group duplicate files together more efficient, it will be great. Any general advice ...
4
votes
1answer
460 views

Using range minimal query for lowest common ancestor (LCA)

Here is my code to use range minimal query to resolve the LCA problem. Any advice on code bugs, performance improvement in terms of algorithm time complexity, code style are appreciated. More ...
4
votes
1answer
794 views

Find valid triples for a sorted list of integers

I'm working on a problem in which I have an input array, sorted positive unique integers, and have to try to find all possible triples \$(x,y,z)\$ which satisfy \$x+y>z\$ and \$x<y<z\$. For ...
3
votes
1answer
77 views

Group duplicate files (part 3)

This is a continued discussion (from here => Group duplicate files (part 2)) with new code and new thoughts/questions (see special question part for details for new questions), and I decide to make a ...
3
votes
2answers
5k views

HackerRank - Array Manipulation

This is my implementation for this hacker rank problem. (And a follow-up.) Problem You are given a list(1-indexed) of size n, initialized with zeroes. You have to perform m operations on the ...
2
votes
1answer
335 views

Tic-Tac-Toe with changeable board size (Part 2)

Part 1: Tic-Tac-Toe with changeable board size (Part 1) I just revisited all my previous questions and saw that I hadn't updated my Tic-Tac-Toe code. So, I improvised my code as per @Austin Hastings ...
2
votes
3answers
127 views

Different path for grid move (part 2)

This is a continued discussion from (Different path for grid move) to optimize for space complexity, and since it is new code and I make a new post. Given a m * n grids, and one is allowed to move ...
20
votes
3answers
4k views

Reversing k-sized sequences in a linked-list

Here is my solution to this problem; please be brutally honest/strict, if I would have written this code, in a 45 minute interview, what would you think? (I am aiming for Google,Facebook). Here is ...
18
votes
6answers
3k views

Testing whether characters of a string are unique

Critiques (even pedantic ones) are welcome. ...
12
votes
7answers
9k views

Sieve of Eratosthenes

For practice, I've implemented Sieve of Eratosthenes in Java by thinking about this visual animation. I would like to hear some suggestions for improvements, especially how to make it more efficient ...
8
votes
3answers
1k views

Given a Perfect Binary Tree, reverse the alternate level nodes of the binary tree

Given a Perfect Binary Tree, reverse the alternate level nodes of the binary tree. Given tree: ...
6
votes
2answers
10k views

Kruskal's algorithm in Java

I have this Java implementation of Kruskal's algorithm. It solves a tiny problem instance correctly, yet I am not quite sure, whether my implementation is correct. The code as follows: MSTFinder....
6
votes
1answer
1k views

Efficient top k words using MultiMap (Google Guava ext lib JAR)

Basic algorithm: Open document/huge text file Use Map and List to separate the words. \$O(K)\$ time complexity (TC) considering ...
6
votes
3answers
2k views

Optimizing unique partitions of integers

I am working on a project involving the unique partitioning of integers. I.e. I am looking to have all of the partitions of n = x1 + x2 + x3 + ... + xk, where xi = xj implies i = j. For example, if I ...

1
2 3 4 5
12