Skip to main content

Coding solutions - Medium

 



Array

Power set problem

#Given a set of distinct integers, nums, return all possible subsets (the power set).

#Note: The solution set must not contain duplicate subsets.

#Example:

#Input: nums = [1,2,3]

#Output:

#[[3],[1],[2],[1,2,3],[1,3],[2,3],[1,2],[]]

nums = [1,2,3]
def subsets1(nums):

if len(nums)==0:

return []

if len(nums)==1:

return [nums,[]]
    subsets = [[]]
    for num in nums:
        subsets += [[num] + lst for lst in subsets]
    return subsets
   
print (subsets1(nums))


#trace

#>>> sub = [[]]

#>>> sub += [[1] + lst for lst in sub]

#>>> sub

#[[], [1]]

#>>> sub += [[2] + lst for lst in sub]

#>>> sub

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

#>>> sub += [[3] + lst for lst in sub]

#>>> sub

#[[], [1], [2], [2, 1], [3], [3, 1], [3, 2], [3, 2, 1]]

#>> 

For example, let us say we only have the empty set {}. What happens to the power set if we want to add {a}? We would then have 2 sets: {}, {a}. What if we wanted to add {b}? We would then have 4 sets: {}, {a}, {b}, {ab}.

Notice 2^n also implies a doubling nature. 2^1 = 2, 2^2 = 4, 2^3 = 8, ...


Given a set, write a Python program to generate all possible subset of size n of given set within a list.

import math; 

  

def printPowerSet(set,set_size):
     
    # set_size of power set of a set
    # with set_size n is (2**n -1)
    pow_set_size = (int) (math.pow(2, set_size));
    counter = 0;
    j = 0;
     
    # Run from counter 000..0 to 111..1
    for counter in range(0, pow_set_size):
        for j in range(0, set_size):
             
            # Check if jth bit in the 
            # counter is set If set then 
            # print jth element from set 
            if((counter & (1 << j)) > 0):
                print (counter, 1<<j)

                #print(set[j], end = "");
        print("");
 
# Driver program to test printPowerSet
set = ['a', 'b', 'c'];

printPowerSet(set, 3); 



Given a set, write a Python program to generate all possible subset of size n of given set within a list.

import math; 

  

def printPowerSet(set,set_size):
     
    # set_size of power set of a set
    # with set_size n is (2**n -1)
    pow_set_size = (int) (math.pow(2, set_size))
    counter = 0
    j = 0
    subsets = []
    sum = 0
    # Run from counter 000..0 to 111..1
    for counter in range(0, pow_set_size):
        sub = ""
        for j in range(0, set_size):
             
            # Check if jth bit in the 
            # counter is set If set then 
            # print jth element from set 
            if((counter & (1 << j)) > 0):
                print(set[j], end = "")
                # Add this line when the subset array is of integer
                #sub += str(set[j])
                sub += set[j]
                # Add this to find sum of subset
                #sum += set[j]
        print("")
        # add this line to find subset of given length (not power set)
        if len(sub) == 2:
            subsets.append(sub)
    print (subsets)
    print (sum)
 
# Driver program to test printPowerSet
#set = [1, 1]
set = ['a','b','c']
# set = [1,2,3]
printPowerSet(set, 3)


#Given an array nums of n integers where n > 1,  return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

#Example:

#Input:  [1,2,3,4]

#Output: [24,12,8,6]

#Note: Please solve it without division and in O(n).


nums = [1,2,3,4]

#output array (just fill empty with 1s)
res = [1] * len(nums)
#left and right pointers
lo = 0
hi = len(nums) - 1
#product for left and right
leftProduct = 1
rightProduct = 1
#keep going until pointers meet
while lo < len(nums):
    #add running from the l/r products to these spots
    res[lo] *= leftProduct
    res[hi] *= rightProduct
    print ("res", res)
    #multiply products by current in nums
    leftProduct *= nums[lo]
    rightProduct *= nums[hi]
    print ("left", leftProduct)
    print ("right", rightProduct)
   
    #inc/dec pointers
    lo += 1
    hi -= 1

print (res)


Find all unique triplets which sums up to zero

Three sum problem

#Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

#Note:

#The solution set must not contain duplicate triplets.

#nums = [-1, 0, 1, 2, -1, -4]

#A solution set is:

#[

#  [-1, 0, 1],

#  [-1, -1, 2]

#]

s = []
nums = [-1, 0, 1, 2, -1, -4]
arr_size = len(nums)
for i in range(0, arr_size-2):
    for j in range(i+1, arr_size-1):
        for k in range(j+1, arr_size):
            if (nums[i] + nums[j] + nums[k] == 0):
                sub_list = [nums[i], nums[j], nums[k]]
                sub_list.sort()
                if sub_list not in s:
                    s.append(sub_list)

print ("Triplets using brute force", s)

# Using sorting
uni_list = []
nums = [-1, 0, 1, 2, -1, -4]
nums.sort() #sort
arr_size = len(nums) #len of array
target_sum = 0
r = arr_size - 1

for i in range(0, arr_size-1):
    l = i + 1 #fix to 2nd element
    while (l < r):
        curr_sum = nums[i] + nums[l] + nums[r]
        if (curr_sum < target_sum):
            l = l + 1
        elif (curr_sum > target_sum):
            r = r - 1
        elif (curr_sum == target_sum):
            sub_list = [nums[i], nums[l], nums[r]]
            sub_list.sort() #only if required
            if sub_list not in uni_list:
                uni_list.append(sub_list)
            l = l + 1

print ("Triplets using sorting", uni_list)

# Using hashmap - extension of 2 sum problem
nums = [-1, 0, 1, 2, -1, -4]
sum_ = 0
uni_set = []
for i in range (0, arr_size-1):
    s = set()
    cur_sum = sum_ - nums[i]
    for j in range(i+1, arr_size):
        t = cur_sum - nums[j]
        if t in s:
            uni_set.append([nums[i],nums[j],t])
        s.add(nums[j])

print ("Triplets using hashmap", uni_set)  


Find all possible combinations of k numbers that add up to a number n, given that only numbers 

# from 1 to 9 can be used and each combination should be a unique set of numbers.

# Input: k = 3, n = 9

# Output: [[1,2,6], [1,3,5], [2,3,4]]


s = [1,2,3,4,5,6,7,8,9]
t = 9
# ans [2,3,4], [1,2,6], [1,3,5]
res = []

for i in range(0, len(s)):
    sum_ = t - s[i] # sum_ has twom ele now
    for j in range(i+1, len(s)-1):
        third_ele = sum_ - s[j] #need to look for 3rd one
        if third_ele in s and (third_ele != s[i] and third_ele != s[j]):
            temp = [third_ele, s[i], s[j]]
            temp.sort()
            if temp not in res:
                res.append(temp)
print (res)


Rearrange positive and negative elements in an array

Given an array of positive and negative integers {-1,6,9,-4,-10,-9,8,8,4} (repetition allowed) sort the array in a way such that the starting from a positive number, 

#the elements should be arranged as one positive and one negative element maintaining insertion order. First element should be starting from positive integer and the 

#resultant array should look like {6,-1,9,-4,8,-10,8,-9,4}

#a = [-1,6,9,-4,-10,-9,8,8,4]
a = [1,6,9,-4,-10,-9,-8,8,4]
# What about zero # What if there are more +ve or -ve number, Should I put remaining at the end?
# Integers, Can i take extra memory ?
# p pointer and n pointer, keeping positive number's position intact, i will play with -ve numbers
# Time  o(n) and space o(1)
print (a)
i = 0
n_list = []
while (i < len(a)):
    if a[i] < 0:
        r = a[i]
        a.remove(r)
        n_list.append(r)
    else:
        i = i + 1
if len(a) <= 0:
    print ("no pos, so")
if len(n_list) <= 0:
    print ("no neg no")
i = 0   
j = 1
while (i<len(n_list)):
    neg = n_list[i]
    a.insert(j, neg)
    j = j + 2
    i = i + 1
print (a)

# time - o(n) + o(m) space- o(m)


def rightRotate(arr, n, outOfPlace, cur):
    temp = arr[cur]
    for i in range(cur, outOfPlace, -1):
        arr[i] = arr[i - 1]
    arr[outOfPlace] = temp
    return arr
 
def rearrange(arr, n):
    outOfPlace = -1
    for index in range(n):
        if(outOfPlace >= 0):
 
            # if element at outOfPlace place in 
            # negative and if element at index
            # is positive we can rotate the 
            # array to right or if element
            # at outOfPlace place in positive and
            # if element at index is negative we 
            # can rotate the array to right
            if((arr[index] >= 0 and arr[outOfPlace] < 0) or
              (arr[index] < 0 and arr[outOfPlace] >= 0)):
                arr = rightRotate(arr, n, outOfPlace, index)
                if(index-outOfPlace > 2):
                    outOfPlace += 2
                else:
                    outOfPlace =- 1
                     
        if(outOfPlace == -1):
             
            # conditions for A[index] to 
            # be in out of place
            if((arr[index] >= 0 and index % 2 == 0) or
              (arr[index] < 0 and index % 2 == 1)):
                outOfPlace = index
    return arr
 
# Driver Code
arr = [-5, -2, 5, 2, 4, 
        7, 1, 8, 0, -8]
 
print("Given Array is:")
print(arr)
 
print("\nRearranged array is:")
print(rearrange(arr, len(arr))) 


Hashmap

Given a string, sort it in decreasing order based on the frequency of characters.
# tree => 'eert' 
# 'e' appears twice while 'r' and 't' both appear once.
# So 'e' must appear before both 'r' and 't'. Therefore "eetr" is also a valid answer.
# Questions - special chars (tr@ee => eetr ? , spaces (treen nn => nnneert ?)
# function takes input as string and output as string, empty string if the string is empty 
# error cases
# count each chars, - dict o(n) + o(1)

def freq_sorting(str):
    if str is None:
        return None
    if str is "" or str is " ":
        return None
    str_dict = {}
    for char in str:
        if char in str_dict:
            str_dict[char] += 1
        else:
            str_dict[char] = 1

    out_str = ""
   
    for key in str_dict:
        k = keywithmaxval(str_dict)
        n = str_dict[k]
        while (n > 0):
            out_str += k
            n = n - 1
        str_dict[k] = 0
    return out_str

def keywithmaxval(d):
     """ a) create a list of the dict's keys and values;
        b) return the key with the max value""" 
    v=list(d.values())
     k=list(d.keys())
     return k[v.index(max(v))]       


str = "iiyyoooporo ioppr"
out = freq_sorting(str)
print (out)

#=======
def frequencySort(s):
    d, res = {}, ""
    for c in s:
        d[c] = d.get(c,0) + 1
    # sorted collects and then sorts the list. O (nlogn)
    dl = sorted(d, key=d.get, reverse=True)
   
    print (dl)
    for v in dl:
        res += (v * d[v])
    return res
   
s = "tree"
out = frequencySort(s)
print (out)
# Time -> o(n) + o(nlogn) + o(m) space-> o(n) + o(m)
#========

d = {'z':67, 'b':5, 'c':9}
print ("ndsfkjhfk", d)
nl = sorted(d.values())
nl = sorted(d.values(), reverse=True)
nl = sorted(d.keys())
print (nl)



Matrix 

2D array rotation - using extra memory

#2d array
a = [[1, 2, 3],
    [5, 6, 7],
    [8, 9, 10]]

b = [[0,0,0],

     [0,0,0],

     [0,0,0]]
m =  3
n = 3
def print_matrix(a):
    for r in range (0, m):
        for c in range(0, n):
            #print ("rowcoln",r,c)
            #print all
            print (a[r][c], end=' ')
        print ("\r")
   

print_matrix(a)


#for r in range (0, m):
#    for c in range(0, n):
#        b[ c ] [ m - r - 1 ] = a[ r ] [ c ]
   
#print_matrix(b)

#for r in range (0, m):
#    for c in range(0, n):
#        b[n-c-1] [r] = a[ r ] [ c ]

#print_matrix(b)

for r in range (0, m):
    for c in range(0, n):
        b[m-r-1] [n-c-1] = a[ r ] [ c ]

print_matrix(b)


2d array rotation in-place

a = [[1, 2, 3, 4],
    [5, 6, 7, 8],
    [17, 9, 10, 11],
    [12, 13, 14, 15]]
   
    #  00 01 02
    #  10 11 12
    #  20 21 22
N = 4

def print_matrix(a):
    for r in range (0, N):
        for c in range(0, N):
            #print ("rowcoln",r,c)
            #print all
            print (a[r][c], end=' ')
        print ("\r")
   

print_matrix(a)
print ("\r")

for x in range(0, int(N/2)):
    for y in range(x, N-x-1):
        temp = a[x][y]
       
        a[x][y] = a[y][N-1-x]
       
        a[y][N-1-x] = a[N-1-x][N-1-y]
       
        a[N-1-x][N-1-y] = a[N-1-y][x]
       
        a[N-1-y][x] = temp

print_matrix(a)


Print 2D matrix in spiral form

def spiralPrint(m, n, a) :
    k = 0; l = 0
 
    ''' k - starting row index
        m - ending row index
        l - starting column index
        n - ending column index
        i - iterator '''
     
 
    while (k < m and l < n) :
         
        # Print the first row from
        # the remaining rows
        for i in range(l, n) :
            print(a[k][i], end = " ")
             
        k += 1
 
        # Print the last column from
        # the remaining columns
        for i in range(k, m) :
            print(a[i][n - 1], end = " ")
             
        n -= 1
 
        # Print the last row from
        # the remaining rows
        if ( k < m) :
             
            for i in range(n - 1, (l - 1), -1) :
                print(a[m - 1][i], end = " ")
             
            m -= 1
         
        # Print the first column from
        # the remaining columns
        if (l < n) :
            for i in range(m - 1, k - 1, -1) :
                print(a[i][l], end = " ")
             
            l += 1
 
# Driver Code
a = [ [1, 2, 3, 4, 5, 6],
      [7, 8, 9, 10, 11, 12],
      [13, 14, 15, 16, 17, 18] ]
       
R = 3; C = 6
spiralPrint(R, C, a)
Labels:

Comments

Post a Comment

Popular posts from this blog

Coding solutions - Amazon card, Data structure, Search and Sort

  Amazon card, Data structure, search and sort Hashmap # HASH MAP implementation in python class Node :     def __init__ (self, key, value) :         self.key = key         self.value = value         self.next = None class HashMap :     def __init__ (self) :         self.store = [ None for _ in range( 16 )]     def get (self, key) :         index = hash(key) & 15         if self.store[index] is None :             return None         n = self.store[index]         while True :             if n.key == key:                 return n.value             else :                 if n.next:         ...
Post a Comment
Read more

Debugging round interview questions

Debugging round interview questions with answers. These are real questions asked in real interviews.  1. When you come in the morning, SLA has increased for the job searching portal (website). It was fine till today morning. How are you going to debug it? There is a matrix that shows service and it’s SLA. What are the steps you are going to take to debug this problem? Answer : If the SLA has gone up suddenly it's definitely a critical issue. I will first report this problem to all stakeholders. I will check listed points to debug the problem - 1. Check what went in the latest release if that is one  2. Check for nodes that are down. If there is an unusual number of nodes that are not reachable then report it to the infrastructure team. 3. Check for database repair which can cause slowness 4. Check its client-side delay or server-side delay to narrow down the issue 5. Check the geolocation of where the website is slow in order to narrow down 6. Check network bandwidth in the da...
Post a Comment
Read more

Types of Software Testing

Different types of Software Testing: Functional Testing types: Unit Testing: Individual units or components of the software are tested. A unit is the smallest testable part of the software. This is usually not manual and mostly done by developers as they write code. Integration Testing: Testing of all integrated modules of the software to make sure modules once combines works as expected or not. The best example would be FE and BE integration testing. System Testing:  The entire system is tested as per the defined requirements. Black box testing performed by QA. End to End Testing: Same as System testing but mimics more real-world use cases and interactions with network, databases and real users. Most companies combine system testing and end-to-end testing as there is a very thin line between both. Sanity Testing: Sanity testing is performed by the QA team to determine SW which is released is ready to do a full round of testing or not. This is usually quick and covers basic func...
Post a Comment
Read more