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!

435 comments:

«Oldest   ‹Older   401 – 435 of 435
Diksha Gupta said...

I like your post. I appreciate your blogs because they are really good. Please go to this website for Data Science course in Bangalore. These courses are wonderful for professionals.

Anjali geetha said...

I have read your excellent post. This is a great job. I have enjoyed reading your post first time. I want to say thanks for this post. Thank you... data science course in Faridabad

sivakumar said...

Thank you so much for ding the impressive job here, everyone will surely like your post. data science course in Indore

diploma in digital marketing malaysia said...

Through this post, I realize that your great information in playing with all the pieces was exceptionally useful. I advise this is the primary spot where I discover issues I've been scanning for. You have a smart yet alluring method of composing.diploma in digital marketing malaysia

datascience course said...

I really loved reading your blog. It was very well authored and easy to understand. Unlike other blogs I have read which are really not that good.Thanks alot! data science course in Kolkata

360digiTMG.com said...

The web site is lovingly serviced and saved as much as date. So it should be, thanks for sharing this with us. data scientist course in mysore

deekshitha said...

When one thinks about data science, there might be word machine learning comes into the mind. Nowadays, machine learning has gained much more importance in data science, and data scientists have witnessed machine learning as a valuable tool in the various data analysis processes. Our Data Science certification training with a unique curriculum and methodology helps you to get placed in top-notch companies. Avail all the benefits and become a champion. Data Science is a dynamic domain with a promising future, start your Data Science Course today with 360DigiTMG and become a Data Scientist without hassle. Data science comprises of various necessary processes. One of the essential things on which data science is centered is the programming languages. With the broad discussion on the differences of both languages, you can indeed note which is easy to learn.business analytics course in nashik

Suresh said...

Advance your technical skills required to crack huge datasets to bring out new possibilities from data. Join the Data Science institutes in Bangalore and get access to top industry trainers, LMS, live projects, assignments, and mock interviews to skyrocket your career in the ever- evolving field of Data Science.
Data Scientist Course in Bangalore

deekshitha said...

Data Science is a dynamic domain with a promising future, start your Data Science Course today with 360DigiTMG and become a Data Scientist without hassle.business analytics course in nashik

Professional Course said...

Embark on a journey to achieve your professional goals by enrolling in the Data Scientist course in Bangalore. Learn the skills of collecting, extracting, analyzing, preparing, visualizing, and presenting results to make valuable decisions. Master the concepts of data science through hands-on projects and case studies to learn the latest trends and skills in this field.

Best Data Science Institute in Bangalore

technologyforall said...

Best Online Data Science Course training with job assistance and internship opportunities .At ‘Technology For All’, we believe in sharing knowledge. Our focus is not just on teaching but involving you in each aspect of learning. With us, you get an opportunity to innovate on projects, work on case studies, gain quality industry knowledge, professional perspective and become job-ready.

Data Scientist said...

Great post i must say and thanks for the information. Education is definitely a sticky subject. However, is still among the leading topics of our time. I appreciate your post and look forward to more. data science classes in pune

Professional Course said...

Learn the fundamentals of Data Science and master the skills to handle epic amounts of data collected by organizations today. Gain expertise in organizing, analyzing, and transforming data to uncover its hidden power. Drive your career forward with a Data Science course in Bangalore and learn to uncover insights to present critical findings using visualization tools. Not only this, avail the best-in-class content delivered by stellar faculty who use a blended approach of theory as well as practical knowledge to ensure all the concepts are crystal clear.

Best Data Science Institute in Bangalore

Anjali geetha said...

Due to data science, it has become possible to collect the massive data of the refugees and arrange it so that it is used to make decisions that are fruitful in the time of crises.data science course in trichy

Anjali geetha said...

The skilled data scientists who are working in the field are very few. But the companies are adopting data science tools to make their business more profitable and intelligent.data science training in trichy

Suresh said...

Get dual certification from IBM and UTM, Malaysia with a single Data Science Course at 360DigiTMG. Enroll now for a successful tomorrow!
Data Science Training in Bangalore

Balaji said...

Companies are increasingly turning to data for decision-making and are depending on data professionals to do so. Develop strong logical and numerical aptitude and learn to work with R, Python, SQL, Hadoop, and statistical techniques like Linear Regression, Logistic Regression, etc. Sign up for the Data Scientist training in Bangalore, and gain expertise in using sophisticated analytical methods and statistical methods to prepare data for predictive and prescriptive modeling.
Business Analytics Course in Jaipur

business analytics course in gorakhpur said...

Fast forward your career with the best Data Analyst Course offered by 360DigiTMG.Gettrained by expert trainers with placement assistance.
<a href="https://360digitmg.com/india/business-analytics-course-in-gorakhpur''>business analytics course in gorakhpur</a>

Rajesh said...

Acquire a firm grounding in the theory of Data Science by signing up for the Data Science courses in Bangalore. Master the relevant skills along with all the essential tools and techniques of Data Science. Get to avail benefits like Flexible timings, Best industry trainers, and a meticulously crafted curriculum with hands-on projects that will give you exposure to a real-world working environment.
Best Data Science Training in Bangalore

deekshitha said...

Many programming languages are used in data science; the most critical are R and Python. These are open source and free languages, but you must be thinking about which one of these languages is easier to learn.data science course in varanasi

digital marketing course said...

Truly, this article is really one of the very best in the history of articles. I am a antique ’Article’ collector and I sometimes read some new articles if I find them interesting. And I found this one pretty fascinating and it should go into my collection. Very good work! digital marketing course

Tech Institute said...

Very useful article to read and Information was helpful.I would like to thank you for the efforts you had made for writing this awesome article.
Data Analytics Course

data science course in lucknow said...

People are impressed with this technology, and the experts have predicted a bright future of data science.
data science course in lucknow

data science course in patna said...

It has increases the importance of the field. If you have also been attracted by the value of data science and want to learn it, you have to understand the basic courses of data science you need to learn to move successfully in the industry.

data science course in patna

data science training in borivali said...

You have to learn all the required skills to transform raw data into a form that will improve the organization.
data science training in borivali

Project Management Course said...

I would like to thank you for the efforts you have made in writing this article. I am hoping the same best work from you in the future as well. In fact your creative writing abilities has inspired me to start my own Blog Engine blog now. Really the blogging is spreading its wings rapidly. Your write up is a fine example of it. Project Management Course

Anjali geetha said...

360DigiTMG delivers the best Data Analytics course with placements. Top industry trainers, LMS access, world-class curriculum, mock interviews, and guidance sessions for resume preparation.Data Analytics Course in Faridabad

data science course in patna said...

Without data analytics, you cannot imagine data science. In this process, data is examined to transform it into a meaningful aspect.
data science course in patna

data science training in borivali said...

You should get certification in the relevant courses if you need to be considered for recruiting data experts.
data science training in borivali

Career Program and Skill Development said...

360DigiTMG offers the best Data Science certification course in the market with placement assistance. Get trained by IIT, IIM, and ISB alumni.


Data Science Training in Jodhpur

deekshitha said...

When one thinks about data science, there might be word machine learning comes into the mind.data science course in nashik

Career Programs Excellence said...

Fast forward your career with the best Data Analyst Course offered by 360DigiTMG. Get trained by expert trainers with placement assistance.


Data Science Training in Delhi

Bhuvankumar said...
This comment has been removed by the author.
business analytics course in patna said...

360DigiTMG offers the best Data Analytics courses in the market with placement assistance. Enroll today and fast forward your career.
business analytics course in patna

Courses said...

Excellent work done by you once again here and this is just the reason why I’ve always liked your work with amazing writing skills and you display them in every article. Keep it going!
Data Analytics Courses in Hyderabad

«Oldest ‹Older   401 – 435 of 435   Newer› Newest»