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)
Comments
Post a Comment