Java Interview - Algorithm & Data Structures Revision

Valid Parentheses

public boolean isValid(String s) {

Stack<Character> st = new Stack<>();

for(char c : s.toCharArray()){

if(c == '(') st.push(')');

else if(c == '{') st.push('}');

else if(c == '[') st.push(']');

else if(st.isEmpty() || st.pop() != c) return false;

}

return st.isEmpty();

}

Excel Sheet Column Title

public String convertToTitle(int n) {

StringBuilder result = new StringBuilder();

while(n > 0){

n--;

result.insert(0, (char) ('A' + n % 26));

n = n / 26;

}

return result.toString();

}

Two Sum IV - Input is a BST

public HashSet<Integer> hs = new HashSet<>();

public boolean findTarget(TreeNode root, int k) {

if(root == null) return false;

if(hs.contains(root.val)) return true;

else hs.add(k - root.val);

return (findTarget(root.left, k) || findTarget(root.right, k));

}

First Bad Version

public int firstBadVersion(int n) {

int start = 1; int end = n;

while(start < end){

int mid = start + (end - start) / 2;

if(!(isBadVersion(mid))) start = mid + 1;

else end = mid;

}

return start;

}

Remove duplicates in a sorted linked list

public ListNode deleteDuplicates(ListNode a) {

if(a == null) return a;

ListNode output = a;

while(a.next != null){

if(a.val == a.next.val) {a.next = a.next.next; continue;}

a = a.next;

}

return output;

}

Number of 1s in a number

public int numSetBits(long a) {

int count = 0;

while(a > 0){

count += a & 1;

a = a >>> 1;

}

return count;

}

List Cycle

public ListNode detectCycle(ListNode a) {
   ListNode slow = a; ListNode fast = a; boolean hasCycle = false;
   while(fast != null && fast.next != null && slow != null){
   slow = slow.next; fast = fast.next.next;
   if(fast == slow) {hasCycle = true; break; }
   }
   if(!hasCycle) return null;
   else{
   fast = a;
   while(slow != fast){
   slow = slow.next; fast = fast.next;
   }
   return slow;
   }

}

Given an array of integers, every element appears twice except for one. Find that single one.

public int singleNumber(final List<Integer> a) {
   int singlenum = 0;
   for(int i = 0; i < a.size(); i++){
   singlenum = singlenum ^ a.get(i);
   }
   return singlenum;
}

GCD

public int gcd(int A, int B) {
while(true) {
if (A == 0) return B;
if (B == 0) return A;
if (A > B) {
A = A % B;
} else {
B = B % A;
}
}
}

If String is palindrome utmost deleting one character

public boolean validPalindrome(String s) {

int l = -1, r = s.length();

while (++l < --r)

if (s.charAt(l) != s.charAt(r)) return isPalindromic(s, l, r+1) || isPalindromic(s, l-1, r);

return true;

}

public boolean isPalindromic(String s, int l, int r) {

while (++l < --r)

if (s.charAt(l) != s.charAt(r)) return false;

return true;

}

Birthday cake blowout

static int birthdayCakeCandles(int n, int[] ar) {
HashMap<Integer, Integer> heights = new HashMap<>(); int max = 0;
for(int i : ar){
max = Math.max(max, i);
if(heights.containsKey(i))heights.replace(i, heights.get(i)+1);
else heights.put(i, 1);
}
return heights.get(max);

}

12 Hour clock to 24 Hour clock

static String timeConversion(String s) {
if(s.charAt(s.length() - 2) == 'A') {
int hour = Integer.parseInt(s.substring(0,2));
if(hour == 12) return "00" + s.substring(2, s.length() - 2);
else return s.substring(0, s.length() - 2);
}
else{
int hour = Integer.parseInt(s.substring(0,2));
if(hour == 12) return s.substring(0, s.length() - 2);
return "" + (hour + 12) + s.substring(2, s.length() - 2);
}

}

Remove duplicates from sorted array (atmost 2 duplicates are ok)

public int removeDuplicates(int[] nums) {

int i = 0;

for(int n : nums){

if(i < 2 || n > nums[i-2]) nums[i++] = n;

}

return i;

}

Minimum absolute difference between two terms in an array

static int minimumAbsoluteDifference(int n, int[] arr) {
Arrays.sort(arr);
int min = arr[arr.length - 1] - arr[0];
System.out.println("Min : " + (arr[arr.length - 1] - arr[0]));
for(int i = 0; i < arr.length - 1; i++){
System.out.println(arr[i + 1] - arr[i]);
min = Math.min(min, arr[i + 1] - arr[i]);
}
return min;

}

If continuous subarray exists where sum is mod of K

public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};;
int runningSum = 0;
for (int i=0;i<nums.length;i++) {
runningSum += nums[i];
if (k != 0) runningSum %= k;
Integer prev = map.get(runningSum);
if (prev != null) {
if (i - prev > 1) return true;
}
else map.put(runningSum, i);
}
return false;

}

Sort 0,1,2

public void sortColors(int[] nums) {
int last = nums.length - 1;
int start = 0;
for(int i = 0; i < nums.length; i++){
while(nums[i] == 2 && i < nums.length - 1) {
nums[i] = nums[last];
nums[last--] = 2;
}
while(nums[i] == 0 && i > 0) {
nums[i] = nums[start];
nums[start++] = 0;
}
}
}

Hamming distance

public int totalHammingDistance(int[] nums) {
int total = 0;
for(int i = 0; i < nums.length - 1; i++){
int bitCount = 0;
for(int j = i + 1; j < nums.length; j++){
bitCount += (nums[i] >> j) & 1;
}
total += bitCount;
}
return total;
}

Number of paths in a graph

public int countComponents(int n, int[][] edges) {
if(n <= 1) return n;
HashMap<Integer, List<Integer>> hm = new HashMap<>();
for(int i = 0; i < n; i++) hm.put(i, new ArrayList<>());
for(int[] i : edges){
hm.get(i[0]).add(i[1]);
hm.get(i[1]).add(i[0]);
}
HashSet<Integer> hs = new HashSet<>();
int count = 0;
for(int i = 0; i < n; i++){
if(hs.add(i)){
dfs(i, hs, hm);
count++;
}
}
return count;
}
public void dfs(int i, HashSet<Integer> hs, HashMap<Integer, List<Integer>> hm){
for(int j : hm.get(i)){
if(hs.add(j)){
dfs(j, hs, hm);
}
}
}

Maximum size subarray

public int maxSubArrayLen(int[] nums, int k) {
HashMap<Integer, Integer> hm = new HashMap<>();
int sum = 0; int len = 0;
for(int i = 0; i < nums.length; i++){
sum += nums[i];
if(sum == k) len = Math.max(len, i + 1);
else if(hm.containsKey(sum - k)) len = Math.max(len, (i - hm.get(sum - k))); //difference is excess and seeing if it already calculated...if excess is removed, we have a match
if(!hm.containsKey(sum)) hm.put(sum, i);
}
return len;
}

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value

public int[] searchRange(int[] nums, int target) {
if(nums == null || nums.length <= 1) return null;
int start = 0; int end = nums.length; int st = 0; int en = 0;
while(start < end){
int mid = (start + end) / 2;
if (nums[mid] < target) start = mid + 1;
else end = mid;
}
int[] op = new int[2];
op[0] = end;
end = nums.length;
while(start < end){
int mid = (start + end) / 2 + 1;
if (nums[mid] > target) end = mid - 1;
else start = mid;
}
op[1] = end;
return op;
}

Longest common prefix

public String longestCommonPrefix(String[] strs) {
if(strs == null || strs.length == 0) return "";
if(strs.length == 1) return strs[0];
Arrays.sort(strs, (String a, String b) -> a.length() - b.length());
int maxLen = strs.length;
String currPrefix = strs[0];
for(int i = 1; i < strs.length; i++){
String nextWord = strs[i]; int ind = 0;
for(int j = 0; j < currPrefix.length(); j++){
if(currPrefix.charAt(j) != nextWord.charAt(j)){
currPrefix = currPrefix.substring(0,ind); break;
}
else ind++;
}
}
return currPrefix;
}

Merge intervals

public List<Interval> merge(List<Interval> intervals) {
List<Interval> op = new ArrayList<>();
if(intervals == null || intervals.size() == 0) return op;
Collections.sort(intervals, (Interval a1, Interval a2) -> a1.start - a2.start);
Interval curr = intervals.get(0);
for(int i = 1; i < intervals.size(); i++){
if(intervals.get(i).start <= curr.end){
curr.end = Math.max(intervals.get(i).end, curr.end);
}
else{
op.add(curr);
curr = intervals.get(i);
}
}
op.add(curr);
return op;
}

Find minimum element in rotated sorted array

public int findMin(int[] nums) {
if(nums == null || nums.length == 0) return 0;
int start = 0; int end = nums.length - 1;
while(start < end){
int mid = (start + end) / 2;
if(nums[mid] < nums[end]) end = mid;
else start = mid + 1;
}
return nums[start];
}

Given a list of parent - child relationship, determine if 2 nodes have a common anchestor apart from themselves.

public static boolean haveSharedAncestor(List<List<Integer>> pairs, int nodeA, int nodeB) {
HashMap<Integer, List<Integer>> cpMap = new HashMap<>(); //store child to parent relation

for(List<Integer> pair : pairs){
int child = pair.get(1);
int parent = pair.get(0);

List<Integer> temp = cpMap.getOrDefault(child, new ArrayList<Integer>());
temp.add(parent);

cpMap.put(child, temp);
}

Queue<Integer> childQ = new LinkedList<>();
childQ.offer(nodeA);
HashSet<Integer> pList = new HashSet<>();
while(!childQ.isEmpty()){
int curr = childQ.poll();
if(cpMap.containsKey(curr)){
for(int par : cpMap.get(curr)) {
pList.add(par);
childQ.offer(par);
}
}
}

childQ.offer(nodeB);
while(!childQ.isEmpty()){
int curr = childQ.poll();
if(cpMap.containsKey(curr)){
for(int par : cpMap.get(curr)) {
if(pList.contains(par)) return true;
childQ.offer(par);
}
}
}
return false;
}

Search This Blog

Java Easy to Understand - Interview Algorithm Practice