nishant
BAN USER- 0of 0 votes
AnswersHow to implement stack using queue
- nishant in India| Report Duplicate | Flag | PURGE
Adobe Software Engineer / Developer Data Structures
Use recursion to solve this problem. Divide it to subproblem and each subproblem prints the boundary. Below is the code for the same:
{
{
package com.practise.amazon;
public class PrintArrayInSpiral {
/**
* @param args
*/
public static void main(String[] args) {
int[][] arr = new int [][] {{1, 2, 3, 4}, {12, 13, 14, 5}, {11, 16, 15, 6}, {10, 9, 8, 7}};
printArrayInSpiral (arr);
}
private static void printArrayInSpiral(int[][] arr) {
printArrayInSpiral(arr, 0);
}
private static void printArrayInSpiral(int[][] arr, int step) {
if ( step > (arr[step].length - step - 1)) {
return;
}
for (int i = step; i < arr[step].length - step - 1; i++) {
System.out.print(arr[step][i]+" ");
}
for (int i = step; i < (arr.length - step); i++) {
System.out.print(arr[i][(arr[step].length - step - 1)]+" ");
}
for (int i = arr.length - step -2; i >= step; i--) {
System.out.print(arr[(arr.length - step -1)][i]+" ");
}
for (int i = arr.length - step -2; i > step; i--) {
System.out.print(arr[i][step]+" ");
}
printArrayInSpiral(arr, step + 1);
}
}
}
}
- nishant November 25, 2013This builds in the idea that whenver we find a valid word we recurese from that point to rest of the word while continuing in original string. Any call that reach end with valid end word is printed
{
public class AddSpaces {
/**
* @param args
*/
public static void main(String[] args) {
String str = "outputisinvalid";
addSpaces(str, "", 0);
System.out.println("done");
}
private static void addSpaces(String str, String soFar, int index) {
int i = 0;
if (index == str.length())
return;
for (i = index; i < str.length(); i++) {
try {
String test = str.substring(index, i+1);
if (exists (test)){
if (soFar.length() > 0)
addSpaces(str, soFar + " "+test, i + 1);
else
addSpaces(str, test, i + 1);
}
}catch (Exception e) {
System.out.println("begin: "+index);
System.out.println("end: "+(i+1));
System.out.println("exception: " + e);
System.exit(0);
}
}
if (i == str.length()) {
if (index == str.length()) {
System.out.println(soFar);
}
else if (exists (str.substring(index))) {
System.out.println(soFar + " " + str.substring(index));
}
}
}
public static boolean exists (String str){
return str.equals("I") || str.equals("work") || str.equals("in")
|| str.equals("out") || str.equals("output") || str.equals("put") || str.equals("is") || str.equals("in") || str.equals("invalid") || str.equals("valid");
}
}
}
The code below is as follows:
1. for any index i of array, take mod of sum so far i.e from 0 to i
2. if mod = 0, print from 0 to index
3. else search for any index with same value and print no from index + 1 to another index
private static void findAllCombinationOfZero(int[] a) {
getMod(a);
for (int i = 0; i < a.length; i++) {
if(a[i] == 0)
{
for (int k = 0; k <= i;k++){
System.out.print(b[k]+" ");
}
System.out.println();
}
for (int k = i + 1; k < a.length; k++) {
if (a[k] == a[i]) {
for (int l = i + 1; l <= k; l++){
System.out.print(b[l]+" "+"("+l+")"+" ");
}
System.out.println();
}
}
}
}
private static void getMod(int[] a) {
int sumSoFar = 0;
for (int i = 0; i < a.length; i++) {
sumSoFar += a[i];
sumSoFar = sumSoFar % N;
a[i] = sumSoFar;
}
for (int i : a) {
System.out.print(i+ " ");
}
System.out.println();
}
o(n) solution:
private static int findMaximumSumSubsequence(List<Integer> list) {
int currentMax = Integer.MIN_VALUE;
int tempMax = 0;
for (Integer integer : list) {
if (integer >= 0) {
if (tempMax < 0)
tempMax = 0;
tempMax += integer;
} else {
if (tempMax > currentMax) {
currentMax = tempMax;
}
tempMax += integer;
}
}
return Math.max(tempMax, currentMax);
}
package com.PermutationOfStrings;
import java.util.HashSet;
public class P {
/**
* @param args
*/
public static void main(String[] args) {
String name = "CareerCup";
printPermutationOfString(name);
}
static HashSet<String> permutation = new HashSet<String>();
private static void printPermutationOfString(String name) {
boolean[] count = new boolean[name.length()];
getAllPermutation (name, count, "");
}
private static void getAllPermutation(String name, boolean[] count,
String soFar) {
if (soFar != null && soFar.length() > 0) {
if (permutation.add(soFar))
System.out.println(soFar);
}
if (soFar.length() == name.length())
return;
for (int i = 0; i < name.length(); i++) {
if (!count[i]){
boolean[] c = count.clone();
c[i] = true;
getAllPermutation(name, c, soFar + name.charAt(i));
}
}
}
}
static Set<String> map = null;
public static void main(String[] args) {
map = new TreeSet<String>();
permutationOfString(null, new String("1112"));
System.out.println(map);
}
private static void permutationOfString(String soFar, String lefts) {
char[] left = lefts.toCharArray();
if (lefts.length() == 1) {
String s = soFar + lefts;
map.add(s);
return;
}
if (soFar == null) {
soFar = "";
}
for (int i = 0; i < lefts.length(); i++) {
char[] leftChar = new char[lefts.length() - 1];
String str = soFar + left[i];
for(int k = 0; k < i; k++){
leftChar[k] = left[k];
}
for (int j = i; j <= lefts.length() - 2; j++) {
leftChar[j] = left[j+1];
}
System.out.println(str);
System.out.println(leftChar);
permutationOfString(str, new String(leftChar));
}
}
If the sorting needs to be done based on only 3 character in a1, ideal solution is to go with 3 colored problem, wherein we sort the number based on 4 pointer. The algorithm says that any char that belongs to type 1 should go to initial part of array and type 3 should go towards end.
Code to explain this is as follow
private static char[] sortSecBasedOnFirst(char[] a1, String str) {
int len = str.length();
char[] output = new char[len];
Map<Character, Integer> map = new HashMap<Character, Integer>();
int index = 1;
for(char c : a1){
map.put(c, index++);
}
int indexForFirst = 0;
int indexForMiddle = 0;
int indexForLast = len - 1;
int indexForDefault = len -1;
for(int i = 0; i < len ; i++){
char c = str.charAt(i);
Integer ind = map.get(c);
if(ind == null ){
ind = -1;
}
switch (ind) {
case 1:
output[indexForMiddle++] = output[indexForFirst];
output[indexForFirst++] = c;
break;
case 2:
output[indexForMiddle++] = c;
break;
case 3:
output[indexForLast--] = c;
break;
default:
output[indexForLast-- ] = output[indexForDefault];
output[indexForDefault--] = c;
break;
}
}
return output;
}
Least common Ancestor is that node form which one of the node is on left side and other is right side.
so start searching the node from top s.t n >= first and n <= second.
For any intermediary node, the case would be n > both or n< both.
accordingly go to the right or left child.
This is order n solution
{
private static Set<Integer> getEvenFrequencyNumber(int[] arr) {
// TODO Auto-generated method stub
HashMap<Integer, Boolean> hashMap = new HashMap<>();
for(int a : arr){
Boolean x = hashMap.get(a);
if(x == null)
hashMap.put(a, false);
else
hashMap.put(a, !x);
}
Set<Integer> ar = hashMap.keySet();
Iterator<Integer> iterate = ar.iterator();
while(iterate.hasNext()){
if(!hashMap.get(iterate.next()))
iterate.remove();
}
System.out.println(ar);
return ar;
}
}
- nishant October 31, 2012
First reverse the total String and which will give entire reveresed String. from here we need to reverse each word endividually
- nishant November 25, 2013