public static int shiftedBinarySearch(int[] array, int target) { return shiftedSearch(array, 0, array.length - 1, target); } public static int binarySearch(int[] array, int startIdx, int endIdx, int target) { int midIdx = (startIdx + endIdx) / 2; if (startIdx > endIdx || endIdx >= array.length) { return -1; } if (startIdx == endIdx) { if (array[midIdx] == target) { return midIdx; } else { return -1; } } int result = -1; if (target <= array[midIdx]) { result = binarySearch(array, startIdx, midIdx, target); } else { result = binarySearch(array, midIdx + 1, endIdx, target); } return result; } public static int shiftedSearch(int[] array, int startIdx, int endIdx, int target) { if (startIdx > endIdx || endIdx >= array.length) { return -1; } if (array[startIdx] == target) { return startIdx; } if (array[endIdx] == target) { return endIdx; } int result = -1; int midIdx = (startIdx + endIdx) / 2; if (array[startIdx] > array[midIdx]) { result = shiftedSearch(array, startIdx, midIdx, target); if (result != -1) { return result; } } if (array[midIdx + 1] < array[endIdx]) { result = binarySearch(array, midIdx + 1, endIdx, target); if (result != -1) { return result; } } if (array[startIdx] < array[midIdx]) { result = binarySearch(array, startIdx, midIdx, target); if (result != -1) { return result; } } if (array[endIdx] < array[midIdx + 1]) { result = shiftedSearch(array, midIdx + 1, endIdx, target); if (result != -1) { return result; } } return result; }
Category Archives: Uncategorized
Lowest Common Manager
#!/bin/python3 class OrgChart: def __init__(self, name, manager): self.name = name self.manager = manager self.directReports = [] def __repr__(self): return f'{self.name}' def getLowestCommonManager(topManager, reportOne, reportTwo): report_one_manager = reportOne.manager report_one_chain = list() while report_one_manager: report_one_chain.append(report_one_manager) report_one_manager = report_one_manager.manager report_two_manager = reportTwo.manager report_two_chain = list() while report_two_manager: report_two_chain.append(report_two_manager) report_two_manager = report_two_manager.manager report_one_chain.reverse() report_two_chain.reverse() common_manager = None for a, b in zip(report_one_chain, report_two_chain): if a == b: common_manager = a else: break return common_manager if __name__ == '__main__': org = [ {"directReports": ["B", "C"], "id": "A", "name": "A"}, {"directReports": ["D", "E"], "id": "B", "name": "B"}, {"directReports": ["F", "G"], "id": "C", "name": "C"}, {"directReports": ["H", "I"], "id": "D", "name": "D"}, {"directReports": [], "id": "E", "name": "E"}, {"directReports": [], "id": "F", "name": "F"}, {"directReports": [], "id": "G", "name": "G"}, {"directReports": [], "id": "H", "name": "H"}, {"directReports": [], "id": "I", "name": "I"} ] top_manager = None members = {} for member in org: name = member['name'] if name not in members: member_obj = OrgChart(name, None) top_manager = member_obj members[name] = member_obj member_obj = members[name] for direct_report in member['directReports']: if not direct_report in members: direct_report_obj = OrgChart(direct_report, member_obj) direct_report_obj.name = direct_report members[direct_report] = direct_report_obj else: direct_report_obj = members[direct_report] member_obj.directReports.append(direct_report_obj) print(getLowestCommonManager(top_manager, members['F'], members['H']))
Longest Peak
package com.vishpat.practice.ds.array; enum States { UNKNOWN, ASCENDING, DESCENDING } public class LongestPeak { public static int longestPeak(int[] array) { States currentState = States.UNKNOWN; States prevState = States.UNKNOWN; int longestSize = 0; int ascendingStartIdx = -1; int descendingEndIdx = -1; if (array.length < 3) { return 0; } for (int i = 0; i < array.length - 1; i++) { prevState = currentState; if (array[i + 1] > array[i]) { switch (prevState) { case UNKNOWN: currentState = States.ASCENDING; ascendingStartIdx = i; break; case ASCENDING: currentState = States.ASCENDING; break; case DESCENDING: currentState = States.ASCENDING; ascendingStartIdx = i; break; } } if (array[i + 1] < array[i]) { switch (prevState) { case UNKNOWN: currentState = States.DESCENDING; break; case ASCENDING: currentState = States.DESCENDING; descendingEndIdx = i + 1; break; case DESCENDING: currentState = States.DESCENDING; descendingEndIdx = i + 1; break; } } if (ascendingStartIdx >= 0 && descendingEndIdx >= 0 && ascendingStartIdx < descendingEndIdx) { int size = descendingEndIdx - ascendingStartIdx + 1; if (size > longestSize && size > 2) { longestSize = size; } } } return longestSize; } }
Max 2 integers from an array
def sol2(data): max_idx1 = 0 max_idx2 = 1 max_sum = data[0] + data[1] for next_idx in range(2, len(data)): if data[max_idx1] + data[next_idx] > max_sum and max_idx1 != next_idx: max_sum = data[max_idx1] + data[next_idx] max_idx2 = next_idx if data[max_idx2] + data[next_idx] > max_sum and max_idx2 != next_idx: max_sum = data[max_idx2] + data[next_idx] max_idx1 = next_idx print(max_idx1, max_idx2) if __name__ == "__main__": data = [1, 5, 3, 2, 4] sol2(data)
Simple in-memory file system
class Dir: def __init__(self, parent, name): self.parent = parent self.name = name self.children = dict() def mkdir_path(self, path): sub_dirs = path.split('/') current_dir = self for child_dir_name in sub_dirs: current_dir = current_dir.mkdir(child_dir_name) def mkdir(self, name): dir = Dir(self, name) self.children[name] = dir return dir def get_child_dir(self, name): return self.children[name] def get_child_dir_path(self, path): sub_dirs = path.split('/') current_dir = self for sub_dir in sub_dirs: current_dir = current_dir.children[sub_dir] return current_dir def write_file(self, name, contents): self.children[name] = contents def write_file_path(self, path, contents): sub_dirs = path.split('/') file_name = sub_dirs[-1] current_dir = self for sub_dir in sub_dirs[:-1]: current_dir = current_dir.children[sub_dir] current_dir.write_file(file_name, contents) def read_file(self, name): return self.children[name] def read_file_path(self, path): sub_dirs = path.split('/') file_name = sub_dirs[-1] current_dir = self for sub_dir in sub_dirs[:-1]: current_dir = current_dir.children[sub_dir] return current_dir.read_file(file_name) def __repr__(self): return f'{self.name} {self.children}' if __name__ == "__main__": fs = Dir(None, '/') fs.mkdir('tmp').mkdir('1') fs.get_child_dir('tmp').get_child_dir('1').write_file('test', 'data') contents = fs.get_child_dir('tmp').get_child_dir('1').read_file('test') assert contents == 'data', "contents of the file don't match" fs.mkdir_path('tmp/1/2/3/4') fs.write_file_path('tmp/1/2/3/4/4.dat', '4') contents = fs.read_file_path('tmp/1/2/3/4/4.dat') assert contents == '4', 'Correct content not found'
Check if concatenation of any permutation of given list of arrays generates the given array
Solution for geeksforgeeks problem
def solve(arr, sub_arrs): sub_arr_membership = {} curr_indx = [-1 for i in range(0, len(sub_arrs))] for idx, sub_arr in enumerate(sub_arrs): for sub_arr_idx, element in enumerate(sub_arr): sub_arr_membership[element] = (idx, sub_arr_idx) for element in arr: idx, sub_arr_idx = sub_arr_membership[element] if curr_indx[idx] > sub_arr_idx: print(f'False') return else: curr_indx[idx] = sub_arr_idx print(f'True')
Custom kubernetes ingress authentication using Hashicorp Vault
This article explains how to implement an ngnix ingress authentication (basic http auth) mechanism for securing your kubernetes (k8s) application endpoints using the credentials stored in hashicorp vault. This can be achieved easily by writing a simple http auth (python-flask) app that talks with the vault. The workflow for custom authentication is explained well in this article.
The basic idea to is modify the opensource httpbin app by adding a new endpoint such as vault-auth. The code this endpoint is going to basic-auth except the http auth credentials will be validate against hashicorp vault instead of the passed parameters. The modified code can then be deployed as a container and as an auth service in your kubernetes cluster.
All the applications whose ingress endpoints need to be secured have to add the following line to their ingress deployment yaml
nginx.ingress.kubernetes.io/auth-url: http://auth.default.svc.cluster.local/vault-auth/x/y
Where auth.default.svc.cluster.local is the service that is running the modified httpbin app
Back to Storage at Cisco
I joined the Webex Storage IAAS (infrastructure as a service) group three weeks ago after a stint of three and half years at Nuage. I had a great experience at Nuage, especially during my first two years during which I got to work quite a bit on Openstack, Vmware cloud, Kubernetes and Openshift. I was super fortunate to make lots of opensource contributions during this period and I think that really helped in getting my new job at Cisco.
At Cisco I am part of the Storage team and really excited to back in the storage domain after learning a lot about networking in last four and half years.
YouCompleteMe
I recently started working on a big C project at Nuage. I have worked in C at Netapp for 9 years and was looking forward to this new work as result. Man, I am so glad so be able to program in C again. I was also happy to realize that my C chops are still quite good.
However having worked with Java/Python for past 2 – 3 years and being used to the awesome Intellij IDE, I really wasn’t enjoying working with vim again. My complaints about vim were two fold. First writing code in C is quite verbose, especially for the low level stuff I was working on. (I really missed Java’s awesome collection library and stream API. Those things made writing software such a joy). The second complaint about vim is lack of auto completion, which makes the first problem all the more worse.
I tried overcoming this problem by using the YouCompleteMe plugin for vim but it wasn’t working quite well with my C project. (C projects do not have a standard way to compile and build, each one of them has a different way of building things). Initially the auto-completion with YouCompleteMe really sucked, until I discovered the bear tool. The bear tool lets you generate a compilation database for your project (You just prepend your make command with bear) and once this is done, autocompletion worked as charm in Vim. Morever YouCompleteMe dynamically complies the C file so, I get syntax errors while writing the code itself. What a timesaver and productivity booster.
Clojure
Have started learning Clojure using the awesome book Clojure for the brave and true and am really loving it. I plan to continue experimenting with the language while solving some of the problems from the Project Euler. I have already started solving some of the problems using Python and my solutions are available on my github page.