Skip to content

Commit 7c5802a

Browse files
benaichbenaich
committed
initial commit
0 parents  commit 7c5802a

File tree

25 files changed

+2103
-0
lines changed

25 files changed

+2103
-0
lines changed

‎DynamicProgramming/Fibonacci.java‎

Lines changed: 20 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,20 @@
1+
package DynamicProgramming;
2+
3+
import java.util.HashMap;
4+
5+
public class Fibonacci {
6+
public static HashMap<Integer, Integer> tab = new HashMap<>();
7+
8+
public static int get(int i) {
9+
if(i == 0 || i == 1){
10+
tab.put(i, i);
11+
}else{
12+
tab.put(i, get(i-1) + get(i-2));
13+
}
14+
return tab.get(i);
15+
}
16+
public static void main(String[] args) {
17+
System.out.println("fib(3) = "+ Fibonacci.get(3));
18+
}
19+
20+
}

‎DynamicProgramming/LCS.java‎

Lines changed: 120 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,120 @@
1+
package DynamicProgramming;
2+
3+
public class LCS {
4+
5+
public static enum Direction {
6+
7+
H, V, O;
8+
};
9+
10+
public class Paire {
11+
12+
public int cal;
13+
public Direction d;
14+
15+
public Paire(int cal, Direction d) {
16+
this.cal = cal;
17+
this.d = d;
18+
}
19+
20+
public Paire() {
21+
this.cal = 0;
22+
}
23+
24+
@Override
25+
public String toString() {
26+
return cal + "-" + d;
27+
}
28+
}
29+
30+
Paire[][] p;
31+
String u, v;
32+
33+
public LCS(String u, String v) {
34+
this.u = u;
35+
this.v = v;
36+
p = new Paire[u.length() + 1][v.length() + 1];
37+
38+
for (int i = 0; i < u.length() + 1; i++) {
39+
for (int j = 0; j < v.length() + 1; j++) {
40+
p[i][j] = new Paire();
41+
}
42+
}
43+
}
44+
45+
public void init() {
46+
for (int i = 1; i < u.length() + 1; i++) {
47+
for (int j = 1; j < v.length() + 1; j++) {
48+
if (u.charAt(i - 1) == v.charAt(j - 1)) {
49+
p[i][j].cal = 1 + p[i - 1][j - 1].cal;
50+
p[i][j].d = Direction.O;
51+
} else if (p[i - 1][j].cal > p[i][j - 1].cal) {
52+
p[i][j].cal = p[i - 1][j].cal;
53+
p[i][j].d = Direction.V;
54+
} else {
55+
p[i][j].cal = p[i][j - 1].cal;
56+
p[i][j].d = Direction.H;
57+
}
58+
}
59+
}
60+
}
61+
62+
public String result(int i, int j) {
63+
if (p[i][j].cal == 0) {
64+
return "";
65+
}
66+
if (p[i][j].d == Direction.O) {
67+
return result(i - 1, j - 1) + u.charAt(i - 1);
68+
}
69+
if (p[i][j].d == Direction.H) {
70+
return result(i, j - 1);
71+
}
72+
return result(i - 1, j);
73+
}
74+
75+
public static String run(String u, String v){
76+
LCS app = new LCS(u,v);
77+
app.init();
78+
return app.result(u.length(), v.length());
79+
}
80+
81+
public void print() {
82+
System.out.print("\t\t");
83+
for (int i = 1; i < v.length() + 1; i++) {
84+
System.out.print(v.charAt(i - 1) + "\t");
85+
}
86+
System.out.println("");
87+
for (int i = 0; i < u.length() + 1; i++) {
88+
if (i == 0) {
89+
System.out.print("\t");
90+
} else {
91+
System.out.print(u.charAt(i - 1) + "\t");
92+
}
93+
for (int j = 0; j < v.length() + 1; j++) {
94+
System.out.print(p[i][j] + "\t");
95+
}
96+
System.out.println("");
97+
}
98+
}
99+
public static String doYouMean(String query, String[] text){
100+
String result[] = new String[text.length];
101+
for (int i = 0; i < text.length; i++) {
102+
result[i] = LCS.run(query, text[i]);
103+
}
104+
int max = 0;
105+
for (int i = 1; i < result.length; i++) {
106+
if(result[max].length() < result[i].length())
107+
max = i;
108+
}
109+
110+
return text[max];
111+
}
112+
public static void main(String[] args) {
113+
System.out.println(LCS.run("abcdbdab","bdcaba" ));
114+
115+
String dbText[] = new String[]{"house of cards", "game of throne", "breaking bad"};
116+
117+
System.out.println("Do you mean " + LCS.doYouMean("gamz of trone", dbText));
118+
}
119+
120+
}

‎FunctionalProgramming/PredicateDemo.java‎

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
/*
2+
* To change this license header, choose License Headers in Project Properties.
3+
* To change this template file, choose Tools | Templates
4+
* and open the template in the editor.
5+
*/
6+
package FunctionalProgramming;
7+
8+
import java.util.function.Predicate;
9+
import java.util.Arrays;
10+
import java.util.List;
11+
12+
public class PredicateDemo{
13+
public static void main(String[] args) {
14+
List<Integer> numbers = Arrays.asList(1,2,3,4,5,6,7,8,9);
15+
16+
System.out.println("Test");
17+
printFilter(numbers, x -> x%2==0);
18+
19+
}
20+
21+
public static <T> void printFilter(List<T> l, Predicate<T> p){
22+
for (T a: l ) {
23+
if(p.test(a)) System.out.println(a);
24+
}
25+
}
26+
}

‎HashTable/HashNode.java‎

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,42 @@
1+
package HashTable;
2+
3+
public class HashNode<K, V> {
4+
5+
private K key;
6+
private V value;
7+
private HashNode<K, V> next;
8+
9+
public HashNode(K key, V value) {
10+
setKey(key);
11+
setValue(value);
12+
}
13+
14+
public V getValue() {
15+
return value;
16+
}
17+
18+
public void setValue(V value) {
19+
this.value = value;
20+
}
21+
22+
public K getKey() {
23+
return key;
24+
}
25+
26+
public void setKey(K key) {
27+
this.key = key;
28+
}
29+
30+
public HashNode<K, V> getNext() {
31+
return next;
32+
}
33+
34+
public void setNext(HashNode<K, V> next) {
35+
this.next = next;
36+
}
37+
38+
@Override
39+
public String toString() {
40+
return "("+ key + ", " + value + ")";
41+
}
42+
}

‎HashTable/HashTable.java‎

Lines changed: 173 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,173 @@
1+
package HashTable;
2+
3+
import java.util.Random;
4+
import java.util.function.Function;
5+
6+
public class HashTable<K, V> {
7+
8+
public static final int INITIAL_TABLE_SIZE = 10;
9+
public static final double LOAD_FACTOR = 0.5;
10+
public static final int BIGNUMBER = 3345;
11+
12+
private HashNode[] array;
13+
private Function<K, Integer> foh;
14+
private int tableSize = INITIAL_TABLE_SIZE;
15+
private int size;
16+
private static int numCollisions = 0;
17+
private static int numResizes = 0;
18+
19+
public HashTable() {
20+
array = new HashNode[tableSize];
21+
CreateHashingFunction();
22+
}
23+
24+
public HashTable(Function<K, Integer> f) {
25+
array = new HashNode[INITIAL_TABLE_SIZE];
26+
foh = f;
27+
}
28+
29+
public float loadFactor() {
30+
return size / (float) tableSize;
31+
}
32+
33+
public int indexOf(K key) {
34+
return foh.apply(key);
35+
}
36+
37+
public void insert(K key, V val) {
38+
int index = indexOf(key);
39+
HashNode e = new HashNode(key, val);
40+
41+
if (loadFactor() > LOAD_FACTOR) {
42+
//resize
43+
numResizes++;
44+
HashNode[] oldArray = array;
45+
array = new HashNode[tableSize * 2];
46+
tableSize = tableSize * 2;
47+
for (int i = 0; i < oldArray.length; i++) {
48+
HashNode<K, V> node = oldArray[i];
49+
while (node != null) {
50+
insert(node.getKey(), node.getValue());
51+
node = node.getNext();
52+
}
53+
}
54+
}
55+
56+
if (array[index] == null) {
57+
array[index] = e;
58+
} else {
59+
insert(array[index], e);
60+
numCollisions++;
61+
}
62+
size++;
63+
}
64+
65+
public void insert(HashNode old, HashNode e) {
66+
if (old.getNext() == null) {
67+
old.setNext(e);
68+
} else {
69+
insert(old.getNext(), e);
70+
}
71+
}
72+
73+
public V get(K key) {
74+
int index = indexOf(key);
75+
HashNode<K, V> node = array[index];
76+
while (node != null) {
77+
if (node.getKey().equals(key)) {
78+
return node.getValue();
79+
}
80+
node = node.getNext();
81+
}
82+
return null;
83+
}
84+
85+
public void delete(K key) {
86+
int index = indexOf(key);
87+
array[index] = null;
88+
}
89+
90+
public int getSize() {
91+
return size;
92+
}
93+
94+
public int getNumCollisions() {
95+
return numCollisions;
96+
}
97+
98+
public int getNumResizes() {
99+
return numResizes;
100+
}
101+
102+
private void CreateHashingFunction() {
103+
foh = (x) -> {
104+
Random r = new Random();
105+
int a, b, p;
106+
a = r.nextInt();
107+
b = r.nextInt();
108+
p = nextPrime(BIGNUMBER);
109+
110+
return Math.abs(((a * x.hashCode() + b * x.hashCode()) * p) % tableSize);
111+
};
112+
}
113+
114+
public void print() {
115+
for (HashNode item : array) {
116+
if (item != null) {
117+
System.out.print(item);
118+
print(item.getNext());
119+
} else {
120+
System.out.println("x");
121+
}
122+
System.out.println();
123+
}
124+
}
125+
126+
public void print(HashNode e) {
127+
if (e == null) {
128+
return;
129+
}
130+
System.out.print(" - " + e);
131+
}
132+
133+
/* helpers */
134+
private static int nextPrime(int a) {
135+
while (!isPrime(a)) {
136+
a++;
137+
}
138+
return a;
139+
}
140+
141+
private static boolean isPrime(int a) {
142+
if (a == 2) {
143+
return true;
144+
} else if (a % 2 == 0) {
145+
return false;
146+
} else {
147+
int i = 3, end = (int) Math.sqrt(a + 0.0);
148+
while (a % i != 0 && i <= end) {
149+
i = i + 2;
150+
}
151+
return i > end;
152+
}
153+
}
154+
155+
public static void main(String[] args) {
156+
HashTable<String, String> ht = new HashTable<>(x -> Math.abs(x.hashCode()) % INITIAL_TABLE_SIZE);
157+
ht.insert("banana", "yellow");
158+
ht.insert("apple", "green");
159+
ht.insert("android", "green");
160+
ht.insert("cat", "white");
161+
ht.insert("body", "black");
162+
163+
ht.print();
164+
165+
System.out.println("----------- Get -----------");
166+
System.out.println("apple : " + ht.get("apple"));
167+
168+
169+
ht.delete("apple");
170+
ht.print();
171+
}
172+
173+
}

0 commit comments

Comments
 (0)