shekhar2010us
BAN USER- 0of 0 votes
AnswersGiven a large document and a short pattern consisting of a few words (eg. W1 W2 W3), find the shortest string that has all the words in any order (for eg. W2 foo bar dog W1 cat W3 -- is a valid pattern)
- shekhar2010us in United States for Data Scientist| Report Duplicate | Flag | PURGE
Linkedin Software Engineer / Developer Algorithm
- 6 Answers Hello, I gave Flextrade online...
Hello, I gave Flextrade online c++ test, they asked 16 short C++ questions and I scored 13 (in 22 minutes). I am not happy with my score and wanted to know should I expect a call for further interviews?
- shekhar2010us December 09, 2011
A note for everyone applying for the same job:
When you get the code to login and give test, its instantaneous, I thought it would be like Bloomberg and will schedule a test within three days of signing in, but you have to give the test as soon as you login. I was not ready for that. Please be sure that you are on test giving mood while logging the first time.| Flag | PURGE
Why complex solutions:
public static void reverseANumber () {
int n = 756;
int rem = 0;
while (n != 0) {
rem = n%10;
System.out.print(rem);
n = n/10;
}
System.out.println("");
}
public static void maximizingProfit() {
int[] data = {5,9,6,2,4,8,3,1};
int maxProfit = 0;
int finalSp = 0;
int finalCp = 0;
for (int i = 1 ; i < data.length; ++i ) {
// selling at time 'i' will make a maximum profit of:
int sp = data[i];
for ( int j = i-1 ; j >= 0 ; --j ) {
int cp = data[j];
int profit = sp - cp;
if (maxProfit < profit) {
maxProfit = profit;
finalSp = data[i];
finalCp = data[j];
}
}
}
System.out.println("Max profit: " + (finalSp - finalCp) + ". Selling " + finalSp + " buying: " + finalCp);
}
Here is a solution without heap. The same thing can be done in an array.
If we need to find 'k' largest numbers, we take an array of size 'k' populated with first k items from the main data source. Now, keep on reading an item, and place it in the result array, if it has a place.
public static void largestkNumbers() {
int k = 4; // find 4 largest numbers
int[] arr = {4,90,7,10,-5,34,98,1,2};
int[] result = new int[k];
//initial formation of elems
for (int i = 0; i < k; ++i) {
result[i] = arr[i];
}
Arrays.sort(result);
for ( int i = k; i < arr.length; ++i ) {
int index = binarySearch(result, arr[i]);
if (index > 0) {
// insert arr[i] at result[index] and remove result[0]
insertInBetweenArray(result, index, arr[i]);
}
}
}
public static void insertInBetweenArray(int[] arr, int index, int num) {
// insert num at arr[index] and remove arr[0]
for ( int i = 0 ; i < index; ++i ) {
arr[i] = arr[i+1];
}
arr[index-1] = num;
}
public static int binarySearch(int[] arr, int num) {
int lo = 0;
int hi = arr.length - 1;
int mid = -1;
while( lo <= hi ) {
mid = (lo+hi)/2;
if ( arr[mid] > num ) {
hi = mid-1;
} else if ( arr[mid] < num ) {
lo = mid+1;
} else {
return mid;
}
}
return mid;
}
Sieve Implementation in Java:
int[] primes = new int[num-1];
for (int i = 0; i < primes.length; ++i) {
primes[i] = i+2;
}
for ( int i = 0 ; i < primes.length && primes[i] != -1 ; ++i ) {
int jmp = primes[i];
int index = i;
while( (index+jmp) < primes.length ) {
index = index+jmp;
primes[index] = -1;
}
}
None of the above solution take care of more than two players. The player array could be {1,2,3,4,1,2,3,4,1,2,3,4}
Also, sorting doesn't work. In this question, players are represented by consecutive numbers, so it seems that sorting will work. But the notion is that player can be represented by key... So, instead of the above array, the player array could be [10,1,100, 10,1,100, 10,1,100].. Sorting will fail here..
This code will take care of both the cases.
int[] players = { 1,2,3,4, 1,2,3,4, 1,2,3,4, 1,2,3,4, 1,2,3,4 };
int len = players.length;
List<Integer> list = new ArrayList<Integer>();
int index = 0;
while ( true ) {
list.add( players[index] );
index++;
if (players[index] == list.get(0)) {
break;
}
}
int repeat = len/list.size();
for ( int i = 0 ; i < list.size(); ++i ) {
for ( int j = 0; j < repeat; ++j ) {
players[i*repeat+j] = list.get(i);
}
}
Given a list of points each of 2-d, here is the code:
public static void midPoints2D() {
List<int[]> list = new ArrayList<int[]>();
list.add( new int[]{4,5} );
list.add( new int[]{8,9} );
list.add( new int[]{1,2} );
list.add( new int[]{4,6} );
list.add( new int[]{3,8} );
list.add( new int[]{8,4} );
list.add( new int[]{9,2} );
list.add( new int[]{8,5} );
list.add( new int[]{8,1} );
HashMap<String, List<int[]>> map = new HashMap<>();
map.put("even-even", new ArrayList<int[]>() );
map.put("even-odd", new ArrayList<int[]>() );
map.put("odd-even", new ArrayList<int[]>() );
map.put("odd-odd", new ArrayList<int[]>() );
for ( int[] arr : list ) {
if ( arr[0] % 2 == 0 && arr[1] % 2 == 0 ) {
List<int[]> l = map.get("even-even");
l.add(arr);
map.put("even-even", l );
} else if ( arr[0] % 2 == 0 && arr[1] % 2 != 0 ) {
List<int[]> l = map.get("even-odd");
l.add(arr);
map.put("even-odd", l );
} else if ( arr[0] % 2 != 0 && arr[1] % 2 == 0 ) {
List<int[]> l = map.get("odd-even");
l.add(arr);
map.put("odd-even", l );
} else {
List<int[]> l = map.get("odd-odd");
l.add(arr);
map.put("odd-odd", l );
}
}
System.out.println(map);
// now values in all keys in the hashmap contains only those int[] which has midpoints
for ( String key : map.keySet() ) {
List<int[]> li = map.get(key);
if ( li.size() > 1 ) {
for (int i = 0 ; i < li.size(); ++i) {
int [] arr1 = li.get(i);
for (int j = i+1 ; j < li.size(); ++j) {
int [] arr2 = li.get(j);
System.out.print( "[" + arr1[0] + "," + arr1[1] + "] and " + "[" + arr2[0] + "," + arr2[1] + "] --> " );
System.out.print( "[" + (arr1[0]+arr2[0])/2 + "," + (arr1[1]+arr2[1])/2 + "]\n" );
}
}
}
}
}
If the definition of mid point is exact "integer" value for the average of the point values, here is a solution for the n-dimension point. Though it does compare only two points.
public static class PointND {
public int[] arr;
public PointND() {}
}
public static void midPoints() {
int [] data1 = {2,2,8,5,9};
int [] data2 = {8,4,4,7,11};
PointND p1 = new PointND();
p1.arr = data1;
PointND p2 = new PointND();
p2.arr = data2;
boolean midPFound = true;
if ( p1.arr.length == p2.arr.length ) {
int [] midPoint = new int[p1.arr.length];
for ( int i = 0 ; i < p1.arr.length; ++i ) {
double mid = ( (double)p1.arr[i] + (double)p2.arr[i] )/2;
if ( mid == (p1.arr[i] + p2.arr[i])/2 ) {
midPoint[i] = (int)mid;
} else {
System.out.println("No Mid point found.");
midPFound = false;
break;
}
}
if (midPFound) {
System.out.println("Mid point is: " );
for ( int a : midPoint ) {
System.out.print(a + " ");
}
System.out.print("\n");
}
} else {
System.out.println("Unequal dimensions of points.");
}
}
Time: O(log n)
Memory: O(log n)
Given: Two nodes: n1, n2 and root: r
Solution:
Step 1: Move up from n1 to r --> store the ids in a list, list1
Step 2: Move up from n2 to r --> store the ids in a list, list2
Step 3: Reverse list1 and list2
Find the id till ids are common in list1 and list2. This "id" will be the solution
Here is the java code for generalized required offset.. The variable "requiredOffset" takes the parameter of the minimum threshold of the offset. For this case, it is 2.
public static void offsetOfRuns() {
String text = "000010000111";
int requiredOffset = 2;
int startIndexOffset = 0;
if ( text.length() > 0 ) {
int count = 1;
char ch = text.charAt(0);
for ( int i = 1 ; i < text.length(); ++i ) {
if ( text.charAt(i) == ch ) {
count++;
if (count == requiredOffset) {
System.out.println(startIndexOffset);
}
} else {
startIndexOffset = i;
count = 1;
ch = text.charAt(i);
}
}
}
}
There is a small error in the above code. It won't count the last character if that's the part of longest repeated sequence. Here is the correct code. Tested for all input data.
public static void calcLongest () {
String [] texts = {"a" , "aab" , "aa" , "abbbbbcc" , "aabbccdd" , "aabbbccaaadddde"};
for (String text : texts) {
char ch = 0;
if ( text.length() > 0 ) {
int longestIndexStart = 0;
int longestLength = 1;
int currIndexStart = 0;
int currLength = 1;
ch = text.charAt(0);
for ( int i = 1 ; i < text.length(); ++i ) {
if ( text.charAt(i) == ch ) {
currLength++;
} else {
ch = text.charAt(i);
if (currLength > longestLength) {
longestIndexStart = currIndexStart;
longestLength = currLength;
}
currIndexStart = i;
currLength = 1;
}
}
if ( currLength > longestLength ) {
longestIndexStart = currIndexStart;
longestLength = currLength;
}
System.out.println( text + " --> " + text.substring(longestIndexStart, longestIndexStart + longestLength ) );
}
}
}
public static void calcLongest () {
String text = "aabbbccaaadddde";
char ch = 0;
if ( text.length() > 0 ) {
int longestIndexStart = 0;
int longestLength = 1;
int currIndexStart = 0;
int currLength = 1;
ch = text.charAt(0);
for ( int i = 1 ; i < text.length(); ++i ) {
if ( text.charAt(i) == ch ) {
currLength++;
} else {
ch = text.charAt(i);
if (currLength > longestLength) {
longestIndexStart = currIndexStart;
longestLength = currLength;
}
currIndexStart = i;
currLength = 1;
}
}
System.out.println(longestIndexStart + "\t" + longestLength);
System.out.println( text.substring(longestIndexStart, longestIndexStart + longestLength ) );
}
}
String is of 'n' length. Palindrome is same around a center, thus there are (2n-3) centers. Taken odd and even length strings and removed the centers at index 0 and (n-1), since they cant be the centers. If they are centers, the palindrome will be a single length character.
Start from the start of the string and for each center, check whether it's a palindrome. If it's a palindrome, expand the center by one index both side.
Time complexity O(n^2) and space is O(1)..
e.g. input : hhgabcbaj, output: abcba..
There are 15 centers, after removing the centers at first and last characters.
center 1: hh (no further expansion), so answer is 'hh'
center 2: hhg - X
center 3: hg - X
center 4: hga - X
center 5: ga - X
center 6: gab - X
center 7: ab - X
center 8: abc - X
center 9: bc - X
center 10: bcb (expand it), abcba (expand it), no further expansion.. answer: 'abcba'
center 11: cb - X
center 12: cba - X
center 13: ba - X
center 14: baj - X
center 15: aj - X
Thus the answer is abcba....
Space complexity O(1) and time complexity O(n^2) worst case.. average case, it's O(n).. But the average case complexity is arguable, so I am keeping it O(n^2) for safe.
Can't it be done by taking the most significant bit and appending the numbers together.
In the above case: {21,9,23}
highest first most significant bit is 9
then it's 2.. but 23 and 21 are same, so we take second most significant bit which is 23
hence 92321 is the answer.
To get the first digit of the number,
int firstDigit (int x) {
while (x > 9) {
x /= 10;
}
return x;
}
I think this can be done in O(log n) complexity. There could be three cases...
Check the first number ... arr[0] > 0 or ==0 or < 0
case 1: arr[0] > 0
answer: none
O(1)
case 2: arr[0] = 0
e.g. arr = [ 0, 1, 2, 3, 5, 6, 7, 8, 9];
Apply binary search to arr[0 to n].
if array[n/2] > n/2, reapply binary search to arr[0 to (n/2 - 1)] until we reach an equality.. and keep track of the n/2 at each step, let it be variable "tracker"..
we will reach the equality at arr[2], and tracker = 4
Now, reapply binary search to arr[n/2 to tracker] because we know that all the elements to its left suffice the condition and will be in the result set.
Continue doing this, till we reach size(arr) = 1
O(logn n)
case 3: arr[0] < 0
This is a bit complex than the above two cases.
Here we have to run binary search twice (on two sides of the array) to check what is the index where positive number starts (let it be 'm'). and then repeat the case 2 with the lower bound 'm' instead of 0.
A simple solution would be to find the successor of the key. Well but the given key may exist or may not exist.
case 1: given key exist in the tree... then its simple to find its successor.
case 2: given key doesn't exist in the tree... In this case, we will first try to find the key in the tree and we will find the successor of the last element before we hit the null.
Time complexity: O(log n)
@ BVarghese
We have to take largest continuous increasing sequence (LCIS) and not largest increasing sequence(LIS). And for this we don't have to use DP. It can be done by a single pass by maintaining two variables, one keeping the record of start of the largest sequence and the other keeping the record of the length of the largest sequence...
So, the total time complexity will be O(n) for inorder and O(n) for LCIS making a total of O(n)..
Hey, you need 'ye' 30/36/40/42/48 whatever years to cross today's richest man. That's unfair because you never know how much wealth today's richest man can gather in the next 'ye' years.......... You cannot compare x and y, where x is present value and y is the value 'ye' years from now. Need to take the present value of y...(discounting it with risk free interest)
So, answer if you find X money after ye years, discount it by 6% for 'ye' years... That way you need few more years.....
yes, 17 is wrong. 4 is the correct answer..... You just need 4 chances to pick two balls of same colors, provided any color.....
If there is a constraint that you should have 2 of red or 2 of blue or 2 of yellow, then we have to use the probability ratios otherwise, we don't even have to care about the probabilities.
Man, do Amazon ask so simple questions in round 3????
There could be many methods, as explained in previous post.....
n*(n^2-1) = n(n+1)(n-1)
(1) when n is 'odd'; (n+1) and (n-1) are even. We get 2*2*2 from this, since n>3
(2) n, n-1, n+1 are consecutive, so one has to be multiple of 3.
From 1 and 2, we get 2*2*2*3=24
Hey Sachin... Urs is a different method actually, please correct me if I understood your method correctly.....
It's based on basic prob definition. p(x)=(number of x occurrences)/(total occurrences).
3+1/5 = White ball occurrence
3+1/5+4/5 = Total occurrences....
So, P(white ball) = {3+1/5}/{3+1/5+4/5}
Nice, I never thought of solving this problem by this method.. Would have taken Nipun's or fiturus's method
:-) tonnes of same answer.... Seems everyone is having good concept in Probability....
- shekhar2010us February 10, 2011@ Mandar In your solution, you urself saying the probabilities of getting 2,3,4,.... are different.... I think 000666 makes complete sense..... Since in that case, you roll two dices and any two distinct solution with give you numbers from 1-12 with equal probability 1/12.......
- shekhar2010us February 10, 2011I think the answer should be:
{(1/N)}*{1/(N-1)}*{1/(N-2)}*{1/(N-3)}*....*{1/(N-10)}
N = range of the random number generator... As N increases, the solution converges to ZERO.
So, going to your solution {(N-f)/N-1)}^9 might be the solution, where f=first number generated and N is the range of the generator.......
but this is not confirming the numbers are consecutive......
@beo
I don't think your statement "The probability to generate a number that is bigger is equal to the probability to generate a smaller number, i.e the probability for a bigger is 1/2" is true...
This is true only if your number is average of the min and max of the random number generated by the generator. For e.g. if the range is 1-100 and your first number is 25, then p(smaller)=24/99 and p(bigger)=75/99
Please correct me I'm wrong.
A = given array.
Ab = ASCII of A % no need to initialize
Initialize B with size max(Ab)
Go thru Ab one by one, get the number 'n' and add 1 to the nth index B.
Finally get the max(B).
Time:2*o(n)
Space:2*o(n)
Two types of argument passing in a function:
Call by reference pass the address of the variable, thus it changes the actual value of the variable, even outside the function.
Call by value passes the copy of the variable, thus it doesn't change the actual value of the variable.
@Tejaswl
The question is not about which coin is heavier, but it's which coin is different, The unusual coin may be lighter also.. Your algo is not taking this into consideration.....
O(n) complexity.
Maintain a set --> just to get all unique airports
Maintain a map --> for paths
Maintain a reverse map
The idea is to find the destination first (destination: one doesn't have start node and only end node)... And then backtrack using reverse map..
- shekhar2010us February 06, 2017