Galileo
BAN USERPython simple BFS solution :
def isValid(mods):
"""Helper function to see if the string is valid."""
stack = []
for i in xrange(len(mods)):
if stack and stack[-1] == '(' and mods[i] == ')':
stack.pop(-1)
else:
stack.append(mods[i])
return not stack
def makeValidString(str):
if not str or isValid(str):
return str
visited, queue = set(), [str]
while queue:
element = queue.pop(0)
for i in xrange(len(element)):
newElement = element[:i] + element[i+1:]
if newElement not in visited:
if isValid(newElement): return newElement
queue.append(newElement)
visited.add(newElement)
Simple Python solution.
a) Get the sum of the input array. If its odd, there can never be two equal parts.
b) If its even, iterate the array and see if the expected sum can be attained or not.
def checkSum(arr):
if sum(arr)%2 != 0: return False
expected = sum(arr)/2
i = curr = 0
while curr < expected:
curr += arr[i]
i += 1
return (arr[:i], arr[i:]) if curr == expected else False
Python solution for converting to double linked list:
def doConvert(node, isLeft=False):
if not node:
return node
node.prev = doConvert(node.left, True)
node.next = doConvert(node.right, False)
if node.prev: node.prev.next = node
if node.next: node.next.prev = node
return node.next or node if isLeft else node.prev or node
Python solution for decoding ways:
def decodeWays(ints):
if not ints or ints.startswith('0'): return 0
dp = [1 for i in xrange(len(ints)+2)]
for i in xrange(len(ints)):
if ints[i] == '0':
if int(ints[i-1]) < 1 or int(ints[i-1]) > 2:
return 0
dp[i+2] = dp[i]
else:
dp[i+2] = dp[i+1]
if 10 < int(ints[i-1:i] + ints[i]) < 27:
dp[i+2] += dp[i]
return dp[-1]
Python solution to print the maxSum subarray.
def getMaxSum(array):
if not array or len(array) == 1:
return None
maxSum = seriesSum = None
for i in xrange(1, len(array)):
if seriesSum is not None:
seriesSum = max(seriesSum + array[i], array[i]+array[i-1])
maxSum = max(seriesSum, maxSum)
else:
seriesSum = maxSum = array[i] + array[i-1]
return maxSum
Functional testing
1) Check if the page is loaded
2) Check if password entered is masked
3) If login is remembered, check if closing the browser and relogging doesnt
take to login page
4) If login is not remembered check if cookies helps to remember the session
within the period
5) Check if user id and password is authenticated
6) If there is two step authentication check if it works
7) If javascript is disabled check if 'sign on' submit triggers the process
8) Check if sign-on page is reloaded after 'signing out'
9) Check if error-message is displayed when entered with incorrect input ie invalid user id or pwd
10) Check if error-message is displayed when password or user id is not entered
11) Check if after login, it doesn't take back to the login page when the website
is opened in a new tab
12) Check if password restrictions are applied when entering password ie integer 0-9,
characters and special characters etc,.
Usability testing
1) Availability of user id and password tab
2) Check if user id and password form field is long enough
3) If there is captcha, check if characters are visible and readable
4) If there is 'remember me' option, check if its a tick box
5) Check if 'sign on' button is available and clickable
6) Check if 'sign out' button is available and clickable
7) Check if the messages displayed ie 'Invalid user-id and password' are visible, clear
and is not truncated
Compatability:
1) Check if everything works in different browsers
Integration:
1) If cookie or history is cleaned, the sign-on page should be re-loaded
2) If browser is closed after sign-on check if the sign-on is not re-loaded on opening again
3) Check if sign-on page works in browser incognito mode.
4) Check if browser stores passwords in cookie during a session
5) Check if browser stores passwords in local desk when 'remember me' option is checked
Performance:
1) sign-on to the application with multiple user accounts at the same time and
capture latency of authentication
Appearance:
1) Check if images and favicon is loaded when the page is requested
2) Check if window is re-sized when browser size is changed
b_found = False
def checkpath(root):
global b_found
if not root:
return False
if root.val == C:
return True
m = checkpath(root.left) or checkpath(root.right)
if m :
if root.val == B:
b_found = True
elif root.val == A:
if not b_found:
return False
return True
else:
return False
b_found = False
def checkpath(root):
global b_found
if not root:
return False
if root.val == C:
return True
m = checkpath(root.left) or checkpath(root.right)
if m :
if root.val == B:
b_found = True
elif root.val == A:
if not b_found:
return False
return True
else:
return False
Approach:
Traverse the tree:
a) if C value is found return True and keep searching for B
b) When B is found in the path mark as True and keep searching for A along the same path
c) When A is also found return True and exit
d) If any of A or B or root or leaf is encountered while the other elements are not found return False. e.g if A is found when B is not still found
b_found = False
def checkpath(root):
global b_found
if not root:
return False
if root.val == C:
return True
m = checkpath(root.left) or checkpath(root.right)
if m :
if root.val == B:
b_found = True
elif root.val == A:
if not b_found:
return False
return True
else:
return False
Simple Python solution:
a) Traverse left and right calculating count of 1s in path on both. Return max as the final count
b) Where 0 is encountered reset count for the path to 0 and return
c) When leaf is encountered return the count
def max_path(root, count):
if not root:
return count
if root.val == 0:
return 0
else:
count += 1
count = max(max_path(root.left, count), max_path(root.right, count))
return count
Simple Python solution:
a) Traverse left and right calculating count of 1s in path on both. Return max as the final count
b) Where 0 is encountered reset count for the path to 0 and return
c) When leaf is encountered return the count
def max_path(root, count):
if not root:
return count
if root.val == 0:
return 0
else:
count += 1
count = max(max_path(root.left, count), max_path(root.right, count))
return count
Simple Python solution:
a) Traverse left and right calculating count of 1s in path on both. Return max as the final count
b) Where 0 is encountered reset count for the path to 0 and return
c) When leaf is encountered return the count
def max_path(root, count):
if not root:
return count
if root.val == 0:
return 0
else:
count += 1
count = max(max_path(root.left, count), max_path(root.right, count))
return count
Solution in python:
def travel(root):
if not root.left and not root.right: # Prints leaves
if not root.visit:
root.visit = True
print root.val
return
if root.left: # Lefts are traversed first and printed
if not root.left.visit:
root.left.visit = True
print root.left.val
travel(root.left)
travel(root.right)
if root.right: # This is visited after it hits a leaf and prints it
if not root.right.visit:
root.right.visit = True
print root.right.val
if not root.visit: # Prints the root finally
root.visit = True
print root.val
# Approach:
# a) Use stack for keeping track of alternate words and reversing them
# b) Uses a boolean to keep track of even and odd words
# Assumptions:
# a) There is only one space char between words
# Boundary conditions tested:
# a) Empty string
# b) Null
# c) proper data type
# d) Strings of length 0,1,2
# e) Unicode handling
def zigzag(string):
"""zigzag reversal of the given string."""
if string is None or len(string) in [0,1,2]:
return string
if not isinstance(string, str):
return 'Invalid data type passed for reversal'
string = string.encode('utf-8')
even = True
stack = []
output = []
i = len(string) - 1
while i >= 0:
while i >= 0 and string[i] != ' ':
if even:
stack.append(string[i])
else:
output.append(string[i])
i -= 1
else:
even = False if even else True
if stack:
while stack:
output.append(stack.pop())
if i >= 0:
output.append(' ')
i -= 1
return ''.join(output)
print zigzag('I am a software programmer')
Python solution
import sys
class String(object):
def __init__(self, string):
if string is not None:
self.strlen = len(string)
self.string = list(string)
self.count = 0
else:
self.string = None
def __lshift__(self, expected):
if (expected < 0 or
expected > sys.maxint or
type(expected) != int):
return 'Invalid expected value passed'
elif expected == 0:
return self.string
elif self.string is None:
return None
elif self.strlen in [1,0]:
return ''.join(self.string)
while self.count != expected:
prev = self.string[self.strlen-1]
for i in range(self.strlen-2, -1, -1):
next = self.string[i]
self.string[i] = prev
prev = next
else:
self.string[self.strlen-1] = prev
self.count += 1
return ''.join(self.string)
def __rshift__(self, expected):
if (expected < 0 or
expected > sys.maxint or
type(expected) != int):
return 'Invalid expected value passed'
elif expected == 0:
return self.string
elif self.string is None:
return None
elif self.strlen in [1,0]:
return ''.join(self.string)
while self.count != expected:
prev = self.string[0]
for i in range(1, self.strlen):
next = self.string[i]
self.string[i] = prev
prev = next
else:
self.string[0] = prev
self.count += 1
return ''.join(self.string)
print String('abcb') >> 1
# Program:
def reversal(string):
if string is None:
return string
if len(string) == 1 or 0:
return string
string = string.encode('utf-8')
string = list(string)
i = 0
j = len(string) - 1
while i <= j:
string[i], string[j] = string[j], string[i]
i += 1
j -= 1
return ''.join(string)
print reversal('ab csdjkf,!wiuro ')
# Test cases:
a) Single character string
b) Empty string
c) Null string
d) Unicode character string
e) Lengthy string (50 MB)
f) String with spaces, punctuations, exclamation, period, etc,.
A python solution:
wrds = [ "abc" , "baa" , "caan" , "an" , "banc" , "bank"]
chars= [ "a" , "a" , "n" , "c" , "b"]
matching_words = []
max_len = 0
for i in wrds:
chars_copy = chars[:] # create a shallow copy
for j in i:
if j not in chars_copy:
break
else:
chars_copy.remove(j)
else:
if len(i) > max_len:
max_len = len(i)
matching_words = [i]
elif len(i) == max_len:
matching_words.append(i)
print matching_words
Simple recursive solution using Python.
Idea: Keep incrementing the number of stars in delta of '2' until it reaches the value of 'n' after which start decrementing the delta
- Galileo May 21, 2017