Remove duplicates from sorted array – Java implementation

Жовтень 14th, 2011 admin Прокоментувати

Task: given sorted array, remove all duplicates from it, but you can’t create another one.
Solution:

package ua.org.bytes.algorithm;
 
public class RemoveDuplicatesInSortedArray {
	public static int removeDuplicates(int[] array) {
		int size = array.length;
		int leftIndex = 0;
		int rightIndex = 1;
		while (rightIndex < size) {
			if (array[leftIndex] != array[rightIndex++]) {
				array[++leftIndex] = array[rightIndex];
			} else {
				continue;
			}
		}
		int result = leftIndex++;
		for (; leftIndex < size; ++leftIndex) {
			array[leftIndex] = 0;
		}
		printArray(array);
		return result;
	}
 
	private static void printArray(int[] array) {
		StringBuffer result = new StringBuffer();
		result.append("[");
		for (int i : array) {
			result.append(i + " ");
		}
		result.append("]");
		System.out.println(result);
	}
 
	public static void main(String[] args) {
		System.out.println(removeDuplicates(new int[] { 1, 2, 2, 2, 4 }));
		System.out.println(removeDuplicates(new int[] { 1, 1, 2, 2, 2, 4, 4, 5,
				6, 7, 8, 9, 9, 9 }));
	}
}
  • Share/Bookmark
Categories: Java Tags: ,

Check if two string are anagrams – Java implementation

Жовтень 14th, 2011 admin Прокоментувати

Hi, in this post I will show code which tells if two strings are anagrams. As usual, information from Wikipedia:

An anagram is a type of word play, the result of rearranging the letters of a word or phrase to produce a new word or phrase, using all the original letters exactly once; e.g., orchestra = carthorse, A decimal point = I’m a dot in place. Someone who creates anagrams is called an anagrammatist. The original word or phrase is known as the subject of the anagram.

Any word or phrase that exactly reproduces the letters in another order is an anagram. However, the goal of serious or skilled anagrammatists is to produce anagrams that in some way reflect or comment on the subject. Such an anagram may be a synonym or antonym of its subject, a parody, a criticism, or praise; e.g. George Bush = He bugs Gore; Madonna Louise Ciccone = Occasional nude income or One cool dance musician; William Shakespeare = I am a weakish speller, Roger Meddows-Taylor = Great words or melody.

In this implementation I use Map to hold repetitions of every character in string. Also, I do String iteration considering that String object can hold Unicode data. Also, this implementation is better that implementation when program calculates histogram for both objects and then compare because this implementation could tell if strings are not anagrams inside second loop and in doesn’t require third loop to compare histograms. The only warning: it uses a lot of boxing-unboxing from/to Integer object.

package ua.org.bytes.algorithm;
 
import java.util.HashMap;
import java.util.Map;
 
public class IsAnagram {
 
	public static boolean isAnagrams(String str1, String str2) {
		if (str1 == null || str2 == null || str1.length() != str2.length())
			return false;
		Map<Integer, Integer> histogram = new HashMap<Integer, Integer>();
		int offset = 0;
		int length = str1.length();
		while (offset < length) {
			Integer key = str1.codePointAt(offset);
			offset += Character.charCount(key);
			Integer cnt = histogram.get(key);
			if (cnt == null)
				cnt = 1;
			else
				cnt = cnt.intValue() + 1;
			histogram.put(key, cnt);
		}
		offset = 0;
		while (offset < length) {
			Integer key = str2.codePointAt(offset);
			offset += Character.charCount(key);
			Integer cnt = histogram.get(key);
			if (cnt == null)//Such character not present in string 1
				return false;
			else
				cnt = cnt.intValue() - 1;
			if (cnt.intValue()<0) //Current character occurred in second string more often
				return false;
			histogram.put(key, cnt);
		}
		return true;
	}
	public static void main(String ...strings){
		System.out.println(IsAnagram.isAnagrams("abc","abc"));
		System.out.println(IsAnagram.isAnagrams("abc","cba"));
		System.out.println(IsAnagram.isAnagrams("abc","cbad"));
		System.out.println(IsAnagram.isAnagrams("abcd","cba"));
		System.out.println(IsAnagram.isAnagrams("abcd","cbaa"));
		System.out.println(IsAnagram.isAnagrams("abca","cbaa"));
	}
}
  • Share/Bookmark
Categories: Java Tags: ,

Heap-organized priority queue – Java Implementation

Жовтень 12th, 2011 admin Прокоментувати

A priority queue is an abstract data type in computer programming.

It is exactly like a regular queue or stack data structure, but additionally, each element is associated with a “priority”.

stack: elements are pulled in last-in first-out-order (e.g. a stack of papers)
queue: elements are pulled in first-in first-out-order (e.g. a line in a cafeteria)
priority queue: elements are pulled highest-priority-first (e.g. cutting in line, or VIP service).

It is a common misconception that a priority queue is a heap. A priority queue is an abstract concept like “a list” or “a map”; just as a list can be implemented with a linked list or an array, a priority queue can be implemented with a heap or a variety of other methods.

A priority queue must at least support the following operations:

insert_with_priority: add an element to the queue with an associated priority
pull_highest_priority_element: remove the element from the queue that has the highest priority, and return it (also known as “pop_element(Off)”, “get_maximum_element”, or “get_front(most)_element”; some conventions consider lower priorities to be higher, so this may also be known as “get_minimum_element”, and is often referred to as “get-min” in the literature; the literature also sometimes implement separate “peek_at_highest_priority_element” and “delete_element” functions, which can be combined to produce “pull_highest_priority_element”)

For more information about Heap-organized priority queue please look here: Heaps

And implementation in Java (Priority determined using compareTo method because this implementation can hold only java.lang.Comparable items):

package ua.org.bytes.algorithm;
 
import java.util.LinkedList;
import java.util.List;
 
public class HeapPriorityQueue<T extends Comparable<T>> {
	private List<T> queue = new LinkedList<T>();
 
	public void enqueue(T element) {
		queue.add(element);
		swimOut(queue.size() - 1);
	}
 
	private void swimOut(int idx) {
		// Getting parent node
		int parentIdx = (int) (Math.round((double) idx / 2) - 1);
		if (parentIdx < 0)
			return;
		if (queue.get(parentIdx).compareTo(queue.get(idx)) < 0) {
			swap(parentIdx, idx);
		}
		swimOut(parentIdx);
 
	}
 
	private void swap(int parentIdx, int idx) {
		T tmp = queue.get(parentIdx);
		queue.set(parentIdx, queue.get(idx));
		queue.set(idx, tmp);
	}
 
	public T dequeue() throws Exception {
		if (queue.size() == 0)
			throw new Exception("Queue is empty");
		T result = queue.get(0);
		if (queue.size() > 1) {
			queue.set(0, queue.remove(queue.size() - 1));
			sink(0);
		} else {
			queue.remove(0);
		}
		return result;
	}
 
	private void sink(int i) {
		int leftChild = i * 2 + 1;
		int rightChild = leftChild + 1;
		int largestIdx = leftChild;
		if (leftChild >= queue.size())
			return;
		if (rightChild < queue.size()) {
			if (queue.get(rightChild).compareTo(queue.get(leftChild)) > 0) {
				largestIdx = rightChild;
			}
		}
		if (queue.get(largestIdx).compareTo(queue.get(i)) > 0) {
			swap(largestIdx, i);
			sink(largestIdx);
		}
	}
 
	public String toString() {
		StringBuilder result = new StringBuilder();
		result.append("[");
		for (T item : queue) {
			result.append(item.toString()).append(", ");
		}
		if (result.lastIndexOf(", ") != -1) {
			result.replace(result.lastIndexOf(", "),
					result.lastIndexOf(", ") + 2, "");
		}
		result.append("]");
		return result.toString();
	}
 
	public static void main(String... strings) throws Exception {
               //How to use it
		HeapPriorityQueue<Integer> queue = new HeapPriorityQueue<Integer>();
		queue.enqueue(1);
		queue.enqueue(3);
		System.out.println(queue.toString());
		queue.enqueue(2);
		System.out.println(queue.toString());
		queue.enqueue(10);
		System.out.println(queue.toString());
		queue.enqueue(6);
		System.out.println(queue.toString());
		queue.enqueue(9);
		System.out.println(queue.toString());
		queue.enqueue(11);
		queue.enqueue(12);
		queue.enqueue(13);
		queue.enqueue(4);
		queue.enqueue(5);
		queue.enqueue(7);
		System.out.println(queue.toString());
		System.out.println(queue.dequeue().toString()+" "+queue.toString());
		System.out.println(queue.dequeue().toString()+" "+queue.toString());
		System.out.println(queue.dequeue().toString()+" "+queue.toString());
		System.out.println(queue.dequeue().toString()+" "+queue.toString());
		System.out.println(queue.dequeue().toString()+" "+queue.toString());
		System.out.println(queue.dequeue().toString()+" "+queue.toString());
		System.out.println(queue.dequeue().toString()+" "+queue.toString());
		System.out.println(queue.dequeue().toString()+" "+queue.toString());
		System.out.println(queue.dequeue().toString()+" "+queue.toString());
		System.out.println(queue.dequeue().toString()+" "+queue.toString());
		System.out.println(queue.dequeue().toString()+" "+queue.toString());
		System.out.println(queue.dequeue().toString()+" "+queue.toString());
		queue.enqueue(1);
		queue.enqueue(3);
		System.out.println(queue.dequeue().toString()+" "+queue.toString());
	}
}
  • Share/Bookmark
Categories: Java Tags: ,

Binary search algorithm – Java implementation

Жовтень 11th, 2011 admin Прокоментувати

In this pot I will publish implementation of binary search algorithm in Java. As usual, quote from Wikipedia:

In computer science, a binary search or half-interval search algorithm finds the position of a specified value (the input “key”) within a sorted array. At each stage, the algorithm compares the input key value with the key value of the middle element of the array. If the keys match, then a matching element has been found so its index, or position, is returned. Otherwise, if the sought key is less than the middle element’s key, then the algorithm repeats its action on the sub-array to the left of the middle element or, if the input key is greater, on the sub-array to the right. If the remaining array to be searched is reduced to zero, then the key cannot be found in the array and a special “Not found” indication is returned.

And implementation (method will return -1 as indication that item not found. Also, recursion is used). Variable callCnt is used to show how many calls algorithm requires to perform search :

package ua.org.bytes.algorithm;
 
public class BinarySearch {
	public static long callCnt = 0;
	public static int binarySearch(int[] array, int valueToFind){
		callCnt = 0;
		return doSearch(array,0,array.length-1,valueToFind);
	}
 
	private static int doSearch(int[] array, int start, int end,int valueToFind) {
		callCnt++;
		if (start>end) return -1;
		int middle = (end+start)/2;
		if (array[middle]==valueToFind) return middle;
		else if (array[middle]>valueToFind) return doSearch(array,start,middle-1,valueToFind);
		else return doSearch(array,middle+1, end, valueToFind);
	}
 
	public static void main(String ... args){
		System.out.println(binarySearch(new int[]{1,2,3,4,5},1) + ", call times: "+callCnt);
		System.out.println(binarySearch(new int[]{1},1) + ", call times: "+callCnt);
		System.out.println(binarySearch(new int[]{1},4) + ", call times: "+callCnt);
		System.out.println(binarySearch(new int[]{1,2,3,4,5},5) + ", call times: "+callCnt);
		System.out.println(binarySearch(new int[]{1,2,3,4,5,7,8,9,10,11},6) + ", call times: "+callCnt);
		System.out.println(binarySearch(new int[]{1,2,3,4,5,7,8,9,10,11},7) + ", call times: "+callCnt);
		System.out.println(binarySearch(new int[]{1,2,3,4,5,7,8,9,10,11},-1) + ", call times: "+callCnt);
		System.out.println(binarySearch(new int[]{1,2,3,4,5,7,8,9,10,11},0) + ", call times: "+callCnt);
	}
}
  • Share/Bookmark
Categories: Java Tags: ,

Maximum subarray problem – solution in Java

Жовтень 11th, 2011 admin Прокоментувати

Hi, I’m starting the series of posts about implementation of some algorithms in Java.
The first problem that I want to write about is Maximum subarray problem. According to Wikipedia:

In computer science, the maximum subarray problem is the task of finding the contiguous subarray within a one-dimensional array of numbers (containing at least one positive number) which has the largest sum. For example, for the sequence of values −2, 1, −3, 4, −1, 2, 1, −5, 4; the contiguous subarray with the largest sum is 4, −1, 2, 1, with sum 6.

The problem was first posed by Ulf Grenander of Brown University in 1977, as a simplified model for maximum likelihood estimation of patterns in digitized images. A linear time algorithm was found soon afterwards by Jay Kadane of Carnegie-Mellon University (Bentley 1984).

And solution in Java (class Result created just to hold result as data structure).
This implementation finds solution considering additional parameter “maximum length of the sequence”. Also, if this parameter is 1, it will find maximum element:

package ua.org.bytes.algorithms;
 
public class FindMaxSum {
 
	public static Result findMaxSum(int[] array, int maxLength) {
		long maxSum = Long.MIN_VALUE;
		int startIdx = 0, endIdx = 0;
		for (int i = 0; i < array.length; ++i) {
			long sum = 0;
			for (int j = i; j < array.length; ++j) {
				if (maxLength >= 1) {
					if (j - i >= maxLength) {
						break;
					}
				}
				sum = sum + array[j];
				if (sum > maxSum) {
					maxSum = sum;
					endIdx = j;
					startIdx = i;
				}
			}
		}
		return new Result(maxSum, startIdx, endIdx, array);
	}
 
	public static class Result {
		//Class which holds result information
		private final long sum;
		private final int startIndex;
		private final int endIndex;
		private final int[] source; //For better output - show 
 
		public Result(long sum, int startIndex, int endIndex, int[] source) {
			super();
			this.sum = sum;
			this.startIndex = startIndex;
			this.endIndex = endIndex;
			this.source = source;
		}
 
		public long getSum() {
			return sum;
		}
 
		public int getStartIndex() {
			return startIndex;
		}
 
		public int getEndIndex() {
			return endIndex;
		}
 
		public String toString() {
			return "For array: " + getSource() + " Sum: " + sum
					+ ", start index=" + startIndex + ", end index=" + endIndex;
		}
		//For pretty output
		public String getSource() {
			if (source == null) return "[]";
			StringBuilder result = new StringBuilder();
			result.append("[");
			for (int i : source) {
				result.append(i + ",");
			}
			result.deleteCharAt(result.length() - 1);
			result.append("]");
			return result.toString();
		}
		//For usage in JUnit assert* functions
		public boolean equals(Object candidate) {
			if (candidate == null)
				return false;
			if (this == candidate)
				return true;
			if (candidate instanceof Result) {
				Result r = (Result) candidate;
				if (r.getStartIndex() == getStartIndex() && r.getEndIndex() == getEndIndex() && r.getSum() == getSum())
					return true;
				return false;
			} else
				return false;
		}
	}
}

How to use it:

package ua.org.bytes.algorithms.exe;
 
import ua.org.bytes.algorithms.FindMaxSum;
 
public class TheApp {
	public static void main(String... args) {
		System.out.println(FindMaxSum.findMaxSum(new int[] { 1, 2, 3, 4, 5 },
				20));
		System.out.println(FindMaxSum.findMaxSum(new int[] { 1, 2, 3, 4, -1 },
				5));
		System.out.println(FindMaxSum.findMaxSum(new int[] { -1, 2, 3, 4, 5 },
				5));
		System.out.println(FindMaxSum.findMaxSum(new int[] { -1, 2, -3, 4, 5 },
				5));
		System.out.println(FindMaxSum.findMaxSum(new int[] { -1, 2, -3, 4, 5 },
				5));
		System.out.println(FindMaxSum.findMaxSum(new int[] { -2, 1, -3, 4, -1,
				2, 1, -5, 4 }, 20));
	}
}

And some unit tests:

package ua.org.bytes.algorithms.test;
 
import static org.junit.Assert.assertEquals;
 
import org.junit.Test;
 
import ua.org.bytes.algorithms.FindMaxSum;
 
 
public class TheAppTest {
	@Test 
	public void testFindMaxSum(){
		FindMaxSum.Result result = FindMaxSum.findMaxSum(new int[]{1,2,3,4,5}, 6);
		assertEquals( new FindMaxSum.Result(15, 0, 4,null),result);
 
		result = FindMaxSum.findMaxSum(new int[]{1,2,3,4,5}, 1);
		assertEquals( new FindMaxSum.Result(5, 4, 4,null),result);
 
		result = FindMaxSum.findMaxSum(new int[]{-1,2,-3,4,5}, 5);
		assertEquals( new FindMaxSum.Result(9, 3, 4,null),result);
	}
}
  • Share/Bookmark
Categories: Java Tags: ,

Case-sensitivity in VBScript and QTP when running script on Firefox browser

Серпень 18th, 2011 admin Прокоментувати

Hi, posting here situation, which I met in my work.
expression

Browser().Page().WebElement("PositionManagerContainer").WebElement("LoadingMessage").Object.ParentNode.ParentNode

Gives error: Object Required “.Object.ParentNode”

But expression

Browser().Page().WebElement("PositionManagerContainer").WebElement("LoadingMessage").Object.parentNode.ParentNode

(the difference in case of ParentNode member of .Object) Is correct and works fine without any errors.

Browser is Firefox. In IE it worked fine.

And here is explanation why (Thanks to Motti):

In general .Object allows access to the native object in the application being tested. Since QTP is VBScript based this means that the .Object property of test objects is IDispatch.

When working with IE QTP can pass the MSHTML object that IE exposes (and which supports IDispatch), since MSHTML is designed to work with VBScript these objects are case insensitive. However when working with Firefox there is no IDispatch supporting object which is exposed by the browser. Therefore QTP has to create a proxy object that implements IDispatch by querying the object exposed by Firefox. Since Firefox is designed to work with JavaScript (which is case sensitive) this proxy object is automatically case sensitive.

The error you saw came from the fact that the first ParentNode returned Empty so the second .ParentNode threw an error.

Therefore when using .Object with Firefox you must use the correct casing for the properties and methods you access.

  • Share/Bookmark
Categories: HP Quick Test Pro Tags: , , ,

How to work with Java arrays in HP Quick Test Professional

Травень 27th, 2011 admin Прокоментувати

When working with Java object properties, you’re bound to come across a property which stores its data in an array. Unlike .Net or VB arrays, Java arrays are completely inaccessible to VBScript, and it you’ll try to access the array’s inner items, you’ll fail. You can see the actual class of array item, but you can’t call any of it’s methods, only methods of the Object parent class.

But Java add-in provides several undocumented methods to work with Java arrays. Here’s a quick sample he provides:

'Just an example for getting a Java array from some object

set comps = JavaWindow("SwingSet").JavaInternalFrame("Internal Frame Generator").Object.getComponents()
 
 
 
'This is the actual workaround - notice the special undocumented command mic_arr_get

set currComp = comps.mic_arr_get(0)
 
'Now that we have the item we want from the array, let’s print it

msgbox currComp.toString()

Let’s review. The first code line is just there to put the array into a more accessible name – comps.

The second line is the most important here – it uses an undocumented method – mic_arr_get, to retrieve the first item in the array (since we send index=0 as the parameter).

The third line just prints the item’s content.

There are two generic methods:

mic_arr_get – Receives an index and returns the item at that index in the array. The returned item will always be an object (so we have to use .ToString).
mic_arr_set – Receives an index and an object and sets the appropriate item in the array.

There’re also more sophisticated versions for mic_arr_get: instead of returning an object and then turning it into a sting (or an integer, etc), you can perform both actions in a single action by using these specialized methods:

mic_arr_get_int : will return the data as an integer
mic_arr_get_char : will return the data as a single char
mic_arr_get_double : will return the data as a double (real) number
mic_arr_get_long : will return the data as a long number
mic_arr_get_short : will return the data as a short number
mic_arr_get_byte : will return the data as a byte number
mic_arr_get_boolean : will return the data as a boolean

Similarly, you can use the specialized methods for inserting specific data-types into an array:

mic_arr_set_int
mic_arr_set_char
mic_arr_set_double
mic_arr_set_long
mic_arr_set_short
mic_arr_set_byte
mic_arr_set_boolean

  • Share/Bookmark
Categories: HP Quick Test Pro Tags: ,

QTP: How to check if environment variable exists

Квітень 21st, 2011 admin Прокоментувати

As you probably know, there is no safe way to check existence of environment variable. Environment object doesn’t have methods like “Exists”, and it will raise an error if you will try to access variable by non-existed key.
This function returns true if environment variable exists, and false – if not exists.

Public Function IfEnvironmentVariableExists(variableName)
	Dim tmp
	Err.Clear
	On Error Resume Next
	tmp = Environment(variableName)
	If err.Number Then
		IfEnvironmentVariableExists = false
	Else
		IfEnvironmentVariableExists = true
	End If
End Function
  • Share/Bookmark
Categories: Автоматизація тестування Tags: , ,

Need to know more about application under test: why don’t you use decompiler?

Березень 31st, 2011 admin Прокоментувати

During usage of QTP and other tools for testing via GUI, often we need to know more about application being tested. For example, it uses custom controls or even 2D or 3D graphics. How can we validate that? Well, it depends on situation, but I want to share the technique that I used in my practice. I used it mainly for validation, but also it was indispensable when I don’t know how to simulate user actions, standard clicks and other staff don’t work.
So, if application is written on Java or on C# (or on other language, that can be easily decompiled) you can use decompiler to see how application built and it’s internal mechanisms. Let’s imagine that we have Java Swing application for deal entry and that can show us information about that deal. Window with deal information contain a lot of fields (JLabels objects), their location can change in new versions or even for different types of deals. So, we can not rely on index. But what if I need to validate that information?
I created one simple demo form, I will describe approach on that sample:
Далі…

  • Share/Bookmark
Categories: Автоматизація тестування Tags: ,

How to use classes in QTP

Березень 30th, 2011 admin Прокоментувати

Classes provides a great possibility for code abstraction and to split task into smaller pieces. And as you probably know VBScript provides limited support for OOP paradigm (It doesn’t support inheritance and polymorphism). But In VBScript there is no easy way to include classes (and other code at all) from external library.
But HP QTP has possibility to associate libraries. But it doesn’t work for classes: we can’t create instances of classes, that was defined in different file (vbs or qfl, etc.) But there is a workaround: for class we can create a function, that will return an instance of class and you can call that function from other libraries or from Actions. Let’s look at example:

Class Message
	Private p_Message
	Public Property Get getMessage
	   getMessage = p_Message
	End Property
End Class
 
Public Function NewMessage
	Set NewMessage = New Message
End Function

You see, that function NewMessage just returns new instance of the class.
So, you can save that class and function definitions in some vbs-file, then associate it to your QTP test and the in Action code you can use that class:

Dim messageObj
Set messageObj = NewMessage
MsgBox messageObj.getMessage

For usability, I have naming convention for that “getter” functions: I use New<ClassName> format.

  • Share/Bookmark
Categories: Автоматизація тестування Tags: , ,