Murali Mohan
BAN USER- 0of 0 votes
AnswersHow do you swap bits at indexes i & j of a 32-bit memory word?
- Murali Mohan in India| Report Duplicate | Flag | PURGE
Marketshare Inc. Java Developer Algorithm - 1of 1 vote
AnswersYou are give a circular pizza with 3n pieces of pizza , each piece of pizza has different volume, The task is to eat n pieces of pizza such that the total consumed volume of pizza is the maximum, condition when the user chooses a piece of pizza he has to discard its immediate 2 neighboring pieces, the pizza is circular and every time we eat and discard there are new neighbors being formed per piece.
- Murali Mohan in United States
For ex:
pizza one : 2 1 1 2 9 1 10 1 9
pizza two: 1 9 2 2 9 1 1 10 1
pizza three: 1 9 2 2 9 1 1 10 10
Suppose the pizza was divided into 2n pieces, would your approach to find the maximum volume change from that of 3n pieces?| Report Duplicate | Flag | PURGE
Marketshare Inc. Java Developer Algorithm - 10of 10 votes
AnswersA tree, (NOT NECESSARILY BINARY), has nodes numbered 0 to N-1. An array has indices ranging from 0 to N-1. The indices denote the node ids and values denote the ids of parents. A value of -1 at some index k denotes that node with id k is the root. For ex:
3 3 3 -1 2 0 1 2 3 4
In the above, nodes with ids 0, 1 & 2 have 3 as parent. 3 is the root as its parent = -1 and 2 is the parent of node id 4.
- Murali Mohan in India for Bangalore
Given such an array, find the height of the tree.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 1of 1 vote
AnswersIn an N*M grid, in how many ways can you reach from top left (0,0) position to an arbitrary location (i,j) provided you can only move to the right or to the bottom in one step?
- Murali Mohan in India for Bangalore
How do you compute the number of ways from (0,0) to (i,j) if there are arbitrary number of blocks on the way?| Report Duplicate | Flag | PURGE
Amazon SDE-2 Problem Solving - 3of 3 votes
AnswersDevelop an algorithm and write code to break a sentence without spaces into a sentence of valid words separated by spaces.
- Murali Mohan in India for Bangalore
For ex: thissentenceisseparated needs to be broken into: this sentence is separated
Assume that you have a dictionary to check for valid words. Your algorithm should return false if the sentence cannot be separated into valid words.| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm - 0of 0 votes
AnswersGiven n, how many structurally different binary trees can be formed?
- Murali Mohan in India for Bangalore
For ex: n = 1 => one tree
n = 2 => two trees
O O
/ \
O O
n = 3 => five trees
O O O O O
/ \ \ / / \
O O O O O O
/ \ / \
O O O O| Report Duplicate | Flag | PURGE
Amazon SDE-2 Problem Solving - 0of 0 votes
AnswersSuppose you have an array of +ve numbers, -ve numbers and zeroes. Devise an algorithm to find the maximum contiguous subsequence product.
- Murali Mohan in India
For 7 -3 -1 2 -40 0 3 6, the max subsequence product = -1 * 2 * -40 = 80
For -3 7 2 0 -5 7 -2 -2 2, the maximum subsequence product = -5 * 7 * -2 = 70| Report Duplicate | Flag | PURGE
InMobi Algorithm
- 0 Answers Interview with Sr. Dev Mgr at Amazon
All,
- Murali Mohan July 17, 2013
I have an interview scheduled with Sr. Dev Mgr at Amazon in a week from now. That is the last round and I am totally clueless as so what will be asked there. Can anyone plz plz plz guide me?
Thanks a million!| Flag | PURGE
I think the interviewer in such cases is only evaluating your awareness level. Wildcard string matching happens by constructing an NFA, which can't happen in an hour. But one should at least know that.
- Murali Mohan June 12, 2013An O(n) solution by finding maximum subsequences using Kadane's algorithm
1. Find maxsubsequence sum M1
2. Negate the whole array and find again maxSubsequenceSum M2
3. M1 + M2 should be the absolute max difference. [M1 and M2 must be appearing in disjoint contiguous subarrays, for if they overlap, M1 and -M2 cannot be maximum +ve and maximum -ve values respectively. and we have a proof by contradiction above]
4. Separately handle degenerate cases such as 1) the maximum subsum being contained in the minimum subsum and 2) vice versa
Full working implementation in java is below. Provide Input to the program as:
4 -1 7
-4 1 -7
-9 -4 1 2 -5 -7 -8
9 4 -1 -2 5 7 8
import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;
public class MaxAbsoluteDiff {
static ArrayList<Integer> numbers = new ArrayList<Integer>();
int pstart = 0, pend = 0, nstart = 0, nend = 0;
int maxpsumgbl = 0, maxnsumgbl = 0, absDiff = 0;
public void readInput() {
Scanner scanner = new Scanner(System.in);
scanner.useDelimiter(System.getProperty("line.separator"));
Pattern delimiters = Pattern.compile(System
.getProperty("line.separator") + "|\\s");
scanner.useDelimiter(delimiters);
int i;
while (scanner.hasNextInt()) {
i = scanner.nextInt();
numbers.add(i);
}
}
public void Kadane() {
int maxpsumrunning = 0, maxnsumrunning = 0;
int j = 0;
for (; j < numbers.size(); j++) {
maxpsumrunning += numbers.get(j);
maxnsumrunning += -numbers.get(j);
if (maxpsumgbl < maxpsumrunning) {
maxpsumgbl = maxpsumrunning;
pend = j;
}
if (maxpsumrunning < 0) {
maxpsumrunning = 0;
if (j + 1 < numbers.size() && numbers.get(j + 1) > 0)
pstart = j + 1;
}
if (maxnsumgbl < maxnsumrunning) {
maxnsumgbl = maxnsumrunning;
nend = j;
}
if (maxnsumrunning < 0) {
maxnsumrunning = 0;
if (j + 1 < numbers.size() && -numbers.get(j + 1) > 0)
nstart = j + 1;
}
}
if (nstart > pstart && nend < pend) {
int subsum = 0;
for (int k = pstart; k < nstart; k++) {
subsum += numbers.get(k);
}
if ((maxpsumgbl + maxnsumgbl - subsum) > subsum) {
maxpsumgbl = maxpsumgbl + maxnsumgbl - subsum;
} else {
maxpsumgbl = subsum;
}
} else if (pstart > nstart && pend < nend) {
int subsum = 0;
for (int k = nstart; k < pstart; k++) {
subsum += -numbers.get(k);
}
if ((maxnsumgbl + maxpsumgbl - subsum) > subsum) {
maxnsumgbl = maxnsumgbl + maxpsumgbl - subsum;
} else {
maxnsumgbl = subsum;
}
}
absDiff = maxpsumgbl + maxnsumgbl;
}
public static void main(String[] args) {
MaxAbsoluteDiff maxsss = new MaxAbsoluteDiff();
maxsss.readInput();
maxsss.Kadane();
System.out.println("Max Abs Diff=" + maxsss.absDiff);
}
}
Doesn't vector initialization use loop inside?
- Murali Mohan June 11, 2013You need to construct an NFA to do pattern matching with regular expressions.
- Murali Mohan June 11, 2013@LAP, I think the degenerate cases of the minimum sum completely contained in the maximum sum or the maximum sum completely contained in the minimum sum can be handled separately.
Suppose Min is completely contained in Maximum subsum, the the maximum subsum would appear something like
P1 + N + P2, Where P1 is the +ve sum that is to the left of the the minimum sum M and P2 is the +ve sum that is to the right of N.
If P1 > P2 then |P1-N| should give the max absolute diff else it would be |P2-N|
if max subsum is completely contained in min subsum, then the min subsum would appear as
N1 + P + N2. Where N1 is the -ve sum that is to the left of the the maximum sum P and N2 is the -ve sum that is to the right of P.
if N1 > N2 then |N1-P| should be the maximum sum else |N2-P|
The min and max subsums can't overlap, for if they overlap, you can arrive at a proof by contradiction by splitting the sum of numbers into three parts: N + O + M
Where N is the sum of the minimum subset excluding the overlapping part.
O is the sum of the overlapping part
S is the sum of the maximum subset excluding the overlapping part
For N+O to be minimum O has to be -ve
M + O to be maximum O has to be +ve, a contradiction.
@Anonymous:
First off, a decent algorithm would never include 0 in the subsets if 0 is a boundary of interval, so the minimum sum and maximum sum subsets would be {-1} and {1} respectively and not {-1,0} and {0, 1}.
Secondly. the minimum sum subarray and maximum sum subarray can't overlap. they can however contain in each other completely.
Proof: Proof is by contradiction:
Suppose that they overlap: split the sum of numbers into three parts: N + O + M
Where N is the sum of the minimum subset excluding the overlapping part.
O is the sum of the overlapping part
S is the sum of the maximum subset excluding the overlapping part
For N+O to be minimum O has to be -ve
M + O to be maximum O has to be +ve, a contradiction.
@LAP, Nice test case. You are right, the range of minimum sum is completely within the range of maximum sum.
When I checked using my java code below, the solution I proposed is working fine for the data given in the example. However, I need to think more about your test case.
import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;
public class MaxAbsoluteDiff {
static ArrayList<Integer> numbers = new ArrayList<Integer>();
static ArrayList<Integer> negnumbers = new ArrayList<Integer>();
public void readInput() {
Scanner scanner = new Scanner(System.in);
scanner.useDelimiter(System.getProperty("line.separator"));
Pattern delimiters = Pattern.compile(System
.getProperty("line.separator") + "|\\s");
scanner.useDelimiter(delimiters);
int i;
while (scanner.hasNextInt()) {
i = scanner.nextInt();
numbers.add(i);
negnumbers.add(-i);
}
}
public int Kadane(ArrayList<Integer> numbers) {
int maxsumgbl = 0;
int maxsumrunning = 0;
int j = 0;
for (; j < numbers.size(); j++) {
maxsumrunning += numbers.get(j);
if (maxsumgbl < maxsumrunning) {
maxsumgbl = maxsumrunning;
}
if (maxsumrunning < 0) {
maxsumrunning = 0;
}
}
return maxsumgbl;
}
public static void main(String[] args) {
MaxAbsoluteDiff maxsss = new MaxAbsoluteDiff();
maxsss.readInput();
int maxSum = maxsss.Kadane(numbers);
int minSum = -maxsss.Kadane(negnumbers);
System.out.println("maxsum=" + maxSum);
System.out.println("minsum=" + minSum);
System.out.println("Abs Diff=" + (maxSum - minSum));
}
}
Will the following solution work?
1. Find maxsubsequence sum M1 (using Kadane's algorithm)
2. Negate the whole array and find again maxSubsequenceSum M2
3. M1 + M2 should be the absolute max difference. [M1 and M2 must be appearing in disjoint contiguous subarrays, for if they overlap, M1 and -M2 cannot be maximum +ve and maximum -ve values respectively]. and we have a proof by contradiction below]
A naive solution is to:
1. Read the file line by line.
2. Print the characters of the ith line as ith column in the output file.
Printing in ith column entails
a. Reading the output file line by line
b. If there is no corresponding line in the output file for the kth character ith line of input file,
create a new line, fill with (k-1) spaces and add the kth character
c. if there is a corresponding(kth) line in the output file and if the length is < k-1, fill with spaces upto (k-1)st character, then append the kth character of the ith line from the input
d else append the kth character
solution to this problem can actually depend on questions like - does the whole file fit into main memory? What is the required time complexity?? etc
Could you please exemplify with a small alphabet, say {a,b,c} mapped to {c,a,b}?
- Murali Mohan June 10, 2013LinkedHashMap lists the elements in the order they were inserted.
TreeHashMap iterates over the elements in their natural order.
In my opinion, a combination of data structures should solve the problem. Use a min-heap and a BST augmented by the size field.
1. The BST will store userids as keys along with last-logged-in field.
2. The min heap will have last-logged-in time as key. Along with the key store the userid.
3. When a new user logs in or an old user re-logs into the system, insert a key into the heap. In the BST if the corresponding userid is present, update it's last-logged-in value. Otherwise insert a new key with the userid
4. Whenever we want to find out the unique users logged in the last 10 mins.
a. Extract min from the heap if current time - last-logged-in time > 10 mins
b. For the corresponding Id in the BST, delete the node if current time - last-logged-in time > 10 mins
c. Repeat the above steps a & b until the min element of the heap satisfies current time - last-logged-in time <= 10 mins
d. Return the value of size field of the root node of the BST.
I don't think using an interval tree can simplify the problem. any further. AFAIK, Interval tree can be used to identify if there exists any interval in the tree, encompassing the given interval.
I tried to think on those lines, but could not find an effective solution. Could you please articulate your thoughts?
You can delete this post if you want to. That would avoid confusion to others.
- Murali Mohan June 08, 20131. Maintain a hash table H and for each of the intervals, store the boundaries as keys and an int as a value. Increment the value if the key is a starting boundary, and decrement if it is an ending boundary.
For eg, for [5, 11], [6, 18], [2, 5],[3,12]
5 -> 1
11 -> -1
6 -> 1
18 -> -1
2 -> 1
5 -> 0
3 -> 1
12 -> -1
Run a loop from 1 to the maximum ending boundary. Maintain running counters and global counters to sum up the values as we see in the hash table and print out the sub-interval that overlaps maximum number of given intervals. Time complexity O(n): Space complexity O(n)
Java implementation below: Input need to be given as:
5,11
6,18
2,5
3,12
import java.util.HashMap;
import java.util.Scanner;
import java.util.regex.Pattern;
public class MaxOverlappingIntervals {
static HashMap<Integer, Integer> intervals = new HashMap<Integer, Integer>();
static int endMax = 0, gblIntervalOverlappingCount = 0,
localIntervalOverlappingCount = 0;
static int subIntBegin = 0, subIntEnd = 0;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Pattern pattern = Pattern.compile(System.getProperty("line.separator") + "|\\s");
scanner.useDelimiter(pattern);
while (scanner.hasNextLine()) {
String input = scanner.next();
if (input.length() == 0) break;
Integer begin = Integer.parseInt(input.split(",")[0]);
Integer end = Integer.parseInt(input.split(",")[1]);
intervals.put(begin,
!intervals.containsKey(begin) ? 1
: intervals.get(begin) + 1);
intervals
.put(end,
!intervals.containsKey(end) ? -1 : intervals
.get(begin) - 1);
endMax = end > endMax ? end : endMax;
}
int val = 0;
for (int i = 0; i <= endMax; i++) {
if (intervals.get(i) != null) {
val = intervals.get(i);
if (val > 0) {
localIntervalOverlappingCount += val;
subIntBegin = i;
/*if (localIntervalOverlappingCount - val == 0) {
subIntBegin = i;
}*/
} else if (val < 0) {
localIntervalOverlappingCount += val;
if ((localIntervalOverlappingCount - val) >= gblIntervalOverlappingCount) {
gblIntervalOverlappingCount = localIntervalOverlappingCount - val;
subIntEnd = i;
}
}
}
}
if (subIntEnd > subIntBegin)
System.out.println("Maximum number(=" + gblIntervalOverlappingCount + ") of species live between: "
+ subIntBegin + "," + subIntEnd + " years of age");
else
System.out.println("No overlapping intervals found");
}
}
1. For both of the input strings S1 and S2, for all their N^2 substrings with beginIndex = i & endIndex = j, compute their integral values V1 and V2 just by summing up their charAt(k) values. [i<=k<=j]
2. Compare V1 and V2. If they are equal, sort the substrings S1.substring(i,j) and S2.substring(i,j) and compare if they are equal.
3. Save (i,j) that contains the maxlength substring and print it.
Full java implementation is given below. Provide in the console, the input strings one after the other.
Eg:
SKANDAPURANAGAJUTA
GARUDAAANURPJUJUGA
import java.util.Arrays;
import java.util.Scanner;
import java.util.regex.Pattern;
public class MaxMatchingPermutedStringWindow {
static String input1, input2;
static int min= 1, max = 0;
private static boolean cmpStrVal(int i, int j) {
int sum=0;
for (int k = i; k <=j ; k++) {
sum += input1.charAt(k) - input2.charAt(k);
}
return 0 == sum;
}
private static boolean compareStr(int i, int j) {
boolean equal = true;
char[] arr1 = input1.substring(i, j + 1).toCharArray();
char[] arr2 = input2.substring(i, j + 1).toCharArray();
Arrays.sort(arr1);
Arrays.sort(arr2);
for (int k = 0; k < arr1.length; k++)
equal &= arr1[k] == arr2[k];
return equal;
}
private static void findMaxMatSubString() {
int len = input1.length();
for (int k = 0; k < input1.length(); k++)
for (int l = k; l < input1.length(); l++)
if (cmpStrVal(k,l) && compareStr(k,l) && (l-k+1) > (max - min + 1)) {
min = k; max = l;
}
System.out.println("Substring from 1st string:" + input1.subSequence(min, max+1));
System.out.println("Substring from 2nd string:" + input2.subSequence(min, max+1));
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Pattern pattern = Pattern.compile(System.getProperty("line.separator"));
scanner.useDelimiter(pattern);
if (scanner.hasNextLine()) {
input1 = scanner.next();
}
if (scanner.hasNextLine()) {
input2 = scanner.next();
} else {
System.out.println("Please provide both the strings");
}
if (input1.length() != input2.length())
System.out.println("The strings are not of equal length!");
else
findMaxMatSubString();
}
}
Are they mutated patterns or permuted patterns? Please define what a mutated pattern is.
- Murali Mohan June 08, 2013I think the problem can be solved recursively as stated previously and also iteratively. Iterative version is presumably tough to do.
Full implementation of recursive method in java is given below.
package org.murali.algos;
import java.util.HashSet;
import java.util.Scanner;
import java.util.Set;
import java.util.regex.Pattern;
public class StringCodes {
static String input;
static String[] codes = { "", "a", "b", "c", "d", "e", "f", "g", "h", "i",
"j", "k", "l", "m", "n", "o", "p", "q", "r", "s", "t", "u", "v",
"w", "x", "y", "z" };
static Set<String> strings = new HashSet<String>();
private static void printCodes(String input, String output) {
if (input != null) {
int len = input.length();
if (len == 0) {
strings.add(output);
} else if (len == 1) {
strings.add(output + codes[Integer.parseInt(input)]);
} else {
if (Integer.parseInt(input.substring(1, 2)) != 0)
printCodes(
input.substring(1),
output
+ codes[Integer.parseInt(input.substring(0,
1))]);
if (Integer.parseInt(input.substring(0, 2)) < 27)
printCodes(
input.substring(2),
output
+ codes[Integer.parseInt(input.substring(0,
2))]);
}
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Pattern pattern = Pattern.compile(System.getProperty("line.separator"));
scanner.useDelimiter(pattern);
if (scanner.hasNextLine()) {
input = scanner.next();
}
Integer.parseInt(input);
printCodes(input, "");
System.out.println(strings);
}
}
Problem is solved using dynamic programming. We need to do a bit of pre-processing before invoking dynamic programming.
1. Sum up all the elements and let the sum be S
2. If S is odd, then the numbers can be partitioned into two sets, such that the difference of the sum of their elements is at least 1. If S is even their difference could be at least 0.
3. In either case, we need to figure out if there exists a subset of the elements in original array whose sum equals to S/2. If such a set exists, the other elements can put into another set which partitions the array into two sets and their sums would be equal.(sums would be roughly equal if S is odd an also depends on the distribution of numbers)
4.Once the set is identified, mark the elements with a -ve sign.
5. The summation of these numbers would yield a minimum number >=0.
Follows is a full implementation in java. Inputs are given using space as delimiter.
Eg: 5 3 7 2 4 6 1
import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;
public class PartitionProblem {
static ArrayList<Integer> input = new ArrayList<Integer>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Pattern pattern = Pattern.compile(System.getProperty("line.separator")
+ "|\\s");
scanner.useDelimiter(pattern);
int intval, sum = 0;
while (scanner.hasNextInt()) {
intval = scanner.nextInt();
input.add(intval);
sum += intval;
}
boolean[][] vals = new boolean[sum / 2 + 1][input.size() + 1];
for (int j = 0; j <= input.size(); j++) {
vals[0][j] = true;
}
for (int j = 1; j <= sum / 2; j++) {
vals[j][0] = false;
}
for (int i = 1; i <= sum / 2; i++) {
for (int j = 1; j <= input.size(); j++) {
vals[i][j] = vals[i][j - 1];
if (!vals[i][j]) {
if ((i - input.get(j - 1)) >= 0) {
vals[i][j] = vals[i - input.get(j - 1)][j - 1];
} else {
vals[i][j] = false;
}
}
}
}
if (vals[sum / 2][input.size()]) {
int i = sum / 2, j = input.size();
while (i >= 0 && j > 0) {
if (!vals[i][j - 1]) {
i -= input.get(j - 1);
input.set(j-1, -input.get(j - 1));
}
j--;
}
}
System.out.println(input);
}
}
I am assuming the code to be bug-free. Feel free to fix any issues.
- Murali Mohan June 06, 2013My thoughts are precisely the same. Thumbs up!
- Murali Mohan June 06, 2013@cengin, aka
Thanks for the bug fix. Yeah, it is working fine now.
The resultant array after merge is of size n1 + n2. Call n1+n2 = m. If m is odd then we have one median which is the floor(m/2)th element. If m is even we have floor(m)th and ceil(m)th elements as medians.
Apply the standard 'SELECT' algorithm that invokes the partition subroutine of quicksort. SELECT computes the median in O(m) time complexity. The merge operation takes O(m) steps. Overall the median can be found in O(m)[= O(n1+n2)] time complexity
@Vin
I think the bug lies in
S[i] = getMax(lst[i] + S[i-2], S[i-1]);
should not consider S[i-1] as it is an adjacent element
- Murali Mohan June 05, 2013Clear case of Dynamic Programming.
Follows the recursive structure:
currentSum = max{A[i], max{A[i-2] + A[i], A[i-2]}, max{A[i-3] + A[i], A[i-3]}, } // i runs from 2 to N.
Full working implementation in java is given below. Give the input numbers using space as delimiter.
Eg: 1 - 1 3 8 4
1 5 3 9 4
1 2 3 4 5
import java.util.ArrayList;
import java.util.Scanner;
import java.util.regex.Pattern;
public class MaxSumSubset {
static ArrayList<Integer> input = new ArrayList<Integer>();
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
Pattern pattern = Pattern.compile(System.getProperty("line.separator")
+ "|\\s");
scanner.useDelimiter(pattern);
int intval, tempMax = 0;
while (scanner.hasNextInt()) {
intval = scanner.nextInt();
input.add(intval);
}
int[] vals = new int[input.size()];
if (vals.length > 1) {
vals[0] = input.get(0);
vals[1] = Math.max(input.get(0), input.get(1));
for (int i = 2; i < input.size(); i++) {
tempMax = Math.max(vals[i - 2], vals[i - 2] + input.get(i));
vals[i] = Math.max(tempMax, input.get(i));
if (i - 3 >= 0) {
int tempMax2 = Math.max(vals[i - 3],
vals[i - 3] + input.get(i));
vals[i] = Math.max(tempMax2, vals[i]);
}
}
}
tempMax = -99999999;
for (int i = 0; i < vals.length; i++) {
if (vals[i] > tempMax) {
tempMax = vals[i];
}
}
System.out.println("Maximum sum=" + tempMax);
}
}
Edited to fix the bug as suggested by Celgin
- Murali Mohan June 05, 2013Duplicate question: refer /question?id=18136672
- Murali Mohan June 04, 20131 + (1.2 + 2.3 + 3.4 + ... + n.(n+1))/2 is the pattern. Folks strong at math should help in giving .a formula.
- Murali Mohan June 04, 20131 + [Summation of i(i+1)/2 where i runs from 1 to n]
Also, did a bit of math and found a closed form formula for this:
1 + [n(n+1)(2n+1) + 3n(n+1)]/12
Out of N points, we can draw N(N-1)/2 lines.
1. For each of the lines, find their slope m and the y-intercept c. Make them a pair (m.c)
2. Use a stable sort algorithm like merge sort to first sort the pair by m - complexity O(N^2 * logN)
3. Sort the pair again by c - complexity O(N^2 * logN)
4. Scan the array to compute which (m,c) pairs are in maximum number.Complexity: O(N^2).
Overall complexity: O(N^2 * logN)
Ravi Gupta's solution is good.
1. Sum of all the array elements - sum of first N-1 elements
2. Second solution: Sum up all the array elements. then XOR the result with numbers from 1 to N-1. The resultant value is the duplicate element.
This appears to be asking to implement sort functionality on a Turing machine.
The lift is either going up or coming down. We have to consider the direction, the ID of a person and the floor #.
While going up
if person ID > current floor number
if the lift is empty
Add the current person to the lift.
else if the person ID in the lift < person ID on the floor OR the person ID in the lift equals current floor #
Swap the person in the lift with the person on the floor.
While coming down
if person ID < current floor number
if the lift is empty
Add the current person to the lift.
else if the person ID in the lift > person ID on the floor OR the person ID in the lift equals current floor #
Swap the person in the lift with the person on the floor.
Each lift movement to the top puts at least one person in right position and each movement from the top to the bottom puts at least one person in the right position. The total number of movements will therefore be at most N to sort N persons into their places.
Eg: if the initial ordering of people was 3 2 1 for N=3 people, then the sort should work as below
Initial: 3 2 1
Step 1: _ 2 1
(3) [inside lift]
Step 2: _ 2 1
(3)
Step 3: _ 2 1
(3)
Step 4: _ 2 3
(1)
Step 5: _ 2 3
(1)
Step 6: _ 2 3
(1)
Step 6: 1 2 3
(_)
Blacklist the question
- Murali Mohan May 29, 2013@Naveen, how did you know the answer is 175 for N=15, M=5 and K=2?
For K >1, I think there is only possible way of painting the boards with minimum cost. My reasoning goes as below. Suppose N=8, M=5 and K=2
The only configuration with the minimum number of boards painted and at the same time satisfying the criteria that every M consecutive boards should have at least K boards painted is:
000CC000
In the above configuration, the first M(=5) boards [1..5] have 2 boards painted, the next M boards, [2..6] have 2 boards painted and so on. Any other configuration leads to the number of painted boards to be >2 which is not optimal. The above configuration holds for 5<=N<=8
In general, I think the optimal solution should be such that for the first M boards, K boards need to be painted from M-K+1 to M. These K painted boards should be shared across all M-size window frames till the one that ends at 2M-K and the pattern needs to be repeated.
For N=15, M=5 and K=2, the optimal pattern is: 000CC000CC000CC
Can you find any counterexample to it? Can you find any other optimal pattern with the same or lesser number of boards but with a different permutation?
For K=1, however, there can be several combinations as depicted in your example.
XORing all the lines till the end may be little overwhelming. What if the different line was the 4th line in a million line file?
1. Compare 1st and 2nd lines.
a. If they both are equal, keep XOring the 1st line(or the 2nd line) with 3rd line onwards. Whenever the result of XOR operation !=0 then return the different line.
2. If they both are different XOR 1st line and 3rd line, XOR 2nd line and 3rd line. return whichever is nonzero
Given n^2 elements in the 2D array, the complexity is O(n^4) for this solution.. right?
- Murali Mohan May 28, 2013You are wrong unless you prove yourself to be correct :). Just kidding.
- Murali Mohan May 25, 2013Store 3 lines at a time: previous, current & next. Initially, previous = line #1, current = line #2 and next = line#3.
while (next != EOF) {
if (!previous.equals(current) {
if (next.equals(current))
return previous;
else return current;
} else if (!current.equals(next)) {
return next;
previous = current;
current = next;
next = readnextLine();
}
3. Error count in the range would be rank(endDate) - rank(startDate)
- Murali Mohan May 20, 2013If we want to maintain a dynamic set of records, a still better approach would be to use a balanced BST. The BST would have date as the 'key' field and should be augmented with a 'errorCount' field that maintains the count of errors seen on a given date.
1. As the input file is scanned, insert/update errorCount field of the appropriate key in the BST
2. To find the errorCount in a given range, use a modified version of rank() operation that adds up the errorCount fields is the subtrees.
Good solution. This may require O(n) extra space though. How about doing the inorder traversal using iteration? hasNext() will check whether the next iteration is possible and next() would return the element of the current iteration.
- Murali Mohan May 18, 2013Killer input by Knuth, though Dilbert's solution can be extended to use a min-heap to store the top 3 +ve values(p1>=p2>=p3) and use a max-heap to store bottom 2 -ve values (n1<=n2). The max3 product can be computed as below:
if ( n1 * n2 > p1 * p2)
return n1 * n2 * p3
else
return p1 * p2 * p3
Use date as the key. Use a cumulative array A that counts the number of errors seen up to (and including) a given date.
Given dates di and dj where di<=dj, the number of errors between those dates is simply
: A[dj]-A[di-1]
The basic idea is to use recursion. We need to have the notion of a 'mirrorNode' to solve this problem. For ex: the last node is the mirror node of the first, the second last is the mirror node of the second and so on. Based on this idea, a simple recursive trick like the below does the job.
A stack cannot be used for this problem as it will take extra memory.
Full java implementation is below.
package org.murali.algos;
import java.util.Scanner;
import java.util.regex.Pattern;
public class LinkedListCareerCup {
class NodeCareerCup {
Object val;
NodeCareerCup next;
public NodeCareerCup(Object val, NodeCareerCup next) {
super();
this.val = val;
this.next = next;
}
}
NodeCareerCup head = null;
public boolean CheckIfPalindrom() {
if (head == null || head.next == null) {
return true;
}
NodeCareerCup retNode = checkPalindromeRec(head, head);
return retNode != null;
}
public NodeCareerCup checkPalindromeRec(NodeCareerCup current, NodeCareerCup head) {
// last node
if (current.next == null) {
if (current.val.equals(head.val)) {
return head.next;
} else {
return null;
}
}
else {
NodeCareerCup mirrorNode = checkPalindromeRec(current.next, head);
if (mirrorNode != null) {
if (mirrorNode.val.equals(current.val)) {
if (mirrorNode.next == null) {
return head;
}
return mirrorNode.next;
}
else {
return null;
}
}
return null;
}
}
public void AddNode(NodeCareerCup node) {
node.next = head;
head = node;
}
public static void main(String[] args) {
LinkedListCareerCup ll = new LinkedListCareerCup();
Pattern pattern = Pattern.compile(System.getProperty("line.separator") + "|\\s");
Scanner scanner = new Scanner(System.in);
scanner.useDelimiter(pattern);
System.out.println("/////////////////////////////////////");
System.out.println("Enter numbers with spaces in-between and hit enter twice. For ex:");
System.out.println("1 2 3 3 2 1\n");
System.out.println("");
System.out.println("/////////////////////////////////////\n");
int i;
while (scanner.hasNextInt()) {
i = scanner.nextInt();
ll.AddNode(ll.new NodeCareerCup(new Integer(i), null));
}
System.out.println("That the given list is a palindrome is " + ll.CheckIfPalindrom());
}
}
I think the problem specification needs to be more clear as to describing whether the array has been rotated left or rotated right. Also left rotation and right rotation themselves need proper definition.
The example 6 7 8 1 2 3 4 5 can be seen to be right rotated - meaning, in the left half of the array, the property of numbers being non-decreasing is broken. In that case, binary search can be busted up on the left half of the array.
On the other hand if the array is rotated as 3 4 5 6 7 8 1 2, doing a binary search on the left hand won't work. You will have to do a binary search on the right half.
If it is not specified whether the array has been left-rotated or right-rotated, then you will have to invoke two binary searches on both the halves, which leads to O(n) time complexity.
If the distances in the network are all equal(say unit distance) apply BFS from the given system to find the nearest printer(s). If the distances are unequal, apply Dijkstra's shortest path algorithm.
- Murali Mohan May 17, 2013BST data structure supports the operations of Min, Max, Predecessor and Successor. Just like in a sorted array we increment the pointer from min value and decrement the pointer from max value to check the sum, we repeatedly use the pointers returned by Successor and Predecessor functions in a BST to check the sum.
- Murali Mohan June 20, 2011This is Josephus problem.
- Murali Mohan October 13, 2010public class NumtoA {
public void convert(int i) {
StringBuilder output = new StringBuilder("");
int rem;
char[] charset = {'0', 'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z' };
while(i > 0) {
rem = i % 26;
if (rem == 0)
{
output.append(charset[26]);
i = i/26 - 1;
}
else
{
output.append(charset[rem]);
i /= 26;
}
}
System.out.println(output.reverse());
}
public static void main(String args[])
{
NumtoA numtoa = new NumtoA();
numtoa.convert(0);
numtoa.convert(1);
numtoa.convert(28);
numtoa.convert(78);
numtoa.convert(676);
numtoa.convert(677);
numtoa.convert(702);
numtoa.convert(703);
}
}
Assuming that the number is of the type a.b1b2...bn where n is finite(and this should be the case because any register can hold finite data)
(After removing the integer part), keep extracting the MSDs from the fractional part and build a 10-ary tree(each child node representing one of the 10 decimal digits) as follows:
a. Root node does not have a value.
b. If not present add the extracted MSD as a child at all levels. If present, increment a counter at the node.
c. On reaching the end of the string, find out the path in the tree with maximum(and equal) value of counter at all the nodes.
For instance: if we take 23.34563456, for the fractional part 34563456 we can build a tree like below(numbers in brackets are counters:
<> <> <>-------- <>--------------
/ / \ / \ | / \ | |
3(1) 3(1) 4(1) 3(1) 4(1) 5(1) 3(1) 4(1) 5(1) 6(1)
/ / \ / \ \
4(1) 4(1) 5(1) 4(1) 5(1) 6(1)
/ / \
5(1) 5(1) 6(1)
/
6(1)
<>-------------- ... till finally <>--------------
/ \ | | / \ | |
3(2) 4(1) 5(1) 6(1) 3(2) 4(2) 5(2) 6(2)
/ \ \ / \ \
4(1) 5(1) 6(1) 4(2) 5(2) 6(2)
/ \ / \
5(1) 6(1) 5(2) 6(2)
/ /
6(1) 6(2)
The longest path on the above tree with maximum values of the counters gives us the answer.
- Murali Mohan October 13, 2010T's solution would work. Another approach if we were to avoid pointers is to store min value along with the element value in each stack element.
- Murali Mohan October 05, 2010
@Anonymous. Right question. You have to try all the possible N^2 combinations. of windows. See my implementation below:
- Murali Mohan June 12, 2013