Abhishek Kothari
BAN USERSimple use another HashSet and keep adding the element of both the array, At the end you will have all the elements of both the array without repetition.
Time Complexity O(max(n,m)), Space O(n+m)
public boolean swapTwoConsecutiveNodes(){
if(head == null) {
System.out.println("List is empty");
return false;
}
Node prev = null;
Node next = null;
Node start = head;
head = start.nextNode;
while(start != null && start.nextNode != null){
next = start.nextNode;
if(prev != null) prev.nextNode = next;
start.nextNode = next.nextNode;
next.nextNode = start;
prev = start;
start = start.nextNode;
}
return true;
}
Time complexity O(nlog(w))
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
public class MinSlidingWindow {
public List<Integer> minSlidingWindows(int windowSize, int[] numbers){
ArrayList<Integer> minList = new ArrayList<Integer>();
PriorityQueue<Integer> kNumbers = new PriorityQueue<Integer>(windowSize);
for(int i = 0; i < numbers.length; i++){
if(kNumbers.size() < windowSize){
kNumbers.add(numbers[i]);
} else {
minList.add(kNumbers.peek());
kNumbers.remove(numbers[i-windowSize]);
kNumbers.add(numbers[i]);
}
}
minList.add(kNumbers.peek());
return minList;
}
public static void main(String[] args) {
int[] numbers = {1,1,3,1,6,3,8,9,10,12,1};
MinSlidingWindow msw = new MinSlidingWindow();
System.out.println(msw.minSlidingWindows(4, numbers));
}
}
There can be O(n) solution using Deque, but when we have to deal with data streaming(billions of number), where input will be just a number to add, using the above method, we can get the new min as per the window size.
In that case we need to make object of PriorityQueue to the class object, and instead of minList, just we need new min to be return
public boolean isAlternate(int num)
{
return (num ^ 0x55555555)==0 || (num ^ 0xaaaaaaaa)==0);
}
1) Go from node to root simultaneously and until you reach the root for any node while traversing.
2) While traversing, keep adding the parents to the list
3) While traversing, keep checking while other node parents set contains my current parent, if yes then current parent is the answer
4) If any node reaches to root node while traversing, we come out of while loop.
5) We do similar way for the node who has not reached till root and keep doing step 2 and 3.
This is similar to the merging of an array, but here we don't merge into single set.
public int getCommonAncestorUsingParents(List<ArrayList<Integer>> graph, int source1, int source2){
if(source1 >= graph.size() || source1 >= graph.size()) return Integer.MIN_VALUE;
int ancestor = 0;
Set<Integer> parentSource1 = new HashSet<Integer>();
Set<Integer> parentSource2 = new HashSet<Integer>();
while(source1 < Integer.MAX_VALUE && source2 < Integer.MAX_VALUE){
if(source1 == source2) return source1;
if(parentSource1.contains(source2)) return source2;
if(parentSource2.contains(source1)) return source1;
parentSource1.add(source1);
parentSource2.add(source2);
source1 = parent[source1];
source2 = parent[source2];
}
if(source1 < Integer.MAX_VALUE){
while(source1 < Integer.MAX_VALUE){
if(source1 == source2) return source1;
if(parentSource2.contains(source1)) return source1;
parentSource1.add(source1);
source1 = parent[source1];
}
} else {
while(source2 < Integer.MAX_VALUE){
if(source1 == source2) return source1;
if(parentSource1.contains(source2)) return source2;
parentSource2.add(source2);
source2 = parent[source2];
}
}
return ancestor;
}
public class IntervalOverlap {
class Interval {
int min;
int max;
public Interval(int min, int max){
this.min = min;
this.max = max;
}
@Override
public boolean equals(Object o){
if(o == null) return false;
if(o instanceof Interval){
Interval interval = (Interval) o;
if(interval.max == this.max && interval.min == this.min) return true;
}
return false;
}
@Override
public int hashCode(){
return min + ",".hashCode() + max;
}
public boolean isOverlap(Interval interval){
if(this.min > interval.max ) return false;
if(this.max < interval.min) return false;
return true;
}
@Override
public String toString(){
return "[" + min + ", " + max + "]";
}
}
// O(n * n) not that good
public HashMap<Interval, List<Interval>> matchOverlappedInterval(List<Interval> intervals){
HashMap<Interval, List<Interval>> mapIntervals = new HashMap<Interval, List<Interval>>();
for(int i = 0 ; i < intervals.size()-1; i++){
mapIntervals.put(intervals.get(i), new ArrayList<Interval>());
for(int j = i+1; j < intervals.size(); j++){
if(intervals.get(i).isOverlap(intervals.get(j))){
System.out.println(intervals.get(i) + " overlaps " + intervals.get(j));
mapIntervals.get(intervals.get(i)).add(intervals.get(j));
}
}
}
return mapIntervals;
}
public void printMapIntervals(HashMap<Interval, List<Interval>> mapIntervals){
for(Interval interval: mapIntervals.keySet()){
for(Interval i : mapIntervals.get(interval)){
System.out.println(interval + ", " + i);
System.out.println(i + ", " + interval);
}
}
}
public static void main(String[] args) {
IntervalOverlap io = new IntervalOverlap();
List<Interval> intervals = new ArrayList<Interval>();
intervals.add(io.new Interval(1,3));
intervals.add(io.new Interval(2,4));
intervals.add(io.new Interval(3,6));
intervals.add(io.new Interval(7,8));
io.printMapIntervals(io.matchOverlappedInterval(intervals));
}
}
O(1) Space, O(n) time complexity
public String getCompressedString(String stringToCompress){
StringBuilder sb = new StringBuilder(stringToCompress);
char prev = sb.charAt(0);
int count = 0;
int j = 0;
for(int i = 0; i < sb.length(); i++){
if(prev == sb.charAt(i)){
count++;
} else {
if(count == 1){
sb.replace(j, j+1, String.valueOf(prev));
j++;
} else {
sb.replace(j, j+2, String.valueOf(prev) + String.valueOf(count));
j = j + 2;
}
prev = sb.charAt(i);
count = 1;
}
}
if(count > 1){
sb.replace(j, j+2, String.valueOf(prev) + String.valueOf(count));
j = j + 2;
} else {
sb.replace(j, j+1, String.valueOf(prev));
j++;
}
return sb.substring(0,j);
}
//O(n) time complexity
public int nextHighNumber(int number){
int[] num = numberToArray(number);
int i = 0;
for(i = 0 ; i < num.length-1; i++){
if(num[i] > num[i+1]) break;
}
if(i == num.length-1) {
System.out.println("No number can be formed");
return 0;
}
int numi = num[i+1];
num[i+1] = num[0];
int temp = 0;
for(int j = 0; j <= i/2; j++){
temp = num[j];
num[j]=num[i-j];
num[i-j] = temp;
}
num[i]=numi;
return arrayToNumber(num);
}
public int[] numberToArray(int number){
System.out.println("Original number: " + number);
int[] num = new int[getNumberLength(number)];
int i = 0;
while(number > 0){
num[i] = number % 10;
number = number / 10;
System.out.print(num[i]);
i++;
}
System.out.println("\n" + "Converted number to array");
return num;
}
public int arrayToNumber(int[] num){
int number = 0;
for(int i = 0; i < num.length; i++){
number = number + num[i] * (int) Math.pow(10, i);
}
System.out.println("\n" + "Converted Array to number");
return number;
}
public int getNumberLength(int number){
int length = 0;
while(number > 0){
length++;
number = number / 10;
}
System.out.println("The length of number is: " + length);
return length;
}
Time Complexity O( n^2 log(n) ).....
I have check for various test cases it gives perfect answer.
input matrix will be like:
{int[][] query1 = new int[][]{ {0,0,0},
{1,2,2},
{1,0,0}};
where 2 means Guard and 1 mean blocked or obstacle
distance matrix is the output matrix, in which
Max value means cant reach,
0 means, you are a guard
otherwise other numeric values.
We keep checking whether the distance of any u, u_c has changed, if yes then we re-compute the distance matrix.
public int[][] getMinDistanceGuardMatrix(int[][] matrix){
int[][] distance = new int[matrix.length][matrix[0].length];
distance = initializeDistanceMatrix(distance);
int maxCols = matrix[0].length;
int maxRows = matrix.length;
boolean alter = true;
while(alter){
alter = false;
for (int u = 0; u < maxRows; u++){
for(int u_c = 0; u_c < maxCols; u_c++){
if(matrix[u][u_c] == 2 & distance[u][u_c]!=0) {
distance[u][u_c] = 0;
// System.out.println("2 " + u + "," + u_c + "= " + distance[u][u_c] );
alter = true;
}
else if(matrix[u][u_c] == 1) distance[u][u_c] = Integer.MAX_VALUE;
else if(matrix[u][u_c]==0){
// System.out.println("0 " + u + "," + u_c + "= " + distance[u][u_c] );
int dist = Integer.MAX_VALUE;
if(u_c + 1 < maxCols && (dist > distance[u][u_c+1])){
dist = distance[u][u_c+1] + 1;
}
if(u_c - 1 > 0 && (dist > distance[u][u_c-1])){
dist = distance[u][u_c-1] + 1;
}
if(u + 1 < maxRows && (dist > distance[u+1][u_c])){
dist = distance[u+1][u_c] + 1;
System.out.println("u+1 " + u + "," + u_c + "= " + dist );
}
if(u - 1 > 0 && (dist > distance[u-1][u_c])){
dist = distance[u-1][u_c] + 1;
}
// System.out.println(" " + u + "," + u_c + "= " + dist );
// System.out.println(" " + u + "," + u_c + "= " + distance[u][u_c] );
if(distance[u][u_c] > dist){
distance[u][u_c] = dist;
// System.out.println("change " + u + "," + u_c + "= " + dist );
alter = true;
}
}
}
}
// printMatrix(distance);
}
return distance;
public void breakWithSpaces(String word, int start){
if(start == word.length()) System.out.println("The words are: " + Arrays.asList(sentence));
for(int i = start; i < word.length(); i++){
if(dictionaryContains(word.substring(start, i+1))){
sentence.add(word.substring(start, i+1));
// System.out.println("Adding " + word.substring(start, i+1));
breakWithSpaces(word, i+1);
sentence.remove(sentence.size()-1);
// System.out.println("Removing " + word.substring(start, i+1));
}
}
}
change i<n to i>n
- Abhishek Kothari April 10, 2014
What we just needed is median of median, find the median of each file and then find the median of the median of all the files.
- Abhishek Kothari June 23, 2014