Java Interview Problems

Last Stone Weight

Each turn, we choose the two heaviest stones and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:

  • If x == y, both stones are totally destroyed;
  • If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x.

At the end, there is at most 1 stone left. …


Java Interview Problems

Two Sum III — Data structure design

add - Add the number to an internal data structure.
find - Find if there exists any pair of numbers which sum is equal to the value.

Example 1:

add(3); add(5); add(8);
find(8) -> true
find(4) -> false

Solution

class TwoSum {
List<Integer> list;
boolean isSorted=true;
public TwoSum() {
list = new ArrayList<>();
}
public void add(int number) {
list.add(number);
isSorted=false;
}
public boolean find(int value) {
if(!isSorted){
Collections.sort(list);
}
int leftPtr = 0;
int rightPtr = list.size()-1;
while(leftPtr < rightPtr){
int sum = list.get(leftPtr)+list.get(rightPtr);
if(sum == value){
return true;
}else if(sum < value){
leftPtr++;
}else{
rightPtr--;
}
}
return false;
}
}


LeetCode Java Solutions

124. Binary Tree Maximum Path Sum

Given a non-empty binary tree, find the maximum path sum.

For this problem, a path is defined as any sequence of nodes from some starting node to any node in the tree along the parent-child connections. The path must contain at least one node and does not need to go through the root.

Example 1:

Input: [1,2,3]       1
/ \
2 3
Output: 6

Example 2:

Input: [-10,9,20,null,null,15,7]   -10
/ \
9 20
/ \
15 7
Output: 42

Solution

/**
* Definition for a binary tree node.
* public class TreeNode {
*…

LeetCode Java Solutions

105. Construct Binary Tree from Preorder and Inorder Traversal

Given preorder and inorder traversal of a tree, construct the binary tree.

Note:
You may assume that duplicates do not exist in the tree.

For example, given

preorder = [3,9,20,15,7]
inorder = [9,3,15,20,7]

Return the following binary tree:

3
/ \
9 20
/ \
15 7

Solution

/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class…

LeetCode Java Solutions

290. Word Pattern

Given a pattern and a string str, find if str follows the same pattern.

Here follow means a full match, such that there is a bijection between a letter in pattern and a non-empty word in str.

Example 1:

Input: pattern = "abba", str = "dog cat cat dog"
Output: true

Example 2:

Input:pattern = "abba", str = "dog cat cat fish"
Output: false

Example 3:

Input: pattern = "aaaa", str = "dog cat cat dog"
Output: false

Example 4:

Input: pattern = "abba", str = "dog dog dog dog"
Output: false

Notes:
You may assume pattern


LeetCode Java Solutions

157. Read N Characters Given Read4

Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters.

Method read4:

The API read4 reads 4 consecutive characters from the file, then writes those characters into the buffer array buf.

The return value is the number of actual characters read.

Note that read4() has its own file pointer, much like FILE *fp in C.

Definition of read4:

Parameter:  char[] buf
Returns: int
Note: buf[] is destination not source, the results from read4 will be copied to buf[]

Below is a high…


LeetCode Java Solutions

434. Number of Segments in a String

Count the number of segments in a string, where a segment is defined to be a contiguous sequence of non-space characters.

Please note that the string does not contain any non-printable characters.

Example

Input: "Hello, my name is John"
Output: 5

Solution

class Solution {
public int countSegments(String s) {
s = s.trim();
if(s == null || s.isEmpty()){
return 0;
}
return s.split("\\s+").length;
}
}

LeetCode Java Solutions

47. Permutations II

Given a collection of numbers that might contain duplicates, return all possible unique permutations.

Example

Input: [1,1,2]
Output:
[
[1,1,2],
[1,2,1],
[2,1,1]
]

Solution

public List<List<Integer>> permuteUnique(int[] nums) {
Map<Integer,Integer> countMap = new HashMap<>();
for(int i=0; i< nums.length; i++){
countMap.put(nums[i],countMap.getOrDefault(nums[i],0)+1);
}
List<List<Integer>> output = new ArrayList<>();
int[] numArray = new int[countMap.size()];
int[] count = new int[countMap.size()];
Set<Integer> keyset = countMap.keySet();
int index=0;
for(Integer val : keyset){
Integer countVal = countMap.get(val);
numArray[index]=val;
count[index]=countVal;
index++;

}
int[] result = new int[nums.length];
calculaltePermutation(numArray, count,result, 0, output);
return output;

}

public void calculaltePermutation(int[] numArray, int[] count, int[] result, int level, List<List<Integer>> output){
if(level == result.length){
List<Integer> levelResult = new ArrayList<>();
for(int res:result){
levelResult.add(res);
}
output.add(levelResult);
}
for(int i=0; i< numArray.length; i++){
if(count[i]==0){
continue;
}
result[level]=numArray[i];
count[i]--;
calculaltePermutation(numArray,count,result,level+1,output);
count[i]++;
}
}

LeetCode Java Solutions

678. Valid Parenthesis String.

Given a string containing only three types of characters: ‘(‘, ‘)’ and ‘*’, write a function to check whether this string is valid. We define the validity of a string by these rules:

  1. Any left parenthesis '(' must have a corresponding right parenthesis ')'.
  2. Any right parenthesis ')' must have a corresponding left parenthesis '('.
  3. Left parenthesis '(' must go before the corresponding right parenthesis ')'.
  4. '*' could be treated as a single right parenthesis ')' or a single left parenthesis '(' or an empty string.
  5. An empty string is also valid.

Example 1:

Input: "()"
Output…

Java Programs for Sorting Algorithms

Insertion Sort

Advantages of Insertion Sort.

  • Efficient algorithm for small dataset.Also better than other O(n²) algorithms
  • Constant space complexity

How Insertion Sort Works

In each iteration, the algorithm removes one element from the input list and find the location of the element in the sorted list and inserts it there.

How Insertion Sort works

Iterative Method

public void insertionSortIterative(int[] array) {
for (int i = 1; i < array.length; i++) {…

Unnikrishnan

Software Engineer from Silicon Valley, having more than 10 years of experience in Software Development,Data Engineering, Data Modeling etc

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