INTERVIEW BIT SOLUTION

-

 1) Rotate Matrix

Interview Bit Solution using ArrayList

public class Solution {
public void rotate(ArrayList<ArrayList<Integer>> a) {
int n = a.get(0).size();
for(int i=0;i<n/2;i++)
{
for(int j=i;j<n-i-1;j++)
{
int temp = a.get(i).get(j);
int pp = a.get(n-j-1).get(i);
a.get(i).set(j, pp);
int oo = a.get(n-i-1).get(n-j-1);
a.get(n-j-1).set(i, oo);

int ll = a.get(j).get(n-i-1);

a.get(n-i-1).set(n-j-1,ll);


a.get(j).set(n-i-1,temp);
}
}
}
}
Using array


import java.util.Arrays;
public class Rotate2DArrayInPlace {

public static void main (String args [] ) throws Exception {

Integer [] [] myNxNArray = new Integer [][] {
{1, 2, 3},
{4,5,6},
{7,8,9}
};

System.out.println("SOURCE ARRAY: \n" + Arrays.deepToString(myNxNArray));
Integer [][] rotatedInPlace = rotateMatrixInPlaceCounterClockwise(myNxNArray);

System.out.println("ROTATED IN PLACE - 90 degrees COUNTER CLOCKWISE");
System.out.println(Arrays.deepToString(rotatedInPlace));

//The array referenced in above definition myNxNArray is changed so you will need to redefine
Integer [] [] myNxNArray1 = new Integer [][] {
{1, 2, 3},
{4,5,6},
{7,8,9}
};

Integer [][] rotatedInPlaceClockwise = rotateMatrixInPlaceClockwise(myNxNArray1);

System.out.println("ROTATED IN PLACE - 90 degrees CLOCKWISE");
System.out.println(Arrays.deepToString(rotatedInPlaceClockwise));

}

/**
* This method rotates the matrix 90 degrees counter clockwise without using extra buffer..
*/
public static Integer[][] rotateMatrixInPlaceCounterClockwise(Integer[][] matrix) throws Exception {
System.out.println("******************rotate**Matrix**InPlace**counter Clockwise**rotation****************");
if(matrix.length == 0 || matrix.length != matrix[0].length) {
throw new Exception ("Invalid Input");
}

int n = matrix[0].length;
int tmp;
for (int i = 0; i < n / 2; i++) {
for (int j = i; j < n - i - 1; j++) {

tmp = matrix[i][j];
System.out.println("tmp:"+tmp);
matrix[i][j] = matrix[j][n - i - 1];
System.out.println("matrix[j][n - i - 1]:"+matrix[j][n - i - 1]+" j: "+j+" i: "+i);
matrix[j][n - i - 1] = matrix[n - i - 1][n - j - 1];
System.out.println("matrix[n - i - 1][n - j - 1]:"+matrix[n - i - 1][n - j - 1]+" j: "+j+" i: "+i);
matrix[n - i - 1][n - j - 1] = matrix[n - j - 1][i];
System.out.println("matrix[n - j - 1][i]:"+matrix[n - j - 1][i]+" j: "+j+" i: "+i);
matrix[n - j - 1][i] = tmp;

}

}
return matrix;
}

/**
* This method rotates the matrix 90 degrees counter clockwise without using extra buffer..
*/
public static Integer[][] rotateMatrixInPlaceClockwise(Integer[][] matrix) throws Exception {
System.out.println("******************rotate**Matrix**InPlace**Clockwise**rotation****************");
if(matrix.length == 0 || matrix.length != matrix[0].length) {
throw new Exception ("Invalid Input");
}

int n = matrix.length;
System.out.println("n:"+n);
int top;
for (int i = 0; i < n / 2; i++) {

for (int j = i; j < n - i - 1; j++) {

top = matrix[i][j];
System.out.println("top:"+top);
System.out.println("top:"+top);
matrix[i][j] = matrix[n - j - 1][i];
System.out.println("matrix[n - j - 1][i]:"+matrix[n - j - 1][i]+" j: "+j+" i: "+i);
matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
System.out.println("matrix[n - i - 1][n - j - 1]:"+matrix[n - i - 1][n - j - 1]+" j: "+ j+" i: "+i);
System.out.println("matrix[n - i - 1][n - j - 1]:"+matrix[n - i - 1][n - j - 1]+" j: "+ j+" i: "+i);

matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
System.out.println("matrix[j][n - i - 1]:"+matrix[j][n - i - 1]+" j: "+j+" i: "+i);

matrix[j] [n - i - 1] = top;
System.out.println("matrix[j][n-i-1]:"+matrix[j][n-i-1]+" j: "+j+" i: "+i);


}

}
return matrix;
}

}

 OUTPUT:

SOURCE ARRAY: 
[[1, 2, 3], [4, 5, 6], [7, 8, 9]]
******************rotate**Matrix**InPlace**counter Clockwise**rotation****************
tmp:1
matrix[j][n - i - 1]:3 j: 0 i: 0
matrix[n - i - 1][n - j - 1]:9 j: 0 i: 0
matrix[n - j - 1][i]:7 j: 0 i: 0
tmp:2
matrix[j][n - i - 1]:6 j: 1 i: 0
matrix[n - i - 1][n - j - 1]:8 j: 1 i: 0
matrix[n - j - 1][i]:4 j: 1 i: 0
ROTATED IN PLACE - 90 degrees COUNTER CLOCKWISE
[[3, 6, 9], [2, 5, 8], [1, 4, 7]]
******************rotate**Matrix**InPlace**Clockwise**rotation****************
n:3
top:1
top:1
matrix[n - j - 1][i]:7 j: 0 i: 0
matrix[n - i - 1][n - j - 1]:9 j: 0 i: 0
matrix[n - i - 1][n - j - 1]:9 j: 0 i: 0
matrix[j][n - i - 1]:3 j: 0 i: 0
matrix[j][n-i-1]:1 j: 0 i: 0
top:2
top:2
matrix[n - j - 1][i]:4 j: 1 i: 0
matrix[n - i - 1][n - j - 1]:8 j: 1 i: 0
matrix[n - i - 1][n - j - 1]:8 j: 1 i: 0
matrix[j][n - i - 1]:6 j: 1 i: 0
matrix[j][n-i-1]:2 j: 1 i: 0
ROTATED IN PLACE - 90 degrees CLOCKWISE
[[7, 4, 1], [8, 5, 2], [9, 6, 3]]
Spiral Matrix Using ArrayList

public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public ArrayList<Integer> spiralOrder(final List<ArrayList<Integer>> A) {
ArrayList<Integer> pp = new ArrayList<Integer>();

int n = A.get(0).size();
int m = A.size();
int l =0;
int r = n-1;
int t=0, b =m-1;
int dir =0;
while(l<=r && t<=b)
{
if(dir==0)
{
for(int k=l;k<=r;k++)
{
int temp = A.get(t).get(k);
pp.add(temp);
}
t++;
}
else if(dir==1)
{
for(int k=t;k<=b;k++)
{
int temp = A.get(k).get(r);
pp.add(temp);
}

r--;
}
else if(dir==2){
for(int k=r;k>=l;k--)
{
int temp = A.get(b).get(k);
pp.add(temp);

}
b--;
}

else if(dir==3){
for(int k=b;k>=t;k--)
{
int temp = A.get(k).get(l);
pp.add(temp);

}
l++;

}
dir = (dir+1)%4;

}

return pp;

}
}

Check duplicates in o(n) using hashset
public class Solution {
    // DO NOT MODIFY THE LIST
    public int repeatedNumber(final List<Integer> a) {
        Set<Integer> set = new HashSet<Integer>();
        for(int num : a){
            if(set.contains(num)){
                return num;
            } else {
                set.add(num);
            }
        }
        return a.size()+1;
    }
}

MISSING AND REPEATING NUMBER
public class Solution {
// DO NOT MODIFY THE LIST. IT IS READ ONLY
public ArrayList<Integer> repeatedNumber(final List<Integer> A) {
int a[] = new int[A.size()+1];
ArrayList<Integer> k = new ArrayList<>();
for(int i=0;i<A.size();i++)
{
a[A.get(i)]++;
}

for(int j=0;j<a.length;j++)
{
if(a[j]==2)
{
k.add(j);
}
}

for(int i=1;i<a.length;i++)
{
if(a[i]==0)
{
k.add(i);
}


}

return k;

}
}

Largest Number InterViewBit

public class Solution {
public String largestNumber(final List<Integer> A) {

ArrayList<String> mm = new ArrayList<>();
for(int i=0;i<A.size();i++)
{
mm.add(String.valueOf(A.get(i)));

}
Collections.sort(mm, new Comparator<String>() {
@Override

public int compare(String o1, String o2) {
String s1 = o1 + o2;
String s2 = o2 + o1;
return s2.compareTo(s1);

}
});
int[] p=new int[A.size()];
for(int i=0;i<A.size();i++)
{
p[i]=A.get(i);
}
int flag=0;

for(int a:p)
{
if(a!=0)
{
flag=1;

}

}

if(flag==0)
{
return "0";
}
/*
for(int i=0;i<A.size()-1;i++)
{
for(int j=i+1;j<A.size();j++)
{
String first = String.valueOf(p[i]);
String second = String.valueOf(p[j]);

if((first+second).compareTo(second+first)<0)
{
int temp = p[i];
p[i] = p[j];
p[j] = temp;
}



}

}
*/
String result = String.join("", mm);

//String strOfInts = Arrays.toString(p).replaceAll("\\[|\\]|,|\\s", "");

return result;
}
}
Largest Contigous Subarray

class Solution {
public int findMaxLength(int[] nums) {

HashMap<Integer,Integer> aa = new HashMap<>();
aa.put(0,-1);//<SUM,INDEX>  //put sum<0,-1>
int count=0;
int maxlen=0;
for(int i=0;i<nums.length;i++)
{
if(nums[i]==0)
{
count-=1;
}
else{

count+=1;
}

if(aa.containsKey(count))
{ //<<current index>-<<stored index in hashmap>>
maxlen=Math.max(maxlen,i-aa.get(count));
}

else{
aa.put(count,i);
}
}

return maxlen;
}
}



Rotate String
class Solution {

public static String leftrotate(String str, int d)
{
String ans = str.substring(d) + str.substring(0, d);
return ans;
}
public static String rightrotate(String str, int d)
{
return leftrotate(str, str.length() - d);
}
public String stringShift(String s, int[][] shift) {

String pp =s;
for(int i=0;i<shift.length;i++)
{
for(int j=0;j<1;j++)
{
if(shift[i][0]==0)
{int d = shift[i][1];
pp= leftrotate(pp,d);
System.out.println("left vala "+pp);
}
else
{int d = shift[i][1];
pp= rightrotate(pp,d);
System.out.println("right vala "+pp);
}
}
}
return pp;
}
}
class Solution {

public static String leftrotate(String str, int d)
{
String ans = str.substring(d) + str.substring(0, d);
return ans;
}
public static String rightrotate(String str, int d)
{
return leftrotate(str, str.length() - d);
}
public String stringShift(String s, int[][] shift) {

String pp =s;


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

for(int j=0;j<1;j++)
{
if(shift[i][0]==0)
{int d = shift[i][1];
pp= leftrotate(pp,d);
System.out.println("left vala "+pp);
}
else
{int d = shift[i][1];
pp= rightrotate(pp,d);
System.out.println("right vala "+pp);
}
}
}


return pp;
}
}

Comments

Post a Comment

Popular posts from this blog

Interview Preparation Kit

-
Interview Preparation Resources : 1. Data Structures and Algorithms Must Do Problems on Topic Wise (GFG) Must Do Problems on Topic Wise (Practice) (GFG) Complete DSA Roadmap (InterviewBit) Abdul Bari Standard DSA Playlist (YT) Leetcode Problems 2. Programming Language OOPs Commonly Asked Questions 1 (GFG) Quiz (GFG) How to draw Class Diagrams (YT) C++ Commonly Asked Questions 1 (GFG) Commonly Asked Questions 2 (GFG) Quiz (GFG) Java Commonly Asked Questions 1 (GFG) Commonly Asked Questions 2 (GFG) Quiz (GFG) 3. Database Management Systems Most Important DBMS Questions + Video Crash Course (InterviewBit) SQL Syntax Ref Commonly Asked Questions 1 (GFG) Commonly Asked Questions 2 (GFG) SQL Problems (Leetcode) How to draw ER Diagram (YT) Sanchit Jain Complete Playlist (YT) 4. Operating Systems Commonly Asked Questions 1 (GFG) Sanchit Jain Complete Playlist (YT) Quiz (GFG) 5. System Design Usually not asked during Internship Interviews Gaura...
Read more

Dinosaurus_Island_Character_level_language_model

-
Image
Dinosaurus_Island_Character_level_language_model_final_v3a Character level language model - Dinosaurus Island ¶ Welcome to Dinosaurus Island! 65 million years ago, dinosaurs existed, and in this assignment they are back. You are in charge of a special task. Leading biology researchers are creating new breeds of dinosaurs and bringing them to life on earth, and your job is to give names to these dinosaurs. If a dinosaur does not like its name, it might go berserk, so choose wisely! Luckily you have learned some deep learning and you will use it to save the day. Your assistant has collected a list of all the dinosaur names they could find, and compiled them into this dataset . (Feel free to take a look by clicking the previous link.) To create new dinosaur names, you will build a character level language model to generate new names. Your algorithm will learn the different name patterns, and randomly generate new names. Ho...
Read more

How to crack the interviews and get a decent job?

-
How to crack the interviews and get a decent job? So, the organizations will be coming in many colleges soon, and conduct their shortlisting tests. Now, I will be talking very short and to the point. Each point is important. Basic Skill Set (BSS):  1. Quick implementation & debugging (practise questions on codeforces, hackerrank, participate in contests) 2. String Matching (important, KMP, Z-Algorithm, etc) 3. Binary Search , Sorting, STL (sets, maps, unordered set/map, vector, sort) - very very very useful 4. Data Structures - (Linked Lists, stacks, queues, BIT useful, Segment Tree - asked in Google) 5. Dynamic Programming - very very important (medium level problems, all companies ask) 6. Binary Trees & BST - super important! (All companies ask this) 7. DFS/BFS questions on Graphs (Dijsktra and flows are rarely asked) 8. DP on Trees (yes, an important topic) 9. Greedy, Backtracking - (Important, can be tricky) 10. Math Concepts like Prime Seive - Not that m...
Read more