akshay
BAN USERHere is code for max sum after deleting 2 consecutive integer
public class MaximumSumByRemoving1OfConsecutiveDigit {
public static int maxSum(int[] arr,int index){
if (index>=arr.length) {
return 0;
} else if (index==arr.length-1) {
return arr[index];
}
return Math.max(arr[index] + maxSum(arr, index + 2), arr[index + 1] + maxSum(arr, index + 3));
}
public static void main(String a[]){
System.out.println(maxSum(new int[]{1,2,3,4,5,6,7},0));
// output : 16
}
}
As it is non-weighted graph BFS will always give shortest path. but there may be more than 1 shortest path with same distance. I have used BFS to find out shortest path.
Here I am adding visited node to queue so that once path is found, queue will have multiple destination node with distance from source. I am filtering out the shortest distance.
Java code is given below -
class Graph {
private int num_of_vertices =0;
private int num_of_edges =0;
private Map<Integer, ArrayList<Integer>> adjListsMap = new HashMap<>();
public int addVertex() {
adjListsMap.put(++num_of_vertices, new ArrayList<>());
return num_of_vertices;
}
public void addEdge(int u,int v) {
if (adjListsMap.containsKey(u) && adjListsMap.containsKey(v)) {
++num_of_edges;
ArrayList<Integer> neighbors = adjListsMap.get(u);
neighbors.add(v);
} else {
throw new IllegalArgumentException("either starting or ending node is not present in graph");
}
}
public List<Integer> getNeighbors(int vertex){
return adjListsMap.get(vertex);
}
}
public class AllShortestPathInGraph {
public static int getNumberOfShortestPath(Graph graph,int source,int destination){
class QueueNode{
Integer vertex;
Integer distance;
public QueueNode(Integer vertex, Integer distance) {
this.vertex = vertex;
this.distance = distance;
}
}
int shortestDistance =0;
Deque<QueueNode> deque = new LinkedList<>();
int shortestPath = 0;
boolean found = false;
deque.add(new QueueNode(source,0));
while (!deque.isEmpty()){
QueueNode node = deque.remove();
for (Integer neighbor : graph.getNeighbors(node.vertex)) {
if(neighbor.equals(destination)){
if (!found) {
found = true;
shortestDistance = node.distance + 1;
shortestPath++;
}
else if (shortestDistance==node.distance+1){
shortestPath++;
}
}
if (!found){
deque.add(new QueueNode(neighbor,node.distance+1));
}
}
}
return shortestPath;
}
public static void main(String[] a) {
Graph graph = new Graph();
for (int i = 0; i < 5; i++) {
graph.addVertex();
}
graph.addEdge(1, 2);
graph.addEdge(1, 3);
graph.addEdge(1, 4);
graph.addEdge(2, 5);
graph.addEdge(3, 5);
graph.addEdge(4, 5);
System.out.println(getNumberOfShortestPath(graph,1,5));
}
}
As input has different types of iterator, So can not make it generic.
import java.util.Arrays;
import java.util.Iterator;
/**
* Created by Akshay on 5/27/2016.
*/
public class InterLeaveIterator implements Iterator {
private Iterator<?>[] iterators;
private int currentIndex;
public InterLeaveIterator(Iterator<?>... iterators) {
this.iterators = iterators;
if (iterators.length == 0) {
throw new IllegalArgumentException();
}
currentIndex = -1;
}
public boolean hasNext() {
boolean hasNext = false;
for (int i = 0; i < iterators.length; i++) {
currentIndex = ++currentIndex % iterators.length;
hasNext = iterators[currentIndex].hasNext();
if (hasNext)
return true;
}
return hasNext;
}
public Object next() {
Object o = iterators[currentIndex].next();
return o;
}
public void remove() {
}
public static void main(String a[]) {
Iterator iterator =
new InterLeaveIterator(
Arrays.asList(new Integer[]{1, 2, 3, 4, 5, 6}).iterator(),
Arrays.asList(new String[]{"a", "b", "c"}).iterator(),
Arrays.asList(new Double[]{1.1, 1.2, 1.3, 1.4}).iterator()
);
while (iterator.hasNext()) {
System.out.println(iterator.next().toString());
}
}
}
Here is code to merge strings where order is same for both
public class MergeStringWithOrder {
public static void merge(String parent,String str1,String str2){
if (str1 == null || "".equals(str1)) {
System.out.println(parent+str2);
return;
} else if (str2==null || "".equals(str2)) {
System.out.println(parent+str1);
return;
}
merge(parent+str1.substring(0,1),str1.substring(1),str2);
merge(parent+str2.substring(0,1),str1,str2.substring(1));
}
public static void main(String a[]){
merge("","hey","sam");
}
}
public static int[] arrayOfProduct(int[] a) {
int product=1;
int [] arrayProduct = new int[a.length];
for (int i = 0; i < a.length; i++) {
arrayProduct[i] = product;
product*=a[i];
}
product=1;
for (int i = a.length-1; i >= 0; i--) {
arrayProduct [i] *= product;
product*= a[i];
}
return arrayProduct ;
}
Below solution takes O(n) time.
static int longestUniqueSubString(String s){
int length = 0;
if(s==null || (length = s.length())==0)
return 0;
int startIndex = 0,subStringLength=0;
HashMap<Character,Integer> map = new HashMap<Character,Integer>();
for (int i = 0; i < length; i++) {
char c = s.charAt(i);
if(map.containsKey(c) && map.put(c, i) >= startIndex){
if((i-startIndex) > subStringLength){
subStringLength=(i-startIndex);
}
startIndex = i;
}
else{
map.put(c, i);
}
}
// if all characters are unique
if(subStringLength==0){
subStringLength= s.length();
}
return subStringLength;
}
Idea is to traverse the tree, There are two pointers p1 and p2 which hold the top most parent of given node value in sub tree. if p1 and p2 are equal, it means p1 node is least common ancestor.
Only one traversal is required to find LCA and takes O(1)
Code is given below :
static class Node<T> {
public T data;
public Node<T> left;
public Node<T> right;
public Node<T> parent;
public Node(T data,Node<T> parent) {
this.data=data;
this.parent = parent;
}
}
static Node<?> parent1,parent2,ancestor;
static Node<?>[] forest;
public static Node<?> closest_common_ancestor(Node<?> n1, Node<?> n2) {
for (Node<?> root : forest) {
leastCommonAncestor(root, n1, n2);
if(ancestor!=null){
return ancestor;
}
}
return null;
}
public static void leastCommonAncestor(Node<?> root
,Node<?> n1,Node<?> n2){
if(root==null || (parent1!=null && parent2!=null)){
return;
}
if (root==n1) {
parent1 = root;
}
if(root==n2){
parent2 = root;
}
leastCommonAncestor(root.left, n1, n2);
leastCommonAncestor(root.right, n1, n2);
if(parent1==parent2){
ancestor = parent1;
return;
}
if(parent1==root){
parent1=root.parent;
}
if(parent2==root){
parent2 = root.parent;
}
}
The idea is to do inorder traversal of the binary tree. While doing inorder traversal, keep track of the previously visited node in a variable say prev. For every visited node, make it next of prev and previous of this node as prev.
static Node prev,head;
public static void convetToCLL(Node root){
if(root==null)
return ;
convetToCLL(root.left);
if(prev==null){ // first node in list
head=root;
}
else{
prev.right = root;
root.left = prev;
}
prev = root;
convetToCLL(root.right);
if(prev.right==null){ // last node in list
head.left = prev;
prev.right = head;
}
}
This solution takes 3n/2+c time and does not require any additional space.
public static void findMaxMin(int[] a){
if(a==null || a.length<1)
return;
int max,min;
max=min=a[0];
for (int i = 0; i < a.length; i=i+2) {
if(a[i]>a[i+1]){
if(max<a[i])
max=a[i];
if(min>a[i+1])
min=a[i+1];
}
else{
if(max<a[i+1])
max=a[i+1];
if(min>a[i])
min=a[i];
}
}
System.out.println("Max : "+max+"\nMin : "+min);
}
Above solution requires additional O(n) space to store winner and loser.
Below implementation does not require any additional space.
public static void findMaxMin(int[] a){
if(a==null || a.length<1)
return;
int max,min;
max=min=a[0];
for (int i = 0; i < a.length; i=i+2) {
if(a[i]>a[i+1]){
if(max<a[i])
max=a[i];
if(min>a[i+1])
min=a[i+1];
}
else{
if(max<a[i+1])
max=a[i+1];
if(min>a[i])
min=a[i];
}
}
System.out.println("Max : "+max+"\nMin : "+min);
}
public static int noOfStringsFromIntegerString(String s,int index,int length)
{ int count =0;
if(index+1>=length)
count = 1;
else {
count = noOfStringsFromIntegerString(s, index+1, length);
int temp = Integer.parseInt( s.substring(index,index+2));
if(temp < 26){
count += noOfStringsFromIntegerString(s, index+2, length);
}
}
return count;
}
Here is java code for api, works with O(logn) complexity.
- akshay June 14, 2016