Interview Prep Day — 3

In Continuation to below post

Interview Prep Day — 2

Today I solved easy leetcode questions by my self, on pen and paper, I made many mistakes still I am happy. It is always good to start from somewhere, rather than just wondering and wasting time.

Given a non-empty array of integers, every element appears twice except for one. Find that single one.

Solution:

public int singleNumber(int[] nums) {
int a = 0;
for (int i : nums) {
a ^= i;
}
return a;
}

The intersection of Two Arrays II

Solution:

I did it using HashMap, stored the value and frequency of the value in hashmap for the first array, then validated if the value exists as a key in the second array and is greater than 1, if yes deduct -1 from the frequency count, else remove the value from the map. Add the values to the list, return the list as an array.

Given an array nums, write a function to move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Example:

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

Note:

1. You must do this in-place without making a copy of the array.
2. Minimize the total number of operations.

Solution:

This was not an easy one for me, if I had to take extra space then I would have solved it easily, by finding out the count of zeros, and then taking the empty array of the same size as the input array, And adding all the non zero values in it and then all the zeros.

But it should be space-optimized. So the solution was to take two pointers one for iterating the array and one for checking the last non zero index. I will shift one by one all the non zero elements starting from 0 index and then increasing the count of non zero element index by one till the whole array is traversed. In this, my all nonzeros have been position at there correct places. Now I will simply place all the empty array with zeros.

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

Solution:

Brute Force Approach-

Iterate array and compare the sum with each value of the array if the sum is equal to the target value. But its complexity will be O(n²), we can optimize it.

By using O(n) space. I mean hashmap, where will store the complement of the value that is complement = target-nums[I]; iterate the whole array, if map contains the nuns[i] then print the result.

public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();

for(int i = 0; i < nums.length ; i++){
int complement = target — nums[i];
if(map.containsKey(nums[i])){
return new int[]{i, map.get(nums[i])};
}else{
map.put(complement, i);
}
}
return null;
}

Given an array, rotate the array to the right by k steps, where k is non-negative.

Solution:

The solution I was able to find was reversing the whole array and then reversing the first k elements in the array and then reverse the other half you will get the result. Simple and easy one.

There is another solution related to it which is the Juggling algorithm, but I struggled to understand it, hopefully, I will do it by tomorrow.

Also, I read the book Understanding Mysql Internals and did a few Java interview questions.

Understanding MySQL Internals — Chapter 1

For tomorrow also I will be reading the same book and will do some new Java interview questions and leetcode questions.

Happy Learning!!!