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:

  • -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 !!!

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Navneet Ojha

I am Indian by birth, Punjabi by destiny. Humanity is my religion. Love to eat, travel, read books and my million dreams keep me alive.