## July 28, 2016

### SDET Prep: Data Structures: Arrays, Hashmaps and how to implement them in Java.

This blog post is part of a series as I research how to move from Automation Development to being a Software Developer in Test. We covered some basic algorithms, before. These next few posts will deal with data structures, illustrating them with Java.

As an automation developer, I've been focusing on browser testing with Selenium WebDriver and Java, being able to draw from my decades of experience testing web applications. When it comes to various data structures, I use arrays, lists, arraylists, and the occasional hashmap in my day-to-day work, but that is about it.

A Software Developer in Test (SDET) isn't that far removed from a Software Development Engineer (SDE), relying on data structures and algorithms I once studied as a Computer Sci major back at Bridgewater State. Note: Each link below goes to the respective Harvard University CS50 video, if any.

If you are a manual tester or automated tester and want to shift to software development, Gayle Laakmann McDowell's Cracking the Coding Interview is an excellent summation of all terms listed above. It seems to be a good resource for even Senior developers, who may be far removed from college.

When you are a Software Developer, you are always trying to find the right tool for the job. When we looked at sorting algorithms:

• insertion sort was quite fast for sorting five or less elements, but O(n ^ 2) after that.
• mergesort was very quick, O(n log n), but needed a bit of space, O(n), when creating new arrays to do the work. Want it fast, but space be damned? This algorithm might qualify.
• quicksort, which we didn't look at yet, is very quick on average, O(n log n), but at its worst can be as bad as insertion sort O(n ^ 2). The good thing it only needs O(log(n)) of space, worse case scenario, no matter how big the set of elements are that need to be sorted.

See more algorithms at the Big-O Cheatsheet, by Eric Rowell. It also has a selection of the Big-O times of Data Structures.

Let's go over how to use a few of the data structures, starting with the most basic ones:

## Arrays

Need a way to store a lot of data right next to each other in memory? Arrays are small identically-sized blocks of space. Only the same data typed can be stored in each slot in memory, such as int or char. If there are n elements, First space is 0. Last space is (n-1).

Java has a built in Array object with methods we can use to manipulate the array.

• Declare an integer array, setting the values: int[] myArray = { 1, 2, 3, 4, 5 };
• Initialize an array of size 5: int[] blankArray = new int[5];
• Find the first element: myArray[0]
• Print out the array size: System.out.println(myArray.length);
• Print the last element of the array: int indexLast = (myArray.length - 1); System.out.println(unsortedArray[indexLast]);
• Print the entire array: System.out.println(Arrays.toString(myArray));
• Sort the array: Array.sort(myArray)
• Search the array using the binary search algorithm: Array.binarySearch(myArray).

If you declared an array of five elements, it will always have five elements, never six. The space is set in stone.

You can also have multidimentional arrays, such as playing tic-tac-toe on a board that is 3 by 3. For that we would initialize a 3 x 3 grid of characters, since we would be using either an "X" or an "O":

• Declare a board: char[][] ticTacToe = new char[3][3];
• The top left corner would be the value: ticTacToe[0][0]
• The middle space would be the value: ticTacToe[1][1]
• The right bottom corner space would be the value: ticTacToe[3][3]
• Want to insert an "O" in the middle? ticTacToe[1][1] = 'O'; // Note the single quotes, suitable for single characters

How about setting up a 10 x 10 board of Battleship to track where your ships are: true if they are on the space, false if they are not on the space?

• Board setup: boolean[][] battleship = new boolean[10][10];

... The idea it is a 10 x 10 array is just an abstraction. It actually is just allocating 100 spaces in memory. But with this data structure we can loop along battleship[x][y] as if it was the grid we imagine.

CS50: Introduction to Arrays (using C++ sourcecode):

https://youtu.be/7mOJN1c1JEo

## HashMaps

Let's make up an example of how a HashMap can be used in Java.

Take the sentence, "The Quick Brown Fox Jumped Over The Lazy Dog". How many 'A's does it have? 'Q's? 'T's?

• Let's store the sentence into a String, and make sure that everything is lowercase. Oh, and trim off any whitespace.
• And for this example, let's pretend that everything is either alphanumeric (A thru Z or 0 thru 9) or whitespace, just to make it a bit more simple. We can use the String object method "toLowerCase()" and "trim()".

Think of a String as a collection of characters. We can convert the String into one long character array by using the method "toCharacterArray()". Then, we can use a foreach loop to go through each character.

... But where would we store the totals of each character? We could easily set up an array of 26, one for each letter in the English language, but there might be space not used. This would be pretty inefficient.

Let's create a Hashmap called "letters". As we go letter by letter through the String sentence (as a character array) we can:

• Declare the Hashmap to be of type <Character, Integer>.
• Loop through the entire sentence, character by character.
Check the letters hashmap. Does it countain a 'q'?

• If so, let's get whatever the count is up to, increment it by 1, then store it in an integer called "newValue".
• Let's then put that newValue back in the hashmap, using the character by the key.

What? No 'q' in the hashmap?

• Let's put in the letters hashmap the value of "1" in that character key.

Here's what I just came up with as a solution:

```@Test
public void test_HashMap(){
String sentence = "The Quick Brown Fox Jumped Over the Lazy Dog"
.toLowerCase().trim();
HashMap<Character, Integer> letters = new HashMap<Character, Integer>();
for (char character : sentence.toCharArray()){
if (letters.containsKey(character)){
int newValue = letters.get(character) + 1;
letters.put(character, newValue);
} else if (character != ' '){
letters.put(character, 1);
}
}
System.out.println(letters);
}
```

If we run the test, we get:
`````` {a=1, b=1, c=1, d=2, e=4, f=1, g=1, h=2, i=1, j=1, k=1, l=1, m=1, n=1, o=4, p=1, q=1, r=2, t=2, u=2, v=1, w=1, x=1, y=1, z=1}
``````

That is all we have for now when it comes to Software Development. Happy Testing!

-T.J. Maher
Sr. QA Engineer,
Fitbit-Boston

// BSCS, MSE, and QA Engineer since Aug. 1996
// Automation developer for [ 1.5 ] years and still counting!

Aruna Ram said...

Wonderful ideas! You are providing the different kinds of content is very useful for me and I gain more details from your article. I am always following your blog and keep posting...
Spark Training in Chennai
Spark Training
Excel Training in Chennai
Corporate Training in Chennai
Embedded System Course Chennai
Linux Training in Chennai
Tableau Training in Chennai
Power BI Training in Chennai
Social Media Marketing Courses in Chennai

seoexpert said...

Nice Post...I have learn some new information.thanks for sharing.
ExcelR data analytics course in Pune | business analytics course | data scientist course in Pune

seoexpert said...

Such a very useful article. I have learn some new information.thanks for sharing.
data scientist course in mumbai

ek said...

You might comment on the order system of the blog. You should chat it's splendid. Your blog audit would swell up your visitors. I was very pleased to find this site.I wanted to thank you for this great read!!
Know more data science course in pune with placements

ExcelR Pune said...

Very nice blog here and thanks for post it.. Keep blogging...
ExcelR data science training

Laura Bush said...

Thanks for sharing this video here about the Data Structures and Algorithms Best Video Tutorials. This video is very informative and I will share it with my other friends as the information is really very useful. Keep sharing your excellent work.

Priyanka said...

Attend The Data Analytics Course in Bangalore with Placement From ExcelR. Practical Data Analytics Course in Bangalore with Placement Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Data Analytics Course in Bangalore with Placement.
ExcelR Data Analytics Course in Bangalore with Placement

ravali said...

I have to search sites with relevant information on a given topic and provide them to teacher our opinion and the article.
ExcelR data science course in mumbai

Excelrsolutions said...

Nice information, valuable and excellent work, as share good stuff with good ideas and concepts, lots of great information and inspiration, both of which I need, thanks to offer such a helpful information here. data science course

ravali said...

I have to search sites with relevant information on given topic and provide them to teacher our opinion and the article.
data analytics courses

sindhuvarun said...

Excellent information with unique content and it is very useful to know about the information based on blogs..
AWS Training in Chennai
AWS Training in Bangalore
AWS Training in Coimbatore
PHP Training in Bangalore
Spoken English Classes in Bangalore
AWS Training in btm
Best AWS Training Institutes in Hyderabad
AWS Training in Marathahalli

Sanfrans said...

Interesting post. I Have Been wondering about this issue, so thanks for posting. Pretty cool post.It 's really very nice and Useful post.I am interested in some of them.I hope you will give more information on this topics in your next articles.
Data Science training
data analytics course

Priyanka said...

Attend The Project Management Courses From ExcelR. Practical Project Management Courses Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Project Management Courses.
ExcelR Project Management Courses

Prawalika said...

good article about data science has given it is very nice thank you for sharing.

Data Science Training institute in Hyderabad

Komal said...