Interview Prep Day — 7

On the right track!!!

In continuation to the below post

Interview Prep Day — 6

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:

• -100.0 < x < 100.0
• 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 straight forward solution using O(mn) space is probably a bad idea.
• 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. For solving this problem I had taken m * n array to store the boolean as true where zero exists.
2. 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:

• All inputs will be in lowercase.
• The order of your output does not matter.

Solution:

the solution I have thought for,

1. Iterate the array
2. Sort the strings in the array
3. take a hashmap
4. check if a sorted string exists as a key in hashmap
5. if yes then add then actual string in the list of the map.
6. if no then create a list and add the actual string in the map
7. 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 !!!