find complementary numbers

Find K Complementary numbers from array Java implementation

Find K complementary numbers from the given array

This is another approach to the problem that I have done it here. On that post, a good deal of visitors pointed out that it is actually o(n*n) not o(n) as I claimed.

Yes, the naive usage of Hashmap for holding the numbers has soared the performance and I have changed the approach as follows.

To remind the k complementary problem and its solution, you are given array of numbers and a number k of which you are going to find numbers that give k complementary. The following is an example of it.

The problem is, given numbers like 7, 1, 5, 6, 9, 3, 11, -1 and given number 10, write a script that would print numbers that would add to 10. In the example, it would be like
7 and 3, 1 and 9, -1 and 11.

Thanks Reda and mtrad for your correction.


package algorithm;

import java.util.ArrayList;
import java.util.List;

/**
 * Algorithm to find the pairs making the K complementary in O(n) complexity
 * 
 * @author http://gullele.com
 */
public class KComplementary2 {
	
	public static void main(String[] args) {
		KComplementary2 kcomp = new KComplementary2();
		int[] numbers = new int[]{7, 1, 5, 6, 9, 3, 11, -1};
		
		for (Integer number : kcomp.getKComplementaryPairs(10, numbers)) {
			System.out.println(" Pairs are "+ number + " and " + (10-number));
		}
	}
	
	public KComplementary2() {}
	
	/**
	 * An algorithm to find the pair from the given array that would sum up the given K
	 * 
	 * @note - the algorithm would be done in o(n)+o(nlogn). First it will run through the whole 
	 * numbers and creates a temporary list of pairs in HashMap with 
	 * (value, sum-value). 
	 * @param sum
	 * @param listOfIntegers
	 * @return
	 */
	public List getKComplementaryPairs(int sum, int[] listOfIntegers) {
		
		/*
		 * The algorithm works using front and last pointers on ascendingly sorted array. The front would be 
		 * instantiated with 0 and last with length-1; if the arr[front]+arr[last] == sum, then pick
		 * the numbers and add them to the pair array.
		 * if their sum is greater than sum, it means time to check the  second higher number that is lower
		 * than the current highest number. And the reverse would hold true if the sum is less than the sum
		 * time to move to the next higher number from the lower side.
		 */
		if (listOfIntegers == null || listOfIntegers.length == 0) {
			return null;
		}
		
		//quick sort the array 
		quickSort(0, listOfIntegers.length-1, listOfIntegers);
		
		int[] sortedArray = listOfIntegers;
		
		//holder for the complementary pairs
		List pairs = new ArrayList();
		int frontPointer = 0;
		int lastPointer = sortedArray.length-1;
		
		while (frontPointer < lastPointer) {
			int currentSum = sortedArray[frontPointer] + sortedArray[lastPointer];
			if (currentSum == sum) {
				/*
				 * Since sum is found, increment front and decrement last pointer
				 * Only one number is required to be hold, the other can be found 
				 * from sum-number since complementary 
				 */
				pairs.add(sortedArray[frontPointer]);//adding is o(1)
				frontPointer++;
				lastPointer--;
			} else if (currentSum > sum) {
				lastPointer--;
			} else {
				frontPointer++;
			}
		}
		
		return pairs;
	}
	
	/**
	 * sort the numbers. I have used quick sort here. QuickSort is nlogn in average case 
	 * well, in worst case it still would be n**2 though :(
	 * @param numbers
	 * @return sorted array numbers.
	 */
	public void quickSort(int lowerIndex, int higherIndex, int[] numbers) {
		/*
		 * Recursively inarray sort. Start from arbitrary value to compare from and recursively sort its 
		 * left and right.
		 */
		int pivot = lowerIndex+(higherIndex-lowerIndex)/2;
		int lower = lowerIndex;
		int higher = higherIndex;
		
		while (lower < higher) {
			while (numbers[lower] < numbers[pivot]) {
				lower++;
			}
			while (numbers[higher] > numbers[pivot]) {
				higher--;
			}
			
			//swap those needed to be on the left on those on the right.
			if (lower <= higher) {
				int temp = numbers[lower];
				numbers[lower] = numbers[higher];
				numbers[higher] = temp;
				lower++;
				higher--;
			}
		}
		if (lowerIndex < higher) {
			quickSort(lowerIndex, higher, numbers);
		}
		
		if (lower < higherIndex) {
			quickSort(lower, higherIndex, numbers);
		}
	}
}

Love algorithms? See how you would solve the following

Can you find the three numbers that would sum to T from given array?

From a file of billion numbers, find missing numbers with limited memory

Find longest palindrom from sequence of characters

Given the string, find the longest palindrom you can form from it


/**
 * @author gullele.com
 */
public class LongestPalindrom {
	public static void main(String[] args) {
		LongestPalindrom longest = new LongestPalindrom();
		System.out.println(longest.longest("zzbmbmbdmm"));
	}
	
	public String longest(String string) {
		if (string.length() == 0 || string == null) {
			return "";
		}
		

		StringBuffer palindrom = new StringBuffer();
		Map charBag = new HashMap();
		for (Character c : string.toCharArray()) {
			int totalChar = charBag.get(c) != null ? charBag.get(c) : 0;
			if ((totalChar + 1) % 2 == 0) {
				palindrom.append(c);
				palindrom = palindrom.insert(0, c);
				charBag.remove(c);
				continue;
			}
			charBag.put(c, ++totalChar);
		}
		
		if (charBag.size() > 0) {
			Iterator it = charBag.entrySet().iterator();
			Map.Entry pair = (Map.Entry)it.next();
			String c = pair.getKey().toString();
			palindrom.insert(palindrom.length()/2, c);
		}
		return palindrom.toString();
	}
}

Allow or deny access

Allow or Restrict sudo access to Users in linux

On collaborative work, you would give access to others who would be helping you out on the code or system admin stuff.

The question would be, how limited can you go with granting access to the users?

The first thing would be adding the user to the sudoers list, lets say you have created a new user named tom and you want to grant sudo access to this user

You can edit the sudoers file with whatever editor you are using. But the most recommended way would be using visudo


sudo visudo 

Grant all the access to user

If you want to give the world access to the user, then add the following line and save the file


tom ALL=(ALL) ALL

tom is the user you want to grant permissions and the first ALL is for the host and the ALL in the bracket is referring to other accounts the user sudouser can act as and the final ALL would be for list of commands – in this case tom has every access provided.

Grant only some commands

Lets say you want to give tom an access of copy and renaming a file


tom ALL=/bin/cp,/bin/mv

The above command would tell the system the user tom has access to cp and mv only. You might need to check the correct binary to cp and mv using which command. That is which cp would tell you the right path to the binary of the cp.

Allow the user everything but installing new softwares using apt-get

Ok, so you might want to give every access to the user but you want to limit installing new softwares using apt-get


tom ALL=ALL,!/usr/bin/apt-get

Here tom can do everything but not apt-get. If you add the ! in front of the command, it means don’t allow.

So using the combinations of the above you can reach the level where you can grant and deny any command for the user of interest

Add scrollbar to mysql result in terminal

MySQL command line scrollbar

MySQL command line provides a full fledged application that allows interaction with mysql engine so easy.

In MySQL command one thing that would annoy is when there is larger result set and scrolling is static or not even accessible.

If you have larger result coming from mysql and you want to scroll through the result on mysql terminal?

You might ask

How to add scrollbar to mysql result in mysql command line?

Reading larger result set in mysql command

Or have you asked how to scroll on results of terminal mysql?

Solution

Go to your terminal and do


mysql> pager less

This would allow you to have that feeling of being on vim

See how to configure LAMP on Amazon here

You asked to pull from the remote but did not specify the branch github error

asked to pull from remote but did not specify the branch github error

Mostly, you got a new repository or even existing one and you are trying to interact with it.

The above problem would be happening this time.

Git would allow you to have many branches of the same repository. So when you try to interact with the repository and you didn’t specify which branch then this would be the problem.

Because this is not the default configured remote
for your current branch, you must specify a branch on the command line

The tasks you are trying to do might be

git pull
git push or even others.

Solution

The first thing you want to do would be to check what branch you are in.

git branch

If you see master in there * master then do

git pull origin master

This would take care of the problem

Maven error Annotations are not supported in -source 1.3

The Error

Are you using annotations in your project?

If so, you will get this error if you try to do mvn compile or mvn install.

You may have also seen this if you are building your project on eclipse as well.

The solution

The default maven relies on JDK 1.3 for its building the project and you might be using a JDK above 1.3. Also, JDK 1.3 does not implement annotations.

The solution is to tell the maven the current non-1.3 JDK you are using on you pom.xml file.


<project>
.
.

  <build> 
    <plugins> 
      <plugin> 
        <artifactId>maven-compiler-plugin</artifactId> 
        <version>2.3.2</version> 
        <configuration> 
          <source>1.8</source> 
          <target>1.8</target> 
        </configuration> 
      </plugin> 
     </plugins> 
   </build> 
</project>

For the source and target you will provide your current JDK you are using.

Running maven project in eclipse step by step

If you have java web project that is maven based, and you want to run the project in eclipse here are the steps.

Mind you this is for the project which is already a maven project, say you did it through terminal or you got it from other repository and you want to run it locally through eclipse.

Assumed -> you have setup the webserver like tomcat on eclipse.

1. Go to Eclipse Run->Run Configuration

2. Double click on M2 Maven Build

3. On the base directory: insert ${project_loc}

4. On the goals: insert tomcat:run and the select and apply

5. Right click on the project and select configure->Convert to Maven Project

configure build path

configure build path

6. Again right click on the project and select Maven->Update Project

update-project

7. For further pulling the dependencies from maven to eclipse, right click on it->properties->Deployment Assembly

8 Click on Add button and select Java build path entries and select Maven Dependencies

9. Now, your dependencies should be pulled all is ready for testing. Go to project menu and click on build project. This will be inactive if Build Automatically is selected.

10. Then to test, right click on one of your servlet and select run as and click on the server option. If all went good, you should be able to see the output from your servlet on the browser.

The above simple steps would allow you to convert the Java web project into maven project in eclipse.

See: How to change directory structure for maven

See: Resolving classpath problem in eclipse

mysql command not found on mac after installation

After downloading mysql dmg on mac if you go to terminal and try to issue mysql command and get mysql command not found there keep reading.

This, in most cases, is the terminal not knowing the mysql command unless you go to the actual installation folder.

To check that out, go to

/user/local/mysql/bin/mysql --version

If this is giving you the right mysql information, then it is a matter of telling the terminal what the mysql command is.

Temporary fix

export PATH=$PATH:/usr/local/mysql/bin

The above command would allow the command files to be recognized by the current issuing terminal. But you won’t be able to access those on new terminal

Permanent fix

echo "export PATH=$PATH:/usr/local/mysql/bin" >>~/.bash_profile

The above command would simply append the path command you exported to the .bash_profile file.

Importing packages to eclipse added by maven to java web project

If eclipse is having a hard time acknowledging the packages you got through maven, here are the step by step fix for it..

1. Go to your projects root, where the pom.xml resides

2. issue mvn eclipse:clean

3. issue mvn eclipse:eclipse

4. this could be optional, on eclipse go to the project, right click on it and select build project

resources can not be added

eclipse j2ee error There are No resources that can be added or removed from the server

Eclipse showing There are No resources that can be added or removed from the server when adding project

If you are trying to test the java web application (j2ee) on your local machine with built in eclipse support and getting error, then it is related to project facet.

Here is how you can solve the error There are No resources that can be added or removed from the server coming from eclipse

1. right click on your web project in eclispe

2. Select properties
properties

3. Select Project facets
project-facets

4. Select Dynamic Web Module
select-dynamic-web-module

5. Click on apply and then click on OK

This will solve the problem.

See also: How to resolve class pass error when working with maven