The Coding Shala

Home >> Interview Questions >> Intersection of two arrays Intersection of Two Arrays Solution In this post, you will learn how to find the intersection of two arrays and its solution in Java. Given two arrays, write a function to compute their intersection. Example 1: Input: nums1 = [1,2,2,1], nums2 = [2,2] Output:  [2] Example 2: Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4] Output:  [9,4] Note:  Each element in the result must be unique.  The result can be in any order. Java Program to find the Intersection of Two Arrays Approach 1: We can find the intersection of two arrays using two HashSets. Java Program:  class Solution { public int [] intersection ( int [] nums1 , int [] nums2 ) { Set < Integer > set = new HashSet < Integer >(); for ( int num : nums1 ) set . add ( num ); Set < Integer > result = new HashSet < Integer >(); ...

Home >> Interview Questions >> copy a linked list with random pointer Copy a Linked List with Random Pointer In this post, you will learn how to copy or clone a linked list with random pointer and its solution in Java.  A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.  Return a deep copy of the list not the reference of the original node. Example: Input: head = [[7,null],[13,0],[11,4],[10,2],[1,0]] Output: [[7,null],[13,0],[11,4],[10,2],[1,0]] Copy a Linked List with Random Pointer Java Solution Approach 1: Using HashMap - extra Space O(n). We can store all node as key and make new node as value. In the next loop can assign next and random pointer to the copied nodes. Java Program:  /* // Definition for a Node. class Node { public int val; public Node next; public Node random; public Node() {} ...

Home >> Interview Questions >> Flatten a Multilevel Doubly Linked List Flatten a Multilevel Doubly Linked List Solution In this post, you will learn how to flatten a multilevel doubly linked list in Java. You are given a doubly linked list which in addition to the next and previous pointers, it could have a child pointer, which may or may not point to a separate doubly linked list. These child lists may have one or more children of their own, and so on, to produce a multilevel data structure, as shown in the example below.  Flatten the list so that all the nodes appear in a single-level, doubly linked list. You are given the head of the first level of the list. Example: Input:  1---2---3---4---5---6--NULL          |          7---8---9---10--NULL                |               11--12--NULL ...

Home >> LeetCode >> Bulb Switcher LeetCode - Bulb Switcher Solution In this post, we will discuss LeetCode's Bulb Switcher Problem and its solution in Java. There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it's off or turning off if it's on). For the i-th round, you toggle every i bulb. For the n-th round, you only toggle the last bulb. Find how many bulbs are on after n rounds. Example: Input: 3 Output: 1 Explanation: At first, the three bulbs are [off, off, off]. After the first round, the three bulbs are [on, on, on]. After the second round, the three bulbs are [on, off, on]. After the third round, the three bulbs are [on, off, off].  So you should return 1 because there is only one bulb is on. Practice this problem on LeetCode(Click Here). Java Solution of Bulb Switcher Problem Let's ...

Home >> Interview Questions >> Longest Substring without repeating characters Longest Substring Without Repeating Characters Java Program In this post, you will learn how to find the length of the longest substring without repeating characters in a string and its Java solution. Given a string, find the length of the longest substring without repeating characters. Example 1: Input: "abcabcbb" Output: 3 Explanation: The answer is "abc", with a length of 3. Example 2: Input: "bbbbb" Output: 1 Explanation: The answer is "b", with a length of 1. Example 3: Input: "pwwkew" Output: 3 Java Solution of Longest Substring without Repeating Characters Approach 1: Using brute force by checking all the substrings.  We'll use HashSet to check if characters are unique or not. Time complexity: O(n^2) Space Complexity: O(n) Java Program:  class Solution { public i...

Home >> LeetCode >> Swap Nodes in Pairs LeetCode - Swap Nodes in Pairs Solution In this post, you will learn how to solve LeetCode's Swap Nodes in Pairs problem with Java Solution. We will solve this problem using recursion and iteration. Given a linked list, swap every two adjacent nodes and return its head.  You may not modify the values in the list's nodes, only nodes itself may be changed. Example: Given 1->2->3->4, you should return the list as 2->1->4->3. Practice this problem on  LeetCode(Click Here). Swap Nodes in Pairs Java Solution Approach 1: Iterative Solution. Java Program:  /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode swapPairs ( ListNode head ) { //check for null or 1 node if ( head == null || head . next == n...

Home >> Programming Questions >> New Year Chaos New Year Chaos Problem Solution In this post, you will learn how to solve New Year Chaos Problem and implement its solution in Java. Problem:   It's New Year's Day and everyone's in line for the Wonderland rollercoaster ride! There are a number of people queued up, and each person wears a sticker indicating their initial position in the queue. Initial positions increment from at the front of the line to at the back.  Any person in the queue can bribe the person directly in front of them to swap positions. If two people swap positions, they still wear the same sticker denoting their original places in line. One person can bribe at most two others.  For Example, if n=8 and Person 5 bribes Person 4, the queue will look like this: 1,2,3,5,4,6,7,8. Fascinated by this chaotic queue, you decide you must know the minimum number of bribes that took place to get the queue into its current state. Inpu...