DEV Community: Bollam Shiva Shankara Varapras

Understanding the OSI Model: A Step-by-Step Breakdown

Bollam Shiva Shankara Varapras — Mon, 21 Oct 2024 03:12:59 +0000

The OSI (Open Systems Interconnection) model is a conceptual framework that helps us understand how data moves across a network. It divides network communication into seven layers, each responsible for specific tasks. This blog will break down these layers, step-by-step, using an easy-to-understand example: visiting a website from your browser.

The 7 Layers of the OSI Model

1. Application Layer (Layer 7)

What It Does: The Application layer is where user interaction happens. This is the layer closest to the end-user and handles software applications like web browsers (Chrome, Firefox).

Example: When you type a URL (e.g., www.example.com) and hit enter, your browser sends an HTTP/HTTPS request to the web server hosting the website. This layer doesn’t handle the data transfer but makes sure that web applications like browsers can communicate over the network.

2. Presentation Layer (Layer 6)

What It Does: The Presentation layer ensures that data is in the correct format for the application. It manages encryption, decryption, compression, and translation of data.

Example: If you’re visiting a secure website (using HTTPS), this layer ensures the data is encrypted with SSL/TLS so your browser can securely exchange information with the web server.

3. Session Layer (Layer 5)

What It Does: This layer manages sessions between devices. It establishes, maintains, and terminates communication sessions between applications.

Example: Once you start browsing a website, the Session layer keeps your session active as you navigate through different pages, ensuring a continuous connection between your browser and the server.

4. Transport Layer (Layer 4)

What It Does: The Transport layer is responsible for reliable data transmission. It manages data flow and error-checking using protocols like TCP (Transmission Control Protocol) or UDP (User Datagram Protocol).

Example: When you load a webpage, TCP ensures that the data (web content) is sent reliably. It establishes a three-way handshake between your browser and the web server to confirm a stable connection.

5. Network Layer (Layer 3)

What It Does: The Network layer is responsible for routing data between different networks. It uses IP addresses to ensure data packets are sent to the correct destination.

Example: Your webpage request is assigned a source IP address (your device) and a destination IP address (the web server). Routers help direct the data packets across different networks until they reach the right destination.

6. Data Link Layer (Layer 2)

What It Does: The Data Link layer manages communication between devices on the same network and ensures that data is properly packaged into frames. It also uses MAC addresses to identify devices within the network.

Example: When your data is sent within your home Wi-Fi network, the Data Link layer ensures that the frames of data move between your laptop and the router using MAC addresses.

7. Physical Layer (Layer 1)

What It Does: The Physical layer is responsible for the actual physical connection and the transmission of raw data (bits) over a medium such as cables, fiber optics, or wireless signals.

Example: The binary data (1s and 0s) representing your webpage request is transmitted from your device to your router via Wi-Fi signals or Ethernet cables. The router then sends the data out to the internet over physical mediums like fiber optic cables.

.js vs. .jsx: Should You Write Your React Code in .jsx?

Bollam Shiva Shankara Varapras — Sun, 01 Sep 2024 04:43:12 +0000

When working with React, one of the decisions you'll face is whether to write your React components in .js or .jsx files. This choice can impact your project's clarity and maintainability. In this blog post, we'll explore the differences between .js and .jsx files and help you decide which is right for you.

What Are .js and .jsx Files?

.js Files

Definition: .js files are the standard extension for JavaScript files.
Usage: You can write React code, including JSX syntax, in .js files. However, this requires proper configuration of your build tools to handle JSX.
Configuration: Make sure your build system (e.g., Babel) is set up to transpile JSX code into standard JavaScript.

.jsx Files

Definition: .jsx is a convention that indicates the file contains JSX syntax.
Usage: Using .jsx makes it explicit that the file includes JSX, which can improve readability and understanding of your code.
Configuration: .jsx files also require appropriate build tool configurations, similar to .js files, to transpile JSX.

Pros and Cons of Using .jsx

Pros

Clarity: By using .jsx, you clearly indicate that the file contains JSX, which can make your codebase easier to navigate and understand.
Convention: Many teams and projects use .jsx to follow established conventions, making it easier for new developers to get up to speed.

Cons

Additional Extension: You’ll need to ensure your development tools (like ESLint, Prettier) are configured to handle .jsx files.
Inconsistency: If your project or team uses .js for everything, introducing .jsx might create inconsistency.

Making Your Decision

Whether to use .js or .jsx comes down to personal or team preference and the conventions of your project. If clarity and following conventions are important to you, .jsx might be the way to go. On the other hand, if you prefer simplicity and consistency, sticking with .js should work just fine as long as your build tools are properly configured.

In the end, both file extensions serve the same purpose, and with the right configuration, you can use either without issues. Choose the one that best fits your project’s needs and your team’s workflow.

1669 Merge in Between Linked Lists - Leetcode

Bollam Shiva Shankara Varapras — Sat, 20 Jul 2024 04:22:23 +0000

Approach

Find the node at index a - 1 and b
Set the next of the node at index
Find the last node of list2
Set the next of the last node of list2 to the next of the node at index b
Return the head of the list

Complexity

Time complexity: O(n)

Space complexity: O(1)

Java Code

class Solution {
    public ListNode mergeInBetween(ListNode list1, int a, int b, ListNode list2) {
        ListNode start = list1;
        ListNode end = list1;
        for (int i = 0; i < a - 1; i++) {
            start = start.next;
        }
        for (int i = 0; i < b; i++) {
            end = end.next;
        }
        start.next = list2;
        while (list2.next != null) {
            list2 = list2.next;
        }
        list2.next = end.next;
        return list1; 
    }
}

Solving "All Nodes Distance K in Binary Tree" Leet code Question

Bollam Shiva Shankara Varapras — Sat, 16 Sep 2023 06:00:00 +0000

Problem Statement

Given a binary tree, you are given a target node target and an integer k. Return a list of all the values that are at a distance k from the target node in the tree.

Approach

The idea to solve this problem is to perform a depth-first search (DFS) traversal of the binary tree to find nodes at a distance k from the target node. We'll use a few helper functions to achieve this.

UpdateParent Function: We'll start by creating a mapping of each node to its parent node. This will help us navigate the tree later.
Traversal Function: In this function, we'll perform the DFS traversal. When we reach a node at a distance k from the target node, we add its value to the result list. We also maintain a HashSet to keep track of visited nodes to avoid revisiting them. The recursion continues until we either find nodes at distance k or reach the end of the tree.
Finally, in the distanceK function, we initialize the necessary data structures and call the UpdateParent function to create the mapping of nodes to their parents. Then, we call the Traversal function to find nodes at distance k from the target node and add their values to the result list.

Complexity Analysis

Time Complexity: The DFS traversal of the binary tree takes O(n) time, where n is the number of nodes in the tree.
Space Complexity: The space complexity is O(n) due to the space used by the HashMap, HashSet, and the recursion stack.

Code :


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {

    public void UpdateParent(TreeNode Parent, TreeNode Current, HashMap<TreeNode, TreeNode> map) {
        if (Current == null) {
            return;
        }
        map.put(Current, Parent);

        UpdateParent(Current, Current.left, map);
        UpdateParent(Current, Current.right, map);
    }

    public void Traversal(int distance, TreeNode node, HashMap<TreeNode, TreeNode> map, List<Integer> list,HashSet<TreeNode> set) {
        if (node == null) {
            return;
        }
        if (set.contains(node)) {
            return;
        }
        set.add(node);

        if (distance == 0) {
            list.add(node.val);
            return;
        }
        Traversal(distance - 1, node.left, map, list, set);
        Traversal(distance - 1, node.right, map, list, set);
        Traversal(distance - 1, map.get(node), map, list, set);

    }

    public List<Integer> distanceK(TreeNode root, TreeNode target, int k) {
        HashMap<TreeNode, TreeNode> map = new HashMap<>();
        HashSet<TreeNode> set = new HashSet<>();
        List<Integer> list = new ArrayList<>();
        UpdateParent(null, root, map);
        Traversal(k, target, map, list, set);
        return list;
    }
}

Solving "Diameter of Binary Tree" Leet code Question

Bollam Shiva Shankara Varapras — Thu, 14 Sep 2023 09:06:53 +0000

Intuition

We want to find the diameter of a binary tree, which is the length of the longest path between any two nodes. This path may or may not pass through the root.

Approach

We perform a depth-first traversal of the tree and calculate the height of each subtree. While calculating the height of each node, we also update the diameter if a longer path is found. The final result will be stored in the diameter variable.

Time complexity
O(n) - We visit each node once.

Space complexity
O(h) - Recursive call stack space, where h is the height of the tree.

Code

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {

    int diameter = 0;

    public int diameterOfBinaryTree(TreeNode root) {
        height(root);
        return diameter;
    }

    public int height(TreeNode node){

        if(node == null) {
            return 0;
        }

        int lh = height(node.left);
        int rh = height(node.right);
        diameter = Math.max(diameter,lh+rh);

        return 1 + Math.max(lh,rh);
    }
}

Happy coding,
shiva

Solving "Binary Tree Level Order Traversal" Leet code Question

Bollam Shiva Shankara Varapras — Wed, 13 Sep 2023 07:06:45 +0000

Leet code Question no: 102

Companies asked this Question:
Company: no of times
Amazon 2
Bloomberg 11
Uber 2
Apple 2
LinkedIn 25
Microsoft 13
Facebook 12
Oracle 7
Google 5
ServiceNow 3
Splunk 2
Adobe 2
Docusign 2
Accolite 2
TikTok 2

Intuition

We aim to perform a level-order traversal of a binary tree, collecting nodes at each level into sublists.

Approach

Utilize a queue for level-order traversal, initializing an empty list WrapList to store results.
While the queue is not empty, dequeue nodes, collect their values into sublists, and enqueue their children.
Add sublists to WrapList as levels are processed and return it as the result.

Complexity

Time complexity: O(n) - We visit each node once during the traversal.
Space complexity: O(n) - The space usage grows with the number of nodes due to the queue and the result list.

Code


/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> WrapList = new LinkedList<>();

        if(root == null)
            return WrapList;

        Queue<TreeNode> queue =  new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){
            int levelNum = queue.size();
            List<Integer> subList = new LinkedList<>();

            for(int i = 0 ;  i < levelNum ; i++){
                TreeNode node = queue.poll();
                subList.add(node.val);

                if(node.left != null) queue.offer(node.left);
                if(node.right != null) queue.offer(node.right);
            }

            WrapList.add(subList);
        }

        return WrapList;
    }
}

Happy coding,
shiva

Solving "Move Zeroes" Leet code Question.

Bollam Shiva Shankara Varapras — Tue, 12 Sep 2023 02:11:33 +0000

283. Move Zeroes

Type: Easy
Liked by 15.2K
Disliked by 380.

Companies that asked this question
Companies: No of times asked
Yandex 8
Apple 3
Amazon 3
Facebook 11
Bloomberg 6
Google 4
Adobe 3
Microsoft 2
Uber 2
Oracle 2
Splunk 2
Tesla 2
tcs 6
Expedia 4
VMware 3
Goldman Sachs 3
ByteDance 3
JPMorgan 3
TikTok 3
LinkedIn 2
Yahoo 2
IBM 2
Morgan Stanley 2
ServiceNow 2
Salesforce 2
Zoho 2
Infosys 2
Nvidia 2
Samsung 2
Wix 1

Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.

Note that you must do this in-place without making a copy of the array.

Example 1:
Input: nums = [0,1,0,3,12]
Output: [1,3,12,0,0]

Example 2:
Input: nums = [0]
Output: [0]

Constraints:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

Intuition

We want to move all the zeros to the end of the array while keeping the non-zero elements in their relative order.

Approach

We maintain two pointers: i to iterate through the array and nonZeroIndex to keep track of the position where we should insert non-zero elements. When we encounter a non-zero element, we swap it with the element at nonZeroIndex and then increment nonZeroIndex.

Complexity

Time complexity:
The code iterates through the array once, so the time complexity is O(n), where n is the length of the array.

Space complexity:
The code uses a constant amount of extra space, so the space complexity is O(1).

Code

class Solution {
    public void moveZeroes(int[] nums) {
        int nonZeroIndex = 0; 
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int temp = nums[i];
                nums[i] = nums[nonZeroIndex];
                nums[nonZeroIndex] = temp;
                nonZeroIndex++; 
            }
        }
    }
}

Happy coding,
shiva

Solving "Climbing Stairs" Leet code Problem

Bollam Shiva Shankara Varapras — Sun, 10 Sep 2023 16:59:10 +0000

Question:

70. Climbing Stairs
Type: Easy
Liked by 19.8K
Disliked by 656.
Companies that asked this question
Companies: No of times asked
Amazon 3
Yahoo 2
Adobe 11
Google 5
Apple 5
Bloomberg 3
Microsoft 3
Uber 2
Nagarro 2
Expedia 12
Oracle 4
Goldman Sachs 3
Facebook 2
Intel 2
Visa 2
Optum 2
Swiggy 2

You are climbing a staircase. It takes n steps to reach the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Example 1:
Input: n =2
Output: 2
Explanation:
`There are two ways to climb to the top.

1 step + 1 step
2 steps`

Example 2:
Input: n = 3
Output: 3
Explanation:
`There are three ways to climb to the top.

1 step + 1 step + 1 step
1 step + 2 steps
2 steps + 1 step`

Constraints:
1 <= n <= 45

Intuition:

The problem is about finding the number of ways to climb a staircase when you can take either 1 step or 2 steps at a time. To solve it, you can use dynamic programming.

Approach:

Create an array to store the number of ways to reach each step.
Initialize the first two elements of the array (representing the first and second steps).
Use a loop to calculate the number of ways to reach each subsequent step.
Return the number of ways to reach the final step.

Complexity:

Time Complexity: O(n)
Space Complexity: O(n)

Code

class Solution {
    public int climbStairs(int n) {
        int[] arr = new int[n+1];

        if(n == 1){
            return 1;
        }
        else{
            arr[1] = 1;
            arr[2] = 2;
            for(int i = 3 ; i <=n ; i++){
                arr[i] = arr[i-1] + arr[i-2];
            }
        }
       return arr[n];
    }
}

Happy coding,
shiva

Solving the "Container With Most Water" Problem on Leet Code

Bollam Shiva Shankara Varapras — Sun, 10 Sep 2023 07:32:32 +0000

11. Container With Most Water

Type : Medium
Liked by: 26.5K
Disliked by: 1.4K

Companies that asked this Question
Companies : No of Times asked

Microsoft 4
Google 4
Amazon 3
Adobe 2
Bloomberg 2
Apple 9
Facebook 4
Uber 3
Oracle 2
TikTok 2
Goldman Sachs 5
Intel 4
Swiggy 4
ByteDance 3
VMware 3
Qualtrics 3
Intuit 3
Flipkart 2
Zoho 2
Samsung 2
eBay 2
Walmart Labs 2
Yandex 2
Yahoo 2
Cisco 2
tcs 2
Tesla 2
C3 IoT 2
Arcesium 2
DE Shaw 2
JPMorgan 2
Wix 1

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.

Example 2:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:
Input: height = [1,1]
Output: 1

Intuition:

The code aims to find the maximum area between two lines in a histogram, where the lines represent the heights of bars.

Approach:

Initialize pointers at both ends of the histogram (LeftPointer at 0 and RightPointer at the last element).
While the LeftPointer is less than the RightPointer:
Calculate the area between the lines formed by the heights at LeftPointer and RightPointer.
Update the MaximumArea if the current area is greater.
Move the pointer that points to the shorter line inward (towards the other pointer).
Repeat step 2 until the pointers meet.

Complexity:

Time complexity: O(n) where n is the number of elements in the height array. We iterate through the array once.
Space complexity: O(1) because we use a constant amount of extra space regardless of the input size.

Code:

class Solution {
    public int maxArea(int[] height) {
        int MaximumArea = 0;
        int LeftPointer = 0;
        int RightPointer = height.length - 1;

        while(LeftPointer < RightPointer){
            if(height[LeftPointer] < height[RightPointer]){
                MaximumArea = Math.max(MaximumArea , height[LeftPointer] *(RightPointer - LeftPointer));
                LeftPointer++;
            }
            else{
                MaximumArea = Math.max(MaximumArea ,height[RightPointer] *(RightPointer - LeftPointer));
                RightPointer--;
            }
        }

        return MaximumArea;
    }
}

Happy coding,
shiva

Solving the "Trapping Rain Water" Problem on Leet Code

Bollam Shiva Shankara Varapras — Sun, 10 Sep 2023 05:35:23 +0000

Question

42. Trapping Rain Water

Type: Hard
Liked by: 29K
Disliked by: 412

Companies that asked this Question
Companies: No of times Asked

Amazon 14
Bloomberg 5
Adobe 4
Apple 4
Goldman Sachs 3
Yandex 3
EPAM Systems 2
Microsoft 16
Google 9
Uber 4
MakeMyTrip 3
Facebook 2
eBay 2
Salesforce 2
Intel 8
Rubrik 8
Qualtrics 7
Tesla 6
Oracle 5
Citadel 5
VMware 4
C3 IoT 4
Snapchat 3
Lyft 3
Visa 3
PayPal 3
ServiceNow 3
Swiggy 3
National Instruments 3
Sapient 3
Zoho 2
Intuit 2
Coupang 2
Yahoo 2
Expedia 2
Twitch 2
Morgan Stanley 2
DE Shaw 2
TikTok 2
Navi 2
Airbnb 1
Zenefits 1
Twitter 1
Wix 1

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rainwater (blue section) are being trapped.

Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:
n == height.length 1 <= n <= 2 * 104 0 <= height[i] <= 105

Intuition:

The goal is to calculate the total trapped water between bars with given heights. We achieve this by computing left and right boundaries for each bar and then calculating trapped water based on these boundaries.

Approach:

Initialize res to 0, lb (left boundaries), and rb (right boundaries) arrays.
Calculate left boundaries (lb) and right boundaries (rb) for each bar in the input array.
Iterate through the input array, calculating trapped water for each bar and accumulating it in res.
Return res as the total trapped water.

Complexity:

Time complexity: O(n) where n is the number of elements in the input array.

Space complexity: O(n) due to the lb and rb arrays used to store boundaries.

Code:

class Solution {
    public int trap(int[] height) {
        int  res = 0;
        int[] lb = new int[height.length];
        int[] rb = new int[height.length];

        lb[0] = height[0];
        for(int i = 1 ; i < height.length -1 ;i++){
            lb[i] = Math.max(height[i],lb[i-1]);
        }

        rb[height.length - 1] = height[height.length - 1 ];
        for(int i = height.length - 2 ; i >= 0;i--){
            rb[i] = Math.max(height[i],rb[i+1]);
        }

        for(int i = 1 ; i < height.length -1 ; i++){
            int tw = Math.min(lb[i],rb[i]) - height[i];
            res = res + tw;
        }

        return res;
    }
}

Happy coding,
shiva

Solving the "Letter Combinations of a Phone Number" Problem on Leet Code

Bollam Shiva Shankara Varapras — Sat, 09 Sep 2023 18:02:22 +0000

17. Letter Combinations of a Phone Number

Question type: Medium
Liked by 17.1K
Disliked by 896

Companies that asked this Question
Company : Noof Times

Amazon 5
Apple 4
Microsoft 6
Google 5
Facebook 4
Uber 4
Bloomberg 3
DE Shaw 3
Adobe 2
eBay 2
Intuit 2
Yahoo 2
Twilio 2
Oracle 8
Twitter 5
Goldman Sachs 5
Epic Systems 4
Swiggy 4
VMware 3
Nutanix 3
Duolingo 3
Snapchat 2
LinkedIn 2
Samsung 2
Morgan Stanley 2
Cisco 2
Walmart Labs 2
Twitch 2
Tesla 2
ServiceNow 2
Capital One 2
Dropbox 1

Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2:
Input: digits = ""
Output: []

Example 3:
Input: digits = "2"
Output: ["a","b","c"]

Approach:

How it works:

Mapping: Imagine each digit (2 to 9) on your phone has some letters associated with it, just like the letters on a computer keyboard. This code stores those associations in a list called keypad.

Main Job: The main job is done by the letterCombinations function. You give it a sequence of digits, and it gives you back a list of all possible words you can make.

Starting Point: If you don't give it any digits (an empty sequence), it says, "I can't make any words with that," and it gives you an empty list.

Magic Helper: Inside the letterCombinations function, there's a special helper called letterCombinationsRecursive. This helper does most of the work.

Recursive Idea: The magic happens here. The helper looks at each digit one by one. For each digit, it finds the letters associated with that digit from the keypad.

Mix and Match: Then, it starts mixing and matching those letters to make words. It tries all possible combinations by adding one letter at a time and keeps track of the words it can create.

Keep Going: It does this for all the digits in the sequence, one after the other. Each time, it adds more letters to the words it's making.

Save the Magic Words: Whenever it finishes a combination (when it has used all the digits), it saves that word in a special list.

Return the Magic Words: After it has gone through all the possibilities, it gives you back the list of magic words it found.

code:

import java.util.ArrayList;
import java.util.List;

class Solution {
    static String[] keypad = { "", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz" };

    public List<String> letterCombinations(String digits) {
        List<String> stringList = new ArrayList<>();
        if (digits.length() == 0) {
            return stringList;
        }

        letterCombinationsRecursive(digits, 0, "", stringList);

        return stringList;
    }

    private void letterCombinationsRecursive(String digits, int index, String ans, List<String> stringList) {
        if (index == digits.length()) {
            stringList.add(ans);
            return;
        }

        String key = keypad[digits.charAt(index) - '0'];

        for (int i = 0; i < key.length(); i++) {
            letterCombinationsRecursive(digits, index + 1, ans + key.charAt(i), stringList);
        }
    }   
}

Happy coding,
shiva

Solving the "Search Insert Position" Problem on LeetCode

Bollam Shiva Shankara Varapras — Thu, 07 Sep 2023 04:53:17 +0000

35. Search Insert Position

Question Type: Easy
Liked by :14.6K
Disliked by: 630

Companies asked this Question:

Company name : No of Times
Amazon 4
Google 2
Apple 8
Microsoft 5
Adobe 4
Yahoo 2
Bloomberg 2
Facebook 7
VMware 5
Uber 4
LinkedIn 2
TikTok 2
tcs 2

Given a sorted array of distinct integers and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.

You must write an algorithm with O(log n) runtime complexity.

Example 1:
Input: nums = [1,3,5,6], target = 5
Output: 2

Example 2:
Input: nums = [1,3,5,6], target = 2
Output: 1

Example 3:
Input: nums = [1,3,5,6], target = 7
Output: 4

Constraints:

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums contains distinct values sorted in ascending order.
-104 <= target <= 104

Approach:

Initialize Pointers:
Initialize two pointers, start and end, to represent the search range within the sorted array.start initially points to the first element (index 0), and end points to the last element (index nums.length - 1).

Binary Search Loop:
Enter a while loop that continues as long as start is less than or equal to end.

Calculate Middle Index:
Calculate the middle index mid as start + (end - start) / 2. This ensures that the middle index is always rounded down to an integer, avoiding potential overflow issues.

Compare with Target:
Check if the element at index mid is equal to the target value.
If they are equal, return mid as the index where the target is found.

Adjust Pointers:
If the element at index mid is greater than the target, update end to mid - 1 to search in the left half of the current range.
If the element at index mid is less than the target, update start to mid + 1 to search in the right half of the current range.

Return Insertion Point:
If the while loop exits without finding the target (i.e., start becomes greater than end), return start as the index where the target should be inserted.

Code(in Java):

class Solution {
    public int searchInsert(int[] nums, int target) {
         int start = 0;
         int end = nums.length - 1;

         while(start <= end){
             int mid = start +(end - start) / 2;
             if(nums[mid] == target) return mid;
             if(nums[mid] > target) end = mid - 1;
             if(nums[mid] < target) start = mid + 1;
         }
         return start;
    }
}

Time Complexity Analysis:
Binary search has a time complexity of O(log n), where n is the number of elements in the array. This approach ensures that the search is performed efficiently.

Happy coding,
shiva