New answers tagged programming-challenge
-1
I realize that this is an old question, but I though I'd provide my approach anyway.
What you really want to do, is count the number of active or set bits, as a power of two is always represented as a single bit.
Now, I'm not much for javascript, so this is semi pseudo/c code, but I do believe the operators are more or less the same.
bool isPowerOf2( ...
2
The first solution
There's a bug in the first loop:
for w in wdict:
if s.startswith(w):
if len(s) == len(w):
ans.append(w)
return ans
^^^^^^^^^^ should not do this!
st.append((w, 0, [w]))
It's not correct to return when one of the words is the same as the sentence,
because ...
2
Strategies
It would have been good to summarize the key points and strategies of the different implementations.
Mostly for yourself, to clarify your thinking and solidify your understanding.
Secondly for reviewers :-)
Let me take a jab at that now.
Solution 1
while there are lists to merge
find the minimum head and merge it
update the list with the ...
5
I will have to agree that you do have a bit much synchronized blocks. All of them could go away if you would use for example Collections.synchronizedList around your ArrayList or CopyOnWriteArrayList.
Your fun statistics() could be an alternative constructor to Statistics
A few other Kotlin-related tips:
var max = if (count > 0) liveTransactions.first()...
4
Disclaimer... I have very little experience with Kotlin.
Not really the focus of your question, but synchronized blocks should be only as big as they need to be. Looking at your statistics code, you put the whole thing in the block.:
synchronized(transactions) {
val threshold = getCurrentThreshold()
val liveTransactions = transactions....
4
One performance problem is the overhead of allocating and resizing a vector. Since you read the size up front, why not simply reserve() enough space?
cin >> array_size;
input_array.reserve(array_size);
If you sorted the sequence, computing the median would become dead simple and very fast (O(1)). This may be a better approach. However, you ...
1
I don't like classes named …class. In languages including C#, it leads to expressions like new IsValidBSTclass(), not yielding a class.
I'd prefer BSTChecker over BSTValidator for the foreseeable bstValidator.isValid().
7
Not related to performance, but never ever do this:
#include <bits/stdc++.h>
using namespace std;
For reference see these Q&A at Stack Overflow:
Why should I not #include <bits/stdc++.h>?
Why is “using namespace std;” considered bad practice?
2
Your code is pretty good. Nice job.
I'd personally change the first else to an elif so you don't have as much indentation.
Rather than using that while loop you can just use one % per number.
For each number if you get the modulo then you can find out how much to add. 7 % 5 is 2. Where 5 - 2 is not less than 3.
And so you can easily change the while to ...
2
The main validation logic doesn't need "min node" and "max node",
only the values.
Passing the nodes as parameters adds complexity,
because you have to handle null values,
which would not be the case with simple integers.
Being an unnecessary complexity (since nodes are not really needed),
I suggest to eliminate it, for example:
public static bool IsValid(...
1
Avoid unnecessary variables
The counter variable is unnecessary.
For each level, you need just a List<int> level,
add the elements of the level to this list,
and then add this list to res.
By eliminating this variable, you also eliminate any concerns about the correctness of res[counter].Add(temp.val);.
With the code changed to level.Add(temp.val),
...
1
You have one bug in your code. The binaryGap function is supposed to be side-effect free. Your implementation isn't since it modifies the global variable i.
To fix this, apply the following patch:
- for (i=0; i<bin.length; i++){
+ for (let i=0; i<bin.length; i++){
There are 2 lines in your code that are redundant:
if (gaps.length===1){
return ...
-4
I did it like this but after seeing other solutions feel maybe it is too long, still earned a 100% though.
public int solution(int N) {
var b = Convert.ToString(N, 2);
var maxGap = 0;
for (var i = 0; i < b.Length; i++)
{
var c = b[i];
var thisGap = CountGap(b, i);
if (thisGap > maxGap)
{
...
0
I have suggestions for you.
The unvisited should be renamed unvisitedIndexes in my opinion.
I suggest that you create a method to build the unvisited set to separate the logic from the main method.
public static int friendsCircle(char[][] friends) {
Set<Integer> unvisited = buildUnvisitedSet(friends);
}
private static Set<Integer> ...
4
Welcome to Code Review. Your code is good and easy to read, you can iterate over only half of the matrix (in my case the elements of the matrix a[i,j] with i < j) because from the test matrices always results a[i, j] = a[j, i] so friendship in symmetric .
I'm using a TreeMap<Integer, Set<Integer>> to store initial situation to guarantee ...
2
For the most part I agree with your code. However there are a couple of things:
IsValidBST I think is redundant. Anyone running this method already knows it applies to a BST. I think just IsValid would be better.
Helper should have a better name, I think an IsValid overload would work and it should be private.
It doesn't make much sense to me to make ...
3
You don't need to actually build a whole list of the digits. It's unnecessary memory consumption. You can pass a generator to max.
use python's -= syntax when subtracting from a variable.
The break is unnecessary as it's covered by the while condition
Final code:
n=int(input())
count=0
while n:
n -= max(int(i) for i in str(n))
count += 1
...
0
It's strange to use a signed type for length, but that appears to be imposed on you by the problem statement, so blame a poor specification for that.
Despite the letters std, <bits/stdc++.h> is not a standard header, so you have a portability bug. Even where it exists, it brings in far more than you need, so get used to including just the headers you ...
3
Since you already have a nice implementation of a prime sieve, you should make use of it when checking for prime factors. Note that prime factors are needed, not all factors. I definitely would not use a recursive algorithm for this. It can fail with a stack limit and you need a lot of unreadable code just to set up the data structures.
I would use ...
1
While this is Code Review@SE:
Do not start coding while not confident the task is well defined.
A good way to check is test first:
If you don't know how to test it, you don't know what to achieve.
(Your program (sort of) outputs
1A 1B 0 0 0 1F 0 0 0 0
2A 2B 2C 2D 0 0 0 0 0 0
3A 0 3C 3D 0 0 0 0 0 0
4A ...
1
;
why all the ;. Python is not JS. They don't do any harm to the program, but they are unnecessary and hamper the readability
1 letter variable names
I try to avoid those as much as possible, unless they are the standard jargon in for example mathematical formula's, i as counter or x and y as coordinate
Comments
As already noted in the other answers. ...
1
The simplest thing that comes into my mind is have a hashmap to cache sum of all the elements from position i to the end
for L = [1, 2, 3, 4, 5] the map would look like
Index | sum till end
0 | 15
1 | 14
2 | 12
3 | 9
4 | 5
once you have this you can do something like this
public int sum(int i, int j) {
return map.get(i) - map.get(...
3
Two comments on your comments:
Have the comment be at the same indentation level as the block that you're commenting. Having all the comments start at column 0 forces the eye to rapidly scan from left to right, and it makes it impossible to discern the overall structure of the program at a glance from the left-hand margin of the code. (It looks like not ...
0
it works, the time complexity is O(nlogn).
static int[] cutTheSticks(int[] arr) {
Map<Integer,Integer> numbersCount = new HashMap<Integer,Integer>();
for(int i=0;i< arr.length;i++){
numbersCount.put(arr[i], numbersCount.getOrDefault(arr[i],0)+1);
}
PriorityQueue<Integer> minHeap = new PriorityQueue<Integer&...
10
Magic number
ALPHABET_LENGTH = 26
You don't need to hard-code ALPHABET_LENGTH = 26 in your program. Let Python do the work for you, with ALPHABET_LENGTH = len(ascii_lowercase)
Avoid String concatenation; use built-in functions
String concatenation is very slow.
new_str = new_str + encoded_char
AlexV's append / join isn't much better.
Python comes ...
2
Pass queue as a const reference
It's quite expensive to pass a whole vector by value, and you are not modifying it. So you can instead make minimumBribes() take a const reference, like so:
void minimumBribes(const vector<int> &queue) {
...
}
Use whitespace to make the code more readable
A simple trick to make the code more readable is to ...
11
Generally speaking your code looks quite good from my point of view. It's nicely structured, readable and documented. Well done!
Using LOWERCASE = ascii_lowercase + ascii_lowercase in conjunction with n = n % ALPHABET_LENGTH also seems to be a very clever way to implement the shift.
You don't need
if n < 0:
n = ALPHABET_LENGTH - n
because modulo ...
-2
import math
import os
import random
import re
import sys
# Complete the hourglassSum function below.
def hourglassSum(arr):
large=-64
for i in range(4):
for l in range(4):
sum=0
for j in range(i,i+3):
for k in range(l,l+3):
if (j==i+1 and k==l)or(j==i+1 and k==l+2):
...
2
A small review;
Once you know that one version digit is larger than the other, you can exit immediately
You did not declare i with const or let
I would advise the use of a beautifier for your code, it's a bit compact in some places
The code does not handle well versions with different counts of digits
You should always pass the base, when you call parseInt
...
-2
Here's my version in java and its time complexity is O(n).
public static int isHollow(int[] a) {
int nonZeroCount = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] != 0 && a[a.length - 1 - i] != 0) {
nonZeroCount += 1;
} else {
break;
}
}
if (nonZeroCount &...
5
The core problem can be solved a lot quicker using the built-in max and making a generator that produces the maximum count of repeated letters. Note that max already takes the first occurrence of the maximum, as required by the challenge, but we need to take care to not compare the words lexicographically, as I did in a previous version, by using a key ...
0
Your current code, if I understand it, starts by sieving each target without recognizing that if the target is less than the highest cache (or _base) then it is prime if and only if it in the cache.
One option is to keep your primes in a single cache (_base), make sure that the cache is high as your target, and check if your target is in your cache.
The ...
2
You could just make a new list rather than use list.insert and list.append.
indexes.insert(0, 0)
indexes.append(len(s))
indexes = [0] + indexes + [len(s)]
For your "slice string" part, I'd make a function called pairwise. As this is a rather well know recipe in Python.
def pairwise(iterable):
return (
(iterable[i], iterable[i+1])
for ...
3
Is numpy a good candidate module for this?
Using numpy is fine, but you can get by just fine without it.
Borrowing Martin R's wrapped_distance function, you could solve the problem without any external libraries as follows:
def coordinates(matrix: List[str], subject: str) -> Iterable[Tuple[int, int]]:
return ((r, c)
for r, row in ...
4
Here
enemy_locations = np.where(grid == 2)
enemy_locations = ((x, y) for y, x in zip(
enemy_locations[0], enemy_locations[1]))
the x/y-coordinates are swapped, and later the x-coordinate of each enemy is subtracted from the y-coordinate of the friend, and vice versa:
moves = [sum((abs(friendly_coords[1] - enemy[0]),
abs(friendly_coords[...
1
You chose to represent the “list of sequences” as a dictionary
var sequences: [Int: [Int]] = [:]
and here you test if a sequence for the given index already exists, and then either append a new element or create the initial sequence for that index:
if var sequence = sequences[seq] {
sequence.append(y)
sequences[seq] = sequence
} else {
...
1
solve() shouldn't print anything, much less all the intermediate results.
It should end with return ans and the main program should print that final result.
You'll get the same answer for (i,j) as for (j,i), so for the inner loop j never needs to be less than i.
The expression abs(l[i] - l[j]) + abs(i - j) gets calculated twice. Instead, assign the value ...
Top 50 recent answers are included
