18
votes
Accepted
Why is the Java HashMap load factor 0.75?
I don't know the answer, but I can walk you through what might be going through the mind of someone designing such a data structure.
Assuming a "good" hash function, and that $n$ is large ...
- 24.9k
8
votes
Formal model of execution for Java (or general imperative language)
There is an (operational) semantics for Java 1.4 formulated in the $\mathbb{K}$ framework. Associated to this framework is a proof system called Matching Logic. While that page describes a prototype ...
- 12.2k
7
votes
Accepted
Formal model of execution for Java (or general imperative language)
Featherweight Java is quite highly regarded in the PL community. But if that doesn't suit your needs, here's a general approach to modelling:
Formalize your language's AST into expressions and ...
- 30.4k
5
votes
Accepted
How is the formula for calculation in row/column major obtained?
Row-major order stores the rows of the array one after another in memory. That is, the array
a d g j
b e h k
c f i l
is stored as
...
- 82.6k
5
votes
Big-O time complexity for this code snippet
You are right, the two innermost loops perform $\Theta(\log n)$ iterations each, so we have a total of $\Theta(\log^2 n)$ iterations, which are repeated $\Theta(n)$ times in the outer loop, which ...
- 1,338
4
votes
Accepted
Sum of unique integers to cnf constraint
Here's a strategy for solving Kakuro with a SAT solver.
Make a nine variables for each cell, each variable indicating whether that cell contains $1$, $2$, etc.
Add a exactly-one-out-nine constraint ...
- 14k
4
votes
Linked list: advantages of preventing movement of nodes and invalidating iterators on add/remove
I think this is due to the differences in the philosophy underlying the design of both programming languages. The C++ philosophy allows data structures to cause undefined behavior as soon as the user ...
- 14.7k
3
votes
Write a routine to print the numbers 1 to 6 and back to 1 again without using any loops
public class Foo {
public static void main(String[] java_is_silly) {
System.out.print("1 2 3 4 5 6 5 4 3 2 1");
}
}
- 31.8k
3
votes
Count of (x,y) pairs that satisfy the equation x^2+y^2 = n^2
Your approach is to try every possible $x$ and $y$ and see if $x^2+y^2=n^2$. However, $n$ is fixed and, for any $x$, either $n^2-x^2$ is a perfect square or it isn't. You can calculate ...
- 82.6k
3
votes
Algorithm to select sets of objects while maximizing number of objects covered
The problem you're describing can be seen as the weighted independent set problem, as follows: Construct a graph $G=(V,E)$, where every node $v$ in $V$ corresponds to your sets of objects. The nodes $...
- 8,462
3
votes
Indentations in If-Else?
Indentation has absolutely no syntactic or semantic meaning in Java, and indeed in most popular languages (the main exception is Python).
Which if does your else belong to? This is an instance of the ...
- 281k
3
votes
Accepted
virtual machine based programming languages vs low level
It is impossible for one language to be faster than another language, period.
A programming language is a set of abstract mathematical rules and restrictions. It is an idea. A piece of paper. You ...
- 6,683
2
votes
How do compilers implement symbolic (rather than textual) insertion?
I can't wrap my head around how the compiler accomplishes this.
The compiler processes the source files in multiple passes.
In the first pass, it gathers information about types and their members, ...
- 1,876
2
votes
How do compilers implement symbolic (rather than textual) insertion?
The Java compiler reads the files you listed with the import statements to see the definitions. For historical reasons C compiler doesn't do this and prefers to get everything in one file, hence the ...
- 6,001
2
votes
Construct an array from a binary tree
Yes, of course. Just put all vertices in the tree into an array, in any order as you like.
There are different popular methods, that all generate interesting properties:
Pre-order: do a DFS starting ...
- 1,605
2
votes
Please help, I have been attempting to understand Quicksort for 9 hours now with little luck!
Elements that are equal to the pivot are not getting moved correctly. You need to change one of your checks (> or <, pick one; usual choice is to use >=) to include the equal case in ...
- 350
2
votes
algorithm to find all values that occur more than n/10 times
Perhaps the hint was aiming at the following approach. Suppose that the array were sorted. If a value appears $m$ times and we divide the array into intervals of length $m$, then the value must appear ...
- 281k
2
votes
Accepted
Intelligent use of XOR operator to find missing number
Let us use a simpler example to verify the fact.
Suppose $n=1$, i.e., we are given an array containing one (distinct) number taken from 0, 1.
If the given number is 0, then the missing number must be ...
- 39.2k
2
votes
why Loop-Programm always terminates
Bounded loops terminate, unbounded (as in your example) don't necessarily terminate.
- 18k
2
votes
Accepted
What is the Time Complexity of Least Topological Ordering?
Yes, the best complexity one can get for this problem is O(V*log(V) + E). Therefore, your approach is correct. Congrats :)
From a practical standpoint, the average ...
1
vote
Blueprint for class and objects in Java
According to Oracle's Java SE Archives
The proper order of a Java file is:
Beginning documentation
Package and Import Statements
Class and Interface Declarations
Where a class/Interface is arranged ...
- 51
1
vote
What is loop invariant for this loop?
"
Pre: stack is empty or contains only integers
Post: Stack top is non-negative Integer
P: Stack top is an Integer ( P is the invariant )
BB: Stack top is negative
T: Stack ...
- 51
1
vote
How to calculate the runtime of a following code?
If I understand correctly, that you denote $n$=list.length and are calculating amount of "list[i] +=" operation. Then of course, as it is triple loop, then for $n$ times fixed "i&...
- 2,399
1
vote
Why whenever a caller or client modifies a library collection class, all iterators are made invalid?
The question is "why".
There are two problems: First, you would have to define how an iterator that doesn't become invalid would change if the underlying container changes. That will be an ...
- 32.6k
1
vote
Intelligent use of XOR operator to find missing number
Start with a list of any n integers. Duplicate the integers and calculate the XOR if these 2n integers. What’s the result? Rearrange the 2n integers in any way and calculate their XOR. What’s the ...
- 32.6k
1
vote
Accepted
Elements of Programming Interviews - 16.4 Generate Power Set - solution 1 time complexity question
Note the following line of code:
powerSet.add(new ArrayList<>(SelectedSoFar);
Whenever we create a subset, we add the subset (list) to a list of list : <...
- 948
1
vote
Accepted
Difficulty in understanding this summations to analyze time complexity
Shellsort is notoriously difficult to analyze (surprising for such a simple algorithm). In Knuth's "Sorting and Searching" it gets an inordinate scrutiny, papers on its performance get published ...
- 14.3k
1
vote
Minimum words in a string given a dictionary
One possible approach to solve this problem is as follows:-
(1) Create a trie of the dictionary for fast matching.
(2) Create a recursive function that does the following:-
(a) Finds all possible ...
- 279
1
vote
Creating sum of all numbers within a sequence
From the top of my head I would use a greedy approach, always remove the lowest available number so the potential sum of later steps lessens the least this way. But I do not have a proof for this ...
- 281
Only top scored, non community-wiki answers of a minimum length are eligible