Interview Prep Day — 7

On the right track!!!

In continuation to the below post

Today I was too busy with my office work, but somehow I managed to not miss my daily learnings. I started with leetcode July challenge which was

Implement pow(x, n), which calculates x raised to the power n (xn).

Example 1:

Input: 2.00000, 10
Output: 1024.00000

Example 2:

Input: 2.10000, 3
Output: 9.26100

Example 3:

Input: 2.00000, -2
Output: 0.25000
Explanation: 2-2 = 1/22 = 1/4 = 0.25

Note:

  • n is a 32-bit signed integer, within the range [−231, 231 − 1]

The simplest and most optimized solution for this was to use pow() builtin function

return Math.pow(x, n);

The other method would be using recursion

public double myPow(double x, int n) {
return Math.pow(x, n);
if(n==0)
return 1;
if(n == 1) return x;
if(n % 2 == 0)
return pow(x * x, n/2);
return x * pow(x * x, n/2);
}
public double myPow(double x, int n) {
if(n < 0)
return 1.0/pow(x, -n);
return pow(x, n);
}
}

Then I read chapter 6 Thread-Based Request Handling from Mysql Internal book, after that started with Design patterns. I will soon start sharing my learning on design patterns.

Set Matrix Zeroes: Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in-place.

Example 1:

Input: 
[
[1,1,1],
[1,0,1],
[1,1,1]
]
Output:
[
[1,0,1],
[0,0,0],
[1,0,1]
]

Example 2:

Input: 
[
[0,1,2,0],
[3,4,5,2],
[1,3,1,5]
]
Output:
[
[0,0,0,0],
[0,4,5,0],
[0,3,1,0]
]

Follow up:

  • A simple improvement uses O(m + n) space, but still not the best solution.
  • Could you devise a constant space solution?

Because less time I solved this problem, using brute force and haven't thought about other solutions

  1. Then iterated the matrix and applied condition if flag is true at particular position, if yes then run 1 loop to change values to 0 for rows and another loop for setting values in column

public void setZeroes(int[][] matrix) {
boolean[][] flag = new boolean[matrix.length][matrix[0].length];
for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[0].length; j++){

if(matrix[i][j] == 0){
flag[i][j] = true;
}else{
flag[i][j] = false;
}
}
}

for(int i = 0; i < matrix.length; i++){
for(int j = 0; j < matrix[0].length; j++){
if(flag[i][j] == true){
for(int m = 0; m < matrix[0].length; m++){
matrix[i][m] = 0;
}
for(int n = 0; n < matrix.length; n++){
matrix[n][j] = 0;
}
}
}
}
}

I did another question from arrays and string

Given an array of strings, group anagrams together.

Example:

Input: ["eat", "tea", "tan", "ate", "nat", "bat"],
Output:
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]

Note:

  • The order of your output does not matter.

Solution:

the solution I have thought for,

  1. Sort the strings in the array
  2. take a hashmap
  3. check if a sorted string exists as a key in hashmap
  4. if yes then add then actual string in the list of the map.
  5. if no then create a list and add the actual string in the map
  6. iterate map and add all the values to result list

public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String, List<String>> map= new HashMap<>();

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

char[] words = strs[i].toCharArray();

Arrays.sort(words);

String sortedString = new String(words);

if(map.containsKey(sortedString)){
map.get(sortedString).add(strs[i]);
}else{
List<String> word = new ArrayList<>();
word.add(strs[i]);
map.put(sortedString, word);
}
}
List<List<String>> result = new ArrayList<>();
for (String s : map.keySet()) {
List<String> val = map.get(s);
result.add(val);

}
return result;
}

Happy Learning !!!