Thursday, December 3, 2020

Get string in between braces when position of brace is given

 Let's say there is a string with braces and braces can be (),{},[] and the string has multiple sub-strings that are in braces. Given the position of start of a brace we need to print the string that qualifies. Say for example

Hello (This world is so beautiful (seriously) and I love it).

If the user inputs 1 as position, the output should be

This world is so beautiful (seriously) and I love it.

If the position is 2 then output should be seriously

Of course handle exceptions as well. How do we do that?


It looks tricky but a straight forward solution. The idea behind is to identify for a given brace where it ends. So, we leverage concept of stack. Algorithm is as follows

For each character in the string
If the character is opening brace, add it to a list
If the character is closing brace, pop the item from list (if there is no corresponding opening brace, we have an index out of range issue) and add the start and end positions to a dictionary/ hash map
After the complete string is traversed,
get the position from where the substring needs to be pulled. For that get the matching end and print the substring





def get_string_in_between(string_, brace, position):
    tmp_open_brace_pos = []
    brace_dict = {'(':')', '{':'}', '[':']'}
    start_end_pos_dict = {}
    if brace not in string_ or brace_dict.get(brace) not in string_:
        print('There are no recognized braces')
    else:
        for cnt, chr_ in enumerate(string_):
            if chr_ == brace:
                tmp_open_brace_pos.append(cnt)
            if chr_== brace_dict.get(brace):
                try:
                    start_end_pos_dict[tmp_open_brace_pos.pop()] = cnt
                except IndexError:
                    print('Unbalanced string. Too many closing braces')

    if tmp_open_brace_pos:
        print('There are too many opening braces')

    else:
        # sort the dictionary keys so we know the positions where the opening braces are
        ordered_indices = sorted(start_end_pos_dict)
        # indexes start at 0. However, the input will be >0 for position
        if position > len(ordered_indices):
            print('Out of range for start position. There are only {} braces'.format(str(len(ordered_indices))))
        else:
            return string_[ordered_indices[position-1]+1 : start_end_pos_dict[ordered_indices[position-1]]]


string = 'Hello (This world is so beautiful (seriously) and I love it)'


d = get_string_in_between(string, '(', 2)
print(d)

Tuesday, June 9, 2020

How to sort a list based on element's position

Let's say there is a list of numbers

data = [9,10,15,51,68,85,19]

Sort the list based on the number in the units place. So, here sort the data based on the second digit and output should be

[10, 51, 15, 85, 68, 9, 19]

Remember single digits has 0 prepended internally. We can do it with a single line using lambda and built in sort function of list

sorted(data, key=lambda x: x%10)

This works well for numerics. What if the list has a combination of strings and numerics or strings? In this case we want to convert everything into a string and sort based on the index of string required. In this example as we are looking at second digit/ letter, index will be 1 (remember indexes start with 0)

sorted(data, key=lambda x: str(x)[1] if len(str(x))>1 else str(x)[0])


Find pair of numbers that will generate target value

Let's say there is a list of values and you are given a target value. How will you find all the pair of numbers when added up will give the target value?

Example:

data = [1,5,11,2,10,9,3,2,10]
target = 12

In this example (1,11), (2,10), (9,3) and (2,10) again will produce the target of 12. However, we don't want to have the sequence of numbers repeating. How can we do that?

There are several ways to do it. However, the clean and easy way to do this is, removing duplicates from the list. How?

data = list(set(data))

We are converting list to set and back to list. This is going to remove duplicate values. Now to get the pairs, we can use list comprehension and produce list of tuples

[(val, target-val) for cnt,val in enumerate(data) if target-val in data[cnt+1:]]

Wednesday, October 31, 2018

Island and Gaps

create table #tmp_test_data
(
   row char(1)
   ,seat_no char(3)
   ,vacant char(1)
)

insert into #tmp_test_data
select 'A', 'A01', 'Y' UNION
select 'A', 'A02', 'Y' UNION
select 'A', 'A03', 'N' UNION
select 'A', 'A04', 'N' UNION
select 'A', 'A05', 'Y' UNION
select 'A', 'A06', 'Y' UNION
select 'A', 'A07', 'N' UNION
select 'A', 'A08', 'N' UNION
select 'A', 'A09', 'Y' UNION
select 'A', 'A10', 'N' UNION
select 'A', 'A11', 'Y' UNION
select 'A', 'A12', 'Y' UNION
select 'A', 'A13', 'Y' 

with cte1
as
(
    select *
          ,dense_rank() over(partition by row order by seat_no) as c_dr
          ,dense_rank() over(partition by row, vacant order by seat_no) as v_dr
          , dense_rank() over(partition by row order by seat_no) - dense_rank() over(partition by row, vacant order by seat_no) as grp
    from #tmp_test_data
),
cte2
as
(
    select Grp
           ,count(grp) as av_unav_cnt
            ,vacant
    from cte1
    group by grp, vacant
)
select row
        ,min(seat_no) as seat_no_start
        ,max(seat_no) as seat_no_end
        ,av_unav_cnt
        ,a.vacant
from cte1 a
join cte2 b on a.grp = b.grp and a.vacant = b.vacant
group by row, a.grp, av_unav_cnt,a.vacant

Monday, August 15, 2016

String Permutations in Python

"""This program prints the number of permutations of a given input. The number of permutation of a given input of length n is n! The algorithm is as follows 1. If the input length is less than or equal to 1, just return 2. For each element in the input, until the end of input is reached 3. Get the sub elements in the input except the current element that's being processed 4. Recursively traverse the sub elements 5. Append the recursive sublements to the current element 6. Return the list. """ def permutate(seq):#check the length of the input. If its less than or equal to 1, return the input as 1! is 1     if len(seq) <= 1:         return [seq]     else:         #Create a temporary list to hold the values         temp = []         #for each element in the given input, traverse until end of the the string         for k in range(len(seq)):             #get the subset of all the elements except the element
#that's being processed             #string slicing works this way             #get the elements until the current element +
#elements after the current element             part = seq[:k] + seq[k+1:]             #recursively traverse for the subset of elements             for m in permutate(part):                #append recursive element to the current element                 temp.append(seq[k] + m)         #return the final output after all the possible recursions are complete         return temp #Main Program #Prompt the user to enter input. Save it in user_input variable user_input = input("Enter the string of characters or numbers for permutations: ") #Call the permutate function and store the output into a list permutations = permutate(user_input) #traverse the list and print the permutations for perm in permutations:     print(perm)

Friday, July 15, 2016

Cleanse Phone Numbers (C++)

Recently I came across a question. The question is as follows.
1. There are several phone numbers (only US phone numbers). All the US phone numbers are basically in the format xxx xxx xxxx which is area code and 7 digit phone number. The number can have spaces between area code, first three digits of phone number or may be without spaces
2. The catch is that each phone number is re-arranged in a way that first three digits of phone number comes first then area code and then the last four digits.

Example:
Phone number is 425 123 4567 or 4251234567. This is the correct representation. But its stored as 123 425 4567 or 1234254567. This needs to be fixed and represented as the correct format. C++ code to cleanse the data. This is the quick solution that I got to. There may be several ways to achieve this


// FirstProject.cpp : Defines the entry point for the console application.
// This program assumes that the phone numbers are entered in the wrong order instead of area code and phone number its xxxareacodeandlastfournumbers
//Some times people may enter space/spaces between area code and first three numbers of phone.
//This program gets all the phone numbers into a vector, removes any spaces between numbers in the string and re-arranges values in the right order

#include "stdafx.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>


using namespace std;

//function prototype
void cleansePhoneNumbers(vector<string>&inputVector);


int main()
{
       vector<string> phoneNumbers;
       string phone = "";

       while (true) //start of infinite loop to add data to vector
       {
              cout << "Enter a phone number (press enter to exit):";
              getline(cin, phone); //get the data into phone string including spaces
              if (phone == "") //if just Enter key is pressed at the prompt
              {
                     break; //loop breaks
              }
              phoneNumbers.push_back(phone); //append the current value in phone to the vector
       }
      
       cleansePhoneNumbers(phoneNumbers); //function call to cleanse phone numbers


       for (string st : phoneNumbers) //for each string at the index of the vector
       {
              cout << "Cleansed Phone Numbers: " << st << endl; //print the value at that index
       }
       return 0;
}

//function definition
void cleansePhoneNumbers(vector<string>&inputVector)
{
       string *temp; //pointer to store address of each index of the vector
       int size;
       string val;
       size = inputVector.size(); //get the size of vector and assign it to size. Length of the vector
      
       for (int i = 0; i < size; i++) //traverse through each index
       {
              temp = &inputVector[i]; //get the address of index into temp pointer. This will be used to update the value in the vector directly
              val = inputVector[i]; //get the value at that index
      
              while (val.find(" ") != val.npos) //loop to remove any spaces in the string at a given idex
              {
                     val.replace(val.find(" "), 1, "");
              }

              val = val.substr(3, 3) + val.substr(0, 3) + val.substr(6, 4); //change the value
             
              *temp = val; //update value in the temp pointer so that actual data in the vector at that index changes

       }

}


Friday, December 4, 2015

Find Median For Given Set Of Numbers

/*
   MEDIAN RULE: IF COUNT OF NUMBERS IS ODD THEN THE VALUE IS MIDDLE NUMBER: FOR EXAMPLE MEDIAN FOR 1,8,10 WILL BE 8
                IF COUNT OF NUMBER IS EVEN THEN THE VALUE IS SUM(MIDDLE NUMBER + SUCCEEDING NUMBER TO MIDDLE NUMBER)/2.0 ESSENTIALLY ITS AN AVERAGE: FOR EXAMPLE 1,2,4,8
                MEDIAN IS (2+4)/2.0 WHICH IS 3.
*/


DECLARE @ArrayForMedian    VARCHAR(MAX) = '1,2,100,23,11,16,17,21,19,33,21,24'
DECLARE @FirstMedianValue  AS FLOAT
DECLARE @SecondMedianValue AS FLOAT
DECLARE @MedianValue       AS FLOAT

DECLARE @MedianTable AS TABLE
(
   ID INT IDENTITY(1,1) NOT NULL PRIMARY KEY
   ,Value INT NOT NULL
)

--traverse and split the string into individual numbers
;WITH ValueCTE
AS
(
   SELECT SUBSTRING(@ArrayForMedian + ',', 1, CHARINDEX(',', @ArrayForMedian +',') - 1) AS val
         ,SUBSTRING(@ArrayForMedian + ',',CHARINDEX(',', @ArrayForMedian +',') + 1, LEN(@ArrayForMedian + ',')) AS Rem

   UNION ALL

   SELECT SUBSTRING(Rem, 1, CHARINDEX(',',Rem) -1)
         ,SUBSTRING(Rem, CHARINDEX(',', Rem) + 1, LEN(Rem))
   FROM ValueCTE
   WHERE CHARINDEX(',',  Rem) <> 0
)
INSERT INTO @MedianTable
(
   Value
)
SELECT Val
FROM ValueCTE


--EVEN COUNT OF NUMBERS
IF (SELECT COUNT(*)%2
    FROM @MedianTable) = 0
BEGIN
   SELECT @FirstMedianValue = Value
   FROM @MedianTable
   WHERE ID = (SELECT COUNT(*)/2
               FROM @MedianTable)
   SELECT @SecondMedianValue = Value
   FROM @MedianTable
   WHERE ID = (SELECT (COUNT(*)/2) + 1
               FROM @MedianTable)

   SELECT @MedianValue = (@FirstMedianValue + @SecondMedianValue)/2.0
END
ELSE
--ODD COUNT OF NUMBERS
BEGIN
   SELECT @MedianValue = Value
   FROM @MedianTable
   WHERE ID = (SELECT CEILING(COUNT(*)/2.0)
               FROM @MedianTable)
END


SELECT @MedianValue