New answers tagged programming-challenge
0
A simple improvement for readability could be to eliminate the - 1 in the indices by replacing size with max = mat.GetLength(0) - 1;:
void rotateMatrix(int[,] mat)
{
int max = mat.GetLength(0) - 1;
for (int x = 0; x < (max + 1) / 2; x++)
{
for (int y = x; y < max - x; y++)
{
int temp = mat[x, y]; // save 1
mat[x, ...
2
I think this code should work and is about the fastest way i can think to do it.
var ispoweroftwo = function(i)
{
var ret = (i == 1);
var n = i;
if(n > 0)
{
do
{
if((n & 1) == n) //divided by an exponent of 2 is exact
{
ret = true;
...
-1
well you know the scores are sorted descending and Alice's scores ascending
what I have done is loop over Alice's scores and inside that loop over scores (removed duplicates (Array.from(new Set(arr))) but starting from the end (n -> 0), then remember the already passed indexes and skip them in the next loops
that gave me 20/20
2
Please review for performance.
The performance looks fine to me. Some key observations:
It's clear that all nodes must be visited to compute the correct answer, so the solution cannot be better than \$O(n)\$ time.
Traversing in level order as you did will require as much additional space as the number of nodes on the most dense level.
Traversing depth ...
1
Is it possible to solve it mathematically and make it faster?
Not faster than the second solution,
which is \$O(n)\$, making a single pass over the input.
It's easy to see that it's not possible to find the correct answer without inspecting every element. For example, if two values are not inspected, then one could pick arbitrarily high values for them to ...
2
Nice. Good use of the carry to add the 1.
One point. Arrays only grow from the end. Array.unshift() means that each item must be moved up and is \$O(n)\$ complexity (making the whole function approx \$O(n^{log(n)})\$ ) while Array.push() is only \$O(1)\$ but then you will have to reverse but would still be \$O(n)\$ overall.
You could also pre-allocate the ...
2
It looks like your logic is fine, but I don't find it very readable. I guess it would be fine if you could clearly explain your logic in a tech interview, but here's how I'd write it just to be more clear.
Use a for loop (that's what they're for!), modify the digits array in place unless they specify you shouldn't, and you can return as soon as you don't ...
2
The time complexity of Sum is \$O(m n)\$,
because in the worst case it may need to enumerate all nodes.
An \$O(m)\$ implementation is possible with \$O(n)\$ extra space, and a bit of extra work in Insert:
Add a Dictionary<string, int> to track the current values of the keys, let's call it values.
Use TrieMSNode.Value to store the sum of all values ...
-4
n=10001
c=4
for i in range(11,1000000,2):
d=0
for x in range(3,int(i**0.5)+1,2):
if i%x==0:
d=1
break
if d==1:
continue
else:
c+=1
if c==n:
break
print(i)
## Here is a simple approach to the question using python
In my code i have taken c=4 which contains elements (2,...
8
I don't have much to add to Henrik's answer at a low level, but I think you've missed the point of the exercise at a high level.
The spec could be implemented as simply as
public class MapSum
{
private readonly IDictionary<string, int> data = new Dictionary<string, int>();
public void Insert(string key, int val) => data[key] = val;
...
8
In Insert(...) you should use TryGetValue instead of ContainsKeyfor efficiency:
foreach (var letter in key)
{
if (!current.Edges.TryGetValue(letter, out var edge))
{
edge = current.Edges[letter] = new TrieMSNode();
}
current = edge;
}
Name your methods after what they do, not after their implementation:
DFS(...)
could be ...
2
WARNING
Never do a double assignment in a variable declaration.
"use strict";
let carry = i = 0; // throws i is not defined
Without strict mode there is no error and i is then declared in the global scope.
Should be either
let carry, i;
carry = i = 0;
or
let carry = 0, i = 0;
or
let i = 0, carry = i;
General
You can simplify some of the code.
...
2
Could you do it without extra space and in \$O(n)\$ runtime?
The implementation uses \$O(n)\$ extra space.
A different approach is possible without extra space,
by rearranging the content of the input array,
so that the values that appear ordered, and at the position where they would be if nothing was missing.
Going with the example [4,3,2,7,8,2,3,1], the ...
3
Never indent as you have done. This make code very unreadable due to the long lines.
Map.values() creates an iteratable object. It does not require an array to be created and is \$O(1)\$ storage as it iterates over the already stored values
You have forced the map to be stored as an array. Array.from(map.values()) That means that it must be iterated and ...
2
You have created a good solution, just a few style points that can reduce code size.
Why null rather than false or even 0 in arr[x - 1] = null;
Why not use commas to remove need for return. Eg .reduce((arr, x) => {arr[x - 1] = null; return arr; } becomes .reduce((arr, x) => (arr[x - 1] = null, arr))
To create an array of indexes you could have used ...
3
Your solution looks rather map-happy.
It is important to remember for this task that counting higher than 2 of any encountered letter is needless processing as is any processing on any letter after the earliest positioned unique letter.
Also, doing a complete sweep of the input string may be ill-advised if the input string is of considerable length.
Due ...
3
Objects should be making the code easier to read. The Object you name position provides no behavioral benefit and serves only to bloat the code.
You should be using good old for loops for this rather than the hacky way you use the array iteration function forEach
Use function declarations function islandPerimeter(grid). Do not use function expressions var ...
2
The algorithm can be rewritten to use Linq instead of a Queue.
public IList<IList<int>> LevelOrder(Node root)
{
IList<IList<int>> result = new List<IList<int>>();
Queue<Node> Q = new Queue<Node>();
..
This increases readability. (At the cost of performance?) I use IEnumerable ...
3
The 99th percentile is due to the linear nature of your approach. The goal of this exercise is to figure out a logarithmic one.
I don't want to spell out the algorithm entirely. Just a hint to get you started. Take a middle element of nums1. Find its lower bound in nums2; call it i2. In the sorted array the selected element would be at the position nums1....
1
A recursive approach that takes into account the threshold of max depth 1000. The threshold of 5000 nodes is ambigious, because what behavior do you expect when there are more nodes?
using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;
using System.Globalization;
using System.Text.RegularExpressions;
public class Program
{
...
5
In terms of data structures and algorithms this all looks pretty straightforward - not much to say about that.
Performance
Edges.ContainsKey and Edges[...] each perform a lookup. Edges.TryGetValue lets you achieve the same with just a single lookup.
Design
I see no reason why Trie.Head should be public, and certainly not why it should have a public ...
4
Inconsistent style
The getMin function checks if the stack is empty, and the top function doesn't.
This inconsistency is confusing.
I'm not sure which way is better, but it's good to be consistent.
Unnecessary and over-eager input validation
push checks if the parameter is a number, and quietly does nothing if it isn't.
If non-numbers should not be ...
3
The getMin function is not constant. You need to keep track of the minimum value whenever you push or pop.
Furthermore you should name your functions.
3
I'd just use string manipulation on this, with a simple conditional for the edge cases.
var reverse = n => {
const s = parseInt([..."" + n].reverse().join(""));
return s >= 2 ** 31 ? 0 : Math.sign(n) * s;
};
The approach is to stringify the number, arrayify the string, reverse it, re-join the array into a string and finally parse the reversed ...
3
The first condition is a bit conservative:
if (root == null || (root.left == null && root.right == null))
Just if (root == null) would be enough, the rest of the implementation naturally handles the cases of root.left == null && root.right == null.
Evaluating curr != root for every node, when it's only useful for the first node is a bit ...
4
I don't know what you mean by declarative in this case. All these functions are pure (except the console.log), but the implementations of the functions are all imperative (which is fine of course)
When adding to a set, you don't need to check if the key exists first. Just add it.
Splitting the string into an array of chars isn't necessary. You can use string ...
2
Do not map to array
I appreciate that streaming strings is a little messy. However, there is no need to create an array; instead we can just transform the stream. I would remove the arrays and change getFrequencyMap to take a String.
Use Map::getOrDefault to simplify countError
In particular, if you do aMap.getOrDefault(ch, 0) then the Math.abs case ...
1
Your solution use a single loop to iterate through all elements
so the complexity is O(N), where N is the number of elements.
The performance can be improved a little by removing the first if statement and inserting left before right in the stack
6
The question states that the input is a number 32 signed int so checking for undefined or null is a waste of time.
The solution is a little long. Some of it due to not being familiar with some old school short cuts.
To get the sign of a number use Math.sign
-JavaScript numbers are doubles but when you use bitwise operations on them they are converted to ...
2
Good attempt, but unfortunately the nested loop brings the time complexity to O(n2). Keep in mind that .find performs a linear search on the vector, inspecting up to the entire array to find an element. We can arrive at a O(n) solution by exploiting the fact that no more than 2 swaps can be performed by any given element, which is a red flag in the problem ...
1
The answer by ggorlen covers most of the points and the alternative that was presented is very efficient, well sort of. In terms of complexity it is less complex and that shows when you compare your function.
If we use your algorithm and clean up some of the nasty bits, we get.
function longestSubstr(str) {
var res = 0, tmp = [];
for (const char ...
2
Style
Nice usage of arrow functions and spread operators. You can extend this to the function name as well:
const lengthOfLongestSubstring = s => { ... };
The code switches between two and four spaces within a block and between blocks. Choose one and stick with it throughout the entire program (the auto-formatter built into Stack Exchange does the job ...
3
Wow that is a lot of code to add two numbers.
Potential bug
The function ListNode has one argument yet in the function addTwoNumbers you call it with two arguments. However it does not manifest as a bug as you add the link in the lines following the node creation.
This also results in you creating twice as many nodes as needed.
E.G the second node is ...
3
There are few ways to simplify the code. First, to deal with rollover you don't need to convert a number to string and back.
if (k > 9) {
rollover = 1;
k -= 10;
}
looks more natural.
Second, the isFirst logic is rather convoluted. A standard technique is to initialize the resulting list with the dummy head, and not worry about ...
2
I think you're over-complicating the problem -- you need to think of a different approach.
Here's an algorithm: consider the first digit in the linked list. Add it to the "running total." If there's another number in the list, multiply it by 10*(number count) and add it to the running total. Keep going until you run out of new numbers.
Think of it this ...
4
A bit of scaffolding
In order to test/review your code, I had to write a bit of additional code. In case it can be relevant to you or other reviewers, here it is:
# Definition for singly-linked list.
class ListNode:
def __init__(self, x):
self.val = x
self.next = None
def __eq__(self, other):
ret = other is not None and ...
2
Opportunities missed
You have essentially the same algorithm in both examples. When I first looked at the solutions the sort at the start was a worry. The logic is sound, to work from the smallest word as there will be no more characters to test then is contained in that word.
However you have the sort AoT and the result is you set first to be the longest ...
0
Your solution is not optimal but you should try something better.
You can utilize BigInteger method or BitSet class to optimize andmake it easy.
For forming a team you have to use bitwise OR
Here are solutions--
// 1st approach
static int[] acmTeam(String[] topic) {
int n = topic.length;
BigInteger[] bi = new BigInteger[n];
...
2
Your code looks frighteningly slow because of the 5 nested for loops, and indeed it is.
To find an efficient algorithm, you should switch off the computer, take out a sheet of paper and solve the following task on paper:
Given an infinite amount of coins labelled 5, 7, 16, which amounts between 1 and 100 can be composed?
While you solve that task, ask ...
1
def divisor_generator(n):
'''Generates the divisiors of input num'''
large_divisors = []
for i in range(1, int(math.sqrt(n) + 1)):
if n % i == 0:
yield i
if i*i != n:
large_divisors.append(n / i)
for divisor in reversed(large_divisors):
yield divisor
I would rename this just divisors, ...
2
It sure sounds like you're running out of memory as you try to build (or allocate) the buffer.
You need to figure out how big a buffer you can (or want to) use. You'll need to ask the system how much RAM it has, and how much is available, and make your buffer that large.
You might get a small boost by opening the file as explicitly write-only.
You'll need ...
0
The whitespace needs a lot of changes to be PEP8-compliant. The capitalisation is also unconventional: functions and variables in Python usually start with a lower-case letter.
The meaning of Player is not entirely clear, and the logic is hard to follow because of that. The convention for this type of combinatorial game is to denote a position as "N" (Next ...
2
There is one fairly obvious optimization that should cut your time in roughly half. Pascal's Triangle is symmetric. Take advantage of that with whatever algorithm you are using. Roughly speaking (without checking my end-conditions so do that):
for (j=1;j<i/2;j++)
{
value = matrix[i-1][j-1] + matrix[i-1][j];
matrix[i][j] = matrix[i][i-j] = value;
if ...
4
As per request in the comment, here's an implementation of the rotate function in a more idiomatic golang way (ie using a pointer receiver):
// let's use constants so code becomes self-documenting
const (
maxRotation float64 = 18 // max rotation as typed constant
fullCircle int = 360 // just like all hard-coded values, let's use constants
...
5
You'll have to have this check before the initialization of the dictionary:
if (employees == null || employees.Count == 0)
{
return 0;
}
or else the initialization of the dictionary may throw if employees == null
You can initialize the dictionary this way:
Dictionary<int, Employee> idToEmployee = employees.ToDictionary(e => e.Id);
...
4
Wouldn't it be possible to calculate the _end as
private int End => (_start + _size) % _maxSize;
so you only have to update _start and _size and then omit _end?
Enqueue will then look as:
public void Enqueue(T newValue)
{
if (_size == _maxSize)
{
throw new InvalidOperationException("Queue at full capacity");
}
...
3
One array solution
The following algorithm is an improvement on the two array system stated bellow it. Basically, we only need the context of the old previous value (as well as the next value, which goes unmodified), so we copy this value. From there we can set the new end to 1 then start over. This cuts down on the memory overhead. I think you'll see ...
9
Yay exceptions!
Though it isn't reservered for execution-ending errors, I would avoid throwing an OutOfMemoryException, because usually it signals something very inconvient indeed. IndexOutOfRangeException also seems inappropriate: I would probably use InvalidOperationException in both Enqueue and Dequeue.
The constructor could do with a check to ensure ...
2
Check each unique sub string once
I agree with the existing answer, however there is a faster way to solve the problem, there is also an early exit possible that many of the challenges will test for.
The early exit can be found by finding out if there are any two characters that are the same. If not then there are no anagrams that are longer than 1 ...
1
You can often replace switch statements with lookup functions. For example
function returnsHome(moves) {
var v = 0, h = 0;
const dirs = {
U() {v++},
D() {v--},
L() {h--},
R() {h++}
};
for (const move of moves) { dirs[move]() }
return !(h || v);
}
// or
function returnsHome(moves) {
var v = 0, h =...
Top 50 recent answers are included
