New answers tagged algorithm
1
My answer is additive to the others; I'm not going to repeat points already made.
1. Nitpick: prefer int[] arr over int arr[]
The "arrayness" ([]) has more to do with the type than it does the variable name, so it's better to keep them together. Not to appeal to authority, but Google's style guide also suggests this.
2. Avoid "for" loops where "for-each" ...
1
I had an idea to just try to make the word by removing all the needed characters from the rack/haystack and see if it works. The idea also follows the "Easier to ask for forgiveness than permission" approach.
def set_includes(haystack, needle):
haystack = list(haystack)
try:
for char in needle:
haystack.remove(char)
...
1
AFNP. The loop condition j != hn is more idiomatically expressed as an exception:
try:
for c in needle:
while haystack[j] < c:
....
except IndexError:
return False
No naked loops. Factor the while haystack[j] < c: into a function. Among other benefits, it'd allow
j = search_character(haystack[j:], c)
The binary ...
2
From eyeballing it, your code doesn't quite produce the format shown after will return (pairs separated by " " instead of "], [".
An alternative to building a String and then printing it is printing its parts immediately -
I'd define a method like long squares(Appendable destination):
works with both StringBuilder and OutputStream. (Returning the count of ...
0
A few suggestions:
Constant variable names: Any values that do not change in the course of the program should be in UPPERCASE, indicating that they are constants.
Unneeded imports: Running your code through pylint, you had two unneeded imports. numpy was not used at all, and ylabel was not used either. Also, this could have just been my machine but the line ...
5
rather than writing all the loops by hand, can I suggest you use a different data structure? (I'm a C# programmer, hopefully my code will be easy to translate into Java.)
If the output order doesn't matter and you aren't interested in duplicates, you could get away with something like this:
var arr = new [] {5, 25, 3, 25, 4, 2, 25};
var set = new HashSet&...
0
Here are a few suggestions:
You should get in the habit of wrapping all code that isn't contained in a function, in a main guard. This will protect the code from being run when the file is imported.
Instead of code like, for example, s = "x" + str(i) + "x", you should use f""in front of your strings so you can directly include variable names into the ...
8
Avoid string addition
String addition is not good for building up strings from many pieces inside of loops. You should use StringBuilder instead.
StringBuilder sb = new StringBuilder();
// ... omitted ...
sb.append(arr[j]).append(',').append(arr[j]).append(' ');
// ... omitted ...
String s = sb.toString();
System.out.println(s);
Avoid square-...
0
Each time you create a new Dictionary even if your first condition is not satisfied. Convert your code as follows:
if (occ == 0)
numsDicOcc.Add(new Dictionary<int, string> { { x, "NOT PRESENT" } });
else{
var dic2 = new Dictionary<int, string> {{x, occ.ToString()}};
if (!numsDicOcc.Contains(dic2))
numsDicOcc.Add(dic2);
...
1
Short take …
most efficient way to do this
resources including developer time
… of uncommented code:
Starting with testCreateTree() raises hope for a stab at test first - I don't see it.
What is this above: is there more to tree than Node, how does searchable manifest?
there is no interface for Node
(and testCreateTree() shows one is urgently needed)
(...
3
Without same table and data scripts it is very hard to identify performance issues. However, here are a few observations that might help:
Unless I'm reading this wrong, this seems pointless, just adding overhead:
ON ((r.ArrivalAirportIATA <> r1.DepartureAirportIATA)
OR (r.ArrivalAirportIATA = r1.DepartureAirportIATA))
When using expressions, ...
1
PEP-8
class vertex:
class graph:
PEP-8 asks that you name these Vertex and Graph, with initial capital.
naming nodes
self.key = key
Yes, you will be using this as a dict key.
But name would have been the more natural identifier for a node name.
unused attribute
Please delete this line:
self.nbnodes = 0
That quantity may be trivially obtained ...
0
First off, I believe you are confusing the terms "specific" and "special" in the description.
Method isSpecial
You could move the if (occurrences.size() > 2) statement into the for loop, because once you know that there are more than 2 different characters, there is no need to continue adding more characters to the Set. Then you can also initialize the ...
4
Using a size_t for a boolean flag, and calling it flag, is nearly an obfuscation. Use int pre-C99 and call it something descriptive like substitute.
strlen() is likely a waste, though it makes describing the algorithm easier. Try to do without the additional iteration.
Getting the length of the longest common prefix looks like a well-defined task which can ...
0
View it as a matrix; meaning, X can go from 0 to 2, and so can Y - free your mind of the actual content. It is likely easier to build a new array and copy values into it using loops on X and Y positions.
Assuming you view mat[][] as mat[X][Y], you filled it as mat[left-to-right][top-to-bottom]. In order to perform what you consider as a 90-degree ...
4
Generally nice code: easy to read, good use of const char* for the string arguments.
It's great that we have unit tests; we can improve them by making them self-checking:
/* return number of test failures (0 or 1) */
int test_one_away(const char *str1, const char *str2, int expected)
{
const int actual = one_way(str1, str2);
if (actual == expected)
...
3
This is more of a suggestion on substance than a review of the code style; I'll leave that for other reviewers.
Your solution looks pretty good to me. I think you could streamline it a bit by doing it all in one shot, without checking the length of the strings first. For example:
int one_way(const char *a, const char *b)
{
int misses = 0, ia = 0, ib = ...
3
Dict updates
This:
if battalion_type not in self.battalion_strength:
self.battalion_strength[battalion_type] = change
else:
self.battalion_strength[battalion_type] += change
can be done more easily in a few different ways. Perhaps the easiest is to make battalion_strength a defaultdict(int). Then, this if goes away and you can "naively" do +=.
...
0
Optimization starts from a sound logical process
Let's think about the problem in particular.
Given a positive integral number n, return a strictly increasing sequence (list/array/string depending on the language) of numbers, so that the sum of the squares is equal to n².
If there are multiple solutions (and there will be), return the result with ...
0
Interesting exercise! Some suggestions:
It looks like a cleaner design might be to have a function (as opposed to a method) which takes a List[ImplicitDate] and returns List[datetime.datetime].
datetime.datetime months are one-offset, so I'm puzzled at the month = future_date.month - 1 line.
1
for (size_t left = 0, right = size - 1; first[left] == second[right]; ++left, --right) {
if (left == size) {
return true;
}
}
Completely incorrect.
IIRC, accessing sizeth character of first is UB. Even more, at this moment right is (size_t)-1, so you may guess.
For instance, when size is 0, right is initialized to -1. Were it a real ...
2
1. Don't use using namespace std;
While that would work in your particular case, it's considered bad practice. Especially when you move out your code to separate header files.
See more details here please:
Why is “using namespace std;” considered bad practice?
2. Check for valid input
You don't check if input was valid here:
cout << "Enter the ...
2
The algorithm
Your algorithm needs O(n) space (for storing all items), and O(n * k) time (for selecting the best ones) (n = items to choose from, k = items chosen, bounded by n).
By choosing as you go, you can get that down to O(k') space and O(n * k') time (k' = maximum items chosen at any time, at least k, bounded by n).
Take a look at std::push_heap, ...
2
Use standard docstrings
This comment:
to get input from user
is best placed in a docstring:
def get_input():
"""
get input from user
"""
Consider using type hints
You're best to google this, because there's a wealth of information about it, but as an example: the idx argument would be idx: int.
Operator precedence
(2 * idx) + 1
doesn't ...
2
General
This should probably be three separate classes, unless there's some compelling reason you haven't shared to wrap WeightedEdge and UnionFind inside KruskalMST. If they must be internal, they should be static because they don't rely on context from KruskalMST.
You should use final to indicate classes are not designed for extension and that properties ...
0
Requirements
It all depends on what you think is 'best'. The code that can be implemented in as little time as possible? The most efficient code? In terms of memory? CPU?
The solution below doesn't do any input checking, but instead is an approach that would be rather fast and very memory efficient
Return type
I prefer a solution that has an Iterator or ...
2
Managing memory requirements
Did you get the method signature from the interviewer? If not, it could use some improvement. Consider Joop Eggen's answer and the worst case scenario, where there are 2^63 different combinations. While his approach is likely the most efficient computationally, the method signature limits the operation to calculating everything ...
4
Usability
Your addCombinations(String input, int index, List<String> output) is harder to use than necessary. The user must:
create the storage for the result
pass in a mysterious 0 value
It would be better to add a "helper" function, to do these tasks for the user:
public static void main(String[] args) {
List<String> output = ...
1
First things first: Why are you returning a new array instead of directly sorting the input array? If we create 2 temporary arrays (left and right part) and then merge them back into the input array we don't need to return a new one (and can optimise later on).
private static void mergesort(int[] input, final int left, final int right) {
//quick note ...
1
Such a problem is also looking whether the interviewed has a nice logic filtering, simplifying things.
Now the problem actually only varies for the question marks. So:
void allCombinations(String pattern) {
if (!pattern.matches("[01\\?]+") {
throw new IllegalArgumentException("Invalid pattern: " + pattern);
}
int questionMarks = pattern....
2
EDIT: After talking to Baldrickk in the comments, I've realized that my sort by key method doesn't work for this problem. For instance, the below approach would sort [50,505040] as 50504050 instead of 50505040. I'm leaving the answer up for those who are interested.
This is my attempt at solving the problem assuming that the OP did indeed misinterpret the ...
0
The approach outlined in the question is brute-force: for each vertex, we do a DFS on all its subtrees, checking if they're all monochromatic. O(N^2)
Instead of running dfs on every vertex, we can selectively choose vertices that would conclusively tell us if it was possible to split up the graph as desired.
Consider a path: 111112111111. It doesn't feel ...
1
I find the problem you are trying to solve to be as hard to grasp from the code presented as from the description:
- document your code, using the conventions of the language (&environment) of choice.
- use telling names
In the for-loop, you don't use i: don't use enumerate().
I think the first comprehension easier to understand with reading (? "r") ...
2
For an interview setting, I think the code presented to be a very decent initial solution but for the lack of comments:
it is easy to read (and consequently should be easy to maintain).
It invites a question if there is any (semi-obvious) way to reduce machine resources used.
(AJNeufeld is entirely right about StringBuilder vs StringBuffer - leaving it ...
0
Making the set out of an interval is an immediate red flag. set is a heavyweight data structure, and making it is a heavyweight operation. It is also much easier to compute an intersection of two intervals, than of two sets.
Making the same set twice is another red flag.
All that said, it seems that you really overthink the problem. It admits a much ...
2
You can use python deque function to rotate string.
word = 'FIRSTCHARSTRING'
commands = [
('L', 2),
('R', 3),
('L', 1),
]
from collections import deque
q = deque(word)
for direction, magnitude in commands:
if direction == 'L':
q.rotate(-magnitude)
else:
q.rotate(magnitude)
if ''.join(q) == word:
print('Yes')
else:
print('No')
3
As mentioned by @IEatBagels, it seems that you didn't understand the question. You're not allowed to split numbers into digits. You're only allowed to reorder whole numbers in order to get the maximum joined number. The output for [0, 12] should be 120, not 210!
Others answers are proud to be O(n) or O(n log n), but well, they're probably wrong.
So I'm ...
-1
Here's what I came up with. It runs in O(n) because of the for each loop, and seems to be a nice readable option to me.
numberList = [1, 19, 93, 44, 2885, 83, 379, 3928]
def largestNumber(value):
string = ''
for number in value:
string = string + str(number)
result = ''.join(sorted(string, reverse=True))
return(int(result))
print(...
6
The question reads :
You are given an array of numbers (not digits, but numbers: e.g. 9, 23, 184, 102, etc.) - you need to construct the largest number from it. For example: you get 21, 2, 10 - the largest number is 22110. (Emphasis mine)
In a comment it was stated :
The task basically was to decompose the numbers into digits and then rearrange ...
7
First of all, whenever you see this ... this is a big no-no:
'9'*work_dict[9] + '8'*work_dict[8] + '7'*work_dict[7] +
'6'*work_dict[6] + '5'*work_dict[5] + '4'*work_dict[4] +
'3'*work_dict[3] + '2'*work_dict[2] + '1'* work_dict[1] +
'0'*work_dict[0]
it could be replaced by a simple
''.join(str(i) * work_dict[i] for i in reversed(range(10)))
Of course, ...
7
Your code
Your code as such seems to be functional, but not really elegant or concise.
First, the variable names don't speak for themselves. Nobody would be hurt if the function input was named numbers instead of a and number instead of ai. work_dict is also not a particularly good name since it's very generic. How about digit_histogram?
Handling single ...
1
Some comments on the code:
for i in range(n-1):
(u, v) = [int(i) for i in input().split()]
You are using i as the outer loop index, and i as the inner (list comprehension) loop index. This is confusing, and should be discouraged.
The second line may be written more simply as:
u, v = map(int, input().split())
The assignment:
colors = ...
3
You can adhere to the Style Guide for Python Code (Python Enhancement Proposal (PEP) 8) (there is tool support for this):
Comment your code properly.
Document your code properly.
In the code, using docstrings, making the documentation accessible to IDEs and introspection.
The first thing to document would be the interface of merge_sort():
it may be of ...
5
Part of code review is challenging assumptions, so to begin with I'd like to challenge the motivation for this code.
You say you want to avoid "Storing the UID (unique id) in the table along with the id". Why would you have two? Any one of those is enough to uniquely identify a row - they are both unique, after all. If you mean the surrogate key (serial ...
2
You can do it without using any additional table. I want to do it without recursion, but you can create recursive version very easily yourself.
First, let's see what is the second table in the link solution. In that table, the value of each table cell is the minimum cost for accessing that cell. But what about the cost table? in the cost table, the value of ...
1
There is a big problem in your code. sorted sorts the input list. So you are sorting input list twice.
For finding out that your list is sorted, you only need to check did you make any swap in the last iteration or not. If you don't, your list is sorted.
def get_input():
input_str = input("Enter elements to be sorted: ")
try:
lst = list(map(...
0
Your code produces buffer overflows because it doesn't check whether it writes beyond the end of buffer. And it cannot know that because it doesn't know the length of the buffer.
Either the function must have the buffer length as a parameter, or it must clearly document that the buffer must be twice as big as the input string. The latter requirement matches ...
2
A call to strlen(compress) is unnecessary. You already know the length of the compressed string; it is j.
You may (in fact, you should) terminate the loop as soon as j reaches the length of the original. Once it happened, the compressed string will for sure be longer than original.
nc + '0' assumes that nc is a single digit. The problem statement doesn't say ...
1
Yes you can do this in O(n) time.
You just need to scan through the array 1 time and track the 3 largest numbers and 2 smallest numbers. At the end compare the product of the 2 smallest * the largest vs the product of the 3 largest. One of those will be the max product of three numbers.
You only have to track the 2 smallest because the product of 3 ...
0
Oh my you are right that is rather slow.
I see that the accepted answer is a significant improvement however it can be done even faster
Flat array
The pixel buffer is a flat array of bytes, you waste a lot of cycles converting 2D coordinates {x,y} to the flat index. It is quicker to convert the flat index to 2D for each of the four points you find.
You ...
Top 50 recent answers are included
