Tech Archives - Amrit Srivastava

Question 3

Given an array of numbers N and an integer k, your task is to split N into k partitions such that the maximum sum of any partition is minimized. Return this sum.

For example, given N = [5, 1, 2, 7, 3, 4] and k = 3, you should return 8, since the optimal partition is [5, 1, 2], [7], [3, 4].

Approach

Start by sorting the array in descending order. This helps group larger numbers together, making it easier to control the maximum partition sum.
Determine the possible range for the maximum partition sum.
The lowest possible value is the largest element in the array.
The highest possible value is the sum of all the elements in the array.
Employ binary search within this range. For each ‘mid’ value:
a. Try dividing the array into partitions such that no partition sum exceeds ‘mid’.
b. If you can successfully divide the array, that means ‘mid’ is a possible maximum partition sum. Try to reduce ‘mid’ further (search in the lower half of the range).
c. If you cannot divide the array, this means ‘mid’ is too small. Explore larger maximum partition sums (search in the upper half of the range).
Continue the binary search until you find the smallest possible ‘mid’ that successfully partitions the array.

Pseudo Code

Code

FUNCTION min_max_partition(nums, k)
   SORT nums in descending order 
   low = largest_number_in(nums)
   high = sum_of_all_elements_in(nums)

   WHILE low < high
       mid = (low + high) / 2 

       IF can_partition(nums, k, mid) 
           high = mid  
       ELSE 
           low = mid + 1

   RETURN low 

FUNCTION can_partition (nums, k, max_allowed_sum)
   current_partition_sum = 0
   num_partitions = 1  

   FOR EACH num IN nums
        IF current_partition_sum + num > max_allowed_sum
            num_partitions = num_partitions + 1 
            current_partition_sum = num  
        ELSE
            current_partition_sum = current_partition_sum + num

   RETURN num_partitions <= k

Explanation

min_max_partition
- We sort the array for potential optimization.
- We establish the search space between the largest number and the total sum.
- The binary search loop iteratively adjusts the low and high boundaries, using the can_partition helper function to evaluate the feasibility of a given mid value as the target maximum partition sum.
can_partition
- This function tracks the current partition’s sum.
- If adding a number would exceed the max_allowed_sum, it starts a new partition.
- It returns True if the array can be divided into ‘k’ or fewer partitions.

Implementation

Golang

package main

import (
	"fmt"
	"sort"
)

func minMaxPartition(nums []int, k int) int {
	// Helper function to check if a partition is possible with a given maximum sum
	canPartition := func(maxSum int) bool {
		subarrays := 0
		currSum := 0
		for _, num := range nums {
			if currSum+num > maxSum {
				subarrays++
				currSum = num // Reset current sum for the new subarray
			} else {
				currSum += num
			}
		}
		return subarrays+1 <= k // Account for the final subarray
	}

	// Sort the array in descending order
	sort.Slice(nums, func(i, j int) bool { return nums[i] > nums[j] })

	low := nums[0] // Lowest possible maximum sum
	high := 0      // Highest possible maximum sum
	for _, num := range nums {
		high += num
	}

	// Binary search to find the minimum maximum sum
	for low < high {
		mid := low + (high-low)/2
		if canPartition(mid) {
			// Can form partitions using 'mid', try finding a lower maximum sum
			high = mid
		} else {
			// 'mid' is too small, increase the lower bound
			low = mid + 1
		}
	}

	return low
}

func main() {
	nums := []int{5, 1, 2, 7, 3, 4}
	k := 3
	result := minMaxPartition(nums, k)
	fmt.Println(result) // Output: 8
}

Question 2

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. Find the minimum element in O(log N) time. You may assume the array does not contain duplicates.

For example, given [5, 7, 10, 3, 4], return 3.

Approach

The core idea is to use a modified binary search. In every iteration, we compare the middle element with the leftmost and rightmost elements. If the middle element is smaller than the rightmost element, the right half is sorted, and the pivot (and the minimum element) must lie in the left half. Conversely, if the middle element is larger than the leftmost element, the left half is sorted, and the pivot is in the right half. In this way, we progressively narrow down the search space until we find the pivot, where the minimum element resides right after it.

Pseudo Code

Code

function findMinimum(nums):
    left = 0
    right = length(nums) - 1

    // Handle arrays with 0 or 1 element
    if right < 0:
        return None // Handle error: Empty array
    if right == 0: 
        return nums[0]

    // Array is already sorted 
    if nums[left] <= nums[right]:
        return nums[left]

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

        // Found the pivot: minimum is the next element
        if nums[mid] > nums[mid + 1]:
            return nums[mid + 1]

        // Left half is sorted    
        if nums[mid] >= nums[left]:
            left = mid + 1
        // Right half is sorted
        else:
            right = mid - 1

    // Should not reach here under normal cases       
    return None

Explanation

Goal: The goal is to find the minimum element in a rotated sorted array within O(log N) time complexity.

Approach: The pseudocode implements a modified binary search approach to achieve this. Here’s how it works:

Initialization: First, it handles edge cases for an empty array or single-element array. Then, it checks if the array is already sorted.
Iterative Narrowing: The code enters a loop and repeatedly calculates the middle element (mid) of the current search space. It then compares this middle element with the leftmost and rightmost elements.
Identifying Pivot: If the middle element is immediately followed by a smaller element, we’ve found the pivot point—the place where the rotation occurred. The minimum element will be the one right after the pivot.
Exploiting Sorted Subarrays: If we haven’t yet found the pivot, the comparisons with the leftmost and rightmost elements tell us which half of the current search space is sorted. This allows us to eliminate either the left or right half from our future search.
Repeat: The process repeats. With each iteration, we reduce the search space by roughly half, leading to logarithmic time complexity.

Implementation

Golang

package main

import "fmt"

func findMin(nums []int) int {
	// Handle edge case of empty array
	if len(nums) == 0 {
		return -1 // Or handle the error appropriately
	}

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

	// If array is already sorted (no rotation)
	if nums[left] <= nums[right] {
		return nums[left]
	}

	for left <= right {
		mid := left + (right-left)/2

		// Check if mid is the pivot point (minimum element)
		if nums[mid] > nums[mid+1] {
			return nums[mid+1]
		}

		// Check which half is sorted to narrow the search
		if nums[mid] >= nums[left] {
			// Left half is sorted, pivot is in the right half
			left = mid + 1
		} else {
			// Right half is sorted, pivot is in the left half
			right = mid - 1
		}
	}

	return -1 // Should not reach here in normal cases
}

func main() {
	arr := []int{5, 7, 10, 3, 4}
	minElement := findMin(arr)
	fmt.Println("Minimum element:", minElement)
}

Package Visibility in Android Apps: Demystifying the queries element

As an Android developer, ensuring your app interacts gracefully with others on a user’s device is essential. However, you also want to avoid overreaching and accessing app data unnecessarily. The <queries> element brings much-needed precision to how your app views and interacts with other apps, promoting better security practices and a clear respect for user privacy.

Understanding Package Visibility

Package visibility filtering prioritizes user privacy and helps limit the reach of apps that don’t have a legitimate need to know what other apps are installed.

The Pre-Android 11 Picture

In older versions of Android (prior to Android 11), apps enjoyed more expansive package visibility. Essentially, an app could query the system to retrieve a list of most or all apps installed on the user’s device. This ability often meant apps could see which other applications a user had, even if those apps had no relation to your app’s core functionality.

Motivation for Change

While convenient for some developer use-cases, unrestricted package visibility brought several concerns

Privacy Implications

Apps with broad access to installed app data could build user profiles, potentially tracking interests and habits without the user’s explicit knowledge.

Security Risks

A malicious app could exploit this knowledge to target other apps with known vulnerabilities.

User Experience

Knowing a user’s app preferences could be used to deliver intrusive, targeted advertising

Package Visibility Filtering

Starting with Android 11, Google made significant changes to address these concerns. Package visibility filtering now acts as the default. Here’s how it works:

Automatic Limitation

Most apps now operate with a filtered view of the installed apps on the device.

Necessity-Based

Apps only “see” other apps directly relevant to their own functionality, minimizing unwarranted data exposure.

Enter the <queries> element

The <queries> element serves as your formal declaration within the Android manifest that your app has legitimate reasons to interact with other apps installed on the user’s device. It addresses the limitations imposed by package visibility filtering, which is a significant privacy and security improvement introduced in Android 11.

Placement

The <queries> element finds its home within your project’s AndroidManifest.xml file. Specifically, it resides as a child element of the <application> tag. Here’s a basic visualization:

AndroidManifest.xml

<manifest ... >
    <application ... >
        <queries> 
            </queries>
    </application>
</manifest>

The true power of the <queries> element lies in its ability to zero in on precisely what your app needs from the ecosystem of installed apps. Instead of having blanket access to every app on the device, you can define the following with pinpoint accuracy:

Apps by Package Name

When to Use: Use this method when your app directly integrates with a known, specific app. Examples include:

A share feature specifically for Facebook or Twitter.
A feature relying on a third-party payment processing app.
Deep integration with another app within your company’s suite of products.
Within your <queries> element, introduce a <package> tag:

<queries>
    <package android:name="com.example.targetapp" /> 
</queries>

Replace "com.example.targetapp" with the actual package name of the app you need to interact with.

Apps by Intent Filters

When to Use: Utilize this method when your app needs to perform a task, but can delegate that task to potentially multiple apps that could be installed on the user’s device. Examples include:

Sharing various content types (images, text, files).
Editing multimedia (photos, videos).
Opening different document formats.
Define an <intent> tag within <queries>, carefully specifying the relevant intent properties:

<queries>
    <intent>
        <action android:name="android.intent.action.EDIT" />
        <data android:mimeType="image/*" />
    </intent>
</queries>

This code indicates a query for apps capable of editing images.
Be sure to adjust action, data types, and any categories to align with your app’s functionality needs.

Apps by Content Providers

When to Use: Employ this method when your app relies on accessing structured data provided by another app’s content provider. Typical examples include:

Retrieving contact information.
Interacting with the user’s calendar.
Accessing photos and videos from the media store.
Use a <provider> tag within <queries>, specifying the authority of the content provider:

<queries>
    <provider android:authorities="com.google.android.calendar" />
</queries>

Replace com.google.android.calendar with the correct authority of the content provider you wish to access.
Exercise caution, as content providers often expose sensitive data. Justify such access carefully.

Always maintain a principle of minimalism when constructing your queries. Aim to provide your app with only the level of visibility it genuinely needs to function, maximizing user privacy and minimizing the potential for misuse.

The `QUERY_ALL_PACKAGES` Permission

When it comes to Android app permissions, QUERY_ALL_PACKAGES is in a league of its own. This sensitive permission enables an app to see almost every other app installed on a user’s device. For this reason, its use is highly scrutinized by Google Play.

Proceed with caution

Before even considering the QUERY_ALL_PACKAGES permission, understand that it should be treated as a last resort. Think of it as a tool with immense power that also carries substantial responsibility. Here’s why exercising extreme caution is essential:

User Privacy

Granting an app this permission significantly expands its awareness of a user’s app preferences and potentially sensitive data. It’s crucial to consider whether your app’s functionality truly justifies this intrusion.

Google Play Restrictions

Play has rigorous review processes for apps requesting QUERY_ALL_PACKAGES. Expect that most apps will not be approved for its use. Be prepared to demonstrate the absolute necessity of this permission and prove that no alternative methods can successfully accomplish your app’s core features.

Code Complexity

Be aware that managing the results from QUERY_ALL_PACKAGES often requires additional coding effort on your part to filter and process a potentially large amount of app data.

If you can achieve your app’s goals using the fine-grained control offered by the <queries> element, avoid QUERY_ALL_PACKAGES entirely to uphold user privacy and simplify your development process.

Typical Use Cases (When to Consider)

While the ideal is to avoid QUERY_ALL_PACKAGES, there are a few specific scenarios where its use might be deemed necessary. It’s important to note that even within these categories, Google Play maintains a strict approval process.

Antivirus and Security Apps

Such apps often need to analyse the full spectrum of installed apps to detect potential threats, malware, or apps exploiting known vulnerabilities.

Device Management Tools

Apps meant for enterprise administration or parental control may require extensive package visibility to enforce policies or restrictions on the device.

File Managers

For deep file management actions, these apps sometimes offer users detailed views of other installed apps within their interface.

Custom Launchers

Apps that provide alternative home screen experiences may need to build a broader app inventory for easy user access.

Important Reminder: Google’s evaluation regarding QUERY_ALL_PACKAGES involves intense scrutiny. Even if your app seemingly fits into one of these categories, it’s important to take these steps:

Explore Alternatives

Always investigate whether you can restructure your app’s features to make use of the targeted queries possible within the <queries> element.

Be Prepared to Justify

Have a comprehensive explanation outlining the absolute necessity of broad app visibility for your app’s core purpose.

The QUERY_ALL_PACKAGES permission should be viewed as a potential compromise on user privacy. Always strive to prioritize alternative strategies using the <queries> element to minimize your app’s footprint on a user’s device.

Best Practices and Tips

Minimalism as a Guiding Principle

The principle of “least privilege” applies here. Query with the smallest scope possible – ask only for visibility into apps that your features absolutely require.

Handle “App Not Found” Gracefully

Write your code to anticipate scenarios where your query matches an app that isn’t installed on the user’s device. Provide alternatives or informative messages rather than causing your app to crash.

Stay Updated on API Changes

Package visibility features have evolved across Android versions. Use recent Gradle plugin versions and check Android documentation for guidance on API level differences.

Emphasize User Privacy

Always approach app discovery and interaction with respect for the user. Remember, they often don’t know the full breadth of apps installed on their device. Display information garnered through queries responsibly.

Consider Advanced Scenarios

Google provides additional mechanisms for specific cases not fully covered in this post (e.g., role-based queries). Consult the Android documentation for complex use cases.

Test Thoroughly

Test your queries on various devices and Android versions to ensure expected behaviour.

Use Comments

Include clear comments in your manifest file to explain the reasoning behind each query for both ease of maintenance and to demonstrate privacy-conscious development to collaborators or reviewers.

Conclusion

Package visibility and app interactions will likely continue to evolve within the Android framework. Always refer to official Android documentation for the most up-to-date recommendations and explore advanced techniques in your ongoing development journey. By proactively using approaches like the <queries> element, you create apps that better align with Android’s principles of user trust and security.

Question 1

Given the head of a singly linked list, swap every two nodes and return its head.

Approach

In the realm of linked lists, a classic algorithmic puzzle is to rearrange the structure by swapping adjacent pairs of nodes. Your task is to develop a solution that elegantly modifies the links within a given linked list to achieve this pairwise swap.

Pseudo Code

Code

function swapPairs(head)
  //  Handle base cases: empty list or single node
  if head == NULL or head.next == NULL
    return head

  // Create pointers to track nodes:
  // 'prev' will point to the node before the pair to swap  
  // 'curr' will point to the first node of the pair  
  // 'next' will point to the second node of the pair
  prev = NULL
  curr = head
  next = head.next

  // Iterate through the list:  
  while curr != NULL and next != NULL
      // Set prev.next to the second node, effectively reversing the first pair
      if prev != NULL 
          prev.next = next 
      else
          head = next // Update 'head' for the first pair swap

      // Perform the swap
      curr.next = next.next
      next.next = curr 

      // Move pointers to prepare for the next swap
      prev = curr
      curr = curr.next 
      next = curr.next if curr != NULL 

  return head

Explanation

Base Cases: Check if the list is empty (head == NULL) or if it has only one node (head.next == NULL). In these cases, no swapping is needed, so you directly return the head.
Pointers:
- prev: Keeps track of the node before the current pair to update its next pointer.
- curr: Points to the first node of the current pair to be swapped.
- next: Points to the second node of the current pair.
Iteration: The while loop iterates until you’ve processed all pairs.
Reversing the Pair:
- If prev is not NULL (it won’t be for the first pair), you set prev.next to next, effectively reversing the direction of the first two nodes.
- If prev is NULL, this is the first pair in the list so you update the head pointer to next.
Swapping:
- curr.next is set to next.next (the node after the pair).
- next.next is set to curr (completing the swap).
Update Pointers:
- Update prev, curr, and next to prepare for the next pair swap.

Implementation

Golang

package main

import "fmt"

// Node represents a node in the singly linked list
type Node struct {
    Val  int
    Next *Node
}

// Function to swap pairs in the linked list
func swapPairs(head *Node) *Node {
    // Base cases: empty list or single node
    if head == nil || head.Next == nil {
        return head
    }

    // Create dummy head (simplifies initial swap)
    dummy := &Node{Next: head}
    prev := dummy
    curr := head
    next := head.Next

    // Iterate and swap pairs
    for curr != nil && next != nil {
        // Reverse pair
        prev.Next = next
        curr.Next = next.Next
        next.Next = curr

        // Update pointers for the next iteration
        prev = curr
        curr = curr.Next
        if curr != nil { // Ensure 'next' isn't out of bounds
            next = curr.Next
        }
    }

    return dummy.Next // Return the new head (from the dummy node)
}

// Example usage
func main() {
    // Create a simple linked list
    head := &Node{Val: 1, Next: &Node{Val: 2, Next: &Node{Val: 3, Next: &Node{Val: 4}}}}

    // Swap pairs
    newHead := swapPairs(head)

    // Print the modified list
    for newHead != nil {
        fmt.Print(newHead.Val, " ")
        newHead = newHead.Next
    }
    fmt.Println()
}

UFS vs. eMMC: Understanding Smartphone Storage

Your smartphone’s speed and responsiveness rely heavily on its internal storage. Two of the most widespread storage technologies are eMMC and UFS. In this blog post, I will break down what these terms mean, their differences, and why understanding them can help you make a more informed decision when buying your next device.

Understanding eMMC

eMMC stands for Embedded MultiMediaCard. Originally derived from older MMC technology, eMMC integrates flash memory and a controller into a single package that’s soldered onto a device’s circuit board

Familiar example

Think of eMMC like a single-lane road. Traffic can move efficiently in one direction at a time, but trying to handle both directions quickly leads to congestion. This is analogous to how eMMC may struggle when both reading and writing data simultaneously

How it works

Embedded: eMMC storage is not removable like an SD card. It’s a chip permanently soldered onto the device’s motherboard.
NAND Flash: At its core, eMMC uses NAND flash memory, the same type found in USB drives and SD cards. This non-volatile memory retains data even without power.
Integrated Controller: The key difference is that eMMC includes a dedicated controller chip. This controller handles all the low-level operations of reading, writing, and managing data stored on the flash memory.
Communication Interface: The eMMC chip connects to the device’s main processor through a standard interface (usually a parallel interface). This allows data transfer between the storage and the rest of the system.
Half-Duplex Operation: Data can only flow in one direction at a time (either read or write), creating a fundamental bottleneck and limiting eMMC’s overall speed potential

Pros

Affordability: eMMC is a mature technology making it a cost-effective storage solution for many devices.
Ubiquitous: Its wide adoption means the majority of budget and even some mid-range smartphones and tablets still utilize eMMC.

Cons

Speed Limitations: “Compared to newer storage technologies like UFS, eMMC has inherently slower read and write speeds.”
Bottlenecks: “This can make your device feel sluggish with tasks like heavy multitasking, opening large apps, or transferring lots of files.”

Understanding UFS

UFS, or Universal Flash Storage, is a significantly newer standard designed for maximum performance. It’s based on the SCSI command set (commonly used in high-performance computer storage) allowing for more efficient data management

Familiar Example

Imagine you’re a chef. An eMMC kitchen gives you one pan at a time. You can either cook the vegetables OR prepare the sauce, but not both simultaneously. A UFS kitchen provides you with multiple pans and burners, allowing you to cook efficiently and serve a dish twice as fast.

How it works

SCSI Architectural Model: UFS is based on the SCSI (Small Computer System Interface) architectural model, a well-established standard for connecting and transferring data between computers and storage devices. This architecture brings advanced features and greater efficiency.
Serial Interface: Instead of the parallel interface used by eMMC, UFS employs a high-speed serial interface called M-PHY (developed by the MIPI Alliance). This offers scalability to enable even faster performance in future device generations.
Multiple Lanes: The serial interface uses dedicated lanes for transmitting and receiving data. This is akin to having multiple highway lanes instead of just one. Higher versions of UFS support more lanes, leading to even greater data transfer speeds.
Full-Duplex Operation: Each lane in UFS can handle both reading and writing data at the same time. This simultaneous movement of data in both directions dramatically boosts throughput compared to eMMC.
Command Queuing: UFS features an intelligent command queuing system that allows the storage device to process multiple read and write requests in the most efficient order. This reduces wait times, maximizes speed, and further contributes to responsiveness.

Pros

Blazing Speed: UFS boasts drastically faster read and write speeds compared to eMMC. This results in a far snappier and smoother user experience in demanding tasks.
Efficient Multitasking: Thanks to its full-duplex capabilities and command queuing, UFS excels at handling multiple operations at once. This means smooth switching between apps, effortless background tasks, and responsive gaming.
Power Savings: While faster, UFS is surprisingly more power-efficient than eMMC, potentially improving your device’s battery life.

Cons

Higher Cost: Due to its complexity, UFS storage modules are more expensive to manufacture than eMMC, translating to a higher price tag for devices utilizing it.

Differences

Feature	eMMC	UFS
Speed	Slower read/write speeds	Significantly faster read/write speeds
Multitasking	More affordable	More expensive
Data transfer	Half-duplex (reads or writes at a time)	Full-duplex (reads and writes simultaneously)
Power efficiency	Less power-efficient	More power-efficient
Common use	Budget and mid-range devices	Flagship and high-performance devices

As you can see, UFS offers several advantages over eMMC in terms of speed, multitasking, data transfer, and power efficiency. However, it is also more expensive. So, the best choice for you will depend on your needs and budget.

If you are a casual user who does not need the fastest speeds or the most efficient multitasking, then eMMC may be a good option for you. However, if you are a power user who demands the best performance, then UFS is the way to go.

How to Check Your Phone’s Storage Type

Knowing the storage type of a phone you’re considering can help you make a more informed decision. Here’s how to find out whether a device uses eMMC or UFS storage:

Before Purchase

The Manufacturer’s Website: This is your best bet. Visit the device’s official product page and look for the detailed specifications section. Storage type (eMMC or UFS) and version (e.g. UFS 3.1) should be listed.
Tech Review Websites and Articles: Trusted review sources often delve into the details of a device’s performance, including the type of storage. Search for reviews and comparisons of the device that might mention the storage specification.
Device-Specific Forums or Communities: Enthusiast forums and subreddits are where you can find in-depth technical discussions. Users within these communities frequently share insights on a device’s storage technology.

After Purchase

Device Settings:
1. Go to Settings
2. Find About Phone (this path may vary slightly amongst devices)
3. Tap on Storage or Hardware Information. Some devices may indicate the storage type here.
Benchmarking Apps: Apps like AndroBench (available on Google Play) provide specific read/write speed tests. Significantly higher test results typically indicate UFS storage, while slower reads/writes suggest eMMC.

Important: Large online retailers don’t always make this specification apparent, focusing instead on storage capacity.

Conclusion

Now that you’re armed with the knowledge of eMMC and UFS, you’re better equipped to make a decision that suits your smartphone needs and budget. Remember, speed isn’t everything, but if you want the snappiest possible experience, opting for a UFS-equipped device will make a noticeable difference!

Radix Sort

Imagine sorting a pile of coins. Instead of comparing values directly, Radix Sort separates them based on the value of their least significant digit (like separating pennies from nickels). Then, it refines further by the next digit, like sorting nickels by their second digit. This intuitive, digit-by-digit approach leads to a beautifully sorted pile.

Process

Radix Sort, as the name suggests, takes inspiration from how we read numbers: digit by digit. Instead of complex comparisons, it sorts data by analyzing individual digits, making it particularly efficient for numbers or strings with fixed lengths. Let’s embark on this digit-by-digit sorting journey:

1. Digit Dive: Imagine a bucket brigade, where each bucket represents a possible value for a specific digit (0-9 in most cases). Radix Sort starts by analyzing the least significant digit (LSD) of each element. It then iterates through the data, throwing each element into the bucket corresponding to its LSD value.

2. Bucket Brigade: Now, each bucket holds elements with the same LSD. Radix Sort processes each bucket independently, potentially using another sorting technique like counting sort within each bucket. This ensures all elements within a bucket share the same LSD and are partially sorted.

3. Refining Order: Once all buckets are processed, it’s time for the next digit! Radix Sort shifts its focus to the second least significant digit (SLSD) and repeats the bucket brigade process. Now, elements are further sorted based on their SLSD within each bucket, refining the overall order.

4. Digit March: This digit-by-digit sorting continues, working its way up to the most significant digit (MSD). With each pass, the buckets contain increasingly refined groups of elements, and the overall order becomes clearer.

5. Final Assembly: After processing the MSD, all elements are finally in their correct positions within the main array. Radix Sort gathers them back from the buckets, resulting in a beautifully sorted list!

Pseudo Code

Code

function radixSort(array, d):
  # d is the maximum number of digits (adjust based on your data)
  # Create an empty array of buckets (0-9 in each bucket)
  buckets = [[None] * 10 for _ in range(d)]

  # Perform passes for each digit from LSD to MSD
  for digit in range(d):
    # Distribute elements into buckets based on their digit at the current position
    for num in array:
      digitValue = (num // 10**digit) % 10  # Extract the current digit
      buckets[digitValue].append(num)

    # Gather elements back from buckets in order
    arrayIndex = 0
    for bucket in buckets:
      for num in bucket:
        array[arrayIndex] = num
        arrayIndex += 1

      # Clear the bucket for the next iteration
      bucket[:] = []

  # Return the sorted array
  return array

Explanation

radixSort: This function takes the array to be sorted and the maximum number of digits (d) as input.
buckets: This array stores 10 sub-arrays, representing buckets for each possible digit (0-9).
digit loop: This loop iterates through each digit position, from least significant (LSD) to most significant (MSD).
Distributing elements: For each element in the array, its digit at the current digit position is extracted, and the element is placed in the corresponding bucket.
Gathering elements: After processing all elements for the current digit, the function iterates through each bucket and gathers the elements back into the main array in the order they appear in the buckets.
Clearing buckets: The buckets are cleared after each iteration to prepare for the next digit.
Return: The sorted array is returned.

Implementation

Kotlin

Golang

Counting Sort

Imagine having a box of mixed socks. Instead of painstakingly comparing each pair, Counting Sort counts the number of socks of each color, allowing you to instantly identify the most frequent (or least frequent) colors, creating order from chaos.

Process

Imagine a messy room overflowing with toys. While other sorting algorithms might meticulously compare each toy, Counting Sort takes a different approach: it counts! Yes, that’s right, it leverages the power of counting to bring order to chaos. Let’s delve into the steps:

1. Counting the Crew: First, Counting Sort creates a temporary array, one slot for each unique value (color, size, type) your toys might have. Then, it iterates through your room (data), patiently counting how many toys belong to each category (value). So, all the red cars get a tally in the “red car” slot, and so on.

2. Calculating Positions: With the popularity (count) of each value known, Counting Sort does some clever math. It calculates the starting position in the final sorted array for each value based on its count and the counts of previous values. Think of it as figuring out how much space each toy category deserves in the organized closet (final array).

3. Placing the Toys (Data): Finally, it’s time to put things away! Counting Sort goes back to your messy room (data) and visits each toy (element) one by one. Based on the toy’s value, it uses the calculated position from step 2 to place it in the correct spot in the final sorted array. It’s like having a map that tells you exactly where each toy belongs!

Pseudo Code

Code

function countingSort(array):
  # Find the maximum element in the array
  max_value = findMax(array)

  # Create a count array to store the frequency of each element
  count_array = [0] * (max_value + 1)

  # Count the occurrences of each element
  for i in range(len(array)):
    count_array[array[i]] += 1

  # Calculate the cumulative sum of the count array
  for i in range(1, len(count_array)):
    count_array[i] += count_array[i - 1]

  # Create the output array
  output_array = [0] * len(array)

  # Place elements in the output array based on their counts
  for i in range(len(array) - 1, -1, -1):
    output_array[count_array[array[i]] - 1] = array[i]
    count_array[array[i]] -= 1

  # Return the sorted array
  return output_array

# Function to find the maximum element
function findMax(array):
  max_value = array[0]
  for i in range(1, len(array)):
    if array[i] > max_value:
      max_value = array[i]
  return max_value

Explanation

findMax: This function finds the maximum element in the array, which determines the size of the count_array.
count_array: This array stores the count of each element. Each index represents a possible value, and the value at that index represents how many times that value appears in the original array.
Counting occurrences: The loop iterates through the original array, incrementing the corresponding element in the count_array for each occurrence.
Cumulative sum: This loop calculates the cumulative sum of the count_array. This means that each element at index i in the count_array now represents the starting position for elements with that value in the final sorted array.
output_array: This is where the sorted elements will be placed.
Placing elements: The loop iterates through the original array in reverse order. For each element, it uses its value to find its corresponding count in the count_array. This count indicates the correct position in the output_array, and the element is placed there. After placing, the count for that element is decremented to ensure correct placement of subsequent occurrences.
Return: The sorted array is returned.

Implementation

Kotlin

Golang

Heap Sort

Think of building a sandcastle and carefully placing each handful of sand to get the highest, perfect cone. Heap Sort works similarly, arranging data like a pyramid, ensuring the “biggest” (or “smallest”, depending on sorting order) element is always on top.

Process

Heap Sort, as the name suggests, involves creating and manipulating a special data structure called a heap to achieve sorted results. But don’t worry, you don’t need actual shovels and sandcastles for this! Let’s delve into the steps:

1. Heapify the Data: Imagine your data as a pile of pebbles. Heap Sort starts by transforming this pile into a “heap,” which resembles a pyramid-like structure. In this pyramid, the element at the top (the “root”) is always the “biggest” (or “smallest,” depending on the sorting order). Elements are carefully arranged based on their values to maintain this property.

2. Extract the “Biggest” Pebble: Just like picking the biggest pebble for your sandcastle, Heap Sort removes the element at the root (the “biggest” in this case) and places it aside. Remember, the heap property ensures this is indeed the largest element!

3. Maintain the Heap: But removing the top pebble disrupts the heap’s structure. Fear not! Heap Sort employs a clever technique called sifting. It replaces the empty root position with another element from the heap and “sifts” it down until the heap property is restored, ensuring the new root is indeed the “biggest.”

4. Repeat and Conquer: This process of extracting the “biggest” element, sifting, and restoring the heap continues until all elements are processed. By the end, the extracted elements, placed in the order they were removed, form the sorted list!

Pseudo Code

Code

function heapSort(array):
  # Build a max-heap from the input array
  buildMaxHeap(array)

  # Repeatedly extract the root (largest element) and swap it with the last element
  for i in range(len(array) - 1, 0, -1):
    swap(array[0], array[i])
    # Maintain the heap property for the remaining elements
    maxHeapify(array, 0, i)

# Functions for building and maintaining the max-heap

function buildMaxHeap(array):
  # Start from the last non-leaf node and sift downwards
  for i in range(len(array) // 2 - 1, -1, -1):
    maxHeapify(array, i, len(array))

function maxHeapify(array, root, heapSize):
  # Compare the root with its children and swap if necessary
  largest = root
  leftChild = 2 * root + 1
  rightChild = 2 * root + 2

  # Find the largest element among root, left child, and right child
  if leftChild < heapSize and array[leftChild] > array[largest]:
    largest = leftChild
  if rightChild < heapSize and array[rightChild] > array[largest]:
    largest = rightChild

  # Swap the root with the largest element if necessary
  if largest != root:
    swap(array[largest], array[root])
    # Recursively heapify the affected sub-tree
    maxHeapify(array, largest, heapSize)

# Swapping function
function swap(a, b):
  temp = a
  a = b
  b = temp

Explanation

The heapSort function takes an array as input.
The buildMaxHeap function builds a max-heap from the array, ensuring the element at the root is always the largest.
The maxHeapify function maintains the heap property by comparing the root element with its children and swapping if necessary.
The main loop of heapSort repeatedly extracts the root (largest element) and swaps it with the last element, reducing the heap size by 1 in each iteration.
The maxHeapify function is called again after each swap to maintain the heap property for the remaining elements.
The swap function simply exchanges the values of two elements.

Implementation

Kotlin

Golang

Quick Sort: The Speed Demon

Imagine sorting a room full of toys by color. Instead of meticulously comparing each toy, Quick Sort picks one (the “pivot”) and throws it like a ball, creating partitions based on colors “faster than light.” That’s the essence of Quick Sort, partitioning and conquering data with speed and a hint of playful chaos.

Process

Quick Sort, true to its name, lives up to its reputation for speed. But unlike a chaotic mess, its efficiency lies in a well-defined strategy: partitioning and conquering. Let’s delve into the steps of this whirlwind sorting dance:

1. Choose a Pivot: Imagine the data as a group of people waiting in line. Quick Sort picks one person (the pivot) and positions them somewhere in the line. This pivot isn’t random; it can be the first, last, or even a median element.

2. Partition the Line: Now comes the magic! Quick Sort iterates through the line, comparing each person to the pivot. Those shorter than the pivot move to one side, and those taller move to the other. Essentially, the line gets divided into two sections based on the pivot’s height.

3. Conquer and Repeat: But wait, the line isn’t sorted yet! Both the shorter and taller groups, though smaller now, might still be unsorted. So, Quick Sort recursively applies the same “choose-pivot-partition” strategy to each group, further dividing and conquering until each group has only one person (sorted!).

4. Merge and Conquer: Finally, when all groups have just one person (sorted!), Quick Sort meticulously merges them back together in the correct order, ensuring the entire line is now sorted from shortest to tallest (or vice versa, depending on how you define “shorter”).

Pseudo Code

Code

function quickSort(array, start, end):
  # Base case: sub-array with 0 or 1 element is already sorted
  if start >= end:
    return

  # Choose a pivot element (e.g., last element)
  pivot = array[end]

  # Partition the array around the pivot
  partitionIndex = partition(array, start, end, pivot)

  # Recursively sort the sub-arrays before and after the partition
  quickSort(array, start, partitionIndex - 1)
  quickSort(array, partitionIndex + 1, end)

function partition(array, start, end, pivot):
  # Initialize index variables
  i = start - 1
  for j in range(start, end):
    if array[j] <= pivot:
      i += 1
      # Swap elements at i and j
      swap(array[i], array[j])
  # Swap pivot element with element at i + 1 (now the partition index)
  swap(array[i + 1], array[end])
  return i + 1

function swap(a, b):
  # Swap the values of elements a and b
  temp = a
  a = b
  b = temp

Explanation

quickSort(array, start, end): This function takes a sub-array (defined by start and end indices) and sorts it using Quick Sort.
Base case: If the sub-array has 0 or 1 element, it’s already sorted and the function returns.
Choose a pivot: The function selects a pivot element (e.g., the last element).
Partition: The partition function rearranges the array elements:
- Elements less than or equal to the pivot are moved to the left side.
- Elements greater than the pivot are moved to the right side.
- The pivot element is placed at the partition index.
Recursive calls: The function recursively calls itself to sort the sub-arrays before and after the partition, excluding the pivot.
swap(a, b): This function swaps the values of two elements.

Implementation

Kotlin

Golang

Merge Sort

Imagine chopping a messy pile of vegetables into smaller pieces, sorting each pile individually, and then merging them back into a perfectly organized whole. That’s the essence of Merge Sort, dividing, sorting, and conquering data to achieve order.

Process

Merge Sort, unlike its comparison-based counterparts, takes a divide-and-conquer approach, resembling how a ruler conquers territories! Let’s dive into the steps:

1. Divide: Imagine the data as a kingdom waiting to be organized. The king (Merge Sort) divides the kingdom (data) into smaller provinces (sub-lists) of roughly equal size.

2. Conquer: Each province undergoes its own mini-conquest. If a province has only one element (citizen), it’s already sorted! Otherwise, the algorithm recursively divides and conquers each province further, breaking them down into even smaller units until each has only one element.

3. Merge and Rule: Once all provinces are single-element kingdoms, the real merging magic begins. The algorithm starts from the smallest conquered provinces and strategically combines them. Imagine two conquered provinces (sorted sub-lists) merging like neighboring kingdoms, carefully comparing and placing citizens (elements) in their rightful order to form a larger, sorted province.

4. Repeat and Expand: This merging continues, combining two sorted provinces at a time, creating larger and larger sorted territories. It’s like the conquered provinces forming alliances, growing in size and order until the entire kingdom (data) is united under the banner of a single, perfectly sorted list.

Pseudo Code

Code

function mergeSort(array):
  if length(array) <= 1:
    return array

  mid = floor(length(array) / 2)
  left = mergeSort(subarray(array, 0, mid))
  right = mergeSort(subarray(array, mid + 1, length(array)))

  return merge(left, right)

function merge(left, right):
  merged = []
  while length(left) > 0 and length(right) > 0:
    if first element of left <= first element of right:
      append first element of left to merged
      remove first element from left
    else:
      append first element of right to merged
      remove first element from right
  append remaining elements of left to merged
  append remaining elements of right to merged
  return merged

function subarray(array, start, end):
  # Creates a new subarray from the original array with specified start and end indices
  new_array = []
  for i in range(start, end):
    append element at index i of array to new_array
  return new_array

Explanation

mergeSort(array):

if length(array) <= 1: If the array has only one element or less, it’s already considered sorted and returned as-is.
mid = floor(length(array) / 2): Calculates the middle index of the array for dividing it into approximately equal halves.
left = mergeSort(subarray(array, 0, mid)): Recursively calls mergeSort on the left half of the array (from index 0 to mid-1).
right = mergeSort(subarray(array, mid + 1, length(array))): Recursively calls mergeSort on the right half of the array (from index mid+1 to the end).
return merge(left, right): Calls the merge function to combine the two sorted halves (left and right) into a single sorted array and returns it.

merge(left, right):

merged = []: Creates an empty array to store the merged result.
while length(left) > 0 and length(right) > 0: Continues the loop as long as both halves have elements left.
- if first element of left <= first element of right:
  - append first element of left to merged: Adds the smaller element from the left half to the merged array.
  - remove first element from left: Removes the added element from the left half.
- else:
  - append first element of right to merged: Adds the smaller element from the right half to the merged array.
  - remove first element from right: Removes the added element from the right half.
append remaining elements of left to merged: Appends any remaining elements in the left half to the merged array.
append remaining elements of right to merged: Appends any remaining elements in the right half to the merged array.
return merged: Returns the final sorted array after merging both halves.

subarray(array, start, end):

new_array = []: Creates a new empty array.
for i in range(start, end): Iterates through the elements from the specified start index to (but not including) the end index.
- append element at index i of array to new_array: Adds the element at the current index (i) from the original array to the new_array.
return new_array: Returns the newly created subarray containing the specified elements.

Implementations

Kotlin

Golang

Approach

Pseudo Code

Implementation

Approach

Pseudo Code

Implementation

Understanding Package Visibility

Enter the <queries> element

Placement

The QUERY_ALL_PACKAGES Permission

Proceed with caution

Typical Use Cases (When to Consider)

Best Practices and Tips

Conclusion

Approach

Pseudo Code

Implementation

Understanding eMMC

Understanding UFS

Differences

How to Check Your Phone’s Storage Type

Conclusion

Process

Pseudo Code

Implementation

Process

Pseudo Code

Implementation

Process

Pseudo Code

Implementation

Process

Pseudo Code

Implementation

Process

Pseudo Code

Implementations

The `QUERY_ALL_PACKAGES` Permission