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;
    }

#!/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']))

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;
    }
}

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)

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'

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')