abhi55's blog

By abhi55, history, 6 hours ago, In English

Given an Array of integers where each element represent 1 to array[i] days. find maximum possible k consecutive days in circular array.

Example: arr = [7, 4, 6, 3, 5] k = 8 output = 33

explanation: we can choose last day of arr4 which is 5 and all of 7 days of arr1. So, it will look like sum(5,1,2,3,4,5,6,7) = 33.

My thoughts: this look like classical sliding window problem to find max subarray of size k but converting original array to actual days array([1, 2, 3, 4, 5, 6, 7, 1, 2, 3, 4, 1, 2, 3, 4, 5, 6, 1, 2, 3, 1, 2, 3, 4, 5]) like this will not be optimal and what if size of k is far greater than length of array?.

Need help if anybody have some pointers how to solve this question.

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it

By abhi55, history, 3 years ago, In English

This question was asked in an online screening test. Any clue how to solve it with Online Approach better than O(N^3)?

My Approach:

Maintain two maps of Map<X, Set> and Map<Y, Set> and for each point find horizontal and vertical points and for every triplet check 4th point exist or not.

Full text and comments »

  • Vote: I like it
  • -4
  • Vote: I do not like it

By abhi55, history, 6 years ago, In English

My DP implementation of max sum is below but i need sequence which is giving max sum instead of max sum value.

public int maxSum(int arr[]) {
     int excl = 0;
     int incl = arr[0];
     for (int i = 1; i < arr.length; i++) {
       int temp = incl;
       incl = Math.max(excl + arr[i], incl);
       excl = temp;
     }
     return incl;
}

So 3 2 7 10 should return (3 and 10) or 3 2 5 10 7 should return (3, 5 and 7) or {5, 5, 10, 100, 10, 5} will return (5, 100 and 5) or {1, 20, 3} will return 20 i exactly want this problem solution but return value i need is sequence of elements included in max sum instead of max sum value

Update:-no need to handle -ve elements because all elements in sequence(Array) are +ve

Full text and comments »

  • Vote: I like it
  • 0
  • Vote: I do not like it