Arrays Flashcards
Dutch National
public static void dutchNationalFlag(int[] a, int pivot) {
int low_boundary = 0, high_boundary = a.length - 1;
int i = 0;
while (i <= high_boundary) {
if (a[i] < pivot) {
Utils.swap(a, i, low_boundary);
low_boundary++;
i++;
} else if (a[i] > pivot) {
Utils.swap(a, i, high_boundary);
high_boundary--;
} else {
i++;
}
}
}Square in Non-Decresing Order
while(start <=end)
{
if (abs(a[start]) > abs(a[end])) {
result[resultIndex] = square(a[start]);
start++;
} else {
result[resultIndex] = square(a[end]);
end–;
}
resultIndex–;
}
Kadane’s - Maximum Sum Subarray
/* * Kadane's algorithm solution */
public static Integer maximumSumSubarray(int[] a) {
if (a == null || a.length == 0) throw new IllegalArgumentException("Input array is empty or null");
int maxSum = a[0], maxEndingHere = a[0];
for (int i = 1; i < a.length; i++) {
maxEndingHere = Math.max(maxEndingHere + a[i], a[i]);
maxSum = Math.max(maxSum, maxEndingHere);
}
return maxSum;
}Move Zero to front or End
SnowBall Algorithm
Daily Temperatures
Given a list of daily temperatures T, return a list such that, for each day in the input, tells you how many days you would have to wait until a warmer temperature. If there is no future day for which this is possible, put 0 instead.
For example, given the list of temperatures T = [73, 74, 75, 71, 69, 72, 76, 73], your output should be [1, 1, 4, 2, 1, 1, 0, 0].
public int[] dailyTemperatures(int[] temperatures) {
Stack stack = new Stack<>();
int[] ret = new int[temperatures.length];
for(int i = 0; i < temperatures.length; i++) {
while(!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
int idx = stack.pop();
ret[idx] = i - idx;
}
stack.push(i);
}
return ret;
}
Checking How many palindrome is present in a string
int count =1;
public int countSubstrings(String s) {
if(s.length()==0)
return 0;
for(int i=0; i=0 && jStrobogrammatic Number
A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).
Write a function to determine if a number is strobogrammatic. The number is represented as a string.
Example 1:
Input: “69”
Output: true
Example 2:
Input: “88”
Output: true
Example 3:
Input: “962”
Output: false
public boolean isStrobogrammatic(String num) {
Map map = new HashMap();
map.put('6', '9');
map.put('9', '6');
map.put('0', '0');
map.put('1', '1');
map.put('8', '8');
int l = 0, r = num.length() - 1;
while (l <= r) {
if (!map.containsKey(num.charAt(l))) return false;
if (map.get(num.charAt(l)) != num.charAt(r))
return false;
l++;
r--;
}
return true; }
Integer Overflow condition
if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
Max integer value is 2,147,483,647 and when you divide it by 10 then 214748364 is the value
so according to code if this value = rev , you need to * 10 then add POP
when you *10 rev = 2147483640 and if you add more than 7 it will overflow
same in case of negative value
Find First and Last Position of Element in Sorted Array
Search using Two Pass:
Pass 1: Find the target on Left side
Pass 2:Find the target on right side
Majority Element: Strictly Greater than 50%
public static Integer majorityFind(int[] a) {
if (a == null || a.length == 0)
return null;
int candidate = a[0];
int count = 1;
for (int i = 1; i < a.length; i++) {
if (a[i] == candidate) {
count++;
} else if (count > 0) {
count--;
} else {
candidate = a[I];
count = 1;
}
}
// check array, verify candidate is majority
count = 0;
for (int i = 0; i < a.length; i++) {
if (a[i] == candidate)
count++;
}
return count > a.length/2 ? candidate : null;
}N-Repeated Element in Size 2N Array
Note: Array is even
Example 1:
Input: [1,2,3,3]
Output: 3
Example 2:
Input: [2,1,2,5,3,2]
Output: 2
Example 3:
Input: [5,1,5,2,5,3,5,4]
Output: 5
public int repeatedNTimes(int[] A) {
if(A[0] == A[A.length-1])
return A[0];
for(int i = 0; i < A.length-1; i++){
if(i < A.length-2 && A[i] == A[i+2]){
return A[i];
}
if(A[i] == A[i+1])
return A[i];
}
return -1;
}
In a row of seats, 1 represents a person sitting in that seat, and 0 represents that the seat is empty.
There is at least one empty seat, and at least one person sitting.
Alex wants to sit in the seat such that the distance between him and the closest person to him is maximized.
Return that maximum distance to closest person.
Input: [1,0,0,0,1,0,1]
Output: 2
Explanation:
If Alex sits in the second open seat (seats[2]), then the closest person has distance 2.
If Alex sits in any other open seat, the closest person has distance 1.
Thus, the maximum distance to the closest person is 2.
public int maxDistToClosest(int[] seats) {
int N = seats.length;
int[] left = new int[N], right = new int[N];
Arrays.fill(left, N);
Arrays.fill(right, N);
for (int i = 0; i < N; ++i) {
if (seats[i] == 1) left[i] = 0;
else if (i > 0) left[i] = left[i-1] + 1;
}
for (int i = N-1; i >= 0; --i) {
if (seats[i] == 1) right[i] = 0;
else if (i < N-1) right[i] = right[i+1] + 1;
}
int ans = 0;
for (int i = 0; i < N; ++i)
if (seats[i] == 0)
ans = Math.max(ans, Math.min(left[i], right[i]));
return ans;
}
Shuffling Array
Random rand = new Random();
private int randRange(int min, int max) {
return rand.nextInt(max - min) + min;
}
private void swapAt(int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public Solution(int[] nums) {
array = nums;
original = nums.clone();
}
public int[] reset() {
array = original;
original = original.clone();
return original;
}
You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.
Suppose you have n versions [1, 2, …, n] and you want to find out the first bad one, which causes all the following ones to be bad.
You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.
Example:
Given n = 5, and version = 4 is the first bad version.
call isBadVersion(3) -> false call isBadVersion(5) -> true call isBadVersion(4) -> true
Then 4 is the first bad version.
public int firstBadVersion(int n) {
int start = 1, end = n;
while (start < end) {
int mid = start + (end-start) / 2;
if (!isBadVersion(mid)) start = mid + 1;
else end = mid;
}
return start;
}Find repeated element when numbers are in range 0..n
for(int i = 0; i < N; i++){
int index = numRay[i] % N;
numRay[index] = numRay[index] + N;
}
for(int i = 0; i < N; i++) {
if (numRay[i]/N > 1)
System.out.println(i + " ");
}
