17
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 ...
- 20.2k
13
votes
Accepted
What fragment of Martin-Löf dependent type theory can be expressed using generic types in Java?
There are a lot of misconceptions here. To begin, MLTT doesn't have subtypes, so Java is not going to simply be a fragment of it. It does not require dependent types to make either of the types you ...
- 11.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 ...
- 11.9k
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 ...
- 29.5k
6
votes
Accepted
Find out duplicate number between 1 to N numbers
Here is the question:
You are given a list of length $n+1$ which contains the numbers $1,\ldots,n$, one of them appearing twice (and the rest appearing once).
Find the number which appears twice.
...
- 274k
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
...
- 81.1k
5
votes
Binary Search Tree Traversals
The rules for traversing a tree are, to visit all nodes of a tree you do this:
Preorder: (1) visit the root node, then (2) visit all the nodes in the left subtree of the root, then (3) visit all the ...
- 14.7k
4
votes
improving java 8's implement to hash map using avl tree
This page on Oracle's website says:
The alternative String hash function added in 7u6 has been removed from JDK 8, along with the jdk.map.althashing.threshold system property. Instead, hash bins ...
- 3,098
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.4k
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 ...
- 12.5k
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 $...
- 7,568
3
votes
Accepted
How to calculate the average of x numbers?
Instead of giving an answer, I will try to paraphrase the steps, I hope this will help you solve your homework.
Identify the problem: What is the input? What is the output?
Comprehend the problem: ...
- 507
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");
}
}
- 29.4k
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 ...
- 81.1k
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 ...
- 274k
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 ...
- 5,421
2
votes
Methods in Java with/without return? Simple but new to coding
You only need to use a return if you plan to return a value or object to the caller. So for instance if you called a method, that then performed a calculation such as an addition you could return the ...
2
votes
Is there a general pattern/structure/format to most (if not all) computer functions?
A method is just a precise sequence of instructions (in the ordinary English-language sense of the word) of how to perform some specific task. It's certainly true that many tasks – and I ...
- 81.1k
2
votes
Accepted
Version of knap sack problem
Your question is equivalent to the decision version of the unbounded knapsack optimization problem. The decision is whether the maximum value (after optimization) is equal to the upper bound. ...
- 306
2
votes
Version of knap sack problem
The problem is similar to coin denomination with infinite number of coins available.
Let me know if this works ... http://www.geeksforgeeks.org/dynamic-programming-set-7-coin-change/
For every ...
- 34
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,856
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 ...
- 5,911
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 ...
- 340
2
votes
Binary Search Tree Traversals
These are recursively defined traversal methods, as you can see from your code. A stack is useful if you want to write an implementation without recursion. Wikipedia has some explanation of the three ...
- 29.1k
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,570
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 ...
- 274k
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 ...
- 38.2k
2
votes
why Loop-Programm always terminates
Bounded loops terminate, unbounded (as in your example) don't necessarily terminate.
- 14.5k
1
vote
Which Data Structure should I use to store words from a novel?
You will probably end up using two nested data structures. I would use a hashmap with the words as keys. The value would be an array/list/set (depending on what you want to do with the occurrence data)...
- 340
1
vote
How is the formula for calculation in row/column major obtained?
B is the base address where the first element residents. For simplicity, let's assume that the array indexes start at zero, so $L_r$ and $L_c$ are both zero.
So the first element $[0,0]$, we have I=...
- 208
Only top scored, non community-wiki answers of a minimum length are eligible