Part 1: Java Algorithms For Coding Interview Round

Two Sum 
Given an array of integers, return indices of the two numbers such that they add up to a specific target. Let us assume that each input would have exactly one solution, and you may not use the same element twice. e.g: nums = [1,2,8,9], target = 9, it will return [0,8]

Java Solution
import java.util.HashMap;
import java.util.Map;

public class TwoSum {

/*Brute Force: loop through each element x, find if there is another value that equals to target - x*/
public static int[] twoSumApproach1(int[] nums, int target) {
for (int i = 0; i  <  nums.length; i++) {
for (int j = 0; j  <  nums.length; j++) {
if (target == nums[j] + nums[i]) {
return new int[] { i, j };
}
}
}
throw new IllegalArgumentException("Result Not Found");
}

/*Two-pass Hash Map*/
public static int[] twoSumApproach2(int[] nums, int target) {
Map < Integer, Integer >  valMap=new HashMap <  > ();
for (int i = 0; i  <  nums.length; i++) {
valMap.put(nums[i], i);
}

int diff=0;
for (int j = 0; j  <  nums.length; j++) {
diff=target-nums[j];
if(valMap.containsKey(diff))
{
return new int[] {j, valMap.get(diff)};
}
}
throw new IllegalArgumentException("Result Not Found");
}

/*One-pass Hash Map*/
public static int[] twoSumApproach3(int[] nums, int target) {
Map < Integer, Integer >  valMap=new HashMap <  > ();
int diff=0;
for (int i = 0; i  <  nums.length; i++) {
diff=target-nums[i];
if(valMap.containsKey(diff))
{
return new int[] {i, valMap.get(diff)};
}
valMap.put(nums[i], i);
}
throw new IllegalArgumentException("Result Not Found");
}
public static void main(String args[]) {
int[] nums = new int[4];
nums[0] = 1;
nums[1] = 2;
nums[2] = 8;
nums[3] = 9;

int target = 9;
int result[] = twoSumApproach1(nums, target);
System.out.println("[" + result[0] + ", " + result[1] + "]");
}
}

Intersection of Two Arrays
Given two arrays, write a function to compute their intersection such that each element in the result must be unique.  e.g
1). nums1=[1,3,4,5,3], nums2=[3,8]
output=[3]
2). nums1=[1,1,4,5,8,9,7,9], nums2=[9,1,1,9]
output=[9,1]

Java Solution
import java.util.HashSet;
public class TwoArraysIntersection {

public static int[] intersection1(int[] nums1, int[] nums2) {
HashSet < Integer >  set1=new HashSet <  > ();
HashSet < Integer >  set2=new HashSet <  > ();

//This will remove duplicates from both the arrays
for(Integer i:nums1)
set1.add(i);

for(Integer j:nums2)
set2.add(j);

int interSize=(set1.size() > set2.size())?set1.size():set2.size();
int [] interArray=new int[interSize];
int interArraySize=0;
for(Integer s:set1)
{
if(set2.contains(s))
{
interArray[interArraySize++]=s;
}
}
return interArray;
}
public static int[] intersection(int[] nums1, int[] nums2) {
HashSet < Integer >  set1=new HashSet <  > ();
HashSet < Integer >  set2=new HashSet <  > ();

//This will remove duplicates from both the arrays
for(Integer i:nums1)
set1.add(i);

for(Integer j:nums2)
set2.add(j);
set1.retainAll(set2);
int [] interArray=new int[set1.size()];
int interArraySize=0;
for(Integer s:set1)
{
interArray[interArraySize++]=s;
}
return interArray;
}
public static void main(String[] args) {
// int[] nums1 = new int[5];
// nums1[0]=1; nums1[1]=3;
// nums1[2]=4;nums1[3]=5;
// nums1[4]=3;
//
// int[] nums2 = new int[2];
// nums2[0]=3; nums2[1]=3;

int[] nums1 = new int[8];
nums1[0]=1; nums1[1]=31;
nums1[2]=4; nums1[3]=5;
nums1[4]=8; nums1[5]=9;
nums1[6]=7; nums1[7]=9;

int[] nums2 = new int[4];
nums2[0]=9; nums2[1]=1;
nums2[2]=1; nums2[3]=9;

int [] interArray=intersection(nums1, nums2);
for(Integer i:interArray)
{
System.out.println(i);
}
}
}

First Unique Character in a String
Find the first non-repeating character in it and return it's index. If it doesn't exist, return -1. e.g:
1). peepsico, output: 4
2). tiger, output:0

Java Solution
import java.util.HashSet;
public class FirstUniqueChar {

public static String getFirstUniqueChar(String str)
{
HashSet < String >  uniqueStr=new HashSet <  > ();
int tmp=1;
String firstUniqueChar="", tempStr="";
for(int i=0;i < str.length();i++)
{
tempStr=str.substring(i, tmp++);
if(!uniqueStr.add(tempStr))
{
firstUniqueChar=tempStr;
break;
}
}
return firstUniqueChar;
}
public static void main(String[] args) {
String str="peep";
System.out.println("First Unique Char from the string '"+str+"' is '"+getFirstUniqueChar(str)+"'");
}
}
Subarray Sum Equals X
Write a function which will take an array of integers and an integer X. You need to find the total number of continuous subarrays whose sum equals to X. e.g:
nums=[2,2,2], X=4
output=2

JAVA Solution
import java.util.HashMap;
public class SubarraySumEquals {
public static int subarraySum(int[] nums, int k) {
        int count = 0, sum = 0;
        HashMap < Integer, Integer >  map = new HashMap  <   >  ();
        map.put(0, 1);
        for (int i = 0; i  <  nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k))
                count += map.get(sum - k);
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        System.out.println(map);
        return count;
    }
public static void main(String[] args) {
int[] nums = {1,3,1,3,1,1,1,1};

int k=4;
System.out.println(subarraySum(nums, k));
}
}

Linked List Cycle (Detect loop in a linked list)
Write down a function, which take head node of a linked list as an input and returns true of a linked list has loop, else it will return false.
There are two approaches to check this:
1). HashSet/ HashTable approach: detectLoop() will go through each node one by one and record each node's reference (or memory address) in a hash set. If the current node is null, we have reached the end of the list and it must not be cyclic. If current node’s reference is in the hash set, then return true.
2). Two Pointer Approach: detectLoopTwoPointers() has two pointers, slow pointer moves one step at a time while the fast pointer moves two steps at a time. If there is no cycle, the fast pointer will eventually reach the end(next node will be null, in this case we can return false). In case of a cyclic list and imagine the slow and fast pointers are two runners racing around a circle track. The fast runner will eventually meet the slow runner.

Java Solution
import java.util.HashSet;
public class LinkedListCycle {

static Node head;
public static Node newNode(int data) {
return new Node(data);
}
static public void push(int new_data) 
{ 
Node new_node = newNode(new_data); 
/*Make next of new Node as head */
new_node.next = head; 
/*Move the head to point to new Node */
head = new_node; 
} 
static boolean detectLoop(Node node) 
{
if (node == null || node.next == null) {
return false;
}
HashSet < Node >  s = new HashSet < Node > (); 
while (node != null) {
if (s.contains(node))
{
System.out.println(node.getData()+", already visited");
return true;
}
s.add(node);
node = node.next;
}
return false;
}

public boolean detectLoopTwoPointers(Node node) {
    if (node == null || node.next == null) {
        return false;
    }
    Node slow = node;
    Node fast = node.next;
    while (slow != fast) {
        if (fast == null || fast.next == null) {
            return false;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return true;
}
public static void main(String[] args) {
LinkedListCycle linkedList=new LinkedListCycle();
linkedList.push(1); 
linkedList.push(2); 
linkedList.push(3); 
linkedList.push(4);
linkedList.push(5);
linkedList.push(6);
/*Create loop for testing */
linkedList.head.next.next.next.next.next = linkedList.head.next.next;
if (detectLoop(head)) 
            System.out.println("Loop found"); 
        else
            System.out.println("Loop not found"); 
}
}
class Node {
int data;
Node next;

Node(int d) {
data = d;
next = null;
}
public int getData() {
return data;
}

}

How to insert (in sorted way) an element in a sorted linked list?
Steps:
1). Check if list is empty, if yes make the new node as head and return it.
2). Else, if the value of the node to be inserted is smaller than the value of the head node, insert the node at the start and make it head.
3). In a loop find the appropriate node after which the new node can be inserted, to do this keep moving until you reach a node who's value is greater than the input node.
4). Insert the new node before the node found in above step.

Java Solution
public class LinkedList {
class Node {
int data;
Node next;

Node(int d) {
data = d;
next = null;
}
}

Node head;

public Node newNode(int data) {
return new Node(data);
}

void sortedInsert(Node newNode) {
Node current;
if (head == null || head.data  > = newNode.data) {
newNode.next = head;
head = newNode;
} else {
current = head;
while (current.next != null && current.next.data  <  newNode.data) {
current = current.next;
}

newNode.next = current.next;
current.next = newNode;
}
}
}

Write a function to delete a given node from a Singly linked list, you need to follow below constraints:
1). This function must accept a pointer to the start node as first parameter and node to be deleted as the second parameter.
2). This function should not return a pointer to the head node.
3). It should not accept pointer to pointer to head node.

deleteNode() function needs to modify head pointer when the node to be deleted is the first node, for this we copy the data of the next node to head and delete the next node.
Else, when a deleted node is not the head node we find the previous node and changing next of the previous node.

Java Solution.
void deleteNode(Node node, Node delNode) { 
     // When node to be deleted is head node 
     if (node.data == delNode.data) { 
     if (node.next == null) { 
          System.out.println("There is only one node in the list"); 
          return; 
     } 
     /* Copy the data of next node to head */
     node.data = node.next.data; 
     // store address of next node 
     delNode = node.next; 
     // Remove the link of next node 
     node.next = node.next.next; 
     // free memory 
     System.gc(); 
     return; 
     } 

     Node prev = node; 
     while (prev.next != null && prev.next != delNode) { 
          prev = prev.next; 
     } 

     // Check if node really exists in Linked List 
     if (prev.next == null) { 
          System.out.println("Given node is not present in Linked List"); 
          return; 
     } 
     // Remove node from Linked List 
     prev.next = prev.next.next; 
     // Free memory 
     System.gc(); 
     return; 
}

Reverse Linked List
Write a function which will reverse a singly linked list using stacks.

Java Solution
import java.util.LinkedList;

public class ReverseLinkedList {
public static LinkedList < Integer >  reverseLinkedList(LinkedList < Integer >  linkedList)
{
LinkedList < Integer >  reversedLinkedList=new LinkedList < Integer > ();
for(int i=linkedList.size()-1;i > =0;i--)
{
reversedLinkedList.add(linkedList.get(i));
}
return reversedLinkedList;
}

public static void main(String[] args) {
LinkedList < Integer >  linkedList=new LinkedList <  > ();
linkedList.add(1);
linkedList.add(2);
linkedList.add(3);
linkedList.add(4);
LinkedList < Integer >  reversedLinkedList=reverseLinkedList(linkedList);
System.out.println("Printing reversed list..");
for (Integer i:reversedLinkedList)
{
System.out.print(i+" ");
}
}
}

Java Solution To Reverse A Linked List in Iterative Way
1). Change the current node's next pointer to point to its previous element. But before doing it, we need to save the previous element since node does not have reference to its previous node.
2). Another pointer to store the next node before changing the reference.
 public Node reverseList(Node head) {
Node previousNode=null;
Node currentNode=head;
Node nextNode=null;
while(currentNode!=null)
{
nextNode=currentNode.next;
nextNode=previousNode;
previousNode=currentNode;
currentNode=nextNode;
}
return previousNode;
}

Java Solution To Reverse A Linked List in Recursive Way
public Node reverseListRecersevily(Node head) {
if(head==null || head.next==null)
return head;
Node node=reverseListRecersevily(head.next);
head.next.next=head;
head.next=null;
return node;
}

Merge a Linked List into another at alternate positions

When size of List1 is greater than or equal to List 2, after merging second list should become empty. The nodes of second list should only be inserted when there are positions available. Also, using extra space is not allowed (Not allowed to create additional nodes), i.e., insertion must be done in-place. e.g:
1).
Input:
List1=A- > V- > M- > L- > N
List2=B- > C- > P- > O- > Z
Output:
List1=A- > B- > V- > C- > M- > P- > L- > O- > N- > Z
List2=Empty

2).
Input:
List1=A- > V- > M
List2=B- > C- > P- > O- > Z
Output:
List1=A- > B- > V- > C- > M- > P
List2=L- > O- > N- > Z

Java Solution:
class LinkedList 
{ 
Node head;
class Node {
int data;
Node next;

Node(int d) {
data = d;
next = null;
}
}

void push(int newData) 
{ 
Node newNode = new Node(newData); 
newNode.next = head; 
head = newNode; 
} 
void merge(LinkedList list2) {
Node a_curr = head, b_curr = list2.head;
Node a_next=null, b_next=null;

while (a_curr != null && b_curr != null) {
a_next = a_curr.next;
b_next = b_curr.next;

//make b_curr as next of a_curr
b_curr.next = a_next;
a_curr.next = b_curr;

//update current pointers for next iteration
a_curr = a_next;
b_curr = b_next;
}
list2.head = b_curr;
}

void printList() {
Node temp = head;
while (temp != null) {
System.out.print(temp.data + " ");
temp = temp.next;
}
System.out.println();
}

public static void main(String args[]) 
{ 
LinkedList list1 = new LinkedList(); 
list1.push(3); 
list1.push(2); 
list1.push(1); 
System.out.println("First Linked List:"); 
list1.printList(); 

LinkedList list2 = new LinkedList(); 
list2.push(8); 
list2.push(7); 
list2.push(6); 
list2.push(5); 
list2.push(4); 
System.out.println("Second Linked List:"); 
list2.printList();

System.out.println("Merging List"); 
list1.merge(list2); 

System.out.println("Merged first linked list:"); 
list1.printList(); 
System.out.println("Modified second linked list:"); 
list2.printList(); 
} 
}

Reverse a given String without changing the position of special characters
Write a function, which will take a String and reverse it in a way that special characters are not affected. E.g: Input: "qw,er$t". Output: "tr,ew$q"

Simplest solution to do this:
1). Create a temporary character array say temp[] and copy alphabetic characters from the input
2). Reverse temp[] using standard string reversal algorithm.
3). Traverse the input string and temp[] in a single loop. Wherever there is alphabetic character is input string, replace it with current character of temp[].

Time complexity of the above solution is O(n), and it requires extra space to store temp[], also it does two traversals of input string.

We can so the reverse with one traversal and that too without extra space, by using below solution:
1). Lets say 'str' is the input string with the length n.
2). Lets say l=0 and r=n-1;
3). write a while loop where i is less than r and perform below steps:
3.a). If str[l] is special character, do l++
3.b). Else, If str[r] is special character, do r--
3.c). Else swap str[l] and str[r]

Java Solution
public class ReverseStringSplChar {
public static void main(String[] args) {
String str = "qw,er$t"; 
System.out.println("Input string: " + str);
     char[] charArray = str.toCharArray(); 
     reverseString(charArray);
     String revStr = new String(charArray); 
     System.out.println(revStr);
}

public static void reverseString(char[] charArray) {
int l = 0, r = charArray.length - 1;
while (l < r) {
if (!Character.isAlphabetic(charArray[l]))
l++;
else if (!Character.isAlphabetic(charArray[r]))
r--;
else {
char tmp = charArray[l];
charArray[l] = charArray[r];
charArray[r] = tmp;
l++;
r--;
}
}
}
}

-K Himaanshu Shuklaa..