CareerCup

def numOfIslands_helper(arr, i, j, visited):
    
    #print(i,j)
    
    #print(visited)
    
    if i>=len(arr) or j >= len(arr[0]) or i<0 or j<0:
        return 0
    
    if (i,j) in visited:
        return 0
    
    
    
    if arr[i][j] == 0:
        visited[(i,j)] = True
        return 0
    else:
    
    
        visited[(i,j)] = True

        numOfIslands_helper(arr,i+1,j+1, visited)
        numOfIslands_helper(arr,i+1,j, visited)
        numOfIslands_helper(arr,i+1,j-1, visited)

        numOfIslands_helper(arr,i,j+1, visited)
        numOfIslands_helper(arr,i-1,j+1, visited)
        numOfIslands_helper(arr,i,j+1, visited)

        numOfIslands_helper(arr,i-1,j-1, visited)

        numOfIslands_helper(arr,i-1,j, visited)

        #visited[(i,j)] = True

        return 1


def numOfIslands(arr):
    
    r = len(arr)
    c = len(arr[0])
    
    #print(r)
    #print(c)
    
    
    # DFS
    # keep tracks of nodes visited so far ( indexes visited so far)
    # iterate from 00 --> r-1, c-1
    # perform DFS at every element
    # expand the island in all 8 directions
    # (i+1, j+1), (i, j+1), (i+1, j), (i-1, j-1), (i, j-1), (i-1, j), (i+1, j-1), (i-1, j+1)
    # pass any node if it's already visited or it's value is zero;
    # key for i,j ==> (i,j) as key;
    
    visited = {}
    
    count = 0
    
    for i in range(r):
        for j in range(c):
            #print(i,j)
            count += numOfIslands_helper(arr, i, j, visited)
            
    #print(visited)
            
    return count
            

arr = [[0 for i in range(5)] for j in range(3)]

arr[0][1] = 1
arr[1][1] = 1
arr[2][1] = 1
arr[0][3] = 1
arr[1][4] = 1
arr[2][4] = 1

print(arr)

print(numOfIslands(arr))

import copy

def all_combinations(arr, element, n, res):
    
    # arr, partiallly filled array, and indexes which are empty contain value as -1
    # num_elements_filled : Elements processed till now
    # n --> given number -- num_elements_filled == can be 
    
    # Base condition; if num_elements_filled == n; append in the resutlt set
    
    if element > n:
        res.append(copy.deepcopy(arr))
        return
    
    for i in range(2*n):
        
        next_pos = i+element+1
        
        if arr[i] == -1 and next_pos<(2*n) and arr[next_pos] == -1:
            
            arr[i] = element
            arr[next_pos] = element
            
            all_combinations(arr,element+1, n, res)
            
            arr[i] = -1
            arr[next_pos] = -1
            
            
def all_combinations_helper(n):
    
    arr = [-1] * (2*n)
    
    res = []
    
    all_combinations(arr,1,n,res)
    
    return res

    
print(all_combinations_helper(3))

def isPeriodic(str1):
    
    # is string is periodic n has to be 2, 3......n/2 at max
    # brute force
    n = int(len(str1)/2) 
    
    for i in range(1, n+1):
        # i simply means the pattern length
        
        #print(i)
        
        temp = str1[0:i]
        #print(i,temp)
        found = None
        for j in range(i,len(str1), i):
            
            temp1 = str1[j:j+i]
            #print(i, j,temp,temp1)
            if temp == temp1:
                continue
            else:
                found = False
                break
        if found is None:
            return i, True
                
            
            #print(temp1)
    
    return -1,False

def canBrekaString(str1, hash_map):
    
    # try to divide the string into all possible words and check if those words exists in the hash_map or not
    
    #print(str1,hash_map)
    
    if not str1:
        return True
    
    for i in range(1,len(str1)+1):
        
        # part part of string is 0-->i, and second part is i-->n
        
        if str1[0:i] in hash_map and hash_map[str1[0:i]]>0:
            
            hash_map[str1[0:i]] -= 1
            canBreak = canBrekaString(str1[i:len(str1)], hash_map)
            
            if canBreak:
                return True
            
            # backtrck
            hash_map[str1[0:i]] += 1
            
    
    return False

def findCounts(n, bcount, ccount):
    
    if bcount < 0 or ccount < 0:
        return 0
    if n == 0: # no more chars left to be added
        return 1
    
    if bcount ==0  and ccount == 0:
        return 1
    
    
    res = findCounts(n-1,bcount, ccount) # if a is added
    
    res += findCounts(n-1,bcount-1, ccount) # if b is added
    
    res += findCounts(n-1, bcount, ccount-1) # if c is added
    
    return res


print(findCounts(4,1,2))

def sortUsingReverse(arr):
    
    # keep the unsorted count and let's call it current size
    cur_size = len(arr)
    
    # find the index of max elemnt in array
    
    while(cur_size > 1):
        
        max_index = 0
        
        for i in range(1,cur_size):
            if arr[i] > arr[max_index]:
                max_index = i
        
        # flip the arr from 0--> max index
        
        reverse(arr,max_index+1)
        
        # flip the array from 0--> cursize-1
        reverse(arr,cur_size)
        cur_size -= 1

def reverse(arr, k):
    mid = int(k/2)
    for i in range(mid):
        new_index = (k-1) - i
        # swap i and new_index
        temp = arr[new_index]
        arr[new_index] = arr[i]
        arr[i] = temp
    return arr



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

import heapq

class Mylists:
    
    
    def __init__(self, lists):
        k = len(lists)
        self.lists = lists
        self.min_heap = []
        self.constructHeap(k)
        
    def constructHeap(self,k):
        # insert first elemnt of all the lists in the heap
        
        for i, list1 in enumerate(self.lists):
            
            heapq.heappush(self.min_heap, (list1[0], 0, i))
            # element val, index and list referance
                                           
        
    def next(self):
        # it first return the top element
        # modify the heap which add the next element in the heap for next iteration
        
        if not self.min_heap:
            return "No more element present"
        
        val, idx, list_ref = heapq.heappop(self.min_heap)
        
        if idx+1 < len(self.lists[list_ref]):
            heapq.heappush(self.min_heap, (self.lists[list_ref][idx+1], idx+1,list_ref))
        
        return val
        
        
    
temp = Mylists([[1,5,7], [2,3,10],[4,6,9]])

print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())

import heapq

class Mylists:


def __init__(self, lists):
k = len(lists)
self.lists = lists
self.min_heap = []
self.constructHeap(k)

def constructHeap(self,k):
# insert first elemnt of all the lists in the heap

for i, list1 in enumerate(self.lists):

heapq.heappush(self.min_heap, (list1[0], 0, i))
# element val, index and list referance


def next(self):
# it first return the top element
# modify the heap which add the next element in the heap for next iteration

if not self.min_heap:
return "No more element present"

val, idx, list_ref = heapq.heappop(self.min_heap)

if idx+1 < len(self.lists[list_ref]):
heapq.heappush(self.min_heap, (self.lists[list_ref][idx+1], idx+1,list_ref))

return val



temp = Mylists([[1,5,7], [2,3,10],[4,6,9]])

print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())
print(temp.next())

Here iw working python code

def check_regex(reg, exp):
    if reg[0] == '^':
        reg = reg[1:]
    elif reg[-1] == '$':
        reg = reg[:-1]
    i = 0
    j = 0
    while i<len(exp):
        if reg[j] == '.':
            i += 1
        elif reg[j] == '*':
            while(exp[i-1] == exp[i]):
                i += 1
        elif exp[i] == reg[j]:
                i += 1
        else:
            return False
        j += 1
    return True

Recursive relation is:

T(n)  = 2 T((n-1)/2) + 1

Total operations required will be : 2^((n-1)/2) -1

Great explanation. here is the working code for the same

A = [5, 6, 4, 3, 6, 2, 3] # array of well diameters
B = [2, 3, 5, 2, 4] # Array of disk diameters


# N is the rings in well, M is total disks
def getminArray(A):
    minArray = []
    for item in A:# O(N)
        if len(minArray) == 0:
            minArray.append(item)
        else:
            if minArray[0] < item:
                minArray.insert(0, minArray[0])
            else:
                minArray.insert(0, item)
    return minArray

def countDisks(A,B):
    minArray = getminArray(A)
    for i,item in enumerate(B):
        if len(minArray) == 0:
            print i+1
            break
        while item > minArray[0]:
            minArray.pop(0)
            if len(minArray) == 0:
                print i+1
                break
        if minArray:
            minArray.pop(0)
        if len(minArray) == 0:
            print i+1
            break
countDisks(A,B)

A = [5, 6, 4, 3, 6, 2, 3] # array of well diameters
B = [2, 3, 5, 2, 4] # Array of disk diameters


# N is the rings in well, M is total disks
def getminArray(A):
    minArray = []
    for item in A:# O(N)
        if len(minArray) == 0:
            minArray.append(item)
        else:
            if minArray[0] < item:
                minArray.insert(0, minArray[0])
            else:
                minArray.insert(0, item)
    return minArray

def countDisks(A,B):
    minArray = getminArray(A)
    for i,item in enumerate(B):
        if len(minArray) == 0:
            print i+1
            break
        while item > minArray[0]:
            minArray.pop(0)
            if len(minArray) == 0:
                print i+1
                break
        if minArray:
            minArray.pop(0)
        if len(minArray) == 0:
            print i+1
            break
countDisks(A,B)

A = [5, 6, 4, 3, 6, 2, 3] # array of well diameters
B = [2, 3, 5, 2, 4] # Array of disk diameters


# N is the rings in well, M is total disks
def getminArray(A):
    minArray = []
    for item in A:# O(N)
        if len(minArray) == 0:
            minArray.append(item)
        else:
            if minArray[0] < item:
                minArray.insert(0, minArray[0])
            else:
                minArray.insert(0, item)
    return minArray

def countDisks(A,B):
    minArray = getminArray(A)
    for i,item in enumerate(B):
        if len(minArray) == 0:
            print i+1
            break
        while item > minArray[0]:
            minArray.pop(0)
            if len(minArray) == 0:
                print i+1
                break
        if minArray:
            minArray.pop(0)
        if len(minArray) == 0:
            print i+1
            break
countDisks(A,B)

Here I am assuming we can convert string to a array of characters and then proceed.

Length of a substring can be between (1 n), for any given length m, find all the combination of a binary array which contain m 1s and rest are all 0. and then print only those value of original array for which value in binay array is 1.

for example: input: 'abc', for length 1, binary array can be [100] [010] [001] == > print ==>a,b,c
for length 2, binary array [110][101][011] ==> ab, ac, bc

Here is working code

public class StringSubSet {
	public static void PrintCombiOfGivenLength(char[] B, int[] Helper, int start, int remain){
		if(remain == 0) {
			System.out.print("[");
			for (int i=0;i<Helper.length;i++){
				if(Helper[i] == 1)System.out.print(B[i]+",");
			}
			System.out.println("]");
			return;
		}
		else{
			for(int i=start;i<B.length;i++){
				Helper[i] = 1;
				PrintCombiOfGivenLength(B,Helper,i+1,remain-1);
				Helper[i] = 0;
			}
		}
	}
	public static void main(String[] args) {
		char[] B = {'a','b','c'};
		int[] Helper = new int[B.length];
		for(int i=1; i<=B.length; i++) {
			PrintCombiOfGivenLength(B,Helper,0,i);
		}
	}
}

public static void main(String[] args) {
		int[] array = {2,5,1,8,10,12,4,15};
		shiftArray(array,3);
		MyUtilities.PrintArray(array);
	}

	public static void Reverse(int[] A,int first, int last) {
		while(first < last){
			MyUtilities.Swap(A, first, last);
			first++;last--;
		}
	}
	private static void shiftArray(int[] array, int n){
		if(n<array.length && n >0){
			Reverse(array,0,array.length-1);
			Reverse(array,0,n-1);
			Reverse(array,n,array.length-1);
		}
	}

You missed out 1 simple check, your code remove all the duplicate characters instead of alternative characters !!!! for example below
input : "Today is the day, yet another day"
output : Today ishe,nr ---> this is wrong,
correct output shoud be : Today ishe ,yt anerd

Modify your if condition in for loop like below

if (!characterSet.contains(Character.toLowerCase(chars[i]))) {
                chars[j++] = chars[i];
                characterSet.add(Character.toLowerCase(chars[i]));
            }
            else{
            	characterSet.remove(Character.toLowerCase(chars[i]));
            }