Replace where ever question mark is there in a string with 0 and 1 with all the patterns created.

Example : input string "a??b?" outputs are a00b0,a00b1,a01b0, a01b1... like that all possiblities Here is the sample code for same

	#!/usr/bin/env python
	str = "a??b?"
	string = list(str)
	dictionary = {'?':['0','1']}
	results = list()
	result_str = ''
	start = -1
	def getResults(word, start):
	for element in word[start:]:
	start += 1
	if start == len(word):
	if element == '?':
	word[start-1] =dictionary[element][0]
	results.append(''.join(word))
	word[start-1] =dictionary[element][1]
	results.append(''.join(word))
	return
	results.append(''.join(word))
	return
	if element == '?':
	word[start-1] =dictionary[element][0]
	getResults(word, start)
	word[start-1] = dictionary[element][1]
	getResults(word, start)
	start = 0
	getResults(string, start)
	print results

view raw qmarkpattern.py hosted with ❤ by GitHub

Print out an imutable singly linked list in reverse in linear time (O(n)) and less than linear space (space<(O(n))

Here is a solution for one pass reversing of singly linked list

	# !usr/bin/env python
	class Node:
	def __init__(self,data):
	self.data = data
	self.next = None
	class LinkedList:
	def __init__(self):
	self.head = None
	self.tail = None
	def addNode(self, data):
	temp = Node(data)
	if self.head == None:
	self.head = temp
	self.tail = temp
	else:
	self.tail.next = temp
	self.tail = temp
	def printList(self):
	temp = self.head
	while temp.next != None:
	print temp.data,
	print '->',
	temp = temp.next
	if temp.next == None :
	print temp.data
	def reverseList(self):
	if self.head == None:
	print "No list present"
	if self.head.next == None:
	return
	temp1 = self.head
	temp2 = self.head.next
	temp3 = temp2.next
	temp1.next = None
	if temp2.next == None:
	temp2.next = temp1
	temp1.next = None
	self.head = temp2
	return
	if temp3.next == None:
	temp3.next = temp2
	temp2.next = temp1
	self.head = temp3
	temp1.next = None
	return
	while(temp3.next != None):
	self.head = temp3
	nextleap = temp3.next
	temp3.next = temp2
	temp2.next = temp1
	temp1 = temp3
	temp2 = nextleap
	temp3 = temp2.next
	if temp3 == None :
	temp2.next = temp1
	self.head = temp2
	break
	if temp3.next == None:
	temp2.next= temp1
	temp3.next = temp2
	self.head = temp3
	break
	llist = LinkedList()
	llist.addNode(1)
	llist.addNode(2)
	llist.addNode(3)
	llist.addNode(4)
	llist.addNode(5)
	llist.addNode(6)
	llist.addNode(7)
	llist.addNode(8)
	llist.addNode(9)
	llist.addNode(10)
	llist.addNode(11)
	llist.addNode(12)
	llist.printList()
	llist.reverseList()
	llist.printList()

view raw reverseListOnePass.py hosted with ❤ by GitHub

String replacement with characters from Map to generate all possible combinations

String replacement with characters from Map to generate all possible combinations Given a hashmap M which is a mapping of characters to arrays of replacement characters, and an input string S, return an array of all possible combinations of S (where any character in S can be substituted with one of its substitutes in M, if it exists). What is the time complexity? What is the space complexity? Can you optimize either? Example input: M = { f: [F, 4], b: [B, 8] } S = fab Expected output: [FaB, Fa8, 4aB, 4a8]

	# !/usr/bin/env python
	dictionary = { 'f': ['F', 4], 'b': ['B', 8, 9] }
	strg = "fab"
	#[FaB, Fa8, 4aB, 4a8]
	stack = list()
	results = list()
	char = ""
	def getResults(start_index):
	charu = strg[start_index]
	if charu in dictionary:
	for element in dictionary[charu]:
	stack.append(element)
	if start_index == len(strg)-1:
	results.append(''.join(map(str, stack)))
	stack.pop()
	continue
	getResults( start_index+1)
	else:
	stack.append( charu)
	getResults(start_index+1)
	if stack:
	stack.pop()
	else:
	return results
	print getResults( 0)

view raw str_pattern_1.py hosted with ❤ by GitHub

String pattern generation based on Dictionary entries

Given a string as input, return the list of all the possible patterns: ''' { "1" : ['A', 'B', 'C'], "2" : ['D', 'E'], "12" : ['X'], "3" : ['P', 'Q'] } ''' Example if input is "123", then output is ["ADP","ADQ","AEP","AEQ","BDP","BDQ","BEP","BEQ","CDP","CDQ","CEP","CEQ","XP","XQ"]

	#! /usr/bin/env python
	dictionary = {'1':['A','B','C'],
	'2':['D','E'],
	'12': ['X'],
	'3':['P','Q']}
	str = "123"
	stack = list()
	def get_possible_patters(start_index):
	results = list()
	if start_index >= strlen:
	return results
	end_index = start_index
	while(end_index < strlen):
	substring = str[start_index:end_index+1]
	if substring in dictionary:
	for element in dictionary[substring]:
	stack.append(element)
	if end_index == strlen-1:
	results.append(''.join(stack))
	else:
	result = get_possible_patters(end_index+1)
	if len(result) == 0:
	#there is a dead end, stop the for loop
	break
	else:
	results += result
	stack.pop()
	end_index += 1
	return results
	strlen = len(str)
	print get_possible_patters(0)

view raw str_dictpattern.py hosted with ❤ by GitHub

Merging overlapping lists

You are given two lists of intervals, A and B.

In A, the intervals are sorted by their starting points. None of the intervals within A overlap.

Likewise, in B, the intervals are sorted by their starting points. None of the intervals within B overlap.

Return the intervals that overlap between the two lists.

Example:

A: {[0,4], [7,12]}
B: {[1,3], [5,8], [9,11]}
Return:

{[1,3], [7,8], [9,11]}

How would you do this?

Here is a solution

	#!/usr/bin/env python
	def mergeLists(L1 , L2):
	len1 = len(L1)
	len2 = len(L2)
	print len1
	print len2
	index1 = 0
	index2 = 0
	pickx = 0
	picky = 0
	mergeList = []
	while (L1[index1][1] > L2[index2][0]):
	if (L1[index1][0] < L2[index2][0]):
	pickx = L2[index2][0]
	else:
	pickx = L1[index1][0]
	if (L1[index1][1] < L2[index2][1]):
	picky = L1[index1][1]
	else:
	picky = L2[index2][1]
	print "%d , %d" %(pickx,picky)
	mergeList.append([pickx,picky])
	index2 = index2+1
	if (index2 == len2):
	print "break"
	break
	if (L2[index2][0] < L1[index1][1]):
	continue
	else:
	index1 = index1 + 1
	if (index1 == len1-1):
	exit
	return mergeList
	L1 = [[0,4], [7,12]]
	L2 = [[1,3], [5,8], [9,11]]
	print mergeLists(L1, L2)

view raw mergeLists.py hosted with ❤ by GitHub

Passing a variable as type , using templates.

Often we may need to transfer the type itself to a function. Here is the implementation done using an example for determining the size of the variable type using templates. You cannot do this normal way as setting type is a compile time activity. If you use templates you can defer this action for compile time and would give you the ability to determine type during compile time. This is edited using the Visual Studio editor.

	#include "stdafx.h"
	#include "iostream"
	#include "string"
	class Test {
	public:
	template <typename T>
	int getSizeInfo(){
	return sizeof(T);
	}
	};
	int main(){
	Test t;
	std::cout << "bool : "<<t.getSizeInfo<bool>() << std::endl;
	std::cout << "char : " << t.getSizeInfo<char>() << std::endl;
	std::cout << "wchar_t : " << t.getSizeInfo<wchar_t>() << std::endl;
	std::cout << "char16_t : " << t.getSizeInfo<char16_t>() << std::endl;
	std::cout << "char32_t : " << t.getSizeInfo<char32_t>() << std::endl;
	std::cout << "short : " << t.getSizeInfo<short>() << std::endl;
	std::cout << "int : " << t.getSizeInfo<int>() << std::endl;
	std::cout << "long : " << t.getSizeInfo<long>() << std::endl;
	std::cout << "long long : " << t.getSizeInfo<long long>() << std::endl;
	std::cout << "float : " << t.getSizeInfo<float>() << std::endl;
	std::cout << "double : " << t.getSizeInfo<double>() << std::endl;
	std::cout << "long double : " << t.getSizeInfo<long double>() << std::endl;
	return 0;
	}

view raw PassingType.cpp hosted with ❤ by GitHub