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) -> truefind(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   3Output: 6`

Example 2:

`Input: [-10,9,20,null,null,15,7]   -10   / \  9  20    /  \   15   7Output: 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

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

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.

`Parameter:  char[] buf    Returns:    intNote: 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

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

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