DEV Community: akbhairwal

6-10PM challenge problem #006 solution

akbhairwal — Wed, 03 Jun 2020 16:22:38 +0000

Shifted Array Search

Solution for the Problem#006 is provided in Java language.

Test cases :

Test case #1
input: [2], 2

Test case #2
input:[1,2], 2

Test case #3
input: [0,1,2,3,4,5], 1

Test case #4
input : [1,2,3,4,5,0], 0

Test case #5
input : [9,12,17,2,4,5], 17

Test case #6
input : [9,12,17,2,4,5,6], 4

Solution



static int shiftedArrSearch(int[] shiftArr, int num) {  
     if(shiftArr.length>0){
      return find(shiftArr,0,shiftArr.length-1,num);
    }else return -1;
  }
  
  
 static int find(int[] arr, int l, int h, int num){
    
   
    int median = (l+h)/2;
    if(arr[median]==num) return median;
     if(l==h) return -1;
      return Integer.max(find(arr,l,median,num), find(arr,median+1,h,num));
  }

6-10PM challenge problem #006

akbhairwal — Tue, 02 Jun 2020 17:34:08 +0000

Shifted Array Search

A sorted array of distinct integers shiftArr is shifted to the left by an unknown offset and you don’t have a pre-shifted copy of it. For instance, the sequence 1, 2, 3, 4, 5 becomes 3, 4, 5, 1, 2, after shifting it twice to the left.

Given shiftArr and an integer num, implement a function shiftedArrSearch that finds and returns the index of num in shiftArr. If num isn’t in shiftArr, return -1. Assume that the offset can be any value between 0 and arr.length - 1.

Explain your solution and analyze its time and space complexities.

Example



input:  shiftArr = [9, 12, 17, 2, 4, 5], num = 2 # shiftArr is the
                                                 # outcome of shifting
                                                 # [2, 4, 5, 9, 12, 17]
                                                 # three times to the left

output: 3 # since it’s the index of 2 in arr

Solution

6-10PM challenge problem #005 solution

akbhairwal — Tue, 02 Jun 2020 07:56:31 +0000

Flatten a Dictionary

Solution for the Problem#005 is provided in Java language.

Test cases :

Test case #1
input: {"Key1":"1","Key2":{"a":"2","b":"3","c":{"d":"3","e":"1"}}}

Test case #2
input:{"Key":{"a":"2","b":"3"}}

Test case #3
input: {"Key1":"1","Key2":{"a":"2","b":"3","c":{"d":"3","e":{"f":"4"}}}}

Test case #4
input : {"":{"a":"1"},"b":"3"}

Test case #5
input :
{"a":{"b":{"c":{"d":{"e":{"f":{"":"awesome"}}}}}}}

Test case #6
input : {"a":"1"}

Solution



static HashMap flattenDictionary(HashMap dict) {   
   HashMap out = new HashMap();
        putAllFlat(out, "", dict);
        return out;
  }
  
  
  static void putAllFlat(HashMapout, String key, Object dictMap) {
    HashMap objMap = (HashMap) dictMap;     
        for(Map.Entry eleMap : objMap.entrySet()){            
               if(eleMap.getValue() instanceof HashMap){
                   if(key.length()>0) {
                       putAllFlat(out, key+"."+eleMap.getKey(), eleMap.getValue());
                   }else {
                       putAllFlat(out, eleMap.getKey(), eleMap.getValue());
                   }
               
              }else {
                  if(eleMap.getKey().length()>0) {
                      if(key.length()>0) {
                          out.put(key+"."+eleMap.getKey(),eleMap.getValue().toString());
                      }else {
                          out.put(eleMap.getKey(),eleMap.getValue().toString());
                      }                   
                  }else {
                      
out.put(key,eleMap.getValue().toString());
                  }            
              }           
            }  
  }

6-10PM challenge problem #005

akbhairwal — Mon, 01 Jun 2020 03:53:15 +0000

Flatten a Dictionary

A dictionary is a collection of unique keys and their values. The values can typically be of any data type (i.e an integer, boolean, double, string etc) or other dictionaries (dictionaries can be nested). However, for this exercise assume that values are either an integer, a string or another dictionary.

Given a dictionary dict, write a method flattenDictionary that returns a flattened version of it .

If you’re using a compiled language such Java, C++, C#, Swift and Go, you may want to use a Map/Dictionary/Hash Table that maps strings (keys) to a generic type (e.g. Object in Java, AnyObject in Swift etc.) to allow nested dictionaries.

If a certain key is empty, it should be excluded from the output (see e in the example below).

Example



input:  dict = {
            "Key1" : "1",
            "Key2" : {
                "a" : "2",
                "b" : "3",
                "c" : {
                    "d" : "3",
                    "e" : {
                        "" : "1"
                    }
                }
            }
        }

output: {
            "Key1" : "1",
            "Key2.a" : "2",
            "Key2.b" : "3",
            "Key2.c.d" : "3",
            "Key2.c.e" : "1"
        }

Important: when you concatenate keys, make sure to add the dot character between them. For instance concatenating Key2, c and d the result key would be Key2.c.d.

Solution

6-10PM challenge problem #004

akbhairwal — Sat, 05 Oct 2019 19:35:47 +0000

Reverse Linked List

Example:

Input: 1->2->7->4->5->NULL
Output: 5->4->7->2->1->NULL
Follow up:

A linked list can be reversed either iteratively or recursively. Could you implement both?

6-10PM challenge problem #003 solution

akbhairwal — Sat, 05 Oct 2019 19:24:45 +0000

Problem#003

Count Island

private static int findIslandCount(int[][] binaryMatrix) {

    int count = 0;
    int[] arr = new int[2];
    Queue<int[]> queue = new LinkedList<int[]>();
    for (int i = 0; i < binaryMatrix.length; i++) {
        for (int j = 0; j < binaryMatrix[0].length; j++) {

            if (binaryMatrix[i][j] == 1) {
                arr[0] = i;
                arr[1] = j;
                queue.add(arr);
                bfs(binaryMatrix, i, j, queue);
                count++;
            }
        }
    }

    return count;
}

private static void bfs(int[][] binaryMatrix, int i, int j, Queue<int[]> queue) {

    int[] arr;
    int x, y;
    while (queue.size() != 0) {

        arr = queue.poll();
        x = arr[0];
        y = arr[1];
        binaryMatrix[x][y] = 0;
        if (x - 1 >= 0) {
            if (binaryMatrix[x - 1][y] == 1) {
                arr = new int[2];
                arr[0] = x - 1;
                arr[1] = y;
                queue.add(arr);
            }

        }
        if (x + 1 < binaryMatrix.length) {
            if (binaryMatrix[x + 1][y] == 1) {
                arr = new int[2];
                arr[0] = x + 1;
                arr[1] = y;
                queue.add(arr);
            }

        }

        if (y - 1 >= 0) {
            if (binaryMatrix[x][y - 1] == 1) {
                arr = new int[2];
                arr[0] = x;
                arr[1] = y - 1;
                queue.add(arr);
            }

        }
        if (y + 1 < binaryMatrix[0].length) {
            if (binaryMatrix[x][y + 1] == 1) {
                arr = new int[2];
                arr[0] = x;
                arr[1] = y + 1;
                queue.add(arr);
            }

        }

    }

}

6-10PM challenge problem #003

akbhairwal — Fri, 27 Sep 2019 20:04:48 +0000

Taking the difficulty level little higher. Today I am sharing a graph problem.

Island Count

A binaryMatrix which is 2D array of 0s and 1s. You need to find the number of island of 1s in this matrix.
Example input:

binaryMatrix =     [ [0,    1,    0,    1,    0],
                     [0,    0,    1,    1,    1],
                     [1,    0,    0,    1,    0],
                     [0,    1,    1,    0,    0],
                     [1,    0,    1,    0,    1] ]

An island can be defined as a group of adjacent values of all 1s.

Two cells, which have same value and next to each other in a single row or column are adjacent. (Diagonal two cells which have same value can't be considered as adjacent cells)

Explain and code the most efficient solution possible and analyze its time and space complexities.

[time limit] 5000ms

[input] array.integer arr

0 ≤ arr.length ≤ 20
[output] array.integer

Input : Above matrix

output 6 # since this is the number of islands in binaryMatrix.

Solution

6-10PM challenge problem #002 solution

akbhairwal — Thu, 26 Sep 2019 15:05:14 +0000

Problem#002

Array of Array Products

public  int[] solve(int[] arr) {
       int [] out = new int[arr.length];
       int product =1;

       for(int i=0;i<arr.length;i++){
           out[i]=product;
           product = product*arr[i];
        }

        product=1;
        for(int j=arr.length-1;j>=0;j--){
            out[j] = out[j]*product;
            product = product* arr[j];
        }
      return out;
   }

n is size of an array
Time complexity is O(n)
Space complexity is O(n)

6-10PM challenge problem #002

akbhairwal — Wed, 25 Sep 2019 18:38:39 +0000

Array of Array Products

There is an array 'arr' of Integers of size n, for every index i (from 0 to n) you can calculate product of all element integers except that element.
Solve without using division and analyze your solution’s time and space complexities.

Examples:

input: arr = [8, 10, 2]
output: [20, 16, 80] # by calculating: [10*2, 8*2, 8*10]

input: arr = [2, 7, 3, 4]
output: [84, 24, 56, 42] # by calculating: [7*3*4, 2*3*4, 2*7*4, 2*7*3]

Solution

Algorithm series 6-10PM challenge

akbhairwal — Wed, 25 Sep 2019 18:21:10 +0000

I have a habit to solve an algorithm and DS problem on daily basis. So I am thinking to share the same with you.
In daily routine I will be sharing a problem to solve. You can post the solution, we can discuss and evaluate the solution for space and time complexity. I will be sharing the solution next day.

6-10PM challenge problem #001 solution

akbhairwal — Wed, 25 Sep 2019 17:55:52 +0000

Problem#001

Move Zeros To End

public int[] moveZerosToEnd(int[] arr) {
    int j = 0;
    for (int i = 0; i < arr.length; i++) {
        if (arr[i] != 0) {
            arr[j] = arr[i];
            j++;
        }
    }
    for (; j < arr.length; j++) {
        arr[j] = 0;
    }

    return arr;
}

6-10PM challenge problem #001

akbhairwal — Tue, 24 Sep 2019 19:04:16 +0000

Move Zeros To End

An array 'arr' which have integers. You need to move all the zeros in the end of the array. You should preserve the relative order of other numbers in the array.

We should implement a solution that is more efficient than a naive brute force.

Example :
Given array arr = [12, 3, 0, 2, 8, 11, 0, 0, 6, 4, 0, 5, 7, 0, 8, 9, 0]
output: [12, 3, 2, 8, 11, 6, 4, 5, 7, 8, 9, 0, 0, 0, 0, 0, 0]

Solution