Skip to content

Instantly share code, notes, and snippets.

@anirbanroydas

anirbanroydas/Sample output of running test_triplet_sum.py

Last active December 6, 2016 19:50
Show Gist options
  • Save anirbanroydas/212ae1a7c48410b79e0c02bbb308a400 to your computer and use it in GitHub Desktop.
Save anirbanroydas/212ae1a7c48410b79e0c02bbb308a400 to your computer and use it in GitHub Desktop.
Download ZIP
triplet_sum : find triplet (3 integers) in an array of size n whose sum is S. It also logs data both to file and I/O stream. Its also configurable. Its also scalable. Its also fault tolerant.
Raw
log_conf.py
"""This module defines the base loggers that can be used to log any kinds of data be it, debug, info, error, warning, critical,
both in a log file and also in the I/O stream.
To change the name of log file, or log level for file and also for stream, just change the constants at the top level.
This is configurable as per your requirements.
"""
# Initate logging loggers, and handlers
import logging
# create formatter
DEFAULT_FORMAT = '[%(levelname)s]: [%(asctime)s] [%(name)s] [%(module)s:%(lineno)d] - %(message)s'
DEFAULT_DATE_FORMAT = '%d-%m-%y %H:%M:%S'
DEFAULT_LOG_FILE = 'triplet_sum.log'
DEFAULT_FILE_LOGLEVEL = logging.INFO
DEFAULT_STREAM_LOGLEVEL = logging.ERROR
DEFAULT_LOGGER_LOGLEVEL = logging.INFO
def get_logger(module_name):
"""Function to return the logger for each module used in the application.
:param module_name: the module name where the logger is called from
:type moduele_name: str
:rerturn: The logger object
:rtype: logging.LOGGER
"""
# File logging
logging.basicConfig(level=DEFAULT_FILE_LOGLEVEL, filename=DEFAULT_LOG_FILE, format=DEFAULT_FORMAT, datefmt=DEFAULT_DATE_FORMAT)
# create console handler and set level to DEBUG
stream_handler = logging.StreamHandler()
stream_handler.setLevel(DEFAULT_STREAM_LOGLEVEL)
formatter = logging.Formatter(DEFAULT_FORMAT, DEFAULT_DATE_FORMAT)
# add formatter to handler
stream_handler.setFormatter(formatter)
# initiate a logger
stream_logger = logging.getLogger(module_name)
# set level for Logger
stream_logger.setLevel(DEFAULT_LOGGER_LOGLEVEL)
# add handler to logger
stream_logger.addHandler(stream_handler)
return stream_logger
Raw
requirements.txt
python >=2.7, <3.0
concurrent.futures
pytest
Raw
Sample output of running test_triplet_sum.py
================================================================================ test session starts ================================================================================
platform darwin -- Python 2.7.11, pytest-2.9.2, py-1.4.31, pluggy-0.3.1 -- /usr/local/opt/python/bin/python2.7
cachedir: .cache
rootdir: /Users/Roy/Documents/Github/sources/private/adwyze-interview/round1/triplet_sum, inifile:
collected 19 items
test_triplet_sum.py::test_triplet_sum_base_case_with_3_positive_elems_and_positive_sum PASSED
test_triplet_sum.py::test_triplet_sum_base_case_with_3_positive_elems_and_negative_sum PASSED
test_triplet_sum.py::test_triplet_sum_base_case_with_3_negative_elems_and_positive_sum PASSED
test_triplet_sum.py::test_triplet_sum_base_case_with_3_negative_elems_and_negative_sum PASSED
test_triplet_sum.py::test_triplet_sum_base_case_with_three_0_elems PASSED
test_triplet_sum.py::test_triplet_sum_base_case_with_duplicate_elems PASSED
test_triplet_sum.py::test_exists_pairs_of_sum_with_positive_elems PASSED
test_triplet_sum.py::test_exists_pairs_of_sum_with_negative_elems PASSED
test_triplet_sum.py::test_exists_pairs_of_sum_for_duplicate_elems PASSED
test_triplet_sum.py::test_exists_pairs_of_sum_for_small_size_array PASSED
test_triplet_sum.py::test_exists_pairs_of_sum_with_invalid_elements PASSED
test_triplet_sum.py::test_triplet_sum_hash_map_with_positive_elems PASSED
test_triplet_sum.py::test_triplet_sum_hash_map_with_negative_elems PASSED
test_triplet_sum.py::test_triplet_sum_hash_map_with_duplicate_elems PASSED
test_triplet_sum.py::test_triplet_sum_hash_map_with_invalid_elements PASSED
test_triplet_sum.py::test_triplet_sum_sorting_raising_NotImplementedError PASSED
test_triplet_sum.py::test_triplet_sum_with_valid_array_hash_map_algorithm PASSED
test_triplet_sum.py::test_triplet_sum_with_Invalid_array PASSED
test_triplet_sum.py::test_triplet_sum_with_valid_array_sorting_algorithm PASSED
============================================================================= 19 passed in 0.33 seconds =============================================================================
Raw
Sample output of running test_utils.py
================================================================================ test session starts ================================================================================
platform darwin -- Python 2.7.11, pytest-2.9.2, py-1.4.31, pluggy-0.3.1 -- /usr/local/opt/python/bin/python2.7
cachedir: .cache
rootdir: /Users/Roy/Documents/Github/sources/private/adwyze-interview/round1/triplet_sum, inifile:
collected 6 items
test_utils.py::test_is_valid_array_with_good_array_of_length_gte_3 PASSED
test_utils.py::test_is_valid_array_with_bad_arrays PASSED
test_utils.py::test_is_valid_number_with_good_number PASSED
test_utils.py::test_is_valid_number_with_bad_number PASSED
test_utils.py::test_is_valid_config_with_good_configurations PASSED
test_utils.py::test_is_valid_config_with_bad_configurations PASSED
============================================================================= 6 passed in 0.18 seconds ==============================================================================
Raw
test_triplet_sum.py
""" This module does the testing of the module triplet_sum.
To run the test:
$ py.test test_triplet_sum.py -v
"""
import pytest
import sys
from triplet_sum import exists_pairs_of_sum, triplet_sum_base_case, triplet_sum_hash_map, triplet_sum_sorting, triplet_sum
def setup_module(module):
print "\nsetup_module module: %s \n\n" % module.__name__
def teardown_module(module):
print "\n\nteardown_module module: %s " % module.__name__
# def setup_function(function):
# print ("setup_function function: %s " % function.__name__)
# def teardown_function(function):
# print ("teardown_function function: %s " % function.__name__)
def test_triplet_sum_base_case_with_3_positive_elems_and_positive_sum():
"""This functions tests the function triplet_sum_base_case with 3 positve elements
and a positive sum.
"""
arr = [5, 2, 11]
sum = 18
print
assert triplet_sum_base_case(arr, sum) == 1
assert triplet_sum_base_case(arr, sum - 1) == 0
assert triplet_sum_base_case(arr, sum + 1) == 0
assert triplet_sum_base_case(arr, sum - 5) == 0
assert triplet_sum_base_case(arr, 0) == 0
def test_triplet_sum_base_case_with_3_positive_elems_and_negative_sum():
"""This function tests the function triplet_sum_base_case with 3 positive elements
and a negative sum.
"""
arr = [5, 2, 11]
sum = -18
print
assert triplet_sum_base_case(arr, sum) == 0
assert triplet_sum_base_case(arr, sum - 5) == 0
assert triplet_sum_base_case(arr, sum + 5) == 0
assert triplet_sum_base_case(arr, 0) == 0
def test_triplet_sum_base_case_with_3_negative_elems_and_positive_sum():
"""This function tests the function triplet_sum_base_case with 3 negative elements and
a positive sum.
"""
arr = [-5, -2, -11]
sum = 18
print
assert triplet_sum_base_case(arr, sum) == 0
assert triplet_sum_base_case(arr, sum - 5) == 0
assert triplet_sum_base_case(arr, 0) == 0
def test_triplet_sum_base_case_with_3_negative_elems_and_negative_sum():
"""This function tests the function triplet_sum_base_case with 3 negative elements and
a negative sum.
"""
arr = [-5, -2, -11]
sum = -18
print
assert triplet_sum_base_case(arr, sum) == 1
assert triplet_sum_base_case(arr, sum - 1) == 0
assert triplet_sum_base_case(arr, sum + 1) == 0
assert triplet_sum_base_case(arr, sum - 5) == 0
assert triplet_sum_base_case(arr, sum + 5) == 0
assert triplet_sum_base_case(arr, 0) == 0
def test_triplet_sum_base_case_with_three_0_elems():
"""This function tests the function triplet_sum_base_case with 3 zero value elements.
"""
arr = [0, 0, 0]
sum = 0
print
assert triplet_sum_base_case(arr, sum) == 1
assert triplet_sum_base_case(arr, sum - 1) == 0
assert triplet_sum_base_case(arr, sum + 1) == 0
assert triplet_sum_base_case(arr, sum - 5) == 0
assert triplet_sum_base_case(arr, sum + 5) == 0
def test_triplet_sum_base_case_with_duplicate_elems():
"""This function tests the function triplet_sum_base_case with duplicate elements.
"""
arr = [2, 120, 120]
print
assert triplet_sum_base_case(arr, 242) == 1
assert triplet_sum_base_case(arr, -242) == 0
assert triplet_sum_base_case(arr, 240) == 0
assert triplet_sum_base_case(arr, 0) == 0
arr = [1111, 1111, 1111]
assert triplet_sum_base_case(arr, 3333) == 1
assert triplet_sum_base_case(arr, -3333) == 0
assert triplet_sum_base_case(arr, 3332) == 0
assert triplet_sum_base_case(arr, 0) == 0
arr = [-151, -151, 10]
assert triplet_sum_base_case(arr, -292) == 1
assert triplet_sum_base_case(arr, 292) == 0
assert triplet_sum_base_case(arr, -302) == 0
assert triplet_sum_base_case(arr, 0) == 0
arr = [-11111, -11111, -11111]
assert triplet_sum_base_case(arr, -33333) == 1
assert triplet_sum_base_case(arr, 33333) == 0
assert triplet_sum_base_case(arr, 0) == 0
assert triplet_sum_base_case(arr, -33332) == 0
assert triplet_sum_base_case(arr, -33334) == 0
def test_exists_pairs_of_sum_with_positive_elems():
"""This function tests the function exists_pairs_of_sum with positive sum.
"""
arr = [5, 1, 20, 40]
print
assert exists_pairs_of_sum(arr, start_index=0, array_length=4, sum=21) == (True, [(1, 20)])
assert exists_pairs_of_sum(arr, start_index=0, array_length=4, sum=-21) == (False, [])
assert exists_pairs_of_sum(arr, start_index=0, array_length=4, sum=20) == (False, [])
assert exists_pairs_of_sum(arr, start_index=0, array_length=4, sum=22) == (False, [])
assert exists_pairs_of_sum(arr, start_index=0, array_length=4, sum=0) == (False, [])
def test_exists_pairs_of_sum_with_negative_elems():
"""This function tests the function exists_pairs_of_sum with negative sum.
"""
arr = [-5, 1, -20, 40, -21, -22]
print
assert exists_pairs_of_sum(arr, start_index=0, array_length=6, sum=-21) == (True, [(-22, 1)])
assert exists_pairs_of_sum(arr, start_index=0, array_length=6, sum=-20) == (True, [(-21, 1)])
assert exists_pairs_of_sum(arr, start_index=0, array_length=6, sum=-19) == (True, [(-20, 1)])
assert exists_pairs_of_sum(arr, start_index=0, array_length=6, sum=20) == (True, [(-20, 40)])
assert exists_pairs_of_sum(arr, start_index=0, array_length=6, sum=-1) == (False, [])
assert exists_pairs_of_sum(arr, start_index=0, array_length=6, sum=1) == (False, [])
assert exists_pairs_of_sum(arr, start_index=0, array_length=6, sum=-41) == (True, [(-21, -20)])
assert exists_pairs_of_sum(arr, start_index=0, array_length=6, sum=41) == (True, [(1, 40)])
def test_exists_pairs_of_sum_for_duplicate_elems():
"""This function tests the function exists_pairs_of_sum with duplicate sum.
"""
arr = [-5, 1, -20, 40, -20, -22, 1, -5, -5, -5, -5, 9, 30, -1, 40, 1, 1, 9, -22]
n = len(arr)
print
assert exists_pairs_of_sum(arr, start_index=0, array_length=n, sum=-21) == (True, [(-22, 1), (-20, -1)])
assert exists_pairs_of_sum(arr, start_index=0, array_length=n, sum=21) == (False, [])
assert exists_pairs_of_sum(arr, start_index=0, array_length=n, sum=41) == (True, [(1, 40)])
assert exists_pairs_of_sum(arr, start_index=0, array_length=n, sum=-10) == (True, [(-5, -5)])
assert exists_pairs_of_sum(arr, start_index=0, array_length=n, sum=20) == (True, [(-20, 40)])
assert exists_pairs_of_sum(arr, start_index=0, array_length=n, sum=0) == (True, [(-1, 1)])
assert exists_pairs_of_sum(arr, start_index=0, array_length=n, sum=32) == (False, [])
def test_exists_pairs_of_sum_for_small_size_array():
"""This function tests the function exists_pairs_of_sum with smaller size of array.
"""
arr = [5, 1, 20, 40]
print
assert exists_pairs_of_sum(arr, start_index=0, array_length=4, sum=21) == (True, [(1, 20)])
assert exists_pairs_of_sum(arr, start_index=1, array_length=4, sum=21) == (True, [(1, 20)])
assert exists_pairs_of_sum(arr, start_index=2, array_length=4, sum=21) == (False, [])
assert exists_pairs_of_sum(arr, start_index=3, array_length=4, sum=21) == (False, [])
assert exists_pairs_of_sum(arr, start_index=0, array_length=4, sum=0) == (False, [])
def test_exists_pairs_of_sum_with_invalid_elements():
"""This function tests the function exists_pairs_of_sum with invalid elements in th array.
"""
print
with pytest.raises(Exception):
arr = [5, 1, 20, 'invalid_value', 40]
assert exists_pairs_of_sum(arr, start_index=0, array_length=5, sum=6)
with pytest.raises(Exception):
arr = [5, 1, -sys.maxint - 5, 20, 40]
assert exists_pairs_of_sum(arr, start_index=0, array_length=5, sum=6)
def test_triplet_sum_hash_map_with_positive_elems():
"""This function tests the function triplet_sum_hash_map with positive elements.
"""
arr = [5, 1, 20, 40]
print
assert triplet_sum_hash_map(arr, 21) == 0
assert triplet_sum_hash_map(arr, 60) == 0
assert triplet_sum_hash_map(arr, 46) == 1
assert triplet_sum_hash_map(arr, 65) == 1
assert triplet_sum_hash_map(arr, 26) == 1
assert triplet_sum_hash_map(arr, -23432) == 0
assert triplet_sum_hash_map(arr, -65) == 0
assert triplet_sum_hash_map(arr[1:], 61) is None
assert triplet_sum_hash_map(arr[1:], -2) is None
assert triplet_sum_hash_map(arr[2:], 60) is 0
def test_triplet_sum_hash_map_with_negative_elems():
"""This function tests the function triplet_sum_hash_map with negative elements.
"""
arr = [-5, 1, -20, 40, -21, -22, -3]
print
assert triplet_sum_hash_map(arr, 21) == 1
assert triplet_sum_hash_map(arr, 60) == 0
assert triplet_sum_hash_map(arr, -40) == 1
assert triplet_sum_hash_map(arr, -42) == 1
assert triplet_sum_hash_map(arr, -43) == 0
assert triplet_sum_hash_map(arr, -23432) == 0
assert triplet_sum_hash_map(arr, 0) == 0
assert triplet_sum_hash_map(arr, -1) == 1
assert triplet_sum_hash_map(arr[2:], -63) == 1
assert triplet_sum_hash_map(arr[2:], -3) == 1
assert triplet_sum_hash_map(arr[2:], 3) is 0
def test_triplet_sum_hash_map_with_duplicate_elems():
"""This function tests the function triplet_sum_hash_map with duplicate elements.
"""
arr = [-5, 1, -20, 40, -20, -22, 1, -5, -5, -5, -5, 9, 30, -1, 40, 1, 1, 9, -22]
print
assert triplet_sum_hash_map(arr, 0) == 1
assert triplet_sum_hash_map(arr, -15) == 1
assert triplet_sum_hash_map(arr, 1) == 1
assert triplet_sum_hash_map(arr, 30) == 1
assert triplet_sum_hash_map(arr, 80) == 0
assert triplet_sum_hash_map(arr, -23432) == 0
def test_triplet_sum_hash_map_with_invalid_elements():
"""This function tests the function triplet_sum_hash_map with invalid elements.
"""
print
arr = [5, 1, 20, 10, 8, 'invalid_value', 40, -5, -5, -5, 9, 30, -1, 40, 1]
assert triplet_sum_hash_map(arr, -15) == -1
assert triplet_sum_hash_map(arr, 26) == -1
assert triplet_sum_hash_map(arr, -15) == -1
assert triplet_sum_hash_map(arr, 38) == -1
assert triplet_sum_hash_map(arr, 31) == -1
assert triplet_sum_hash_map(arr, 25) == -1
arr = [5, 1, 0, 1, 0, -sys.maxint - 5, 20, 40]
assert triplet_sum_hash_map(arr, 1) == -1
def test_triplet_sum_sorting_raising_NotImplementedError():
"""This function tests the function triplet_sum_sorting.
"""
print
with pytest.raises(NotImplementedError):
arr = [-5, 1, -20, 40, -20, -22, 1, -5, -5, -5, -5, 9, 30, -1, 40, 1, 1, 9, -22]
assert triplet_sum_sorting(arr, -40)
def test_triplet_sum_with_valid_array_hash_map_algorithm():
"""This function tests the function triplet_sum with valid array and hash_map algorithm.
"""
print
arr = [-5, 1, -20, 40, -20, -22, 1, -5, -5, -5, -5, 9, 30, -1, 40, 1, 1, 9, -22]
assert triplet_sum(arr, sum=-40, algorithm='hash_map') == 0 or triplet_sum(arr, sum=-40, algorithm='hash_map') == 1
def test_triplet_sum_with_Invalid_array():
"""This function tests the function triplet_sum with invalid array.
"""
print
arr = [-5, 1, -20, 40, -20, "-22", 1, -5, -5, -5, -5, 9, 30, -1, 40, 1, 1, 9, -22]
assert triplet_sum(arr, sum=-40, algorithm='hash_map') == -1
def test_triplet_sum_with_valid_array_sorting_algorithm():
"""This function tests the function triplet_sum with valid array and sorting algorithm.
"""
print
arr = [-5, 1, -20, 40, -20, "-22", 1, -5, -5, -5, -5, 9, 30, -1, 40, 1, 1, 9, -22]
with pytest.raises(NotImplementedError):
assert triplet_sum(arr, sum=-40, algorithm='sorting')
Raw
test_utils.py
"""This is the testing module for testing the utils module.
To run the test:
$ py.test test_utils.py -v
"""
import sys
from utils import is_valid_array, is_valid_number, is_valid_config
def setup_module(module):
print "\nsetup_module module: %s \n\n" % module.__name__
def teardown_module(module):
print "\n\nteardown_module module: %s " % module.__name__
# def setup_function(function):
# print ("setup_function function: %s " % function.__name__)
# def teardown_function(function):
# print ("teardown_function function: %s " % function.__name__)
def test_is_valid_array_with_good_array_of_length_gte_3():
arr = [-5, 1, -20, 40, -20, -22, 1, -5, -5, -5, -5, 9, 30, -1, 40, 1, 1, 9, -22]
print
assert is_valid_array(arr) is True
assert is_valid_array(arr[:4]) is True
assert is_valid_array(arr[:3]) is True
def test_is_valid_array_with_bad_arrays():
arr = [-5, 1, -20, 40, -20, -22, 1, 'invalid input', -5, -5, -5, 9, 30, -1, 40, 1, 1, 9, -22]
print
assert is_valid_array(arr) is True
assert is_valid_array(arr[0:2]) is False
assert is_valid_array(arr[0]) is False
assert is_valid_array(tuple(arr)) is False
assert is_valid_array() is False
def test_is_valid_number_with_good_number():
print
assert is_valid_number(0) is True
assert is_valid_number(12345) is True
assert is_valid_number(-12341324) is True
assert is_valid_number(sys.maxint - 1) is True
assert is_valid_number(-sys.maxint - 1 + 1) is True
def test_is_valid_number_with_bad_number():
print
assert is_valid_number('0') is False
assert is_valid_number('abcd') is False
assert is_valid_number('-12341324') is False
assert is_valid_number(sys.maxint + 1) is False
assert is_valid_number(-sys.maxint - 1 - 1) is False
assert is_valid_number() is False
def test_is_valid_config_with_good_configurations():
print
good_config = {
'array': [-5, 1, -20, 40, -20, -22, 1, -5, -5, -5, -5, 9, 30, -1, 40, 1, 1, 9, -22],
'sum': 30,
'algorithm': 'hash_map'
}
assert is_valid_config(good_config) is True
def test_is_valid_config_with_bad_configurations():
print
bad_configs = {
'array': [-5, 1, -20, 40, -20, -22, 1, -5, -5, -5, -5, 9, 30, -1, 40, 1, 1, 9, -22],
'sum': 30,
'algo': 'hash_map'
}
assert is_valid_config(bad_configs) is False
del bad_configs['algo']
bad_configs['algorithm'] = 'quicksort'
assert is_valid_config(bad_configs) is False
bad_configs['algorithm'] = 'hash_map'
bad_configs['array'] = tuple(bad_configs['array'])
assert is_valid_config(bad_configs) is False
bad_configs['array'] = list(bad_configs['array'])
bad_configs['sum'] = '12343'
assert is_valid_config(bad_configs) is False
bad_configs['sum'] = 14
bad_configs['algorithm'] = 34
assert is_valid_config(bad_configs) is False
assert is_valid_config() is False
Raw
triplet_sum.log
[INFO]: [08-08-16 12:35:19] [__main__] [triplet_sum:178] - Found Triplet number 1: (-5, -5, 40)
[INFO]: [08-08-16 12:35:19] [__main__] [triplet_sum:178] - Found Triplet number 2: (1, -1, 30)
[INFO]: [08-08-16 12:35:19] [__main__] [triplet_sum:178] - Found Triplet number 3: (40, -5, -5)
[INFO]: [08-08-16 12:35:19] [__main__] [triplet_sum:178] - Found Triplet number 4: (30, -1, 1)
Raw
triplet_sum.py
"""This module has functions which actually find the triplets given in an array.
Features:
1. The array and the sum are taken from the configuration file.
2. This module also take the algorithm to use to find the triplets.
3. The module function triplet_sum returns all the copies of triplets,
4. and returns all the triplets (including the duplicate by combination but unique by positions)
"""
from operator import itemgetter
import triplet_sum_config as config
from utils import is_valid_array, is_valid_number, is_valid_config
from log_conf import get_logger
LOGGER = get_logger(__name__)
def exists_pairs_of_sum(arr, start_index, array_length, sum):
"""This function finds if there is pair of integers in the given array whose sum is equal to the given sum.
This funciton basically solves a subproblem of our triplet sum problem.
The function takes as input the original array reference, the starting index of the array from where the elements
are to be considered in the respective call of the function and also the sum for which the pair is to be found.
This function returns all the pairs avaialble. But it doesn't return the duplicate pairs. The duplicates are inelligently handled.
:param arr: the original array reference
:type arr: list
:param start_index: the starting index of the array from where to consider the elements from
:type start_index: int
:param array_length: length of the original array
:type array_length: int
:param sum: the sum for which the pair of integers is to be found
:type sum: int
:return: a tuple of (exists, list of pairs)
:rtype: tuple
"""
# [-5, 1, -20, 40, -20, -22, 1, -5, -5, -5, -5, 9, 30, -1, 40, 1, 1, 9, -22]
exists = False # return value if pair exists for particalur some or not
list_of_pairs = list() # list of all unique pairs
hash_map = dict() # a key-value pair hash table
result = None
for i in xrange(start_index, array_length):
number = arr[i]
if not is_valid_number(number):
raise Exception
temp_key = sum - number
if temp_key in hash_map:
# handle duplicate pairs
if hash_map[temp_key] == 1:
# pair exists condition satisfies
if number <= temp_key:
pair = (number, temp_key)
else:
pair = (temp_key, number)
exists = True
list_of_pairs.append(pair)
# make value at this key and at temp_key as 2, so to change it from 1,
# this will not allow a duplicate key to enter this if condition next time
hash_map[temp_key] = 2
else:
# handle duplicate pairs
# initialize hash_map with this key only if it has
# come across this key for the first time, otherwise don't to exclue the duplicate case
if number not in hash_map:
hash_map[number] = 1
# final result which is a tuple of the boolean value exists and the list of pairs
list_of_pairs.sort(key=itemgetter(0))
result = (exists, list_of_pairs)
return result
def triplet_sum_base_case(arr, sum):
"""This function handles the special case when the original array is of lenght 3.
It basically checks if the sum of the 3 elements is equal to required sum or not.
It checks for the validity and then sends the output.
:param arr: the original array reference
:type arr: list
:param sum: the sum for which the triplet is to be found
:type sum: int
:return: either the tripler present or not, if present the log the result and output to I/O
:rtype: int
"""
num_1, num_2, num_3 = arr[0], arr[1], arr[2]
if not is_valid_number(num_1) or not is_valid_number(num_3) or not is_valid_number(num_3):
return -1
if sum == num_1 + num_2 + num_3:
# logs the single found triplet info
LOGGER.info('Found Triplet number 1: (%d, %d, %d) ' % (num_1, num_2, num_3))
print 'Triple No. 1: (%d, %d, %d) ' % (num_1, num_2, num_3)
return 1
else:
# log no triplet found info
LOGGER.info('No Triplet present for given sum')
print 'No Triplet present for given sum'
return 0
def triplet_sum_hash_map(arr, sum):
"""This function implements the triplet sum problem using the hashing algorithm.
The function takes the array and the required sum as input and returns all the triplets possible.
The function calls for each array element progressiveley moving forward, the exists_pair_sum function to solve the
problem in order of n complexity.
:param arr: the original array reference
:type arr: list
:param sum: the sum for which the triplet is to be found
:type sum: int
:return: the triplets
:rtype: int
"""
# Complexity : Time - O(n2) , Space - O(n)
# [-5, 1, -20, 40, -20, -22, 1, -5, -5, -5, -5, 9, 30, -1, 40, 1, 1, 9, -22]
array_length = len(arr) # length of array
count = 0 # count of number of unique triplets
duplicate_check_list = dict() # a dictionary(hash map) of all unique elements of array
exists = False # boolean value for pair of temp_sum exists or not, returned as a tuple element by the function exists_pairs_of_sum
list_of_pairs = list() # list of all unique pairs returned as a tuple element by the function exists_pairs_of_sum
# handles the case when length of array is equal to 3 (special case)
if array_length == 3:
triplet_sum_base_case(arr, sum)
return
for i in xrange(0, array_length - 2):
number = arr[i]
if not is_valid_number(number):
return -1
# handle duplicate triplet condition
# check if already considered the same element previously
if number in duplicate_check_list:
continue
temp_sum = sum - number
arr_start_index = i + 1
try:
exists, list_of_pairs = exists_pairs_of_sum(arr, arr_start_index, array_length, temp_sum)
except:
return -1
if exists:
for pairs in list_of_pairs:
# logs each found triplet info
LOGGER.info('Found Triplet number %d: (%d, %d, %d) ' % (count + 1, number, pairs[0], pairs[1]))
# increment triplet count by 1
count = count + 1
print 'Triplet No. %d: (%d, %d, %d) ' % (count, number, pairs[0], pairs[1])
# hndles duplicate triplet condition
# add key, arr[i], to the duplicate_checking dictionary(hash_map) to handle the duplicate triplet condition
duplicate_check_list[number] = 1
# hanles case when no triple found
if count == 0:
# logs the no triple found info
LOGGER.info('No Triplet present for given sum')
print 'No Triplet present for given sum'
return 0
else:
return 1
def triplet_sum_sorting(arr, sum):
"""This function implements the triplet sum problem using the sorting algorithm.
The function takes the array and the required sum as input and returns all the triplets possible.
The functoin first sorts the array using timsort which has avg and worst case time complexity of O(nlogn) and worse space complexity of O(n).
Then the function for each array element progressiveley moving forward, finds the pair in the rest of the array using modified binary search
method for the modified sum of sum - arr[i], where i is the element in consideration in the current loop executoin while progressively moving forward.
:param arr: the original array reference
:type arr: list
:param sum: the sum for which the triplet is to be found
:type sum: int
:return: the triplets
:rtype: int
"""
# log NotImplementedError
LOGGER.error('NotImplementedError Exception raised: while calling triplet_sum_sorting')
# Todo
# Complexity : Time - Worst(Timsort)-> O(nlogn) + O(n2) or Worst(Quicksort)-> O(n2), Space - O(n) (Timsort) or O(1) (Quicksort)
raise NotImplementedError
def triplet_sum(arr, sum, algorithm):
"""This function is the main method called by the main function.
The function takes the array and the required sum as input and returns all the triplets possible.
The functoin calls either triplet_sum_hash_map or triplet_sum_sorting according the configuration parameter.
Hence the application is configurable.
:param arr: the original array reference
:type arr: list
:param sum: the sum for which the triplet is to be found
:type sum: int
:param algorithm: the algorithm to use, hash_map or sorting
:type algorithm: str
:return: either the success/failure informatoin or raises an exception if anything goes wrong
:rtype: int
"""
# check for validity of array, i.e, its length, its type, its element's type.
if not is_valid_array(arr):
# return since array is not valid
return -1
if algorithm == 'hash_map':
try:
result = triplet_sum_hash_map(arr, sum)
return result
except:
raise
elif algorithm == 'sorting':
try:
result = triplet_sum_sorting(arr, sum)
return result
except:
raise
def main():
config_data = config.inputs
if not is_valid_config(config_data):
# invalid settings, so returning
return
arr = config_data['array']
sum = config_data['sum']
algorithm = config_data['algorithm']
try:
result = triplet_sum(arr, sum, algorithm)
if result == -1:
LOGGER.error('Unsuccessful Attempt overall')
print 'Unsuccessful Attempt'
except:
LOGGER.error('Unsuccessful Attempt overall')
print 'Unsuccessful Attempt'
if __name__ == "__main__":
main()
Raw
triplet_sum_config.py
"""This is the configuration file, which can be used to change the settings of the input and
change settings of how the application will run.
The configurable settings gives the power of customizing the tests, or the application as a whole.
This also makes the app much more development friendly.
This also makes the app user friendly.
"""
inputs = {
# The array whichi is a list of n numbers
'array': [-5, 1, -20, 40, -20, -22, 1, -5, -5, -5, -5, 9, 30, -1, 40, 1, 1, 9, -22],
# The given sum of the triplet to find
'sum': 30,
# the algorithm to use : either hash_map or sorting
'algorithm': 'hash_map'
}
Raw
utils.py
"""This module basically contains all the utility functions which are called for
many sub problems which are used many times in the main program.
This module also has a lot of constant which you can change and further configure your requirements.
"""
import sys
from log_conf import get_logger
LOGGER = get_logger(__name__)
MIN_ARRAY_LENGTH = 3 # Minimum array length = 3
MAX_ARRAY_LENGTH = 10000000 # Maximum array length = 10 million
ARRAY_TYPE = list # Data type of array object, this case its list
ARRAY_ELEMENT_TYPE = int # Data tpye of elements of array
MAX_ELEMENT_VALUE = sys.maxint # Maximum value of indivdual element of the array
MIN_ELEMENT_VALUE = -sys.maxint - 1 # Minmum value of indivdual element of the array
# define("algo", default='hash_map', help="Algorithm to use to solve the
# problem, either hash_map or sorting", type=str)
def is_valid_array(arr=None):
"""This function checks if the given array is valid or not.
For validity it checks if the array is of type list and it checks for the size limits of the array.
:param arr: the original array reference
:type arr: list
:return: True of False if its valid or not
:rtype: bool
"""
if not arr:
return False
if not isinstance(arr, list):
# logs the error regarding invalid array data type
LOGGER.error('Not a Valid Array: Array should be a list object.')
return False
array_length = len(arr)
if array_length < MIN_ARRAY_LENGTH or array_length > MAX_ARRAY_LENGTH:
# logs the error regarding invalid array size
LOGGER.error('Not a Valid Array: Array of length should be atleast 3 and less than 10 million. Array_lenght: %d ' % array_length)
return False
# if all conditions pass, the return as Valid array
return True
def is_valid_number(number=None):
"""This function checks if the given number of the array is valid or not.
For validity it checks if the number is of type int and it checks for the range limits of the number.
:param number: the element of array to check validity for
:type number: int
:return: True of False if its valid or not
:rtype: bool
"""
if not number and number != 0:
return False
if not isinstance(number, int):
# logs the error regarding invalid element type
LOGGER.error('Not a Valid Number: Indivdual elements of list should be of type Integer(int)- Number: %s ' % str(number))
return False
if number < MIN_ELEMENT_VALUE or number > MAX_ELEMENT_VALUE:
# logs the error regarding invalid value of element
LOGGER.error('Not a Valid Number: Indivdual elements of list should be of greater system min and less than system max- Number: %s ' % str(number))
return False
return True
def is_valid_config(config_data=None):
"""This function checks if the given config in the configuration file is valid or not.
For validity it checks if the config has all the keys, thier types, their value ranges and type.
:param config_data: the config from the configuration file
:type config_data: int
:return: True of False if its valid or not
:rtype: bool
"""
if not config_data:
return False
if not isinstance(config_data, dict):
# logs the error regarding invalid inputs data type
LOGGER.error('Inputs is not valid: Inputs in settings should be a dictionary object')
return False
if 'array' not in config_data or 'sum' not in config_data or 'algorithm' not in config_data:
# logs the error regarding invalid inputs keys
LOGGER.error('Invalide Inputs keys. Settings\' inputs dictionary should have all the 3 keys, [arr], [sum] and [algorithm]')
return False
if not isinstance(config_data['array'], list):
# logs the error regarding invalid inputs type
LOGGER.error('Invalide array type. Array should be of type list.')
return False
if not isinstance(config_data['sum'], int):
# logs the error regarding invalid inputs type
LOGGER.error('Invalide Sum type. Sum should be of type int.')
return False
if not isinstance(config_data['algorithm'], str):
# logs the error regarding invalid inputs type
LOGGER.error('Invalide Algorithm type. Algorithm should of type str.')
return False
algorithm = config_data['algorithm']
if algorithm != 'hash_map' and algorithm != 'sorting':
# logs the error regarding invalid algorithm
LOGGER.error('Invalide algorithm value. it should be either hash_map or sorting. Algorithm: %s ' % algorithm)
return False
return True
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment