sukheshmg
BAN USER- 0of 0 votes
AnswersYou are given an unsorted integer array consisting of 1's and 0's. You need to rearrange the array with alternating groups of 0's and 1's. The group length is determined by the function f(x)
- sukheshmg in India
f(0) = 1
f(1) = 2
f(n) = [square of f(n-1) - square of f(n-2)]
if you run out of either 1's or 0's, then fill the array with whatever is left.
input: 0,0,1,0,1,1,1,0,0,1,0,0,1,1,0,0
output: 0, 1,1, 0,0,0, 1,1,1,1,1, 0,0,0,0,0
f(1) = 1
f(2) = 2
f(3) = sqr(f(2)) - sqr(f(1)) = 3
f(4) = sqr(f(3)) - sqr(f(2)) = 5
f(5) = sqr(f(4)) - sqr(f(3)) = 16
here we don't have enough 0's left to fill the last group. So, we add the five 0's that were left.| Report Duplicate | Flag | PURGE
Amazon SDE1 Algorithm
Here we try to find the number of bridges we can retain without causing an intersection.
Model the bridges as nodes in a graph and intersections as edges between nodes.
Now, we try to build a new graph adding nodes to an empty graph. At each step, we have choice of adding or not adding a node from the original graph to the new graph.
Tested this with some test sets. Looks like working. Please let me know if it fails for a case.
public class Graph2 {
// the adjacency matrix
int[][] matrix;
// number of nodes in the graph
int numNodes;
public Graph2(int[][] pmatrix, int nodes) {
matrix = pmatrix;
numNodes = nodes;
}
/**
* Find the maximum number of nodes that can be added to a new graph from
* this graph such that the new graph is completely disconnected (has no
* edges in it)
*
* @param nodeToCheck
* The node that has to be processed now
* @param newGraphNodes
* Array of nodes that has been added in the new graph
* @return The max number of nodes that can be added without having any
* edges in the graph
*/
int maxNodes(int nodeToCheck, int[] newGraphNodes) {
/* check if the new graph has an edge */
if (isIntersecting(newGraphNodes)) {
return -1;
}
/* check if there is an unprocessed node */
if (nodeToCheck < 0) {
return 1;
}
/* create a new array and copy the content. can't use clone here */
int na1[] = new int[newGraphNodes.length + 1];
System.arraycopy(newGraphNodes, 0, na1, 0, newGraphNodes.length);
/* append the node to be processed to this array */
na1[na1.length - 1] = nodeToCheck;
/*
* this checks the max nodes possible to obtain by adding the current
* node under process
*/
int l1 = 1 + maxNodes(nodeToCheck - 1, na1);
/*
* this checks the max nodes possible to obtain by leaving out the
* current node under process
*/
int[] na2 = newGraphNodes.clone();
int l2 = maxNodes(nodeToCheck - 1, na2);
if (l1 > l2) {
return l1;
} else {
return l2;
}
}
boolean isIntersecting(int[] nodes) {
int lastAddedNode = numNodes - nodes.length;
for (int i = numNodes - 1; i > lastAddedNode; i--) {
if (matrix[i][lastAddedNode] == 1) {
return true;
}
}
return false;
}
public static void main(String[] args) {
int m[][] = { { 0, 1, 0, 0, 0, 0, 0, 0, 0 },
{ 1, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 1, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 1, 0, 0, 0, 0, 0, 1 }, { 0, 0, 0, 0, 0, 0, 0, 0, 0 },
{ 0, 0, 0, 0, 0, 0, 0, 0, 0 }, { 0, 0, 0, 0, 0, 1, 0, 0, 0 } };
Graph2 test = new Graph2(m, 9);
int na[] = new int[0];
int l = test.maxNodes(8, na);
System.out.println("Min number of bridges to remove: "
+ (test.numNodes - l));
}
}
first find the index at which it was rotated
- split the array into two equal array
- compare first and last element of sub arrays
- one of the subarrays is skewed i.e. has first element greater than last element
- call the function recursively for the skewed subarray
once you have the this index, you can do a simple binary search
complexity is log n for finding the skew index and again log n for binary search
This solution is based on the idea of skipping forward by a length equal to the most number of repeats seen so far.
public class MostRepeatingInSortedArray {
public int mostRepeating(int a[]) {
// the index of current element
int current = 0;
int most_repeated = a[0];
int max_repeats = 1;
// just to see how many times the basic operation is done
int complexity = 0;
/* always increment by the max repeats seen so far */
while (current + max_repeats < a.length) {
/* same element again */
if (a[current + max_repeats] == a[current]) {
complexity++;
current += max_repeats;
max_repeats += max_repeats;
most_repeated = a[current];
while (a[current] == a[current + 1]) {
complexity++;
current += 1;
max_repeats++;
}
complexity++;
current++;
} else {
/* different element dound */
complexity++;
/* move the current index */
current += max_repeats;
/* backtrack */
int rep = 1;
while (a[current] == a[current - rep]) {
complexity++;
rep++;
}
complexity++;
/* check elements ahead of you */
int rep2 = 1;
while (a[current] == a[current + rep2]) {
complexity++;
rep2++;
if (current + rep2 == a.length) {
break;
}
}
complexity++;
int total_rep = rep + rep2 - 1;
if (total_rep > max_repeats) {
max_repeats = total_rep;
most_repeated = a[current];
}
current += rep2;
}
}
System.out.println("complexity: " + complexity);
System.out.println("elements: " + a.length);
return most_repeated;
}
public static void main(String[] args) {
MostRepeatingInSortedArray test = new MostRepeatingInSortedArray();
int[] input = new int[] { 1, 1, 1, 1, 2, 3, 3, 3, 4, 5, 5, 5, 5, 5, 5,
5, 5, 5, 5, 6, 6, 6, 6, 7, 8, 9, 9, 9, 9, 9, 10, 11, 12, 12,
12, 13, 13, 13, 13, 13, 13, 13, 22, 23, 24, 32, 33, 35, 36, 55,
55, 55, 55, 55, 56, 56, 57, 58, 59, 59, 59, 60, 65, 65, 65, 65,
65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 66, 66,
66, 67, 67, 68, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70,
70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70,
70, 70, 71, 72, 72, 72, 72, 72, 72, 72, 72, 72, 80, 80, 85, 86 };
int out = test.mostRepeating(input);
System.out.println("most repeated: " + out);
}
}
can you guys please help me in understanding how this solution is O(log n)? As far as I see it is still O(n) because eventhough you are splitting the array in the mid, you are still making the comparisons in both the sub arrays.
in binary search, once the array is split, we know if the element lies in one of the sub arrays easily (based on if the element is bigger than or smaller than the mid element)
thanks for pointing it out. my assumption that we don't need a repositioning of start as long as there is ascending order was wrong. if the sum goes negative, we need to reposition the start.
here is the edited code:
public class KadaneForPair {
private class Pair {
public int a;
public int b;
public Pair(int a, int b) {
this.a = a;
this.b = b;
}
}
public Pair[] findMaxSubArray(Pair[] input) {
int start = 0;
int maxSum = input[0].b;
int bestSum = input[0].b;
int bestStart = 0;
int bestEnd = 0;
for (int i = 1; i < input.length; i++) {
/*
* we reposition start index when the sum goes negative or if the
* ascending quality breaks
*/
if (input[i].a < input[i - 1].a || input[i].b + maxSum < 0) {
// change this to <= if you want the longest possible subarray
if (input[i].b + maxSum < 0) {
start = i + 1;
maxSum = 0;
i++;
} else {
start = i;
maxSum = input[i].b;
}
} else {
maxSum += input[i].b;
}
if (maxSum > bestSum) {
bestSum = maxSum;
bestStart = start;
bestEnd = i;
}
}
System.out.println("bestStart: " + bestStart + " bestEnd: " + bestEnd);
Pair[] out = new Pair[bestEnd - bestStart + 1];
System.arraycopy(input, bestStart, out, 0, bestEnd - bestStart + 1);
return out;
}
public static void main(String args[]) {
KadaneForPair test = new KadaneForPair();
Pair[] input = new Pair[5];
input[0] = test.new Pair(1, 2);
input[1] = test.new Pair(2, -100);
input[2] = test.new Pair(3, 3);
input[3] = test.new Pair(4, 4);
input[4] = test.new Pair(5, 5);
Pair[] out = test.findMaxSubArray(input);
System.out.println("input:");
display(input);
System.out.println("output: ");
display(out);
Pair[] input2 = new Pair[3];
input2[0] = test.new Pair(-1, -3);
input2[1] = test.new Pair(-1, -2);
input2[2] = test.new Pair(-1, -1);
out = test.findMaxSubArray(input2);
System.out.println("input:");
display(input2);
System.out.println("output: ");
display(out);
}
private static void display(Pair[] out) {
for (int i = 0; i < out.length; i++) {
System.out.print("(" + out[i].a + ", " + out[i].b + ") ");
}
System.out.println();
}
}
can you please explain?
this is the output i got
bestStart: 0 bestEnd: 0
input:
(-1, -1) (-1, -1) (-1, -1)
output:
(-1, -1)
your input has all negative elements. if you sum up any two of them you get a lower value than either of them. so, your output array must have a single element i.e. the element that has the highest 2nd element in the pair.
Modified Kadane's algorithm
public class KadaneForPair {
private class Pair {
public int a;
public int b;
public Pair(int a, int b) {
this.a = a;
this.b = b;
}
}
public Pair[] findMaxSubArray(Pair[] input) {
int start = 0;
int maxSum = input[0].b;
int bestSum = input[0].b;
int bestStart = 0;
int bestEnd = 0;
for (int i = 1; i < input.length; i++) {
/*
* we reposition start index only when the continuity of first a
* breaks.
*/
if (input[i].a < input[i - 1].a) {
start = i;
maxSum = input[i].b;
} else {
maxSum += input[i].b;
}
if (maxSum > bestSum) {
bestSum = maxSum;
bestStart = start;
bestEnd = i;
}
}
System.out.println("bestStart: " + bestStart + " bestEnd: " + bestEnd);
Pair[] out = new Pair[bestEnd - bestStart + 1];
System.arraycopy(input, bestStart, out, 0, bestEnd - bestStart + 1);
return out;
}
public static void main(String args[]) {
KadaneForPair test = new KadaneForPair();
Pair[] input = new Pair[5];
input[0] = test.new Pair(10, 2);
input[1] = test.new Pair(2, 10);
input[2] = test.new Pair(3, 2);
input[3] = test.new Pair(5, 87);
input[4] = test.new Pair(-1, 10);
Pair[] out = test.findMaxSubArray(input);
System.out.println("input:");
display(input);
System.out.println("output: ");
display(out);
}
private static void display(Pair[] out) {
for(int i =0;i<out.length;i++){
System.out.print("(" + out[i].a+ ", " + out[i].b + ") ");
}
System.out.println();
}
}
this is a fairly difficult problem :)
i came up with another idea but didn't test it because of time constraints. i tried a couple of simple examples though.
i guess the approach of selecting the player with most number of likes should still work. But in case of a tie, we have to chose the player whose fans are most 'loyal' to him i.e. we have to chose the player whose fans like least number of players other than him.
for this purpose, we will calculate a "loyalty index" for each player
loyalty index = number of other players liked by a fan of this player
and the player with least loyalty index is favored. in case of tie in loyalty index, any player ca be chosen among them.
For example, player 1 is liked by fan 1. fan 1 likes player 3 also. similarly, player 1 is liked by fan 2 and fan2 likes 0 other players. So,
loyalty index for player 1 = 1
for player 2 = 1
for player 3 = 2
so, we can chose either player 1 or player 2
101
100
010
011
sum array = 2 2 2
loyalty index array = 1 1 2
adding some details to @mohd.husn001's answer
we got to create a sum array that contains sum of likes per player (i.e. per column). At each step, the player with the max number of likes will be selected.
10101
00001
01011
sum array - 11113
at first step player 5 will be selected. now the 5th column and the rows for which 5th element is 1 (in this case all of them) are removed.
}
- sukheshmg November 06, 2016