I am trying to grasp the idea behind the prefix sum concept looking at the example presented in the Prefix Sum Lesson by Codility here (The mushroom picker problem) My understanding is that the whole concept is based on the simple property where for finding a sum of all elements between two positions A(pos_left, pos_right) of an array A a
Tag: algorithm
convert an unfair coin into a fair coin in Python 2.7
Using Python 2.7. Suppose I have an unfair coin and I want to turn it into a fair coin using the following way, Probability of generating head is equal for unfair coin; Flip unfair coin and only accept head; When a head is appearing, treat it as 1 (head for virtual fair coin), when another head is appearing, treat it
Python program to check matching of simple parentheses
I came across this exercise of checking whether or not the simple brackets “(“, “)” in a given string are matched evenly. I have seen examples here using the stack command which I haven’t encountered yet. So I attempted a different approach. Can anyone tell me where I am going wrong? The idea is to pile up “(” and “)”
Extract string inside nested brackets
I need to extract strings from nested brackets like so: Result (Order doesn’t matter): Note, the string could have N brackets, and they will always be valid, but may or may not be nested. Also, the string doesn’t have to start with a bracket. The solutions I have found online to a similar problem suggest a regex, but I’m not
Finding the “centered average” of a list
“Return the “centered” average of a list of integers, which we’ll say is the mean average of the values, except ignoring the largest and smallest values in the list. If there are multiple copies of the smallest value, ignore just one copy, and likewise for the largest value. Use integer division to produce the final average. You may assume that
How to check for duplicates with less time in a list over 9000 elements by python
um trying to check whether there are duplicate values exists in an integer list by python . this was successful and I found that the execution time getting higher when the size of the list getting increase. How may I improve the run time of the following logic? Answer You could use a set: EDIT: a faster version, as pointed
hexToBinary dictionary
So I am working on this problem: Recall from the Number Systems unit the method for converting hexadecimal numbers to binary by converting each hex digit to its equivalent four binary digits. Write a Python function named hexToBinary with parameters (number, table) that uses this algorithm to convert a hexadecimal number to a (return) binary number. The algorithm visits each
How to modify Levenshtein algorithm, to know if it inserted, deleted, or substituted a character?
So I am trying to devise a spin off of the Levenshtein algorithm, where I keep track of what transformations I did in the string(inserted a, or substitute a for b). Example: Basically, say I am computing the edit distance of “bbd” and “bcd” The edit distance will be 1 and the transformation will be “substitude b for c” Question:
BFS algorithm in Python
Guys! Can someone help me with this bfs code? I can’t understand how to solve this queue line. Answer To extend your queue with all nodes not yet seen on the path, use set operations: or use a generator expression: Lists don’t support subtraction. You don’t really need to filter the nodes, however, your code would work with a simple:
Fast hash for strings
I have a set of ASCII strings, let’s say they are file paths. They could be both short and quite long. I’m looking for an algorithm that could calculate hash of such a strings and this hash will be also a string, but will have a fixed length, like youtube video ids: MD5 seems to be what I need, but