Challenge

Project 2

JJenil Popat25 Jul 2022

public class GFG {

static void printPermutn(String str, String ans)
{

if (str.length() == 0) {
System.out.print(ans + " ");
return;
}

for (int i = 0; i < str.length(); i++) {

char ch = str.charAt(i);

String ros = str.substring(0, i) +
str.substring(i + 1);

printPermutn(ros, ans + ch);
}
}

public static void main(String[] args)
{
String s = "abc";
printPermutn(s, "");
}
}

import java.util.LinkedList;
import java.util.Queue;
import java.io.*;
import java.util.*;

class Node{
int data;
Node left;
Node right;
Node(int data){
this.data = data;
left=null;
right=null;
}
}

class GfG {

static Node buildTree(String str){

if(str.length()==0 || str.charAt(0)=='N'){
return null;
}

String ip[] = str.split(" ");

Node root = new Node(Integer.parseInt(ip[0]));

Queue queue = new LinkedList<>();

queue.add(root);
int i = 1;
while(queue.size()>0 && i < ip.length) {

Node currNode = queue.peek();
queue.remove();
String currVal = ip[i];

if(!currVal.equals("N")) {
currNode.left = new Node(Integer.parseInt(currVal));
queue.add(currNode.left);
}
i++;
if(i >= ip.length)
break;

currVal = ip[i];
if(!currVal.equals("N")) {
currNode.right = new Node(Integer.parseInt(currVal));
queue.add(currNode.right);
}
i++;
}

return root;
}
static void printInorder(Node root)
{
if(root == null)
return;

printInorder(root.left);
System.out.print(root.data+" ");

printInorder(root.right);
}

public static void main (String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

int t=Integer.parseInt(br.readLine());

while(t-- > 0){
String s1 = br.readLine();
String s2 = br.readLine();
Node root1 = buildTree(s1);
Node root2 = buildTree(s2);
Solution g = new Solution();
//System.out.println(g.isIdentical(root,roott));
boolean b = g.isIdentical(root1,root2);
if(b==true)
System.out.println("Yes");
else
System.out.println("No");
}
}
}

class Node{
int data;
Node left,right;
Node(int d){
data=d;
left=right=null;
}
}

class Solution
{

boolean isIdentical(Node root1, Node root2)
{

if(root1 == null && root2 == null) {
return true;
}

if(root1 == null || root2 == null) {
return false;
}

return (root1.data == root2.data) && isIdentical(root1.left,root2.left)
&& isIdentical(root1.Aright,root2.right);
}

}

4.LOWEST COMMON ANCESTOR IN A BINARY TREE:-The time complexity is O(n).

class Node
{
int data;
Node left, right;

public Node(int item)
{
data = item;
left = right = null;
}
}

public class BinaryTree
{

Node root;

Node findLCA(int n1, int n2)
{
return findLCA(root, n1, n2);
}

Node findLCA(Node node, int n1, int n2)
{

if (node == null)
return null;

if (node.data == n1 || node.data == n2)
return node;
Node left_lca = findLCA(node.left, n1, n2);
Node right_lca = findLCA(node.right, n1, n2);

if (left_lca!=null && right_lca!=null)
return node;

return (left_lca != null) ? left_lca : right_lca;
}

public static void main(String args[])
{
BinaryTree tree = new BinaryTree();
tree.root = new Node(1);
tree.root.left = new Node(2);
tree.root.right = new Node(3);
tree.root.left.left = new Node(4);
tree.root.left.right = new Node(5);
tree.root.right.left = new Node(6);
tree.root.right.right = new Node(7);
System.out.println("LCA(4, 5) = " +
tree.findLCA(4, 5).data);
System.out.println("LCA(4, 6) = " +
tree.findLCA(4, 6).data);
System.out.println("LCA(3, 4) = " +
tree.findLCA(3, 4).data);
System.out.println("LCA(2, 4) = " +
tree.findLCA(2, 4).data);
}
}

class shorting {

public static void main(String[] args)
{

int arr[] = { 4, 3, 2, 1 };

for (int i = 0; i < arr.length; i++) {

for (int j = i + 1; j < arr.length; j++) {
int temp = 0;
if (arr[j] < arr[i]) {

temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
System.out.print(arr[i] + " ");
}
}
}

6.SHORTEST SOURCE TO DESTINATION PATH

import java.io.*;
import java.util.*;
class ABC {
public static void main(String args[]) throws IOException {
BufferedReader read =
new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(read.readLine());
while (t-- > 0) {
int N, M, x, y;
String S[] = read.readLine().split(" ");
N = Integer.parseInt(S[0]);
M = Integer.parseInt(S[1]);
int a[][] = new int[N][M];
for (int i = 0; i < N; i++) {
String s[] = read.readLine().split(" ");
for (int j = 0; j < M; j++) a[i][j] = Integer.parseInt(s[j]);
}
String s1[] = read.readLine().split(" ");
x = Integer.parseInt(s1[0]);
y = Integer.parseInt(s1[1]);
Solution ob = new Solution();
System.out.println(ob.shortestDistance(N, M, a, x, y));
}
}
}

class Solution {
int shortestDistance(int N, int M, int A[][], int X, int Y) {

ArrayList<ArrayList> q = new ArrayList<ArrayList>();
ArrayList<ArrayList> q4 = new ArrayList<ArrayList>();
ArrayList q1 = new ArrayList();
int[][] visited = new int[N][M];
q1.add(0);
q1.add(0);

q.add(q1);
int count = 0;

if(A[0][0]==0)
{
return -1;
}

if(A[X][Y]==0)
{
return -1;
}

while(!q.isEmpty())
{

q4 = new ArrayList<ArrayList>();

for(ArrayList q2: q)
{
if(visited[q2.get(0)][q2.get(1)] == 0)
{
visited[q2.get(0)][q2.get(1)] = 1;
if(q2.get(0)>0)
{
if(A[q2.get(0)-1][q2.get(1)] == 1 && (visited[q2.get(0)-1][q2.get(1)] == 0))
{
if((q2.get(0)-1==X) && (q2.get(1)==Y))
{
return count + 1;
}

q1 = new ArrayList();
q1.add(q2.get(0)-1);
q1.add(q2.get(1));
q4.add(q1);
}
}

if(q2.get(1)>0)
{
if((A[q2.get(0)][q2.get(1)-1] == 1) && (visited[q2.get(0)][q2.get(1)-1] == 0))
{
if((q2.get(0)==X) && (q2.get(1)-1==Y))
{
return count + 1;
}

q1 = new ArrayList();
q1.add(q2.get(0));
q1.add(q2.get(1)-1);
q4.add(q1);
}
}

if(q2.get(1)<M-1)
{

if(A[q2.get(0)][q2.get(1)+1] == 1 && (visited[q2.get(0)][q2.get(1)+1] == 0))
{
if((q2.get(0)==X) && (q2.get(1)+1==Y))
{
return count + 1;
}

q1 = new ArrayList();
q1.add(q2.get(0));
q1.add(q2.get(1)+1);
q4.add(q1);
}
}

if(q2.get(0)<N-1)
{
if(A[q2.get(0)+1][q2.get(1)] == 1 && (visited[q2.get(0)+1][q2.get(1)] == 0))
{
if((q2.get(0)+1==X) && (q2.get(1)==Y))
{
return count + 1;
}

q1 = new ArrayList();
q1.add(q2.get(0)+1);
q1.add(q2.get(1));
q4.add(q1);
}
}

}
}
count = count+1;
q = new ArrayList<ArrayList>();
q.addAll(q4);
}
return -1;
}
};

7SHORTEST SOURCE TO DESTINATION PATH

8. circle string

import java.io.*;
import java.util.*;
import java.lang.*;

class circle
{
public static void main(String args[])throws IOException
{
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(in.readLine().trim());
while(t-->0){
String A[] = in.readLine().trim().split(" ");
int N = Integer.parseInt(A[0]);
A = in.readLine().trim().split(" ");

Solution ob = new Solution();
System.out.println(ob.isCircle(N, A));
}
}
}

class Solution {
public static void isCyclic(int i, ArrayList<ArrayList<Integer>> list, boolean[] visited) {
visited[i] = true;
for(Integer e: list.get(i)) {
if(!visited[e]) {
isCyclic(e, list, visited);
}
}
}

static int isCircle(int N, String A[]) {
int[] in = new int[26];
int[] out = new int[26];

ArrayList<ArrayList<Integer>> list = new ArrayList<>();

for(int i=0; i<26; i++) {
list.add(new ArrayList<Integer>());
}

for(int i=0; i<N; i++) {
in[A[i].charAt(0)-'a']++;
out[A[i].charAt(A[i].length()-1)-'a']++;
list.get(A[i].charAt(0)-'a').add(A[i].charAt(A[i].length()-1)-'a');
}

for(int i=0; i<26; i++) {
if(in[i] != out[i]) {
return 0;
}
}
boolean[] visited = new boolean[26];
isCyclic(A[0].charAt(0)-'a', list, visited);
for(int i=0; i<26; i++) {
if(in[i] != 0 && !visited[i]) {
return 0;
}
}
return 1;
}
}

9.rearrange

import java.util.*;
import java.lang.*;
import java.io.*;

class GFG {
public static void main (String[] args) {
try {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(br.readLine());
while (t-- > 0) {
String str = br.readLine();
Solution ob= new Solution();
String str1 = ob. rearrangeCharacters(str);

int flag=1;
int[] c = new int[26];
Arrays.fill(c,0);
for(int i=0; i<str.length(); i++)
c[str.charAt(i)-'a']+=1;
int f = 0;
int x = (str.length()+1)/2;
for(int i=0; i<26; i++)
{
if(c[i]>x)
f = 1;
}
if(f == 1)
{
if(str1=="-1")
System.out.println(0);
else
System.out.println(1);
}
else
{
int[] a = new int[26];
Arrays.fill(a,0);
int[] b = new int[26];
Arrays.fill(b,0);
for(int i=0; i<str.length(); i++)
a[str.charAt(i)-'a']+=1;
for(int i=0; i<str1.length(); i++)
b[str1.charAt(i)-'a']+=1;

for(int i=0; i<26; i++)
if(a[i]!=b[i])
flag = 0;

for(int i=0;i<str1.length();i++)
{
if(i>0)
if(str1.charAt(i-1)==str1.charAt(i))
flag=0;
}
if(flag==1)
System.out.println(1);
else
System.out.println(0);
}
}
} catch (Exception e) {

}
}
}

class Solution
{
static class Pair implements Comparable<Pair>{
char ch;
int f;
Pair(char ch,int f){
this.ch = ch;
this.f =f;
}
public int compareTo(Pair o){
return o.f -this.f;
}
}
public static String rearrangeCharacters(String str) {
PriorityQueue<Pair> pq = new PriorityQueue<>();
HashMap<Character,Integer> mp = new HashMap<>();
for(int i=0;i<str.length();i++){
char ch = str.charAt(i);
mp.put(ch,mp.getOrDefault(ch,0)+1);
}
for(char key:mp.keySet()){
pq.add(new Pair(key,mp.get(key)));
}
StringBuilder stb = new StringBuilder();
Pair pre = new Pair('#',-1);
while(pq.size()>0){
//System.out.print(stb);
Pair rem = pq.remove();
// System.out.println(rem.ch+" "+rem.f);
stb.append(rem.ch);
if(pre.f>0){
pq.add(pre);
}
rem.f--;
pre = rem;
}
if(stb.length()==str.length()){
return stb.toString();
}
return "-1";
}
}

10. longest dis

import java.io.*;
import java.util.*;
class long
{
public static void main(String args[])throws IOException
{
BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
int t = Integer.parseInt(read.readLine());
while(t-- > 0)
{
String S = read.readLine();

Solution ob = new Solution();
System.out.println(ob.longestSubstrDistinctChars(S));
}
}
}

class Solution{
static int longestSubstrDistinctChars(String s){

int l=0, r=0, n = s.length();
HashMap<Character, Integer> hm = new HashMap<>();
int maxL=0;
while(r<n){
char c1 = s.charAt(r);
if(hm.containsKey(c1)){
l=Math.max(hm.get(c1)+1, l);

}
hm.put(c1, r++);

maxL = Math.max(maxL, r-l);
}
return maxL;
}
}

11.power of 2

public boolean isPowerOfTwo(int n) {
if(n<=0)
return false;

while(n>2){
int t = n>>1;
int c = t<<1;

if(n-c != 0)
return false;

n = n>>1;
}

return true;
}

Project 2

Ship work like this
in your own course.

Talk to a career counsellor

Ship work like thisin your own course.

Talk to a career counsellor

Ship work like this
in your own course.