Skip to content

Commit 17450dd

Browse files
siriaksiriak
authored
Merge branch 'master' into master
2 parents ddaa16d + 85c836c commit 17450dd

File tree

12 files changed

+455
-30
lines changed

12 files changed

+455
-30
lines changed

‎.github/workflows/update_directory.yml

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -18,10 +18,9 @@ jobs:
1818
runs-on: ubuntu-latest
1919
steps:
2020
- uses: actions/checkout@master
21-
- uses: actions/setup-python@master
21+
- uses: actions/setup-python@v4
2222
with:
23-
python-version: '3.9' # Version range or exact version of a Python version to use, using SemVer's version range syntax
24-
architecture: 'x64' # optional x64 or x86. Defaults to x64 if not specified
23+
python-version: '3.10'
2524
- name: Update Directory
2625
shell: python
2726
run: |

‎DIRECTORY.md

Lines changed: 58 additions & 4 deletions
Large diffs are not rendered by default.

‎src/main/java/com/thealgorithms/datastructures/caches/LFUCache.java

Lines changed: 147 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,147 @@
1+
package com.thealgorithms.datastructures.caches;
2+
3+
import java.util.HashMap;
4+
import java.util.Map;
5+
6+
/**
7+
* Java program for LFU Cache (https://en.wikipedia.org/wiki/Least_frequently_used)
8+
* @author Akshay Dubey (https://github.com/itsAkshayDubey)
9+
*/
10+
public class LFUCache<K,V> {
11+
12+
private class Node {
13+
private K key;
14+
private V value;
15+
private int frequency;
16+
private Node previous;
17+
private Node next;
18+
19+
public Node(K key, V value, int frequency) {
20+
this.key = key;
21+
this.value = value;
22+
this.frequency = frequency;
23+
}
24+
}
25+
26+
private Node head;
27+
private Node tail;
28+
private Map<K,Node> map = null;
29+
private Integer capacity;
30+
private static final int DEFAULT_CAPACITY = 100;
31+
32+
public LFUCache() {
33+
this.capacity = DEFAULT_CAPACITY;
34+
}
35+
36+
public LFUCache(Integer capacity) {
37+
this.capacity = capacity;
38+
this.map = new HashMap<>();
39+
}
40+
41+
/**
42+
* This method returns value present in the cache corresponding to the key passed as parameter
43+
*
44+
* @param <K> key for which value is to be retrieved
45+
* @returns <V> object corresponding to the key passed as parameter, returns null if <K> key is not present in the cache
46+
*/
47+
public V get(K key) {
48+
if(this.map.get(key) == null) {
49+
return null;
50+
}
51+
52+
Node node = map.get(key);
53+
removeNode(node);
54+
node.frequency += 1;
55+
addNodeWithUpdatedFrequency(node);
56+
57+
return node.value;
58+
}
59+
60+
/**
61+
* This method stores <K> key and <V> value in the cache
62+
*
63+
* @param <K> key which is to be stored in the cache
64+
* @param <V> value which is to be stored in the cache
65+
*/
66+
public void put(K key, V value) {
67+
if(map.containsKey(key)) {
68+
Node node = map.get(key);
69+
node.value = value;
70+
node.frequency += 1;
71+
removeNode(node);
72+
addNodeWithUpdatedFrequency(node);
73+
}
74+
else {
75+
if(map.size() >= capacity) {
76+
map.remove(this.head.key);
77+
removeNode(head);
78+
}
79+
Node node = new Node(key,value,1);
80+
addNodeWithUpdatedFrequency(node);
81+
map.put(key, node);
82+
}
83+
}
84+
85+
/**
86+
* This method stores the node in the cache with updated frequency
87+
*
88+
* @param Node node which is to be updated in the cache
89+
*/
90+
private void addNodeWithUpdatedFrequency(Node node) {
91+
if(tail != null && head != null) {
92+
Node temp = this.head;
93+
while(temp != null) {
94+
if(temp.frequency > node.frequency) {
95+
if(temp==head) {
96+
node.next = temp;
97+
temp.previous = node;
98+
this.head = node;
99+
break;
100+
}
101+
else {
102+
node.next = temp;
103+
node.previous = temp.previous;
104+
temp.previous.next = node;
105+
node.previous = temp.previous;
106+
break;
107+
}
108+
}
109+
else {
110+
temp = temp.next;
111+
if(temp == null) {
112+
tail.next = node;
113+
node.previous = tail;
114+
node.next = null;
115+
tail = node;
116+
break;
117+
}
118+
}
119+
}
120+
}
121+
else {
122+
tail = node;
123+
head = tail;
124+
}
125+
}
126+
127+
/**
128+
* This method removes node from the cache
129+
*
130+
* @param Node node which is to be removed in the cache
131+
*/
132+
private void removeNode(Node node) {
133+
if(node.previous != null) {
134+
node.previous.next = node.next;
135+
}
136+
else {
137+
this.head = node.next;
138+
}
139+
140+
if(node.next != null) {
141+
node.next.previous = node.previous;
142+
}
143+
else {
144+
this.tail = node.previous;
145+
}
146+
}
147+
}

‎src/main/java/com/thealgorithms/datastructures/heaps/MinHeap.java

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -50,7 +50,7 @@ private void swap(int index1, int index2) {
5050
// Toggle an element up to its right place as long as its key is lower than its parent's
5151
private void toggleUp(int elementIndex) {
5252
double key = minHeap.get(elementIndex - 1).getKey();
53-
while (getElementKey((int) Math.floor(elementIndex / 2.0)) > key) {
53+
while (getElementKey((int) Math.floor(elementIndex / 2.0) + 1) > key) {
5454
swap(elementIndex, (int) Math.floor(elementIndex / 2.0));
5555
elementIndex = (int) Math.floor(elementIndex / 2.0);
5656
}

‎src/main/java/com/thealgorithms/datastructures/lists/SkipList.java

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -117,7 +117,9 @@ public void remove(E e) {
117117
}
118118
for (int i = 0; i <= layer; i++) {
119119
current.previous(i).setNext(i, current.next(i));
120-
current.next(i).setPrevious(i, current.previous(i));
120+
if (current.next(i) != null) {
121+
current.next(i).setPrevious(i, current.previous(i));
122+
}
121123
}
122124
size--;
123125
}

‎src/main/java/com/thealgorithms/sorts/QuickSort.java

Lines changed: 0 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -76,23 +76,4 @@ private static <T extends Comparable<T>> int partition(T[] array, int left, int
7676
}
7777
return left;
7878
}
79-
80-
// Driver Program
81-
public static void main(String[] args) {
82-
83-
// For integer input
84-
Integer[] array = {3, 4, 1, 32, 0, 1, 5, 12, 2, 5, 7, 8, 9, 2, 44, 111, 5};
85-
86-
QuickSort quickSort = new QuickSort();
87-
quickSort.sort(array);
88-
89-
// Output => 0 1 1 2 2 3 4 5 5 5 7 8 9 12 32 44 111
90-
print(array);
91-
92-
String[] stringArray = {"c", "a", "e", "b", "d"};
93-
quickSort.sort(stringArray);
94-
95-
// Output => a b c d e
96-
print(stringArray);
97-
}
9879
}

‎src/main/java/com/thealgorithms/strings/HammingDistance.java

Lines changed: 32 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,32 @@
1+
package com.thealgorithms.strings;
2+
3+
/* In information theory, the Hamming distance between two strings of equal length
4+
is the number of positions at which the corresponding symbols are different.
5+
https://en.wikipedia.org/wiki/Hamming_distance
6+
*/
7+
public class HammingDistance {
8+
9+
/**
10+
* calculate the hamming distance between two strings of equal length
11+
*
12+
* @param s1 the first string
13+
* @param s2 the second string
14+
* @return {@code int} hamming distance
15+
* @throws Exception
16+
*/
17+
public static int calculateHammingDistance(String s1, String s2) throws Exception {
18+
if (s1.length() != s2.length()) {
19+
throw new Exception("String lengths must be equal");
20+
}
21+
22+
int stringLength = s1.length();
23+
int counter = 0;
24+
25+
for (int i = 0; i < stringLength; i++) {
26+
if (s1.charAt(i) != s2.charAt(i)) {
27+
counter++;
28+
}
29+
}
30+
return counter;
31+
}
32+
}

‎src/test/java/com/thealgorithms/datastructures/caches/LFUCacheTest.java

Lines changed: 67 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,67 @@
1+
package com.thealgorithms.datastructures.caches;
2+
3+
import static org.junit.jupiter.api.Assertions.assertEquals;
4+
5+
import org.junit.jupiter.api.Test;
6+
7+
class LFUCacheTest {
8+
9+
@Test
10+
void testLFUCacheWithIntegerValueShouldPass() {
11+
12+
LFUCache<Integer, Integer> lfuCache = new LFUCache<>(5);
13+
lfuCache.put(1, 10);
14+
lfuCache.put(2, 20);
15+
lfuCache.put(3, 30);
16+
lfuCache.put(4, 40);
17+
lfuCache.put(5, 50);
18+
19+
//get method call will increase frequency of key 1 by 1
20+
assertEquals(10, lfuCache.get(1));
21+
22+
//this operation will remove value with key as 2
23+
lfuCache.put(6, 60);
24+
25+
//will return null as value with key 2 is now evicted
26+
assertEquals(null, lfuCache.get(2));
27+
28+
//should return 60
29+
assertEquals(60, lfuCache.get(6));
30+
31+
//this operation will remove value with key as 3
32+
lfuCache.put(7, 70);
33+
34+
assertEquals(null, lfuCache.get(2));
35+
assertEquals(70, lfuCache.get(7));
36+
}
37+
38+
@Test
39+
void testLFUCacheWithStringValueShouldPass() {
40+
41+
LFUCache<Integer, String> lfuCache = new LFUCache<>(5);
42+
lfuCache.put(1, "Alpha");
43+
lfuCache.put(2, "Beta");
44+
lfuCache.put(3, "Gamma");
45+
lfuCache.put(4, "Delta");
46+
lfuCache.put(5, "Eplison");
47+
48+
//get method call will increase frequency of key 1 by 1
49+
assertEquals("Alpha", lfuCache.get(1));
50+
51+
//this operation will remove value with key as 2
52+
lfuCache.put(6, "Digamma");
53+
54+
//will return null as value with key 2 is now evicted
55+
assertEquals(null, lfuCache.get(2));
56+
57+
//should return string Digamma
58+
assertEquals("Digamma", lfuCache.get(6));
59+
60+
//this operation will remove value with key as 3
61+
lfuCache.put(7, "Zeta");
62+
63+
assertEquals(null, lfuCache.get(2));
64+
assertEquals("Zeta", lfuCache.get(7));
65+
}
66+
67+
}

‎src/test/java/com/thealgorithms/datastructures/lists/SkipListTest.java

Lines changed: 16 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -42,12 +42,26 @@ void contains() {
4242
}
4343

4444
@Test
45-
void remove() {
45+
void removeFromHead() {
4646
SkipList<String> skipList = createSkipList();
47+
String mostLeftElement = skipList.get(0);
4748
int initialSize = skipList.size();
4849
print(skipList);
4950

50-
skipList.remove("a");
51+
skipList.remove(mostLeftElement);
52+
53+
print(skipList);
54+
assertEquals(initialSize - 1, skipList.size());
55+
}
56+
57+
@Test
58+
void removeFromTail() {
59+
SkipList<String> skipList = createSkipList();
60+
String mostRightValue = skipList.get(skipList.size() - 1);
61+
int initialSize = skipList.size();
62+
print(skipList);
63+
64+
skipList.remove(mostRightValue);
5165

5266
print(skipList);
5367
assertEquals(initialSize - 1, skipList.size());

‎src/test/java/com/thealgorithms/others/PasswordGenTest.java

Lines changed: 37 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,37 @@
1+
package com.thealgorithms.others;
2+
3+
import org.junit.jupiter.api.Test;
4+
5+
import static org.junit.jupiter.api.Assertions.*;
6+
7+
8+
public class PasswordGenTest {
9+
@Test
10+
public void failGenerationWithSameMinMaxLengthTest() {
11+
int length = 10;
12+
assertThrows(IllegalArgumentException.class, ()-> {
13+
PasswordGen.generatePassword(length, length);
14+
});
15+
}
16+
17+
@Test
18+
public void generateOneCharacterPassword() {
19+
String tempPassword = PasswordGen.generatePassword(1, 2);
20+
assertTrue(tempPassword.length()==1);
21+
}
22+
23+
@Test
24+
public void failGenerationWithMinLengthSmallerThanMaxLengthTest() {
25+
int minLength = 10;
26+
int maxLength = 5;
27+
assertThrows(IllegalArgumentException.class, ()-> {
28+
PasswordGen.generatePassword(minLength, maxLength);
29+
});
30+
}
31+
32+
@Test
33+
public void generatePasswordNonEmptyTest() {
34+
String tempPassword = PasswordGen.generatePassword(8, 16);
35+
assertTrue(tempPassword.length()!=0);
36+
}
37+
}

0 commit comments

Comments
 (0)