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!
// Check out Adventures in Automation and Like us on Facebook!

41 comments:

priyanka said...

I am impressed by the information that you have on this blog. It shows how well you understand this subject.
data science courses

Abhinavhyd said...

With so many books and articles coming up to give gateway to make-money-online field and confusing reader even more on the actual way of earning money,
360Digitmg data analytics course in hyderabad

priyash said...

wonderful article. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article resolved my all queries.
Data science Interview Questions

Priyanka said...

Attend The Business Analytics Course From ExcelR. Practical Business Analytics Course Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Data Analytics Course.
Business Analytics Course
Data Science Interview Questions

renuka said...

Excellent Blog! I would like to thank for the efforts you have made in writing this post. I am hoping the same best work from you in the future as well. I wanted to thank you for this websites! Thanks for sharing. Great websites!
360Digitmg best financial -Analytics course- in-Hyderabad

ravali said...

Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!

data science course

DataScience Datascience said...

I have to search sites with relevant information ,This is a
wonderful blog,These type of blog keeps the users interest in
the website, i am impressed. thank you.
machine learning course in hyderabad

Priyanka said...

Attend The Bangalore Digital Marketing Course From ExcelR. Practical Bangalore Digital Marketing Course Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Bangalore Digital Marketing Course.
Bangalore Digital Marketing Course

dataexpert said...

Very nice job... Thanks for sharing this amazing and educative blog post! ExcelR Data Scientist Course In Pune

priyash said...

Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article inspried me to read more. keep it up.
Correlation vs Covariance

ravali said...

Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!

Simple Linear Regression

Correlation vs Covariance

ek said...

I will really appreciate the writer's choice for choosing this excellent article appropriate to my matter.Here is deep description about the article matter which helped me more.
PMP Certification
You completely match our expectation and the variety of our information.

Data Science Institute In Banglore said...

I am impressed by the information that you have on this blog. It shows how well you understand this subject.
Data Science Institute in Bangalore

Data Science pune said...

Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!
Data Science Course in Pune
Data Science Training in Pune

Programs said...

Nice blog. I finally found great post here Very interesting to read this article and very pleased to find this site. Great work!
Data Science Training in Pune
Data Science Course in Pune

DataScience Datascience said...

Awesome blog. I enjoyed reading your articles. This is truly a great read for me. I have bookmarked it and I am looking forward to reading new articles. Keep up the good work!
Data Science Course in Bangalore

DataScience Datascience said...

After reading your article I was amazed. I know that you explain it very well. And I hope that other readers will also experience how I feel after reading your article.
Data Science Training in Bangalore

ek said...

I will really appreciate the writer's choice for choosing this excellent article appropriate to my matter.Here is deep description about the article matter which helped me more.
PMP Certification
You completely match our expectation and the variety of our information.

Data Analytics Pune said...

I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it.
Data Analytics Course in Pune
Data Analytics Training in Pune

Business Analytics Course said...

I am impressed by the information that you have on this blog. It shows how well you understand this subject.
Business Analytics Course in Pune
Business Analytics Training in Pune

albina N muro said...

thanks for the tips and information..i really appreciate it.. buy cheap instagram likes spread

ek said...

I have express a few of the articles on your website now, and I really like your style of blogging. I added it to my favorite’s blog site list and will be checking back soon…
Data Scientist Courses Super site! I am Loving it!! Will return once more, Im taking your food likewise, Thanks.

Data Science Training in Hyderabad said...

I feel really happy to have seen your web page and look forward to so many more entertaining times reading here. Thanks once more for all the details.
Data Science Training in Hyderabad | Data Science Course in Hyderabad

Business Analytics Training in Hyderabad said...

You are in point of fact a just right webmaster. The website loading speed is amazing. It kind of feels that you're doing any distinctive trick. Moreover, The contents are masterpiece. you have done a fantastic activity on this subject!
Business Analytics Training in Hyderabad
Business Analytics Course in Hyderabad

Saketh said...

Such a very useful article. Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article.ExcelR's PMP Certification

TECHNOLOGY said...

Nice Post. Very informative Message and found a great post. Thank you.
Business Analytics Course in Pune
Business Analytics Training in Pune

priyash said...

Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
Correlation vs Covariance
Simple linear regression
data science interview questions

EXCELR said...

Great post i must say and thanks for the information.
Data Science Course in Hyderabad

Priyanka said...

Attend The Data Analyst Course From ExcelR. Practical Data Analyst Course Sessions With Assured Placement Support From Experienced Faculty. ExcelR Offers The Data Analyst Course.
Data Analyst Course

dataexpert said...

I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. ExcelR Data Scientist Classes In Pune Any way I’ll be subscribing to your feed and I hope you post again soon. Big thanks for the useful info.

priyanka said...

Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
Correlation vs Covariance
Simple linear regression
data science interview questions

DataScience Datascience said...

I was just browsing through the internet looking for some information and came across your blog. I am impressed by the information that you have on this blog. It shows how well you understand this subject. Bookmarked this page, will come back for more.
Data Science Course in Bangalore

DataScience Datascience said...

Pretty good post. I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. Any way I’ll be subscribing to your feed and I hope you post again soon.
Data Science Training in Bangalore

priyash said...

Very interesting to read this article.I would like to thank you for the efforts you had made for writing this awesome article. This article inspired me to read more. keep it up.
Correlation vs Covariance
Simple linear regression
data science interview questions

ek said...

Data Analytics course Pune
I like viewing web sites which comprehend the price of delivering the excellent useful resource free of charge. I truly adored reading your posting. Thank you!
Cool stuff you have, and you keep overhaul every one of us.

ek said...

I will really appreciate the writer's choice for choosing this excellent article appropriate to my matter.Here is deep description about the article matter which helped me more.
PMP Certification Pune
Thank you so much for ding the impressive job here, everyone will surely like your post.

Data Science Hyderabad said...

I feel very grateful that I read this. It is very helpful and very informative and I really learned a lot from it.
Data Science Course in Hyderabad

Data Science Training said...

Really nice and interesting post. I was looking for this kind of information and enjoyed reading this one. Keep posting. Thanks for sharing.
Data Science Training in Hyderabad

sai said...


Really nice and interesting post. I was looking for this kind of information and enjoyed reading this one. Keep posting. Thanks for sharing.
digital marketing course in guduvanchery

saketh321 said...

I just stumbled upon your blog and wanted to say that I have really enjoyed reading your blog posts. ExcelR Data Analytics Course In Pune Any way I’ll be subscribing to your feed and I hope you post again soon. Big thanks for the use

Anirban Ghosh said...

The content that I normally go through in the recent times is nothing like what you have on paper. Thank you for writing this!
SAP training in Kolkata
SAP training Kolkata
Best SAP training in Kolkata
SAP course in Kolkata