Akhil
BAN USER
For convenience I have used int Array with 1 and 0. PFB program:
package com.frogjump;
public class CanFrogJumpThePond {
static int pond[] = { 1, 0, 1, 0, 1, 0, 0, 1 };
public static void main(String[] args) {
System.out.println("Frog Path : "+findPathAcrossThePond());
}
public static String findPathAcrossThePond() {
String path = "";
int halfway = pond.length / 2;
int firstJumpPos = 0;
while (firstJumpPos < halfway) {
if (pond[firstJumpPos] == 1) {
path=findPathAcrossThePond(firstJumpPos, firstJumpPos+1);
if(!path.isEmpty()){
path=String.valueOf(firstJumpPos)+"->"+path;
break;
}
} else {
firstJumpPos++;
}
}
return path;
}
public static String findPathAcrossThePond(int currPos, int previousJumpLen) {
String partialPath = "";
int nextJumpPos = 0;
int nextJumpLen = 0;
// Same Jump length
nextJumpPos = currPos + previousJumpLen;
nextJumpLen = previousJumpLen;
if (nextJumpPos < pond.length - 1) {
if (pond[nextJumpPos] == 1) {
partialPath = findPathAcrossThePond(nextJumpPos, nextJumpLen);
if (!partialPath.isEmpty()) {
return String.valueOf(nextJumpPos) + "->" + partialPath;
}
}
} else if (nextJumpPos == pond.length - 1) {
return String.valueOf(nextJumpPos);
}
// +1 Jump length
nextJumpPos = currPos + previousJumpLen + 1;
nextJumpLen = previousJumpLen + 1;
if (nextJumpPos < pond.length - 1) {
if (pond[nextJumpPos] == 1) {
partialPath = findPathAcrossThePond(nextJumpPos, nextJumpLen);
if (!partialPath.isEmpty()) {
return String.valueOf(nextJumpPos) + "->" + partialPath;
}
}
} else if (nextJumpPos == pond.length - 1) {
return String.valueOf(nextJumpPos);
}
// -1 Jump length
nextJumpPos = currPos + previousJumpLen - 1;
nextJumpLen = previousJumpLen - 1;
if (nextJumpPos < pond.length - 1) {
if (pond[nextJumpPos] == 1) {
partialPath = findPathAcrossThePond(nextJumpPos, nextJumpLen);
if (!partialPath.isEmpty()) {
return String.valueOf(nextJumpPos) + "->" + partialPath;
}
}
} else if (nextJumpPos == pond.length - 1) {
return String.valueOf(nextJumpPos);
}
return partialPath;
}
}
Result:
Frog Path : 0->2->4->7
O(1) algorithm for this case. Space performance doesn't vary with input.
package com.largestpalindromeinlist;
public class Node {
Node next;
String data;
public static boolean isPallindrome(String str) {
return str.equals(new StringBuilder(str).reverse().toString());
}
public static String getLargestPallindrome(Node root) {
String largestPallindrome = "";
while (root!= null) {
if(isPallindrome(root.data) && root.data.length()>largestPallindrome.length()){
largestPallindrome=root.data;
}
root=root.next;
}
return largestPallindrome;
}
}
Try recursion method as below:
package com.returnallnodes;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
public class Node {
Iterator<Node> children;
public static Iterator<Node> getAllNodes(Node root){
List<Node> allNodes=new ArrayList<Node>();
if(root!=null){
while(root.children.hasNext()){
Iterator<Node> childNodes=getAllNodes(root.children.next());
while(childNodes.hasNext()){
allNodes.add(childNodes.next());
}
}
}
return allNodes.iterator();
}
}
The idea is to have two references to the list and move them at different speeds. Move one forward by 1 node and the other by 2 nodes.
package com.dectectloops;
public class Node {
Node next;
public static void main(String[] args) {
// TODO Auto-generated method stub
}
boolean hasLoop(Node first) {
if(first == null) // list does not exist..so no loop either.
return false;
Node slow, fast; // create two references.
slow = fast = first; // make both refer to the start of the list.
while(true) {
slow = slow.next; // 1 hop.
if(fast.next != null)
fast = fast.next.next; // 2 hops.
else
return false; // next node null => no loop.
if(slow == null || fast == null) // if either hits null..no loop.
return false;
if(slow == fast) // if the two ever meet...we must have a loop.
return true;
}
}
}
By assigning removing any element in the loop you can remove a loop, if that's what you meant.
- Akhil December 03, 2015Here approach is to use recursion to explore (i+1,j) and (i,j+1) branches and finally prints the path.
package com.explorescrorepossibilities;
public class ScorePossibilities {
static int iFinal=2, jFinal=3;
public static void main(String[] args) {
System.out.println("Final Score :" + iFinal + "-" + jFinal);
System.out.println("Score Possibilities :");
findScorePossibilities();
}
private static void findScorePossibilities(){
findScorePossibilities(0,0,"[");
}
private static void findScorePossibilities(int iNext, int jNext,String pathSoFar) {
if(iNext<iFinal){
findScorePossibilities(iNext+1,jNext, pathSoFar+iNext+"-"+jNext+",");
}
if(jNext<jFinal){
findScorePossibilities(iNext,jNext+1, pathSoFar+iNext+"-"+jNext+",");
}
if(iNext==iFinal && jNext==jFinal){
System.out.println(pathSoFar+iNext+"-"+jNext+"]");
}
}
}
Prints:
Final Score :2-3
Score Possibilities :
[0-0,1-0,2-0,2-1,2-2,2-3]
[0-0,1-0,1-1,2-1,2-2,2-3]
[0-0,1-0,1-1,1-2,2-2,2-3]
[0-0,1-0,1-1,1-2,1-3,2-3]
[0-0,0-1,1-1,2-1,2-2,2-3]
[0-0,0-1,1-1,1-2,2-2,2-3]
[0-0,0-1,1-1,1-2,1-3,2-3]
[0-0,0-1,0-2,1-2,2-2,2-3]
[0-0,0-1,0-2,1-2,1-3,2-3]
[0-0,0-1,0-2,0-3,1-3,2-3]
Snice requirement analysis capture is through modeling. Its clear that the clients are not very clear about all the particulars. I suggest Iterative approach. Waterfall is can be also good here. Another factor the havent been specified is nature of the project which too is important in this decision.
- Akhil July 26, 2014My approach would be scan each character by character and determine if they are comments or not. This considers the occurrence of //,/*.*/, ".
package cc.commentremover;
import java.util.ArrayList;
public class CommentRemover {
ArrayList<String> text;
int readCount;
public CommentRemover() {
readCount = 0;
text = new ArrayList<String>();
text.add("This is/* \"a\" */text but followin is \" \\*string *\\\"");
}
public static void main(String[] args) {
// TODO Auto-generated method stub
CommentRemover remover = new CommentRemover();
System.out.printf("Input Text: %s \n", remover.text.toArray());
System.out.print("Output Text: ");
remover.removeComment();
}
public String getNextLine() {
if (readCount >= text.size()) {
return null;
} else {
return text.get(readCount++);
}
}
public void removeComment() {
Boolean isComment = false;
int prevEncounter[] = { 0, 0, 0 };
String nextLine = getNextLine();
while (nextLine != null) {
char nextLinecharArray[] = nextLine.toCharArray();
int pos = 0;
while (pos < nextLinecharArray.length) {
if (nextLinecharArray[pos] == '"' && isComment == false) {
if (prevEncounter[2] != 1) {
prevEncounter[2] = 1;
} else {
prevEncounter[2] = 0;
}
} else if (nextLinecharArray[pos] == '/'
&& prevEncounter[2] == 0 && isComment == false) {
pos++;
if (nextLinecharArray[pos] == '*') {
isComment = true;
prevEncounter[1] = 1;
pos++;
continue;
} else if (nextLinecharArray[pos] == '/') {
isComment = true;
prevEncounter[0] = 1;
pos++;
continue;
} else {
pos--;
}
} else if (nextLinecharArray[pos] == '*'
&& prevEncounter[2] == 0 && isComment == true
&& prevEncounter[1] == 1) {
pos++;
if (nextLinecharArray[pos] == '/') {
isComment = false;
prevEncounter[1] = 0;
pos++;
continue;
}
} else if (pos == (nextLinecharArray.length - 1)
&& prevEncounter[2] != 1 && isComment == true
&& prevEncounter[0] == 1) {
prevEncounter[0] = 0;
isComment = false;
continue;
}
if (!isComment) {
System.out.print(nextLinecharArray[pos++]);
} else {
pos++;
}
}
nextLine = getNextLine();
}
}
}
I dont think its thats complicated. Following is my code with O(n).
package cc.cloudera.highestproduct;
public class HighestProductFinder {
public static void main(String[] args) {
// TODO Auto-generated method stub
int intArray[] = { 1, -2, -2, -4, 2, 0 };
int product, largestNeg, negCount;
product = 0;
negCount = 0;
largestNeg = 0;
for (int i = 0; i < intArray.length; i++) {
if (intArray[i] == 0) {
continue;
} else {
if (product == 0) {
product = intArray[i];
} else {
product *= intArray[i];
}
if (intArray[i] < 0) {
negCount++;
if (largestNeg == 0) {
largestNeg = intArray[i];
} else {
largestNeg = largestNeg > intArray[i] ? largestNeg : intArray[i];
}
}
}
}
if (negCount != 0 && negCount % 2 != 0) {
product /= largestNeg;
}
System.out.println("Max Product: " + product);
}
}
Use of array list would greatly decrease job :)
Try this one:
package cc.amazon.arraycounter;
import java.util.ArrayList;
import java.util.Arrays;
public class Counter {
public static void main(String[] args) {
// TODO Auto-generated method stub
ArrayList<Integer> array = new ArrayList<Integer>();
Integer arr[] = { 1,3,2,4,5,4,2 };
array.addAll(Arrays.asList(arr));
ArrayList<Integer> count = new ArrayList<Integer>();
int counter = 0;
int pos = 0;
for (Integer integer : array) {
counter = 0;
for (Integer num : array.subList(pos, array.size() - 1)) {
if (num <= integer) {
counter++;
}
}
count.add(counter);
pos++;
}
System.out.println("Output: " + count);
}
}
This has required O(nlogn) complexety
- Akhil June 22, 2014May be this would be better:
public static final int[] findDuplicates(final int[] data) {
// take a copy of the data.
int[] sorted = Arrays.copyOf(data, data.length);
// sort it. This is O(n log(n)) which will be the bulk of our time.
Arrays.sort(sorted);
// now scan the sorted data for even-numbered sequences of values.
int len = 0;
boolean even = false;
// sorted[0] is our first sequence, and currently it is not even.
// note that the scan starts at position 1.
for (int i = 1; i < sorted.length; i++) {
if (sorted[i] == sorted[len]) {
// this element is the same as the sequence, so 'count' the even-ness.
even = !even;
} else {
// this element is different to our sequence, it's a new sequence.
if (even) {
// the old sequence had an even count, so we 'preserve' it.
len++;
}
// move the value of the new sequence to the 'beginning'.
sorted[len] = sorted[i];
// and the new sequence is odd.
even = false;
}
}
if (even) {
// the last sequence was even, we preserve it.
len++;
}
// return the first part of the array, which contains the even sequence values.
return Arrays.copyOf(sorted, len);
}
- Akhil June 22, 2014PFB code finds the path, avoid possible loops also.
/**
*
*/
package cc.google.pathfinder;
import java.util.ArrayList;
import java.util.List;
/**
* @author Akhil
*
*/
public class PathFinder {
static List<String> visitedCity;
static boolean pathFound = false;
/**
* @param args
*/
public static void main(String[] args) {
List<Step> steps = new ArrayList<Step>();
List<String> pathToBeTaken = new ArrayList<String>();
visitedCity = new ArrayList<String>();
steps.add(new Step("A", "B"));
steps.add(new Step("B", "B"));
steps.add(new Step("B", "A"));
steps.add(new Step("E", "P"));
steps.add(new Step("C", "X"));
steps.add(new Step("B", "C"));
pathToBeTaken = findPath(steps, "A", "X");
System.out.println("Path : " + pathToBeTaken);
}
static List<String> findPath(List<Step> steps, String start,
String destination) {
List<String> pathTobeTaken = new ArrayList<String>();
List<String> temp = new ArrayList<String>();
visitedCity.add(start);
if (!pathFound) {
List<Step> avilableRoutes = availRoutesTo(start, steps);
if (!avilableRoutes.isEmpty()) {
for (Step step : avilableRoutes) {
if (step.getFinish().equals(destination)) {
pathFound = true;
pathTobeTaken.add(start);
pathTobeTaken.add(destination);
return pathTobeTaken;
} else {
if (!step.getStart().equals(step.getFinish())
&& !visitedCity.contains(step.getFinish())) {
temp = findPath(steps, step.getFinish(),
destination);
if (pathFound && temp != null) {
pathTobeTaken.add(start);
pathTobeTaken.addAll(temp);
return pathTobeTaken;
} else {
visitedCity.remove(step.getFinish());
}
}
}
}
} else {
return null;
}
}
return null;
}
static List<Step> availRoutesTo(String city, List<Step> routes) {
List<Step> avilableRoutes = new ArrayList<Step>();
for (Step step : routes) {
if (step.getStart().equals(city)) {
avilableRoutes.add(step);
}
}
return avilableRoutes;
}
}
Result:
Path : [A, B, C, X]
L ← Empty list that will contain the sorted elements
S ← Set of all nodes with no incoming edges
while S is non-empty do
remove a node n from S
add n to tail of L
for each node m with an edge e from n to m do
remove edge e from the graph
if m has no other incoming edges then
insert m into S
if graph has edges then
return error (graph has at least one cycle)
else
return L (sorted order)
Any of these set sorted?
- Akhil February 16, 2016