DEV Community: Dharani

DNS resolver

Dharani — Mon, 23 Mar 2026 16:46:12 +0000

DNS(Domain name system)

1) It converts Domain name -> IP address

Ex domain: WWW. google.com

sub domain : www
second level domain : google
top level domain : .com

2) work flow:
i) root server: it does not know the ip, it undergoes .com servers
ii) Tld server: it does not know exact ip, ask the server google.com
iii) Sld server: it knows the actual ip, so it returns the ip address of what we have searched.

3) simple flow diagram:
user-> root -> tld(.com) -> sld(google.com) -> ip address

IP Address and Subnet

Dharani — Mon, 23 Mar 2026 16:38:22 +0000

IP:
Internet protocol is a unique number assigned to each device on a network.
ex: 192.168.0.1
made up of four parts separated by dots
IP has two parts( Network part, Host part)

Network part:
Identifies which the network the device belongs to
ex: first 3 parts of IP is network part

Host part:
Identifies which device inside the network
ex: last part of IP is host part

it has 2 version (ipv4 & ipv6)

1) IPv4 address:
it has 32bit address
consider(0-255)
128 64 32 16 8 4 2 1 (add each element)

2) IPv6 address:
it has 128 bit address

SUBNET:
subnet = dividing a larger network into smaller networks

Two Sum and Sorted Two Sum

Dharani — Sun, 22 Mar 2026 05:40:50 +0000

Introduction

The Two Sum problem is one of the most popular questions in programming interviews. It helps in understanding arrays, hashing, and two-pointer techniques.

Problem Statement

Two Sum

Given an array of integers and a target value, return the indices of the two numbers such that they add up to the target.

Two Sum II (Sorted Array)

Given a sorted array, find two numbers such that they add up to a target. Return their indices.

💡 Approach 1: Two Sum (Using Hash Map)

Create a dictionary to store numbers and their indices
For each element:
- Find complement = target - element
- Check if complement exists in dictionary
If yes → return indices

Python Code (Two Sum)


python
def two_sum(nums, target):
    hashmap = {}

    for i, num in enumerate(nums):
        complement = target - num

        if complement in hashmap:
            return [hashmap[complement], i]

        hashmap[num] = i

Approach 2: Two Sum II (Sorted Array - Two Pointer)
Use two pointers:
left = 0
right = n - 1
Calculate sum:
If sum == target → return indices
If sum < target → move left
If sum > target → move right

python code (sorted Two sum)

def two_sum_sorted(nums, target):
    left, right = 0, len(nums) - 1

    while left < right:
        total = nums[left] + nums[right]

        if total == target:
            return [left, right]
        elif total < target:
            left += 1
        else:
            right -= 1


## Input
 nums = [2, 7, 11, 15]
 target = 9

## output
 [0,1]

Kadanes Algorithm - p2

Dharani — Sun, 22 Mar 2026 05:31:50 +0000

Introduction

Kadane’s Algorithm is an efficient method used to find the maximum sum of a contiguous subarray within a given array. It is widely used in dynamic programming and interview problems.

Problem Statement

Given an array of integers, find the maximum sum of a contiguous subarray (containing at least one element).

A subarray is a continuous part of an array.

Approach (Kadane’s Algorithm)

We use two variables:

current_sum → stores current subarray sum
max_sum → stores maximum sum found so far

Steps:

Initialize:
- current_sum = 0
- max_sum = -∞
Traverse the array:
- Add element to current_sum
- Update max_sum
- If current_sum becomes negative → reset to 0

Python Code


python
def kadane(arr):
    current_sum = 0
    max_sum = float('-inf')

    for num in arr:
        current_sum += num
        max_sum = max(max_sum, current_sum)

        if current_sum < 0:
            current_sum = 0

    return max_sum

# Example
arr = [2, 3, -8, 7, -1, 2, 3]
print("Maximum Subarray Sum:", kadane(arr))


## Input
[2, 3, -8, 7, -1, 2, 3]

## output
11

subarray: [7, -1, 2, 3]

First and Last Occurences

Dharani — Sun, 22 Mar 2026 05:23:46 +0000

Introduction

Finding the first and last occurrences of an element is a common problem in arrays. It is especially useful in searching and indexing tasks.

Problem Statement

Given a sorted array and a target value, find the first and last position of the target element.

If the element is not found, return [-1, -1].

Approach (Binary Search)

We use Binary Search twice:

First Binary Search → to find the first occurrence
Second Binary Search → to find the last occurrence

Python Code


python
def first_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            result = mid
            right = mid - 1   # search left side
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result


def last_occurrence(arr, target):
    left, right = 0, len(arr) - 1
    result = -1

    while left <= right:
        mid = (left + right) // 2

        if arr[mid] == target:
            result = mid
            left = mid + 1   # search right side
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1

    return result


def search_range(arr, target):
    return [first_occurrence(arr, target),
            last_occurrence(arr, target)]

# Example
arr = [5, 7, 7, 8, 8, 10]
target = 8
print("Positions:", search_range(arr, target))


## Input
 arr = [5, 7, 7, 8, 8, 10]
target = 8

## output
[3,4]

Sort 0s, 1s, 2s

Dharani — Sun, 22 Mar 2026 05:20:03 +0000

Introduction

Sorting an array containing only 0s, 1s, and 2s is a common problem in data structures. It is also known as the Dutch National Flag problem.

Problem Statement

Given an array containing only 0s, 1s, and 2s, sort the array in ascending order without using extra space.

Approach (Dutch National Flag Algorithm)

We use three pointers:

low → for 0s
mid → for traversal
high → for 2s

Steps:

If element is 0 → swap with low and move both low and mid
If element is 1 → move mid
If element is 2 → swap with high and move high

Python Code


python
def sort_colors(arr):
    low = 0
    mid = 0
    high = len(arr) - 1

    while mid <= high:
        if arr[mid] == 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low += 1
            mid += 1

        elif arr[mid] == 1:
            mid += 1

        else:  # arr[mid] == 2
            arr[mid], arr[high] = arr[high], arr[mid]
            high -= 1

    return arr

# Example
arr = [2, 0, 2, 1, 1, 0]
print("Sorted Array:", sort_colors(arr))


## Input
 [2, 0, 2, 1, 1, 0]

## output
 [0, 0, 1, 1, 2, 2]

Find The Majority Element

Dharani — Sun, 22 Mar 2026 05:17:05 +0000

Introduction

Finding the majority element is a common problem in data structures. It helps in understanding arrays, counting techniques, and efficient algorithms.

Problem Statement

Given an array of size n, find the element that appears more than ⌊n/2⌋ times.

You can assume that the majority element always exists.

Approach 1: Brute Force

Count frequency of each element
Return the element with count > n/2

Python Code (Brute Force)


python
def majority_element(arr):
    n = len(arr)
    for i in arr:
        if arr.count(i) > n // 2:
            return i


## Input
   [2,2,1,1,2]

## output
   [2]

Squares Of a Sorted Array

Dharani — Sun, 22 Mar 2026 05:14:17 +0000

Introduction

The "Squares of a Sorted Array" problem is a common question that helps us understand arrays and the two-pointer technique.

Problem Statement

Given a sorted array of integers (which may include negative numbers), return a new array of the squares of each number, also sorted in non-decreasing order.

Approach (Two-Pointer Technique)

Since negative numbers become positive after squaring, we use two pointers:

Initialize:
- left = 0
- right = n - 1
Compare squares of left and right elements
Place the larger square at the end of result array
Move the corresponding pointer
Repeat until all elements are processed

Python Code


python
def sorted_squares(nums):
    n = len(nums)
    result = [0] * n

    left, right = 0, n - 1
    pos = n - 1

    while left <= right:
        if abs(nums[left]) > abs(nums[right]):
            result[pos] = nums[left] ** 2
            left += 1
        else:
            result[pos] = nums[right] ** 2
            right -= 1
        pos -= 1

    return result

# Example
nums = [-4, -1, 0, 3, 10]
print("Sorted Squares:", sorted_squares(nums))


## Input
  [-4, -1, 0, 3, 10]

## Output
   [0, 1, 9, 16, 100]

Sort a Linked List Using Merge Sort

Dharani — Sun, 22 Mar 2026 05:10:36 +0000

Introduction

Sorting a linked list efficiently is an important problem in data structures. Merge Sort is the best choice for linked lists because it does not require random access like arrays.

Problem Statement

Given the head of a linked list, sort the list in ascending order using Merge Sort.

Why Merge Sort for Linked List?

Works efficiently on linked lists
Time Complexity: O(n log n)
Does not require extra space for shifting elements

Approach

We use Divide and Conquer:

Find the middle of the linked list
Divide the list into two halves
Recursively sort both halves
Merge the sorted halves

Python Code


python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

# Function to find middle of linked list
def get_middle(head):
    slow = head
    fast = head.next

    while fast and fast.next:
        slow = slow.next
        fast = fast.next.next

    return slow

# Function to merge two sorted lists
def merge(l1, l2):
    dummy = ListNode()
    tail = dummy

    while l1 and l2:
        if l1.val < l2.val:
            tail.next = l1
            l1 = l1.next
        else:
            tail.next = l2
            l2 = l2.next
        tail = tail.next

    tail.next = l1 if l1 else l2
    return dummy.next

# Merge Sort function
def merge_sort(head):
    if not head or not head.next:
        return head

    mid = get_middle(head)
    right = mid.next
    mid.next = None

    left = merge_sort(head)
    right = merge_sort(right)

    return merge(left, right)

## Input
   4-> 2-> 1-> 3

## output
   1 -> 2 -> 3 -> 4

Reverse a Linked List

Dharani — Sun, 22 Mar 2026 05:06:44 +0000

Introduction

Reversing a linked list is one of the most common problems in data structures. It helps in understanding pointers and linked list traversal.

Problem Statement

Given the head of a singly linked list, reverse the list and return the new head.

Approach (Iterative Method)

We can reverse the linked list using three pointers:

Initialize:
- prev = None
- current = head
Traverse the list:
- Store next node
- Reverse the link
- Move prev and current forward
Continue until current becomes None
Return prev as new head

Python Code


python
class ListNode:
    def __init__(self, val=0, next=None):
        self.val = val
        self.next = next

def reverseList(head):
    prev = None
    current = head

    while current:
        next_node = current.next   
        current.next = prev        
        prev = current             
        current = next_node        

    return prev


## Input
    1 -> 2 -> 3 -> 4 -> 5

## ouput
   5-> 4-> 3-> 2-> 1

Kadanes Algorithm

Dharani — Sun, 22 Mar 2026 05:03:13 +0000

Introduction

Kadane’s Algorithm is an efficient way to find the maximum sum of a contiguous subarray. It is widely used in array and dynamic programming problems.

Problem Statement

Given an array of integers (both positive and negative), find the contiguous subarray with the maximum sum and return that sum.

Approach (Kadane’s Algorithm)

We use a dynamic approach:

Initialize two variables:
- current_sum = 0
- max_sum = very small number
Traverse the array:
- Add current element to current_sum
- If current_sum becomes greater than max_sum → update max_sum
- If current_sum becomes negative → reset it to 0

Python Code


python
def max_subarray_sum(arr):
    current_sum = 0
    max_sum = float('-inf')

    for num in arr:
        current_sum += num
        max_sum = max(max_sum, current_sum)

        if current_sum < 0:
            current_sum = 0

    return max_sum

# Example
arr = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
print("Maximum Subarray Sum:", max_subarray_sum(arr))


## Input
  [-2, 1, -3, 4, -1, 2, 1, -5, 4]

## Output
   6

Move Zeros

Dharani — Sun, 22 Mar 2026 04:58:49 +0000

Introduction

Moving zeros in an array is a common problem that helps in understanding array manipulation and two-pointer techniques.

Problem Statement

Given an array, move all zeros to the end while maintaining the relative order of non-zero elements.

Approach (Two-Pointer Technique)

We use two pointers:

Initialize a pointer j = 0 (position for non-zero elements)
Traverse the array using index i
If element is non-zero:
- Swap arr[i] with arr[j]
- Increment j
Continue until the end

Python Code


python
def move_zeros(arr):
    j = 0

    for i in range(len(arr)):
        if arr[i] != 0:
            arr[i], arr[j] = arr[j], arr[i]
            j += 1

    return arr

# Example
arr = [0, 1, 0, 3, 12]
print("Result:", move_zeros(arr))


## Input
 [0,1,0,3,4]

## Output
 [1,3,4,0,0]