Skip to content

Instantly share code, notes, and snippets.

View vkostyukov's full-sized avatar

Vladimir Kostyukov vkostyukov

365 followers · 38 following
View GitHub Profile
@vkostyukov
vkostyukov / BigInteger.java
Last active December 11, 2015 05:49
Patch for java.math.BigInteger class that increases multiply performance by using Karatsuba algorithm
...
public BigInteger multiply(BigInteger val) {
if (val.signum == 0 || signum == 0)
return ZERO;
int n = Math.max(bitLength(), val.bitLength());
if (n > 1000)
return multiplyKaratsuba(val, n);
int[] result = multiplyToLen(mag, mag.length,
@vkostyukov
vkostyukov / Permutation.scala
Created January 26, 2013 08:54
Puzzle Example from CCI.
object Permutation extends App {
def generate(s: String): Array[String] = s.length() match {
case 1 => Array(s)
case 2 => Array("" + s(0) + s(1), "" + s(1) + s(0))
case _ =>
val first = s.head
var perms = generate(s.tail)
var result: Array[String] = Array.fill(perms.length * (perms(0).length() + 1)) { "" }
var offset = 0
@vkostyukov
vkostyukov / Reverse.scala
Last active December 11, 2015 18:28
True version of "reverse list problem" in Scala
object Reverse extends App {
def reverse(l: List[Int]): List[Int] = l match {
case head :: Nil => head :: Nil
case head :: tail => reverse(tail) :+ head
}
assert { reverse(List(1, 2, 3, 4, 5)).corresponds(List(5, 4, 3, 2, 1)) {_ == _} }
}
@vkostyukov
vkostyukov / Mistery.qp
Last active December 11, 2015 18:38
A Mistery Quipu Program by Timwi.
"0 1 2 3 4 5 6 7 8 9 10 11"
\/ \/ 8& 6& 8& 6& 1& 8& 1& 1& 8& 4&
[] [] [] [] 9& [] 9& [] []
2& 1& 2& 6& [] 2& [] 1@ /\
// -- [] [] -- // -- 1&
2& -- ** 0& 1& ==
** 3& [] [] 2&
[] ** ** ??
** 5& 7&
@vkostyukov
vkostyukov / CF262B.scala
Created January 31, 2013 16:19
My solution for http://www.codeforces.com/problemset/problem/262/B
object CF262B extends App {
import java.io.{PrintWriter}
import java.util.{Locale, Scanner}
val in = new Scanner(System.in)
val out = new PrintWriter(System.out)
def nextInt = in.nextInt
def nextDouble = in.nextDouble
@vkostyukov
vkostyukov / List.scala
Last active December 12, 2015 03:18
Plaing around data sturtures implementation in Scala.
/**
* This file is part of Scalacaster project, https://github.com/vkostyukov/scalacaster
* and written by Vladimir Kostyukov, http://vkostyukov.ru
*
* Linked List http://en.wikipedia.org/wiki/Linked_list
*
* Prepend - O(1)
* Append - O(n)
* Head - O(1)
* Tail - O(1)
@vkostyukov
vkostyukov / StackSort.scala
Created February 5, 2013 10:46
StackSort algorithm that uses main ideas of MergeSort
def sort(s: Stack[Int]): Unit = {
def dump(a: Stack[Int], b: Stack[Int]): Unit = {
if (!b.empty) {
val v = b.pop
dump(a, b)
a.push(v)
}
}
@vkostyukov
vkostyukov / Stack.scala
Created February 22, 2013 04:46
Implementing Stack using two Queues. Push - O(n), Pop - O(1)
import scala.collection.immutable.Queue
class Stack[+A](val in: Queue[A] = Queue.empty[A], val out: Queue[A] = Queue.empty[A]) {
def push[B >: A](v: B): Stack[B] = {
var i = in.enqueue(v)
var o = out
while (!o.isEmpty) {
val (vv, oo) = o.dequeue
o = oo
@vkostyukov
vkostyukov / BSonLLBenchmark.scala
Created June 16, 2013 11:47
This is a benchmark that proves thesis: "there is no advantages of using binary search on linked list".
object BSonLLBenchmark extends App {
class HeavyObject(val n: Int) extends Ordered[HeavyObject] {
def compare(that: HeavyObject): Int = {
var d = 0
for (i <- 1 to 100000000) {
d += (math.abs(math.max(this.n, that.n) / math.min(this.n, that.n)) + 1) / i
}
@vkostyukov
vkostyukov / Test287.java
Created July 17, 2013 10:24
public class Test287 {
public static int binarysearch(int a[], int k) {
return binarysearch(a, k, 0, a.length);
}
public static int binarysearch(int a[], int k, int lo, int hi) {
if (lo == hi) return -1;
int p = (lo + hi) / 2;