Two ways of searching value within an array

The following code demonstrates two ways or methods to know whether a value exists or not within an array :

import java.util.Arrays;

public class SearchingAValueWithinAnArray {
static boolean exists1(int[] ints, int k) {
Arrays.parallelSort(ints);
return Arrays.binarySearch(ints, k) >= 0;
}

static boolean exists2(int[] ints, int k) {
return Arrays.stream(ints).parallel().filter(element -> element == k).findFirst().isPresent();
}

public static void main(String[] args) {
int[] ints = { -9, 14, 37, 102 };
System.out.println(SearchingAValueWithinAnArray.exists1(ints, 102)); // true
System.out.println(SearchingAValueWithinAnArray.exists2(ints, 36)); // false
}
}

Binary Search Tree

A Binary Search Tree (BST) is a tree in which all the nodes follow the below-mentioned properties −

• The left sub-tree of a node has a key less than or equal to its parent node's key.
• The right sub-tree of a node has a key greater than to its parent node's key.

Thus, BST divides all its sub-trees into two segments; the left sub-tree and the right sub-tree and can be defined as −

left_subtree (keys)  ≤  node (key)  ≤  right_subtree (keys)

Representation

BST is a collection of nodes arranged in a way where they maintain BST properties. Each node has a key and an associated value. While searching, the desired key is compared to the keys in BST and if found, the associated value is retrieved.

Following is a pictorial representation of BST −

We observe that the root node key (27) has all less-valued keys on the left sub-tree and the higher valued keys on the right sub-tree.

Copied from here.

My Solution:

public class Node {

Node left, right;

int value;

public Node(int value) {

this.value = value;

}

public Node add(int value) {

if (value < this.value)

if (this.left != null)

return this.left.add(value);

else

return this.left = new Node(value);

if (value > this.value)

if (this.right != null)

return this.right.add(value);

else

return this.right = new Node(value);

return this;

}

public Node find(int v) {

if (this == null || v == value)

return this;

else if (value > v && this.left != null)

return left.find(v);

else if (value < v && this.right != null)

return right.find(v);

else

return null;

}

public int findSmallestValue() {

return this.left == null ? this.value : this.left.findSmallestValue();

}

public void traverseInOrder() {

if (this.left != null)

this.left.traverseInOrder();

System.out.print(" " + this.value);

if (this.right != null)

this.right.traverseInOrder();

}

public void traversePreOrder() {

System.out.print(" " + this.value);

if (this.left != null)

this.left.traversePreOrder();

if (this.right != null)

this.right.traversePreOrder();

}

public void traversePostOrder() {

if (this.left != null)

this.left.traversePostOrder();

if (this.right != null)

this.right.traversePostOrder();

System.out.print(" " + this.value);

}

}

Kariakoo Algorithm

Kariakoo dance asks every performer to follow a precise sequence of steps:

• Stage 0 : First, get away from obstacles by setting up your starting point at position 0

• Stage 1 : Take one step forward (+1 step)

• Stage 2 : Take two steps backward (-2 steps)

• To follow, the steps as well as the direction you will have to take in your next move will each time be obtained thanks to a specific calculation: the number of steps you took on the previous stage minus the number of steps you took on the penultimate stage.

That is, on stage 3, a dancer will have to take 3 steps backwards (-2 - 1).

At stage 3, the dancer is at position -4.

stage(n) = stage(n-1) - stage(n-2)

pos(n) = pos(n-1) + stage(n)

At stage 4, the dancer is at position -5.

Solution:

public class Kariakoo {

static final int NUMBER_OF_POSSIBLE_POSITIONS = 6;

final static int[] POSSIBLE_POSITIONS = { 0, 1, -1, -4, -5, -3 };

/**

* Computes the position of the Kariakoo​​​​​​​‌​‌‌​​​​​​‌​​‌‌​‌​​‌‌‌​‌

* dancer.

*/

static int getPositionAt(int n) {

return POSSIBLE_POSITIONS[n % NUMBER_OF_POSSIBLE_POSITIONS];

}

public static void main(String[] args) {

System.out.println(Kariakoo.getPositionAt(3)); // -4

System.out.println(Kariakoo.getPositionAt(100000)); // -5

System.out.println(Kariakoo.getPositionAt(2147483647)); // 1

}

}

Ma solution pour le problème de magasins

Enoncé :

Des magasins produisent tous les jours des fichiers de logs contenant les informations relatives à leur activité de vente journalière. De plus, chaque magasin possède son propre référentiel de prix journalier. Le fichier des transactions journalières contient ces infos:

 txId|datetime|magasin|produit|qte

Exemple:
1|20150302T223544+0100|2a4b6b81-5aa2-4ad8-8ba9-ae1a006e7d71|531|5
1|20150302T224008+0100|bdc2a431-797d-4b07-9567-67c565a67b84|55|3
1|20150302T224214+0100|72a2876c-bc8b-4f35-8882-8d661fac2606|39|8
2|20150302T225357+0100|29366c83-eae9-42d3-a8af-f15339830dc5|10|6
2|20150302T230721+0100|8e588f2f-d19e-436c-952f-1cdd9f0b12b0|773|2
2|20150302T231647+0100|bdc2a431-797d-4b07-9567-67c565a67b84|759|1
3|20150302T232938+0100|bf0999da-ae45-49df-983e-89020198330b|789|6
3|20150302T234000+0100|6af0502b-ce7a-4a6f-b5d3-516d09514095|520|5
3|20150302T234640+0100|29366c83-eae9-42d3-a8af-f15339830dc5|733|3
3|20150302T235351+0100|dd43720c-be43-41b6-bc4a-ac4beabd0d9b|985|9
3|20150303T000050+0100|bf0999da-ae45-49df-983e-89020198330b|307|1
3|20150303T001547+0100|6af0502b-ce7a-4a6f-b5d3-516d09514095|563|7
4|20150303T001635+0100|af068240-8198-4b79-9cf9-c28c0db65f63|733|8
4|20150303T001723+0100|72a2876c-bc8b-4f35-8882-8d661fac2606|54|1
4|20150303T001944+0100|af068240-8198-4b79-9cf9-c28c0db65f63|3|3
4|20150303T002931+0100|bdc2a431-797d-4b07-9567-67c565a67b84|124|8
4|20150303T003551+0100|6af0502b-ce7a-4a6f-b5d3-516d09514095|562|1
5|20150303T004132+0100|8e588f2f-d19e-436c-952f-1cdd9f0b12b0|266|3
6|20150303T005731+0100|2a4b6b81-5aa2-4ad8-8ba9-ae1a006e7d71|617|0
6|20150303T010831+0100|29366c83-eae9-42d3-a8af-f15339830dc5|617|3

où :
txId : id de transaction (nombre)
datetime : date et heure au format ISO 8601
magasin : UUID identifiant le magasin
produit : id du produit (nombre)
qte : quantité (nombre) prix : prix du produit en euros

Et celui du référentiel produit:
 produit|prix

Exemple:
1|63.19
2|23.86
3|12.19
4|9.54
5|23.76
6|14.46
7|32.94
8|96.28
9|8.53
10|77.43
11|17.64
12|34.52
13|59.87
14|62.25
15|92.13
16|42.4
17|52.54
18|89.37
19|80.54

20|19.41

Besoin : Déterminer, pour chaque heure, les 100 produits qui ont les meilleures ventes et ceux qui génèrent le plus gros Chiffre d'Affaire par magasin.

Télécharger la solution