Unmix My Strings

Unmix My Strings

lPaeesh le pemu mnxit ehess rtnisg! Oh, sorry, that was supposed to say: Please help me unmix these strings! Somehow my strings have all become mixed up; every pair of characters has been swapped. Help me undo this so I can understand my strings again. 

 unmix("123456") ➞ "214365" 
 unmix("hTsii  s aimex dpus rtni.g") ➞ "This is a mixed up string." 
 unmix("badce") ➞ "abcde" 

Input: hTsii s aimex dpus rtni.g, Output: This is a mixed up string. 

Input: 214365, Output: 123456 

Input: badce, Output: abcde 

	public class UnmixStrings {
	public static void main(String[] args) {
	System.out.println(String.format("Input: hTsii s aimex dpus rtni.g, Output: %s",unmix("hTsii s aimex dpus rtni.g")));
	System.out.println(String.format("Input: 214365, Output: %s",unmix("214365")));
	System.out.println(String.format("Input: badce, Output: %s",unmix("badce")));
	}
	public static String unmix(String str) {
	StringBuilder sb = new StringBuilder();
	int length = str.length();
	boolean oddLength = !(length%2==0);
	int i=0;
	for(;i<length-1;i=i+2)
	{
	sb.append("" + str.charAt(i + 1) + str.charAt(i));
	}
	if (oddLength) {
	sb.append(str.charAt(i));
	}
	return sb.toString();
	}
	}

view raw UnmixStrings.java hosted with ❤ by GitHub

Question Reference: https://edabit.com/challenge/XRAGxXj4KtakkvD3F

Largest Gap

Given an array of integers, return the largest gap between the sorted elements of the array.

For example, consider the array:

[9, 4, 26, 26, 0, 0, 5, 20, 6, 25, 5] ... in which, after sorting, the array becomes:

[0, 0, 4, 5, 5, 6, 9, 20, 25, 26, 26] ... so that we now see that the largest gap in the array is between 9 and 20 which is 11.

	import java.util.Arrays;
	public class LargestGap {
	public static void main(String[] args) {
	System.out.println(largestGap(new int[]{9, 4, 26, 26, 0, 0, 5, 20, 6, 25, 5}));
	}
	public static int largestGap(int[] numbers) {
	int result = 0;
	Arrays.sort(numbers);
	for(int i=0;i<numbers.length-1;i++) {
	int diff = numbers[i+1]- numbers[i];
	if (result < diff) {
	result = diff;
	}
	}
	return result;
	}
	}

view raw LargestGap.java hosted with ❤ by GitHub

Maximum Loot Problem

Maximum Loot Problem

More details about the problem are mentioned at:

https://practice.geeksforgeeks.org/problems/stickler-theif/0

Input:
5 5 10 100 10 5

Output:
110

Input:
1 2 3

Output:
4

	/**
	* Deepak Singhvi
	*/
	public class MaxLoot {
	public static int maxLoot(int input[], int inputSize)
	{
	if (inputSize == 0)
	return 0;
	if (inputSize == 1)
	return input[0];
	if (inputSize == 2)
	return Math.max(input[0], input[1]);
	// maxLoot[i] is the temporary store value at any point of time of calculation.
	// maxLoot[n-1] i.e. the last element would have maximum loot value.
	int[] maxLoot = new int[inputSize];
	maxLoot[0] = input[0];
	maxLoot[1] = Math.max(input[0], input[1]);
	for (int i = 2; i<inputSize; i++)
	maxLoot[i] = Math.max(input[i]+maxLoot[i-2], maxLoot[i-1]);
	return maxLoot[inputSize-1]; // maximum loot value.
	}
	public static void main (String[] args) {
	int input[] = {5, 5, 10, 100, 10, 5};
	System.out.println("Maximum loot value : " + maxLoot(input, input.length));
	input = new int[]{1,2,3};
	System.out.println("Maximum loot value : " + maxLoot(input, input.length));
	}
	}

view raw MaxLoot.java hosted with ❤ by GitHub

Maximum sum of hour glass in matrix

Rather than explaining something more in detail, following sample input, output and explanation would help to understand what do we need to do for this problem.

Input:

int[][] input1 = {
    {1, 2, 3, 4, 5},
    {0, 5, 1, 5, 2},
    {0, 0, 0, 1, 3},
    {4, 1, 1, 0, 1},
    {0, 0, 0, 0, 3},
};

Output:
3   4   5
    5
0   1   3

Max Sum for input1 is: 21

Input:
int[][] input2 = {
    {3, 0, 0, 5},
    {2, 5, 5, 5},
    {0, 0, 0, 1},
    {4, 4, 0, 0},
    {0, 0, 3, 0},
};
Output:
2   5   5
    0
4   4   0

Max Sum for input2 is: 20

Input:
int[][] input3 = {
    {-1, -1, 0, -9, -2, -2},
    {-2, -1, -6, -8, -2, -5},
    {-1, -1, -1, -2, -3, -4},
    {-1, -9, -2, -4, -4, -5},
    {-7, -3, -3, -2, -9, -9},
    {-1, -3, -1, -2, -4, -5}
};

Output:
-1   -1   0
    -1
-1   -1   -1

Max Sum for input3 is: -6

    

      

        

  

    
    


        


  


  

        

          

          
public class MaximumSumOfHourGlassInMatrix {
        
        

          

          


        
        

          

          
  private static int[][] input1 = {
        
        

          

          
      {1, 2, 3, 4, 5},
        
        

          

          
      {0, 5, 1, 5, 2},
        
        

          

          
      {0, 0, 0, 1, 3},
        
        

          

          
      {4, 1, 1, 0, 1},
        
        

          

          
      {0, 0, 0, 0, 3},
        
        

          

          
  };
        
        

          

          


        
        

          

          
  private static int[][] input2 = {
        
        

          

          
      {3, 0, 0, 5},
        
        

          

          
      {2, 5, 5, 5},
        
        

          

          
      {0, 0, 0, 1},
        
        

          

          
      {4, 4, 0, 0},
        
        

          

          
      {0, 0, 3, 0},
        
        

          

          
  };
        
        

          

          


        
        

          

          


        
        

          

          
  private static int[][] input3 = {
        
        

          

          
      {-1, -1, 0, -9, -2, -2},
        
        

          

          
      {-2, -1, -6, -8, -2, -5},
        
        

          

          
      {-1, -1, -1, -2, -3, -4},
        
        

          

          
      {-1, -9, -2, -4, -4, -5},
        
        

          

          
      {-7, -3, -3, -2, -9, -9},
        
        

          

          
      {-1, -3, -1, -2, -4, -5}
        
        

          

          
  };
        
        

          

          


        
        

          

          
  public static void main(String args[]) {
        
        

          

          
    System.out.println("Max Sum for input1 is: " + findMaxSum(input1) + "\n");
        
        

          

          
    System.out.println("Max Sum for input2 is: " + findMaxSum(input2)+ "\n");
        
        

          

          
    System.out.println("Max Sum for input3 is: " + findMaxSum(input3)+ "\n");
        
        

          

          
  }
        
        

          

          


        
        

          

          
  private static int findMaxSum(int arr[][]) {
        
        

          

          
    int rowLength = arr.length;
        
        

          

          
    if (rowLength < 3) {
        
        

          

          
      System.err.println("Bad Input, row length must be 3 or more");
        
        

          

          
      return -1;
        
        

          

          
    }
        
        

          

          
    int colLength = arr[0].length;
        
        

          

          
    if (colLength < 3) {
        
        

          

          
      System.err.println("Bad Input, column length must be 3 or more");
        
        

          

          
      return -1;
        
        

          

          
    }
        
        

          

          


        
        

          

          
    int maxSum = Integer.MIN_VALUE;
        
        

          

          
    int tempMaxSum = Integer.MIN_VALUE;
        
        

          

          
    StringBuilder maxSumStr = new StringBuilder();
        
        

          

          
    String resultMaxSumStr = "";
        
        

          

          
    for (int i = 0; i < rowLength - 2; i++) {
        
        

          

          
      for (int j = 0; j < colLength - 2; j++) {
        
        

          

          
        int sum =
        
        

          

          
            arr[i][j]      + arr[i][j + 1]     +arr[i][j + 2]
        
        

          

          
                           + arr[i + 1][j + 1] +
        
        

          

          
            arr[i + 2][j]  +arr[i + 2][j + 1]  +arr[i + 2][j + 2];
        
        

          

          


        
        

          

          
        maxSum = Math.max(maxSum, sum);
        
        

          

          


        
        

          

          
        if (tempMaxSum < maxSum) {
        
        

          

          
          maxSumStr.append(arr[i][j]).append("   ").append(arr[i][j + 1]).append("   ")
        
        

          

          
              .append(arr[i][j + 2]).append("\n")
        
        

          

          
              .append("    ").append(arr[i + 1][j + 1]).append("\n")
        
        

          

          
              .append(arr[i + 2][j]).append("   ").append(arr[i + 2][j + 1]).append("   ")
        
        

          

          
              .append(arr[i + 2][j + 2]).append("\n\n");
        
        

          

          
          tempMaxSum = maxSum;
        
        

          

          
          resultMaxSumStr = maxSumStr.toString();
        
        

          

          
          maxSumStr = new StringBuilder();
        
        

          

          
        }
        
        

          

          
      }
        
        

          

          
    }
        
        

          

          
    System.out.print(resultMaxSumStr);
        
        

          

          
    return maxSum;
        
        

          

          
  }
        
        

          

          
}
        
  



    

  


      
      

        view raw
        
          MaximumSumOfHourGlassInMatrix.java
        
        hosted with ❤ by GitHub
      
    

Stack and Queue using Deque

Deque is double ended queue, which like the doubly linked list with having frond/head in the start and last/tail in the end of the list.

	/**
	* Author: Deepak Singhvi
	*/
	class Deque {
	private Integer data;
	Deque next;
	Deque prev;
	public Integer getData() {
	return data;
	}
	public void setData(Integer data) {
	this.data = data;
	}
	public Deque getNext() {
	return next;
	}
	public void setNext(Deque next) {
	this.next = next;
	}
	public Deque getPrev() {
	return prev;
	}
	public void setPrev(Deque prev) {
	this.prev = prev;
	}
	}

view raw Deque.java hosted with ❤ by GitHub

	/**
	* Author: Deepak Singhvi
	*/
	class DequeueImpl {
	private Deque head;
	private Deque tail;
	public DequeueImpl() {
	}
	public void insertAtFirst(Integer element) {
	Deque newNode = new Deque();
	newNode.setData(element);
	if (isEmpty()) {
	head = tail = newNode;
	} else {
	newNode.next = head;
	head.prev = newNode;
	head = newNode;
	}
	}
	public void insertAtLast(Integer element) {
	Deque newNode = new Deque();
	newNode.setData(element);
	if (isEmpty()) {
	head = tail = newNode;
	} else {
	newNode.prev = tail;
	tail.next = newNode;
	tail = newNode;
	}
	}
	public Integer removeFirst() {
	if (isEmpty()) {
	System.out.println("No element found");
	return null;
	}
	Integer value = head.getData();
	head = head.next;
	head.prev = null;
	return value;
	}
	public Integer removeLast() {
	if (isEmpty()) {
	System.out.println("No element found");
	return null;
	}
	Integer value = tail.getData();
	tail = tail.prev;
	tail.next = null;
	return value;
	}
	public boolean isEmpty() {
	return null == head ? true : false;
	}
	@Override
	public String toString() {
	if (isEmpty()) {
	return "";
	}
	StringBuilder sb = new StringBuilder();
	Deque temp = head;
	while (temp != null) {
	sb.append(temp.getData()).append("->");
	temp = temp.next;
	}
	return sb.toString();
	}
	}

view raw DequeueImpl.java hosted with ❤ by GitHub

Stack using Deque

Input:
push(1)
push(2)
push(3)
push(4)

Output:
4
3->2->1

	/**
	* Author: Deepak Singhvi
	*/
	public class StackDeque extends DequeueImpl {
	public static void main(String args[]) {
	StackDeque stack = new StackDeque();
	stack.push(1);
	stack.push(2);
	stack.push(3);
	stack.push(4);
	System.out.println(stack.pop());
	System.out.println(stack.toString());
	}
	public void push(Integer element) {
	insertAtFirst(element);
	}
	public Integer pop() {
	return removeFirst();
	}
	}

view raw StackDeque.java hosted with ❤ by GitHub

Queue using Deque

Input:
enqueue(1)
enqueue(2)
enqueue(3)
enqueue(4)

Output:
1
2->3->4

	/**
	* Author: Deepak Singhvi
	*/
	public class QueueDeque extends DequeueImpl {
	public static void main(String args[]) {
	QueueDeque queue = new QueueDeque();
	queue.enqueue(1);
	queue.enqueue(2);
	queue.enqueue(3);
	queue.enqueue(4);
	System.out.println(queue.dequeue());
	System.out.println(queue.toString());
	}
	public void enqueue(Integer element) {
	insertAtLast(element);
	}
	public Integer dequeue() {
	return removeFirst();
	}
	@Override
	public String toString() {
	return super.toString();
	}
	}

view raw QueueDeque.java hosted with ❤ by GitHub

Implementing Stack Using Queue

Implementing stack using two queues, where we push element to q2 and then move pop and add all the to q1. Swap q2 to q1 to proceed with pop or another push operation.

Input:
push(1)
push(2)
push(3)

pop()
pop()
pop()
pop()

Output:
1 :3
2 :2
3 :1
Queue Empty
4 :null

	import java.util.LinkedList;
	import java.util.Queue;
	/**
	* Author : Deepak Singhvi
	*/
	public class StackUsingQueue {
	private Queue<Integer> q1 = new LinkedList<>();
	private Queue<Integer> q2 = new LinkedList<>();
	public static void main(String args[]){
	StackUsingQueue s = new StackUsingQueue();
	s.push(1);
	s.push(2);
	s.push(3);
	System.out.println("1 :" + s.pop());
	System.out.println("2 :" + s.pop());
	System.out.println("3 :" + s.pop());
	System.out.println("4 :" + s.pop());
	}
	public void push(Integer element){
	q2.add(element);
	while(!q1.isEmpty()) {
	q2.add(q1.poll());
	}
	Queue<Integer> temp = q1;
	q1 = q2;
	q2 = temp;
	}
	public Integer pop() {
	if(q1.isEmpty()) {
	System.out.println("Queue Empty");
	return null;
	}
	return q1.poll();
	}
	}

view raw StackUsingQueue.java hosted with ❤ by GitHub

Queue Using Stack Data Structure

Implementing Queue Using Stack


Two approaches
1) Using Multiple Stacks

Input:
enque(4)
dequeue()
enque(2)
dequeue()
enque(7)
dequeue()

Output:
1: 4
2: 2
3: 7

	import java.util.Stack;
	/**
	* Author: Deepak Singhvi
	*/
	public class QueueUsingStack {
	private Stack<Integer> s1 = new Stack<Integer>();
	public static void main(String args[]) {
	QueueUsingStack q = new QueueUsingStack();
	q.enQueue(4);
	q.enQueue(2);
	q.enQueue(7);
	int counter = 1;
	System.out.println(counter++ + ": " + q.deQueue());
	System.out.println(counter++ + ": " + q.deQueue());
	System.out.println(counter++ + ": " + q.deQueue());
	}
	public void push(Integer element) {
	s1.push(element);
	}
	public Integer pop() {
	return s1.pop();
	}
	public Integer enQueue(Integer element) {
	return s1.push(element);
	}
	public Integer deQueue() {
	Integer value = null;
	Integer topElement = null;
	if(s1.isEmpty()) {
	System.out.println("Queue Empty");
	return null;
	}
	if(s1.size() == 1) {
	topElement = pop();
	}
	else {
	value = pop();
	topElement = deQueue();
	push(value);
	}
	return topElement;
	}
	}

view raw QueueUsingStack.java hosted with ❤ by GitHub

2) Using Single Stack and Recursive Method

Input:
enque(4)
dequeue()
enque(8)
enque(2)
dequeue()
enque(7)
dequeue()

Output:
1: 4
2: 2
3: 7
4: 8

	import java.util.Stack;
	/**
	* Author: Deepak Singhvi
	*/
	public class QueueUsingMultipleStack {
	private Stack<Integer> s1 = new Stack<Integer>();
	private Stack<Integer> s2 = new Stack<Integer>();
	public static void main(String args[]) {
	QueueUsingMultipleStack q = new QueueUsingMultipleStack();
	q.enQueue(4);
	q.enQueue(2);
	q.enQueue(7);
	int counter = 1;
	System.out.println(counter++ + ": " + q.deQueue());
	q.enQueue(8);
	while (!q.s1.isEmpty()) {
	System.out.println(counter++ + ": " + q.deQueue());
	}
	}
	public Integer enQueue(Integer element) {
	return s1.push(element);
	}
	public Integer deQueue() {
	if (s1.isEmpty()) {
	System.out.println("Queue Empty");
	return null;
	}
	while (!s1.isEmpty()) {
	s2.push(s1.pop());
	}
	Integer firstElement = s2.pop();
	while (!s2.isEmpty()) {
	s1.push(s2.pop());
	}
	return firstElement;
	}
	}

view raw QueueUsingMultipleStack.java hosted with ❤ by GitHub