Skip to main content
OverflowAI is here! AI power for your Stack Overflow for Teams knowledge community. Learn more
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 ...
Pseudonym's user avatar
  • 22.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 ...
Derek Elkins left SE's user avatar
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 ...
Derek Elkins left SE's user avatar
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 ...
Joey Eremondi's user avatar
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. ...
Yuval Filmus's user avatar
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 ...
David Richerby's user avatar
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 ...
Rick Decker's user avatar
  • 14.8k
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 ...
SilvioM's user avatar
  • 898
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 ...
tsleyson's user avatar
  • 3,128
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 ...
chi's user avatar
  • 14.6k
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 ...
orlp's user avatar
  • 13.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 $...
Discrete lizard's user avatar
  • 8,248
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: ...
ilke444's user avatar
  • 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"); } }
Andrej Bauer's user avatar
  • 30.5k
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 ...
David Richerby's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
Jörg W Mittag's user avatar
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 ...
Hendrik Jan's user avatar
  • 30.8k
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 ...
David Richerby's user avatar
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. ...
Travis's user avatar
  • 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 ...
PNL QLF's user avatar
  • 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, ...
svick's user avatar
  • 1,866
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 ...
adrianN's user avatar
  • 5,951
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 ...
Jakube's user avatar
  • 1,585
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 ...
HackerBoss's user avatar
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 ...
Yuval Filmus's user avatar
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 ...
John L.'s user avatar
  • 39k
2 votes

why Loop-Programm always terminates

Bounded loops terminate, unbounded (as in your example) don't necessarily terminate.
Pål GD's user avatar
  • 16.4k
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 ...
Radu Andrei Vaida's user avatar
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 ...
gnasher729's user avatar
  • 30.4k

Only top scored, non community-wiki answers of a minimum length are eligible