## Manhattan associates Interview Question for SDE-2s

Country: India

Comment hidden because of low score. Click to expand.
1
of 1 vote

There are a couple of key points here:
1. Two equivalent binary strings are still equivalent no matter which column you remove.
2. There is no way to choose a column from n binary strings of m bits such that two or more members of N become equivalent unless m > n or unless N already has duplicates in it (see point #1).

Coded solution below...

``````function dups(array) {
"use strict"
hashmap = {}
for (i = 0; i < array.length; i++)
if (!hashmap[array[i]])
hashmap[array[i]] = true
else
return true

var hashmap
, array
, i

return false
}
function manhattan() {
"use strict"
args = Array.prototype.slice.call(arguments)
tests = args.shift()
no = 0
while (tests--) {
no++
rows = args.shift()
cols = args.shift()
if (rows > cols) {
console.log('test ' + no + ': NO')
continue
}
array = []
for (i = 0; i < rows; i++) {
array.push(args.shift())
}
if (dups(array)) {
console.log('test ' + no + ': NO')
continue
}
console.log('test ' + no + ': YES')
}

var args
, tests
, rows
, cols
, array
, no
, i
}

//ex
manhattan(4
// test1
, 3, 3
, 5, 0, 4 /* 0b101, 0b000, 0b100 */

// test2
, 2, 2
, 3, 3 /* 0b11, 0b11 */

// test3
, 4, 3
, 5, 0, 4, 7 /* 0b101, 0b000, 0b100, 0b111 */

// test4
, 3, 3
, 5, 5, 4 /* 0b101, 0b101, 0b100 */
)

/*
! node manhattan.js
test 1: YES
test 2: NO
test 3: NO
test 4: NO
!
*/``````

Comment hidden because of low score. Click to expand.
0

Maybe I misunderstood the algorithm you proposed, but don't you need to also check for duplicates even if n > m?

Comment hidden because of low score. Click to expand.
0

I think the algorithm needs to be if n > m-1.

i.e., 5 unique 3 bit elements can't be reduced to 5 unique 2 bit elements because 2bits can only describe 4 unique elements.

Comment hidden because of low score. Click to expand.
0

n > (m-1)^2

Comment hidden because of low score. Click to expand.
0

For the input below, the answer is YES?
000
101
011
100

Comment hidden because of low score. Click to expand.
0

Yes. Remove 2nd column.

00
11
01
10

Each row is unique after removing 2nd column.

Comment hidden because of low score. Click to expand.
1
of 1 vote

Updated answer a sort of brute force-ish O(n*m) solution. Use bit masks to "remove" the column (zero it out) if their is no bit mask that can generate n unique values then the answer is no.

Note that bit operations are pretty inefficient in Javascript since the language supports no integers, but whatever.

``````function manhattan_ii() {

"use strict"
args = Array.prototype.slice.call(arguments)
args = args.reverse()
tests = args.pop()
while (tests) {
rows = args.pop()
cols = args.pop()
bits = ""
for (i = 0; i < cols; ++i) {
bits += "1"
}
for (i = 0; i < bits.length; ++i) {
}
samples = []
for (i = 0; i < rows; ++i) {
samples.push(parseInt(args.pop(), 2))
}
bool = false
for (i = 0; i < masks.length; ++i) {
hash = {}
for (j = 0; j < samples.length; ++j) {
if (hash[n]) {
break
} else {
hash[n] = true
}
}
if (j === samples.length) {
bool = true
break;
}
}
console.log("Test #" + tests + " : " + (bool ? "YES" : "NO"))
tests--
}
var args
, tests
, rows
, cols
, bits
, i
, samples
, j
, bool
, hash
,n
}
manhattan_ii(2,3,3,"101", "000", "100", 2, 2, "11", "11")
manhattan_ii(1, 4, 3, "011", "101", "111", "100")
manhattan_ii(1, 4, 3, "110", "101", "111", "100")
manhattan_ii(1, 5, 3, "110", "110", "101", "111", "100")
manhattan_ii(1, 2, 2, "11", "10")

/* output...

! node manhattan-ii.js
[ 3, 5, 6 ]
Test #2 : YES
[ 1, 2 ]
Test #1 : NO
[ 3, 5, 6 ]
Test #1 : NO
[ 3, 5, 6 ]
Test #1 : YES
[ 3, 5, 6 ]
Test #1 : NO
[ 1, 2 ]
Test #1 : YES
!
*/``````

Comment hidden because of low score. Click to expand.
1
of 1 vote

fyi it's also printing out the values of the bit masks that it determines in order to mask to the columns for testing

Comment hidden because of low score. Click to expand.
1
of 1 vote

The answer is to check if all these rows are unique. If they are unique, just return true. If they are not, just return false. Because if two of the rows are the same, no matter how many columns you remove, they are still the same. If they are originally unique, no matter how many columns you remove, they are still unique.

Comment hidden because of low score. Click to expand.
0

Comment hidden because of low score. Click to expand.
0

Could you please explain your answer in this case 101, 000, 111.. In this case, all the rows are unique. Once you delete column 1, the row is no longer unique.

Comment hidden because of low score. Click to expand.
0

Won't work for this:

001
010
011
100
101
110
111

These are all unique to start with, but if you remove the first column, 001 and 101 will be identical; if you remove the second one, 001 and 011 will be identical; and if you remove the third one, 010 and 011 will be identical.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Can You please tell me , how in the first case , that the answer is YES???

Is it like after removing the second column , the rows are 11 , 00 and 11 ?

Comment hidden because of low score. Click to expand.
1
of 1 vote

After removing the second column, the rows will be 11 , 00 and 10

Comment hidden because of low score. Click to expand.
0
of 0 vote

Assuming you have input from text file (say input.txt), below is a solution in Java.

``````import java.io.BufferedReader;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

class Solution {
public static void main(String[] args) {
try {
} catch (FileNotFoundException e) {
return;
}

try {
for (int i = 0; i < tests; i++) {
}
} catch (IOException e) {
} finally {
try {
} catch (IOException e) {
}
}
}

int n = Integer.parseInt(tokens[0]);
int m = Integer.parseInt(tokens[1]);

List<String> tmpList = new ArrayList<String>(n);
for (int i = 0; i < n; i++) {
}

int columnRemoveIndex = 0;
Set<String> tmpSet = new HashSet<String>(n);
while (columnRemoveIndex < m) {
tmpSet.clear();
boolean canRemove = true;
for (String s : tmpList) {
StringBuilder tmpBuilder = new StringBuilder(s);
canRemove = false;
break;
}
}
if (canRemove) {
System.out.println("Yes");
return;
}
columnRemoveIndex++;
}
System.out.println("No");
}
}``````

Comment hidden because of low score. Click to expand.
0
of 0 vote

1) Count # of1 in each row let represent it by count(i) for row i
2) If there are 2 rows exists for which count(i) - count(j) >= 2 then ans is "no" (it meas count for each row should be either x or x+1 where x is min( count(i) where 1<=i <=m)
3) Now create a column and set 0 for each row for which count(i) =x and set 1 for which count(i) = x+1
4) now search created column in matrix. If matrix has no such column then ans = "NO"
5) else if matrix has such column then remove column from matrix and check all columns of matrix IF all columns are same then ans ="yes" else ans = "NO"

Comment hidden because of low score. Click to expand.
0

You can not solve this just by counting 1s. The placement of 1s and 0s are important as well. Your algorithm give the wrong answer of NO for the first sample in the question.

Comment hidden because of low score. Click to expand.
0
of 0 vote

The following algorithm is O(n*m^2):

- Create Flag array with the length of m. This array keep track of the column we can remove without creating similar rows.
- Set all elements of Flag to true.

- Compare every two rows:
If the are completely similar, return NO // not possible
else if they differ in one element, set the Flag of that column to false // We can not remove this column.

- If Flag has a true value, return YES
else return NO.

Here is the code, I skipped the part to read from file, and assume the data is in a n*m int[][] matrix:

``````public boolean canRemoveCol(int[][] matrix) {
int n = matrix.length;
int m = matrix[0].length;

boolean[] flag = new boolean[m];
Arrays.fill(flag, 0, m);
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
int c = -1; // c keeps track of number of different
for (int k = 0; k < m; k++) {
if (matrix[i][k] != matrix[j][k]) {
if (c != -1) { // more than one different
c = -2;
break;
} else {
c = k; // first different between the two rows
}
}
}

if (c == -1) return false; // Found no difference between the two rows, so not possible.
if (c > -1) flag[c] = false; // Found only one difference.
}
}

for (int i = 0; i < m; i++) {
if (flag[i]) return true; // We can remove this column.
}

return false;
}``````

Comment hidden because of low score. Click to expand.
0

It can be improved to O(n*m*log m) if we use bit manipulation and broke each line to several (less than 30) integers. This way the internal loop of O(m) is replaced with O(log m). But the code gets more complicated.

Comment hidden because of low score. Click to expand.
0
of 0 vote

First off, since each row is an m length list of binary digits, let's treat the rows as binary numbers. Take O(n) time to gather a list of n integers where the i-th integer represents the i-th row.

Next set the variable 'answer' to the value 2^(m+ 1) -1 (the number represented by m consecutive binary 1s). As we discover that the j-th column is not a candidate for removal, we'll change the j-th binary digit to 0.

Next note that there are a bunch of handy one-liners to tell if a number is a power of 2 in constant time, so that operation can be used freely. You can google it.

Now IF AND ONLY IF any two rows differ by only a singe binary digit (one row has a 0, the other has a 1) then that column for that digit is NOT a candidate for removal. Two rows differ only by the kth binary digit if the absolute value of the difference between their respective integer representations is exactly 2^k.

So now for each of the integers in our list, we find the absolute value of their difference d. If d is a power of 2 then the [k = log_2(d)]-th column is not a candidate. We mark the k-th digit in 'answer' to 0 by doing 'answer' = 'answer' & (~d). Check the difference between all of the rows.

Finding the difference between all of the rows takes time (n - 1) + (n - 2) + … + 1. This is equal to (n * (n - 1)) / 2 = (n^2 - n) / 2. Our runtime is thus O(n^2).

At the end of the day, we just check to see if 'answer' == 0. If so, no columns are candidates and we output NO. Otherwise ('answer' > 0) we output YES. Also, happy bonus info, the 1s in the binary form of 'answer' tell us which columns remain as deletion options.

Comment hidden because of low score. Click to expand.
0
of 0 vote

Check if all the rows are unique, if not return NO (why ? Coz if two rows are not unique then removing elements in it will not make it unique)

If so then, iterate over rows find the columns which are same at each step finally remove one column from it (if more than 1 present)
Eg:
1 0 0
1 0 1
1 1 1
After 1st iteration (1 == 1, 0 == 0, 0 == 0)
1 0 0
After 2nd iteration (1 == 1, 0 == 0, 0 == 1)
1 0 -
After 3rd (nth) iteration (1 == 1, 0 == 1)
1 - -

Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

### Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

### Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.