Interview Preparation

Given a number find the smallest number that is greater than n, and has same number of digits as n. Input: n = "218765" Output: "251678" Input: n = "1234" Output: "1243" Input: n = "4321" Output: "Not Possible" Input: n = "534976" Output: "536479" Steps: Consider  3,2,8,4,1 1. Start from right and find the digit that is smaller than its next digit.     3, 2 < 8 >4 >1 2. Swap that digit with its next higher number in the right.     3, 2 , 8, 4 ,   1    (next higher digit of 2 is 4)     3, 4 ,8, 2 ,1 3. Reverse the digits to the right of that digit (4).    3,4,1,2,8 Code: import java.util.*; public class Solution {          static void findNextGreater(int[] a){         int n = a.length;         int position = -1;                  for(int i=n-1; i>0; i--){     ...

Given a matrix with sorted rows find the row with maximum number of 1's. Naive Solution: T: O(m*n)    In the outer loop select a row. In inner loop cont the number of 1's in that row. update the max count after every iteration. If we found count equal to column number then break. Because the count can be no more that. import java.util.*; public class Solution {       public static void main(String[] args) {         int[][] a = {{0,1,1,1},{0,0,1,1},{1,1,1,1},{0,0,0,0}};         int m = a.length;         int n = a[0].length;         int max = 0;         int row = -1;         for(int i=0; i<m; i++){             int count = n;             for(int j=0; j<n && a[i][j]==0; j++){                 count--;     ...

Given a string we have check contiguous substrings with same first and last characer. Input: abcab Output: 7 (a,abca,b,bcab, c, a, b) Naive Solution: T: O(n^2) S: O(1)      We initialize the count to length of the string as each and every element contribute to its length.       In the outer loop we will pick a element. In the inner loop we will compare it other elements and if they are equal we will increment the counter.  Code: import java.util.*; public class Solution {          public static void main(String[] args) {         String str = "aba";         char[] s = str.toCharArray();         int len = s.length;         int count = len;         for(int i=0; i<len-1; i++){             for(int j=i+1; j<len; j++){               ...

Method: 1. Reverse(0,d-1) 2. Reverse(d,n-1) 3. Reverse(0,n-1) Code: import java.util.*; public class Solution {          static void reverse(int[] a, int start, int end){         int temp = 0;         for(int i=start,j=end; i<j; i++,j--){             temp = a[i];             a[i] = a[j];             a[j] = temp;         }        return;     }          static void rotate(int[] arr, int d){         int n = arr.length;         reverse(arr,0,d-1);         reverse(arr,d,n-1);         reverse(arr,0,n-1);     }     public static void main(String[] args) {         int[] arr = {1, 2, 3, 4, 5, 6, 7};     ...

Given an matrix of zero's and ones if 1 is present at a[i][j] then make all elements in ith row and jth column to 1's. Input: 1 0 0 0 Output: 1 1 1 0 Solution 1 (Using two temporary arrays): T: O(m*n) S:O(m+n)    If we find  element 1  in the matrix then its row and column elements  will be 1. We will have two auxiliary arrays row[m] and column[j]. We will iterate through all the elements, if we find 1 in a[i][j] then we will set row[i] = 1 and column[j]=1.   Then we will iterate through elements and if the row or column value is set to one then that element's value is set to 1. Code: import java.util.*; public class Solution {     public static void main(String[] args) {         int[][] a = {{1,0},{0,0},{0,0}};         int m = a.length;         int n = a[0].length;         int[] row = new int[m];         int[] col = new i...