Python Programming

 Problem 1 : Addition without arithmetic operator 

def addition(a,b):

while(b!=0):

carry=a&b

a=a^b

b=carry>>1

return a

def main():

a=int(input("enter first number"))

b=int(input("enter second number"))

print("sum is", int(addition(a,b)))

main()

Problem 2 : Given a string, find the length of the longest substring in it with no more than K distinct characters.

Code (python)

def longest_substring_with_k_distinct(str, k):

  window_start = 0

  max_length = 0

  char_frequency = {}

 

  # in the following loop we'll try to extend the range [window_start, window_end]

  for window_end in range(len(str)):

    right_char = str[window_end]

    if right_char not in char_frequency:

      char_frequency[right_char] = 0

    char_frequency[right_char] += 1

 

    # shrink the sliding window, until we are left with 'k' distinct characters in the char_frequency

    while len(char_frequency) > k:

      left_char = str[window_start]

      char_frequency[left_char] -= 1

      if char_frequency[left_char] == 0:

        del char_frequency[left_char]

      window_start += 1  # shrink the window

    # remember the maximum length so far

    max_length = max(max_length, window_end-window_start + 1)

  return max_length

 

 

def main():

  print("Length of the longest substring: " + str(longest_substring_with_k_distinct("araaci", 2)))

  print("Length of the longest substring: " + str(longest_substring_with_k_distinct("araaci", 1)))

  print("Length of the longest substring: " + str(longest_substring_with_k_distinct("cbbebi", 3)))

 

 

main()

Problem 3

Given an array of characters where each character represents a fruit tree, you are given two baskets and your goal is to put maximum number of fruits in each basket. The only restriction is that each basket can have only one type of fruit. (Concept)

Code #

Here is what our algorithm will look like,

 

def fruits_into_baskets(fruits):

  window_start = 0

  max_length = 0

  fruit_frequency = {}

 

  # try to extend the range [window_start, window_end]

  for window_end in range(len(fruits)):

    right_fruit = fruits[window_end]

    if right_fruit not in fruit_frequency:

      fruit_frequency[right_fruit] = 0

    fruit_frequency[right_fruit] += 1

 

    # shrink the sliding window, until we are left with '2' fruits in the fruit frequency dictionary

    while len(fruit_frequency) > 2:

      left_fruit = fruits[window_start]

      fruit_frequency[left_fruit] -= 1

      if fruit_frequency[left_fruit] == 0:

        del fruit_frequency[left_fruit]

      window_start += 1  # shrink the window

    max_length = max(max_length, window_end-window_start + 1)

  return max_length

 

 

def main():

  print("Maximum number of fruits: " + str(fruits_into_baskets(['A', 'B', 'C', 'A', 'C'])))

  print("Maximum number of fruits: " + str(fruits_into_baskets(['A', 'B', 'C', 'B', 'B', 'C'])))

 

 

main()

Problem 4

Cyclic Sort (easy)

Problem Statement

We are given an array containing ‘n’ objects. Each object, when created, was assigned a unique number from 1 to ‘n’ based on their creation sequence. This means that the object with sequence number ‘3’ was created just before the object with sequence number ‘4’. (Concept)

Python Code 

def cyclic_sort(nums):

  i = 0

  while i < len(nums):

    j = nums[i] - 1

    if nums[i] != nums[j]:

      nums[i], nums[j] = nums[j], nums[i]  # swap

    else:

      i += 1

  return nums

 

 

def main():

  print(cyclic_sort([3, 1, 5, 4, 2]))

  print(cyclic_sort([2, 6, 4, 3, 1, 5]))

  print(cyclic_sort([1, 5, 6, 4, 3, 2]))

 

 

main()