Arun
BAN USERNot in O(1) space. But O(n) in time complexity... I guess so
class AlternateProg {
public static void main(String args[]) {
//int[] arr = {1, -22, -23, -4, 4,-2,-5,6,-7,7,-8,-9};
//int[] arr = {-5, -2, 5, 2, 4, 7, 1, 8, 0, -8};
int[] arr = { 1 ,2 ,3,4,5,6 };
AlternateProg.printArray("Input Array", arr);
AlternateProg.printArray("Output Array", AlternateProg.getShufflePostive(arr));
AlternateProg.algo2(arr,arr.length);
}
public static void printArray(String type, int[] arr) {
System.out.println("\n"+type+" :");
for(int elem: arr) {
System.out.print(elem +" ");
}
}
public static int[] getShufflePostive(int[] arr) {
int neg = -1,temp = 0;
int[] arr2 = new int[arr.length];
for(int i = 0, last_index=arr.length-1 ; i < arr.length; i++) {
if( arr[i] < 0 )
arr2[++neg] = arr[i];
else
arr2[last_index--] = arr[i];
} // end of for loop
for(int i =0; i <= neg; i++) arr[i] = arr2[i];
for(int i =arr.length-1, j = neg+1; i > neg; )
arr[j++] = arr2[i--];
if(neg >= 0){
//move extra elements to the end of array
if( arr.length-neg > neg){ // more positive
for(int i = arr.length-1; i > neg * 2 ; i--){
arr2[i] = arr[i];
}
for(int neg_pos = 1, pos_pos=neg+1,i=1; neg_pos <= neg; neg_pos++, i +=2, pos_pos++ ) {
arr2[neg_pos*2] = arr[neg_pos];
arr2[i] = arr[pos_pos];
}
}else{ // more negative
for(int i=neg,pos = arr.length-1; i >= arr.length - neg; i--,pos--) {
arr2[pos] = arr[i];
}
for(int neg_pos = 1, pos_pos=neg+1,i=1; pos_pos <= arr.length-1; neg_pos++, i +=2, pos_pos++ ) {
arr2[neg_pos*2] = arr[neg_pos];
arr2[i] = arr[pos_pos];
}
}
}
return (neg >= 0)? arr2 : arr;
}
}
import java.io.InputStreamReader;
import java.io.BufferedReader;
import java.util.List;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.Collections;
import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;
class DependencyTree {
public static void main(String args[]) throws Exception {
List<CodeDependency> obj = new ArrayList<CodeDependency>();
BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
System.out.println("Enter number of dependencies\n");
int num = Integer.parseInt(bufferedReader.readLine());
CodeDependency codeObj;
for(int i =0; i < num; i++) {
System.out.println("Dependency "+i+": ");
String[] arr = bufferedReader.readLine().split("->");
codeObj = new CodeDependency(arr[0],arr[1]);
obj.add(codeObj);
}
DependencyTree dependencyObj = new DependencyTree();
dependencyObj.printCodeDependency(dependencyObj.findDependency(obj));
}
public void printCodeDependency(List<SourceCode> sourcecodes){
Iterator<SourceCode> itr = sourcecodes.iterator();
while(itr.hasNext()){
System.out.print(itr.next().getParent());
if(itr.hasNext()) System.out.print("->");
}
}
public Map<String,SourceCode> mapParent;
public List<SourceCode> findDependency(List<CodeDependency> obj) {
mapParent = new HashMap<String,SourceCode>();
SourceCode code;
Set<String> hsRootCode = new HashSet<String>();
Set<String> hsChildCode = new HashSet<String>();
for(CodeDependency dependency : obj) {
// Add Child to parent with its child as null
if(!mapParent.containsKey(dependency.getChild()) ){
code = new SourceCode(dependency.getChild(), 0 , null);
mapParent.put(dependency.getChild(), code);
}
// Add parent
if(mapParent.containsKey(dependency.getParent()) ){
code = mapParent.get(dependency.getParent());
code.setChild(dependency.getChild());
}
else {
code = new SourceCode(dependency.getParent(), 0 ,dependency.getChild());
}
// Map root node and list of child node to help the iteration process
hsChildCode.add(dependency.getChild());
if(!hsChildCode.contains(dependency.getParent()))
hsRootCode.add(dependency.getParent());
if(hsRootCode.contains(dependency.getChild()))
hsRootCode.remove(dependency.getChild());
mapParent.put(dependency.getParent(),code);
}
if(hsRootCode.size() > 0) {
for(String codeName : hsRootCode)
findDepth(codeName , 1);
}
else
{
System.out.println("\n **************** Circular dependency found **************");
System.exit(-1);
}
List<SourceCode> codeDependency = new ArrayList<SourceCode>();
for( String codeItr: mapParent.keySet()) {
codeDependency.add(mapParent.get(codeItr));
}
Collections.sort(codeDependency);
return codeDependency;
}
public Set<String> hsCode = new HashSet<String>();
public void findDepth(String codeName, int pos) {
if (!hsCode.contains(codeName)) {
hsCode.add(codeName);
SourceCode code = mapParent.get(codeName);
if(code.getDepth() < pos) {
code.setDepth(pos);
mapParent.put(codeName,code);
// System.out.println(" "+codeName+ " " + pos);
for (String itrCode : code.getChild())
{
if (itrCode != null) findDepth(itrCode, pos+1);
}
}
hsCode.remove(codeName);
}
else {
System.out.println("\n **************** Circular dependency found **************");
System.exit(-1);
}
}
public static class CodeDependency {
String child;
String parent;
public CodeDependency(){
}
public CodeDependency(String child, String parent) {
this.child = child;
this.parent = parent;
}
public String getChild() {
return child;
}
public String getParent() {
return parent;
}
}
public class SourceCode implements Comparable<SourceCode> {
String parent;
int depth;
List<String> child;
public SourceCode(String parent, int depth, String child) {
this.child = new ArrayList<String>();
this.parent = parent;
this.depth = depth;
this.child.add(child);
}
public void setDepth(int depth) {
this.depth = depth;
}
public int getDepth() {
return depth;
}
public String getParent() {
return parent;
}
public List<String> getChild() {
return child;
}
public void setChild(String child) {
this.child.add(child);
}
@Override
public int compareTo(SourceCode obj) {
return this.getDepth() - obj.getDepth();
}
}
}
Small change in code requires for below scenario
- Arun April 14, 2015isMatch("cccba", "c*ba")