November 24, 2019

Part 2.1: Leet Code Solutions For Java Coding Interview Round

1). Remove K Digits

Given a non-negative integer number represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
The length of num is less than 10002 and will be ≥ k.
The given num does not contain any leading zero

Example 1: Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.

Example 2: Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.

Example 3: Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.

Steps:
  1. We will iterate for k times.
  2. In each iteration we will check remove the current digit if it's equal or smaller then next number.
  3. After iteration, we need to remove all the leading zeros.
GIT URL: Java Solution Of Leet Code's Remove K Digits problem

Java Solution

2). Reverse Linked List

Reverse a linked list from position m to n. Do it in one-pass.
Note:
  • 1 is less than or equal to m.
  • m is less than or equal to n.
  • n is less than or equal to the length of list.
Example:
Input: 1- > 2- > 3- > 4- > 5- > NULL, m = 2, n = 4
Output: 1- > 4- > 3- > 2- > 5- > NULL

Algorithm:-
Step 1: Decrement m and n until m reaches 1. After completion of step 1:
        a). m will become 1 and n will be equal to previous value of m.
        b). current will point to the element at n position.
        c). previous will be the previous of element at n position.

Step 2: Reverse the nodes until n becomes 0. After completion of step 2:
        a). m will remain 1, and n will be 0.
        b). current will point to the element at last position.
        c). previous will be the previous of element at the last position.
        d). previous will be the element at n position (n which was passed).
        e). ncurrent  will be the element at m position (m which was passed), nprevious will be its previous element.
Step 3: nprevious will point to previous and ncurrent will point to current.

GIT URL: Leet Code solution: Reverse a linked list from position m to n

Java Solution

3). Swap Nodes in Pairs

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.

GIT URL: Leet Code solution: Swap Nodes in Pairs solution

Java Solution

4). Number of Islands
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands.
An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:
Input:
11110
11010
11000
00000
Output: 1

Example 2:
Input:
11000
11000
00100
00011
Output: 3

Algorithm:
Iterate the 2D array, every-time you encounter the 1:
a). increase the island count

b). recursively replace all the horizontally/vertically land(1) with water(0).


GIT URL: Leet Code solution: Number of Islands solution
Java Solution

-K Himaanshu Shuklaa..

No comments:

Post a Comment