DEV Community: Phanindra Allamsetty

1. Arrays & Hashing: Contains Duplicate

Phanindra Allamsetty — Wed, 19 Mar 2025 14:45:13 +0000

For a list of all coding patterns questions and tests, checkout my GitHub repo

Problem: Contains Duplicate

Given an integer array nums, return true _if any value appears at least twice in the array, and return _false if every element is distinct.

Example:
Input: nums = [1, 2, 3, 1]
Output: true
Explanation: The element 1 occurs at indices 0 and 3.

Example:
Input: nums = [1, 2, 3, 4]
Output: false
Explanation: No duplicate values are found.

Example:
Input: nums = [1, 1, 1, 3, 3, 4, 3, 2, 4, 2]
Output: true

Constraints:
- 1 <= nums.length <= 10^5
- -10^9 <= nums[i] <= 10^9

There are multiple ways of solving this problem. From the most naive solution, which is to run nested loops and compare if the same elements exists elsewhere to a less naive solution where you can sort the elements in the array and compare successive elements. If you see equal elements, you can return true. The nested loops method takes O(n^2) time whereas the sorting method takes O(nlong n) time. However, the space complexity id O(1) in both cases since we are using the same array to check for duplicates.

Another approach which is of O(n) time complexity and O(n) space complexity is to use a hashset to track each element and to detect duplicates. Using Hashmaps and Hashsets is usually the best approach to detect duplicates.

The way this approach works is that we create a hashset. For each element in the array, we check if it already exists in the hashset. If it does, we return true because we found a duplicate. If we don't find it, we add the element to the hashset and move on to the next one, where we do the same thing again.

Time complexity: O(n)
Space complexity: O(n)

public boolean containsDuplicate(int[] nums) {
    Set<Integer> numSet = new HashSet<>();

    for(int n: nums) {
        if(numSet.contains(n)) {
            return true;
        }

        numSet.add(n);
    }

    return false;
}

PRESTO card Metrolinx fare system

Phanindra Allamsetty — Mon, 23 Dec 2024 13:24:21 +0000

Introduction

PRESTO is the fare system for public transportation in the Greater Toronto Area. This system not only contains the city of Toronto but also other regional and city transit systems in the cities next to Toronto. Some of them are suburbs of Toronto whereas others are independent cities by themselves. In this post, we are trying to design the PRESTO ticket fare system.

While the annual number of usage counts in all the networks is approximately 41 million, not all of them use the PRESTO system. Some of them use Credit Cards/Debit Cards, day ticket, weekend ticket, cash, etc. However, for the sake of simplicity we will assume that all of them use the PRESTO system.

Workflow

The way this system works is a rider purchases a PRESTO card from one of the authorized vendors or the vending machines. Each PRESTO card has a number assigned to it to uniquely identify the card. The user can then login into the PRESTO app on their mobile or web and link that account with the card. A PRESTO account can have multiple cards linked to it. However, each PRESTO card can be linked to only one account. So there exists a one to many relationship between the user account and PRESTO card whereas a card to account relationship is one-to-one.

After linking these cards to their accounts, the users can use either credit card or debit card or their bank account to their account. This data needs to be securely saved for auto-pay. The user can "recharge" their card with a certain amount and can use the different transportation services by tapping their PRESTO card to a terminal device at each bus stop, train station, etc. Once the user taps this card, a certain amount is deducted which is valid for 2 hours. The amount deducted differs from one transportation network to another. For example, for TTC, it is $3.30 whereas for UP it is $9. This fare is valid until 2 hours. One exception to this rule are GO Transit and UP which do not depend on the duration. So the user needs to tap the card at both the source and destination to mark a trip and be charged accordingly.

Functional Requirements

The functional requirements for the PRESTO card should be:

User registration.
Linking PRESTO Card number with a user account.
"Tap" functionality, which calculates the amount to be charged.
The app should let the user check their current balance.
Fare inspector verification to check if the current PRESTO has an active trip.

Non-functional Requirements

The non-functional requirements for this system are:

High Availability: The system needs to be highly available. We are aiming for 99.5% availability duration.
Scalability: The system should easily scale up during peak traffic hours (office commute time), holidays or during special events because the number of user registrations, card linking requests and taps will go up significantly during those times.
Eventual Consistency can be tolerated because once the card is tapped, the local balance will be directly deducted but the balance can be updated later. We can have a periodic sync of the card balance with the server. Since only the first tap is considered in a two hour duration or two taps for GO and UP, we can update the data eventually in few minutes instead of instantaneously.

Back-of-the-envelope Estimates

We know that the number of taps in 2024 was 41 million. Considering an increase of 2 million people per year, we are looking at 51 million taps in 5 years. So the total number of taps in 5 years is 43 + 45 + 47 + 49 + 51 = 237 million, which is an average of 47.5 million tap requests, which is 47.5 * (10 ^ 6) requests per year.

This means the number of requests per second is ~55 requests per second.

Assume 100 new card registrations per day, which is a very small number per second.
The number of new user registrations is lesser than that. So we can assume 60 requests per second to the server.
Therefore, the number of servers needed is not a significant number.

Low-level Design

APIs:

POST /api/user
POST /api/card/{cardNumber}/{userId}
POST /api/card/{cardNumber}/tap/{terminalId}
GET /api/card/{cardNumber}/balance
GET /api/card/{cardNumber}/inspector/{inspectorId}

High-level Design

As stated earlier, the number of servers needed is not significant. But the number of servers needed could increase during peak hours or special events. Scaling up would mean adding new servers. This can happen during the times when the traffic is high. Since we need to dynamically change the number of servers based on the traffic, it would be good to add a load balancer.

The service layer can be broken into microservices, each handling a different aspect of the system such as the User service, Tap service, and the Card service. Since the scaling needs of each of these components is different, splitting them into microservices will make it easier to scale them up or down independently.

Also, it would make sense to have these services deployed in multiple pods and also in different regions. This is so that if one server were to go down, a server in a different region could take over and serve the incoming requests.

Since eventual consistency is what is needed, we can use a non-relational database such as MongoDB or Cassandra. This would ensure availability and scalability of data. This would also ensure that no data is lost. However, we need to add logic to calculate the balance separately. This would also keep the system simple.

Leetcode 227 (Java): Basic Calculator II

Phanindra Allamsetty — Fri, 02 Aug 2024 21:09:41 +0000

Problem:

Given a string s which represents an expression, evaluate this expression and return its value.

Assumptions and General Information:

The integer division should truncate toward zero.
You may assume that the given expression is always valid. All intermediate results will be in the range of [(-2^31), (2^31) - 1].
No built-in functions are allowed.
s represents a valid expression.
All the integers in the expression are non-negative integers in the range [0, (2^31) - 1].

Examples

Input: s = "3+2*2"
Output: 7

Input: s = "1 + 2 * 3 - 5 / 4"
Output: 6

Input: s = "2 * 35 - 7"
Output: 63

Constraints

1 <= s.length <= 3 * (10 ^ 5).
s consists of integers and operators ('+', '-', '*', '/') separated by some number of spaces.
The answer is guaranteed to fit in a 32-bit integer.

Solution

Brute Force

A naive approach to solve this problem would be to iterate through the string and find the operator with the highest precedence (in the order '/', '*', '+', '-') as per the BODMAS principle and perform the operation on the number preceding and succeeding the operator. We need to remember that we need to look for the number until we hit another operator or the lower or upper bounds of the string. We then calculate the result and save it. We then create another string with this intermediate result and move forward to the next operator.

Since we have 4 operators, we perform this 4 times. By the end of it we should have a string that can be typecasted to a string. We also try to find the numbers (instead of digits) on each side of the operator.The maximum time taken for this operation can also be n. Therefore, the time complexity will be O(n^2) and the space complexity includes creating a string for each of the iterations. Therefore, the space complexity of another O(n).

First Approach

We can use a stack to evaluate these expressions. Think of it as only one operation that needs to be performed on numbers in a stack. This would be a O(n) solution. In order for us to achieve that, we should evaluate all the other operations so that only one low precedence operation is left.
Let us assume addition as that operation.

For example, "1 + 2 * 3 - 5/ 4" can be simplified to "1 + 6 - 1". This can also be written as "1 + 6 + (-1)". If we have 1, 6 and -1 in the stack, we can just return their sum.

In order to implement this, we keep track of a current number and a current operator. When the current operator is '+', we just add the number to the stack. For '-', we add -1 times the number to the stack. For '*' and '/', we take the current top of the stack, perform the operation with the current number and put it back on to the stack. Towards the end, we will have a stack that contains elements that need to be added.

Code

public int calculate(String s) {
    char[] strArray = s.toCharArray();
    int currentNumber = 0;
    char operator = '+';
    Stack<Integer> stack = new Stack<>();
    int currentTop = -1;
    int newTop = -1;

    for (int i = 0; i < strArray.length; i++) {
        char currentChar = strArray[i];
        if (Character.isDigit(currentChar)) {
            currentNumber = currentNumber * 10 + currentChar - '0';
        }

        if ((!Character.isDigit(currentChar) && !Character.isWhitespace(currentChar)) || (i == strArray.length - 1)) {
            switch (operator) {
                case '+':
                    stack.push(currentNumber);
                    break;
                case '-':
                    stack.push(-1 * currentNumber);
                    break;
                case '*':
                    currentTop = stack.pop();
                    newTop = currentTop * currentNumber;
                    stack.push(newTop);
                    break;
                case '/':
                    currentTop = stack.pop();
                    newTop = currentTop / currentNumber;
                    stack.push(newTop);
                    break;
            }

            operator = currentChar;
            currentNumber = 0;
        }
    }

    int sum = 0;
    while (!stack.empty()) {
        sum += stack.pop();
    }

    return sum;
}

Optimized Approach

The above solution with a stack has a time complexity of O(n). However, the space complexity is also O(n) because we need to save elements onto a stack and the size of the stack varies with the input.

This problem can be solved in O(1) or constant space complexity. We will be making some changes to the above algorithm in order to avoid using the stack.

For this, we will use an integer variable called result, which will hold the intermediate result. Therefore, instead of saving elements to the stack, we just add them to result. However, there is an issue with '*' and '/', where we save the partial results to the stack. To avoid that, we will use another variable called lastNumber to hold the partial result.

Using these two variables, we can avoid using the stack therefore reduce the space complexity.

Code

public int calculate(String s) {
    char[] strArray = str.toCharArray();
    int currentNumber = 0;
    char currentOperator = '+';
    int result = 0;
    int lastNumber = 0;

    for(int i = 0; i < strArray.length; i++) {
        char currentChar = strArray[i];

        if(isDigit(currentChar)) {
            currentNumber = currentNumber * 10 + currentChar - '0';
        }

        if(!isDigit(currentChar) && !isWhitespace(currentChar) || i == strArray.length - 1) {
            switch(currentOperator) {
                case '+':
                    result += lastNumber;
                    lastNumber = currentNumber;
                    break;
                case '-':
                    result += lastNumber;
                    lastNumber = -1 * currentNumber;
                    break;
                case '*':
                    lastNumber = lastNumber * currentNumber;
                    break;
                case '/':
                    lastNumber = lastNumber / currentNumber;
                    break;
            }

            if(i == strArray.length - 1) {
                result += lastNumber;
            }

            currentNumber = 0;
            currentOperator = currentChar;
        }
    }
    return result;
}

Leetcode 143 (Java): Reorder Linked List

Phanindra Allamsetty — Thu, 01 Aug 2024 21:29:30 +0000

Problem: Given the head of a singly linked list. The list can be represented as:

L0 --> L1 --> L2 --> ... --> Ln-1 --> Ln

Reorder the list to be of the following form:

L0 --> Ln --> L1 --> Ln-1 --> ...

You may not modify the values in the list's nodes. Only nodes themselves may be changed.

Example:
Input: (1) --> (2) --> (3) --> (4) --> null
Output: (1) --> (4) --> (2) --> (3) --> null

Example:
Input: (1) --> (2) --> (3) --> (4) --> (5) --> null
Output: (1) --> (5) --> (2) --> (4) --> (3) --> null

Constraints:

The number of nodes in the list is in the range [1, 5 * 10^4]
1 <= Node.val <= 1000

Solution

A brute force algorithm to solve this problem would be to initialize a current pointer, navigate to the end of the linked list for each current pointer, and place the last node of the linked list as the next pointer of the current pointer. However, the time complexity for this solution is O(n^2) because we will be iterating through the linked list n times. The space complexity, however, is O(1).

A better solution would be to find the middle node of the linked list, reverse the second half of the linked list and then merge the first and second halves to the linked list.

Example:
(1) --> (2) --> (3) --> (4) --> (5) --> (6) --> null

Middle node:
middle
(1) --> (2) --> (3) --> (4) --> (5) --> (6) --> null

To find the middle node, we declare two pointers: fast and slow and initialize them to head of the linked list. The slow node traverses the nodes one after the other. The fast node traverses the nodes by skipping one node in each iteration making it twice as fast as the slow now. Therefore, by the time the fast node reaches the end of the linked list, the slow node would have reached the middle node.

ListNode slow = head;
ListNode fast = head;

while(fast != null && fast.next != null) {
  slow = slow.next;
  fast = fast.next.next;
}

Reverse the second half:
next
previous (4) --> (5) --> (6) --> null
current

                 next

previous <-- (4) (5) --> (6) --> null
current

     previous        next

null <-- (4) (5) --> (6) --> null
current

             previous        next

null <-- (4) <-- (5) (6) --> null
current

                     previous

null <-- (4) <-- (5) <-- (6) null
current

To reverse the second half of the linked list, we declare a current pointer and assign the slow pointer to it. Therefore, the current node points to the middle node of the linked list. We also assign two pointers, previous and next and assign them to null. previous will hold the current node when current moves on to the next pointer. This way we keep track of three pointers: previous, current and next.

We traverse through the second half of the linked list through the current pointer until we reach the end. For each iteration, we assign the next pointer to the next of current. We then assign the next of the current to the previous pointer. This way we are flipping the direction of the next pointers. We then assign the current to previous and next to current. This way all three pointers move one node forward while changing the order of the current node.

ListNode previous = null;
ListNode current = slow;
ListNode next = null;

while(current != null) {
  next = current.next;
  current.next = previous;
  previous = current;
  current = next;
}

This will make the previous node the second half in the reversed order.

Merge both halves:
(1) --> (6) --> (2) --> (5) --> (3) --> (4) --> null

By now, we have the second half of the linked list reversed. We need to assume both halves as two different linked lists and merge them and adjust the null pointer at the end accordingly.

ListNode first = head;
ListNode second = previous;
ListNode temp = head;

while(second.next != null) {
  temp = temp.next;
  first.next = second;
  second = second.next;
  first.next.next = temp;
  first = first.next.next;
}

Code

public ListNode reorder(ListNode head) {
  if(head == null) {
    return head;
  }


  // Find the middle node
  ListNode slow = head;
  ListNode fast = head;

  while(fast != null && fast.next != null) {
    slow = slow.next;
    fast = fast.next.next;
  } 

  // Reverse the second half of the linked list
  ListNode previous = null;
  ListNode current = slow;
  ListNode next = null;

  while(current != null) {
    next = current.next;
    current.next = previous;
    previous = current;
    current = next;
  }

  // Merge both halves
  ListNode first = head;
  ListNode second = previous;
  ListNode temp = head;

  while(second.next != null) {
    temp = temp.next;
    first.next = second;
    second = second.next;
    first.next.next = temp;
    first = first.next.next;
  }
  return head;
}

The time complexity of the above algorithm is O(n), whereas the space complexity if O(1).