Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

0
votes
0answers
7 views

Find all starting indices in a string which are anagrams of a word

The task: Given a word W and a string S, find all starting indices in S which are anagrams of W. For example, given that W is "ab", and S is "abxaba", return 0, 3, and 4. My solution: <...
0
votes
0answers
21 views

Decrease the time taken by the code using Dynamic programming

I am trying to solve a question given on Codeforces involving Dynamic Programming with 3D arrays. F. Trucks and Cities There are \$n\$ cities along the ...
1
vote
1answer
32 views
3
votes
3answers
107 views

Image filter for gradient detection

This filter is basically gradient detection (the variable gradImg) like an edge detection (Sobel or Prewitt filters) and also the direction of that gradient whether ...
2
votes
1answer
44 views

Fast Factorisation (Python Implementation)

An algorithm for finding prime factors of a number given a list of all primes up to the square root of the number. It's worst case time complexity is \$O(n^{1/2})\$, the best case would be \$O(\log(n))...
0
votes
1answer
50 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: ...
4
votes
5answers
84 views

Get n-th perfect number

The task: A number is considered perfect if its digits sum up to exactly 10. Given a positive integer n, return the n-th perfect number. For example, given 1, you should return 19. Given ...
4
votes
3answers
49 views

Uniformly generate a number from 0 to n-1 that isn't on a blacklist

The task: Given an integer n and a list of integers l, write a function that randomly generates a number from 0 to n-1 that isn't in l (uniform). Solution 1: ...
3
votes
1answer
75 views

Swap even and odd bits of unsigned 8-bit integer

The task: Given an unsigned 8-bit integer, swap its even and odd bits. The 1st and 2nd bit should be swapped, the 3rd and 4th bit should be swapped, and so on. For example, 10101010 should ...
0
votes
1answer
57 views

Return a sorted ordering of courses such that we can finish all courses

The task: We're given a hashmap associating each courseId key with a list of courseIds values, which represents that the prerequisites of courseId are courseIds. Return a sorted ordering of ...
1
vote
1answer
53 views

Find out whether string A can be shifted to get string B

The task: Given two strings A and B, return whether or not A can be shifted some number of times to get B. For example, if A is abcde and B is cdeab, return true. If A is abc and B is acb, ...
4
votes
1answer
90 views

Word Chain Implementation

The idea originaes from the CodeKata19, find a word chain for two words of a wordlist example 1 turning lead into gold: ...
2
votes
2answers
47 views

Chained Sort Python Implementation

So I've run into a few occasions where I'd want to sort a list according to a criteria, then for all loosely sorted sublists (a sequence of equal elements), I'd want to sort those sublists according ...
2
votes
3answers
59 views

Contiguous elements of the list sum to K

The task: Given a list of integers and a number K, return which contiguous elements of the list sum to K. For example, if the list is [1, 2, 3, 4, 5] and K is 9, then it should return [2, ...
5
votes
2answers
229 views

Get all monotonic sublists from a list

So, i recently wrote code that can count the number of monotonic items (increasing, decreasing and constant). For an input such as x = [1,2,3,3,2,0] The provided ...
2
votes
1answer
61 views

Write a function that adds two numbers stored in a linked list and returns the sum

Just for fun I did the following exercise from "Cracking the coding interview. 4th edition": You have two numbers represented by a linked list, where each node contains a single digit. The digits ...
1
vote
2answers
45 views

Simple war scheduling algorithm in Java

Let \$\mathcal{C} = \{ C_1, \dots, C_n \}\$ bet a set of \$n\$ different countries. We associate with each country \$C_i\$ with its potential \$P_i\$. We choose a specific country \$C_e\$ in \$\...
1
vote
1answer
43 views

Modelling Immerman–Szelepcsényi in Haskell

I am trying to model the proof of Immerman–Szelepcsényi Theorem with Haskell since it heavily uses non-determinism. An explanation of what the point of this is can be found here. ...
6
votes
2answers
62 views

Rearrage sequence so that adjacent numbers add to perfect squares

Consider the array: original_array1[17] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17} I want to sort it in such a way that: Sum of adjacent numbers should be a ...
3
votes
1answer
78 views

Basic substring algorithms + auxiliary string-generating functions

Summary: a bunch of algorithms to find if particular substring exists in the string. Meanwhile there's a lot to learn and I am looking forward to implementing more complex ones, I suppose there's some ...
2
votes
2answers
58 views

JavaScript flood fill

I tried to implement a very simple color flood fill to experiment a bit with Javascript. All comments about the code are welcome but I am especially interested in performance as it seems to be a bit ...
0
votes
2answers
61 views

Select nth smallest distinct integer from inputs

Kata in question Given a list of integers, return the nth smallest integer in the list. Only distinct elements should be considered when calculating the answer. n will always be positive (n > 0) ...
3
votes
2answers
72 views

Find the longest sub string of a word after concatenation of given words array

An Array of N words is given. Each word consists of small letters ('a'-'z'). Our goal is to concatenate the words in such a way as to obtain a single word with longest possible substring composed of ...
3
votes
1answer
77 views

Word break problem with recursion and memorization [closed]

For practice, I solved Leetcode 139. worbreak question: Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-...
0
votes
0answers
48 views

Find the smallest subarray with sum greater than a given value

Given some array, find the smallest subarray with a sum that is greater than a value given. So for instance, given this array: {1, -4, -45, 6, 0, 19, 16, 17} ...
2
votes
2answers
162 views

Mr. Muffin's ball-passing game

I have an assignment to solve this problem. There are a total of 18 test case files, 5 of which I have failed due to exceeding some time limit on the script and I am unable to verify if there are any ...
3
votes
2answers
63 views

Finding the number of integers between 1 and K, who's sum of the digits is a multiple of D

Good day. So, I need to find the number of integers between 1 and K (inclusive) satisfying the following condition, modulo (10^9)+7: The sum of the digits in base ten is a multiple of D Here is my ...
3
votes
1answer
46 views

SplitSort — An adaptive algorithm to handle collections with few inversions

SplitSort SplitSort is a rather simple Inv-adaptive and Rem-adaptive sorting algorithm described in Splitsort — an adaptive sorting algorithm by Christos Levcopoulos and Ola Petersson. The paper ...
1
vote
1answer
80 views

Products excluding each element of the array

Given an array of integers, return a new array such that each element at index i of the new array is the product of all the numbers in the original array except the one at i. For example, if our ...
0
votes
2answers
44 views

Given a list of numbers and a number k, return whether any two numbers from the list add up to k

Given a list of numbers and a number k, return whether any two numbers from the list add up to k. For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17. How can i improve the ...
3
votes
0answers
42 views

Locality Sensitive Hash (similar to k-Nearest Neighbor), in Python+Numpy

I've tried implementing Locality Sensitive Hash, the algorithm that helps recommendation engines, and powers apps like Shazzam that can identify songs you heard at restaurants. LSH is supposed to run ...
2
votes
3answers
98 views

Find the greatest common divisor of n numbers

Just had this as a practice test problem and I'm curious how to optimize for performance. Thanks! The greatest common divisor (GCD), also called the highest common factor (HCF) of N numbers is the ...
5
votes
1answer
95 views

Find the longest common sequence of two strings in Rust

I've attempted to solve a small coding challenge I found online as a nice way to begin learning Rust. The largest challenge I feel going in with Rust is how working with strings is so fundamentally ...
2
votes
2answers
74 views

Number of anagrams in an array of words (Codewars)

Codewars Kata in Question. An anagram is a word, a phrase, or a sentence formed from another by rearranging its letters. An example of this is "angel", which is an anagram of "glean". ...
0
votes
1answer
53 views

Could someone check the Minimax Algorithm correctly implemented? [closed]

I'm working on AI tic-tac-toe that computer make a move and I wanted to know that I correctly implemented the minimax algorithm. Please someone check my code to identify a problem or any kind of bug. ...
1
vote
2answers
54 views

Recursive Transversal (Python)

For a programming challenge I was doing, I needed to traverse a list of lists, and while writing the standard 2D traversal function, I thought why not generalise it, so I did. Here's my best effort: ...
3
votes
1answer
39 views

Extended Binary Search Function (python)

I wrote a function to find the closest value in a list to a given search value. What prompted me to write it was as boilerplate for a prime number problem so I could find the closest prime to a given ...
6
votes
1answer
70 views

Identify Duplicate Files

A friend of mine has the following issue. He has a nearly-full 1TB hard drive on which he keeps copies of all the pictures from his digital camera(s). However, he knows that he has copied the entire ...
4
votes
1answer
145 views

Dijkstra algorithm implementation in Swift

I've implemented Dijkstra's algorithm to find the minimum path between two nodes. ...
1
vote
2answers
52 views

Check whether an array can be the result of merging two smaller arrays, maintaining order

I'm prepping for a tech interview coming up and trying to have a better understanding of what I should look out for in writing code. Also, feel free to correct the terminology that I use as I want to ...
1
vote
0answers
22 views

KMP algorithm in scala

I implemented KMP pattern matching algorithm in Scala. My code works but it looks more imperative and a scala translation of C/C++ implementation. I am not able to figure out how to manage multiple ...
1
vote
1answer
65 views

Leetcode Longest Common Prefix

I just recently finished the following problem on Leetcode problem. I know it's not the cleanest or fastest solution. I would appreciate if I can get some feedback on how to optimize the code. The ...
1
vote
0answers
38 views

Bin-packing-problem solution using recursion

I needed to make a freight calculator and had to solve a bin packing problem. I utilized a github package. Basically with the help of my stack overflow question I made a class Method that Splits an ...
2
votes
1answer
42 views

Counts “islands” of 1s in sea of 0s (2d array matrix)

This solution surpassed 100% of submissions for efficiency! My method was to recursively check surrounding values and change any contiguous "land" to "water". Is there a better way to write what I ...
5
votes
2answers
83 views

Given a string S and a set of words D, find the longest word in D that is a subsequence of S

I'm trying to improve my code and algorithm to find out the longest word from a dictionary occurring as the sub-sequence in the given string. Example : For example, given the input of S = "abppplee"...
0
votes
0answers
39 views

Brute force least adjacent swap anagram transform in Java

In this post, we are given two anagrams, and we wish to compute a shortest sequence of adjacent character swaps. For example, ...
4
votes
0answers
38 views

Improved Knuth-Morris-Pratt over a source of indeterminate length

Following the successful review of my previous implementation. Please review my new, generic implementation of the Knuth-Morris-Pratt algorithm. Its modified to search a source of indeterminate ...
4
votes
2answers
92 views

Knuth-Morris-Pratt over a source of indeterminate length

Please review my generic implementation of the Knuth-Morris-Pratt algorithm. Its modified to search a source of indeterminate length in a memory efficient fashion. ...
2
votes
1answer
98 views

Family Relationship Tree

Developer Assignment - Family And Relations Going through the old stuff in his attic, Indiana comes across a chart which looks like a family tree of multiple generations which shows his ...