dora
BAN USER- 0of 0 votes
AnswersGiven a large MxN matrix of 1s and 0s like this:
1 1 0 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 0 1 0 ...
Calculate the number of 1s in a given subset PxQ matrix. In effect, write a function:
int ones(int startx, int starty, int len, int width);
Looking for something better than O(n^2).
- dora in United States| Report Duplicate | Flag | PURGE
Google
public int rearrange(List<Character> tasks, int k) {
if (tasks.size() == 1) return 1;
HashMap<Character, Integer> hm = new HashMap<>();
for (Character c: tasks) {
if (hm.contains(c)) hm.put(c, hm.get(c) + 1);
else (hm.add (c, 1));
}
// Sort tasks by frequency
ArrayList<Map.Entry> sortedTasks = Collections.sort(hm.entrySet().toArray(), (p1, p2) -> p1.value > p2.value);
// Add all tasks except the first, S
int sum = 0;
for (int i = 1; i < sortedTasks.size(); i++) {
sum += sortedTasks.get(i).value;
}
// If X is #of tasks of highest frequency, the formula for total duration is
// X + (X-1)k - S
return ((sortedTasks.get(0).value - 1) * k) - sum + sortedTasks.get(0).value;
}
Right. The question can be interpreted in many ways, so something to discuss with the interviewer.
I assumed the subset would be of consecutive elements. My solution is a O(n) way of finding K consecutive elements.
If the ask is "max of any k numbers", then using a min heap (klogn + n) is the most optimal way.
public int sumK(int[] list, int k) {
if (k > list.length) return ERROR;
int sum = 0, maxSum = 0, l = 0;
for (int i = 0; i < k; i++) {
sum += list[i];
}
maxSum = sum;
for (int j = k; j < list.length; j++, l++) {
sum = sum + list[j] - list[l];
if (sum > maxSum) maxSum = sum;
}
return maxSum;
}
public List<Node> interleave(List<Node> list) {
if (list == null) return null;
// find center of the list
Node center = findCenter(list);
// reverse the second half
Node reversed = reverse(center.next);
center.next = null;
// interleave
Node fTemp = list, nfTemp = list.next, rTemp = reversed, nrTemp;
while (fTemp != null || rTemp != null) {
nfTemp = fTemp.next;
rfTemp = rTemp.next
fTemp.next = rTemp;
rTemp.next = nfTemp;
rTemp = nrTemp;
fTemp = nfTemp;
}
return list;
}
private List<Node> findCenter(List<Node> list) {
if (list == null) return null;
Node n = list;
Node 2n = n.next;
while (2n != null && 2n.next != null) {
n = n.next;
2n = 2n.next.next;
}
return n;
}
private List<Node> reverse(List<Node> list) {
if (list == null) return null;
Node first = list, second = first.next, third;
first.next = null;
while (second != null) {
second.next = first;
first = second;
second = third;
third = (second != null) ? second.next : null;
}
return first;
}
public Pair<String, String> decode(String input){
if (TextUtils.isEmpty(input)) return "";
StringBuilder sb = new StringBuilder();
int num = 1;
StringBuilder accumulator = new StringBuilder();
for (int i = 0; i < input.length(); i++) {
Character c = input.charAt(i));
if (c.isDigit()) {
for (int j = 0; j < num; j++) { // add chars found so far
sb.append(accumulator.toString());
accumulator.delete(0, accumulator.length());
}
num = Integer.valueOf(c);
continue;
} else if (c.isLetter()) {
accumulator.append(c);
continue;
} else if (c == '[') {
Pair<String, String> p = decode(input.substring(i+1, input.length())));
i += p.first().length();
accumulator.append(s);
} else if (c == ']') {
for (int j = 0; j < num; j++) {
sb.append(accumulator.toString());
}
return new Pair (input.substring(0, i), sb.toString());
}
}
sb.append(accumulator.toString());
return new Pair(input, sb.toString());
}
public String matchingString(String input, String alphabet) {
if (TextUtil.isEmpty(input) || TextUtil.isEmpty(alphabet)) return “”;
HashSet<String> hs = new HashSet<>();
for (int i = 0; i < input.length(); i++) {
if (hs.contains(input.charAt(i))) {
hs = new HashSet<>();
}
hs.add(input.charAt(i));
if (hm.size() == alphabet.length()) {
return input.substring(i - alphabet.length(), alphabet.length());
}
}
}
Its quite irksome when companies ask questions like these.. writing clumsy for loops prove nothing about ones knowledge of algorithms or coding. And in real life if you ever encounter a problem like this, one can always re-frame the problem and solve it in a much better way.
- dora January 07, 2017Isn't the following an O(n) solution? It requires O(n) space though.
public int lcString(String a, String b) {
Map<Character, Integer> map = new HashMap<>();
// Store a in the map
for (int i = 0; i < a.length; i++) {
map.add(a.charAt(i), i);
}
// for each character in b, see if it is occurring linearly in the map
int lcs = 0, currLcs = 0;
Integer oldLocation = -1, newLocation = -1;
for (int i = 0; i < b.length; i++) {
newLocation = map.get(b.charAt(i));
if ((newLocation != null) && (newLocation == oldLocation+1)) // increasing
currLcs++;
else {
if (lcs < currLcs)
lcs = currLcs;
currLcs = 0;
}
oldLocation = newLocation;
}
// currLcs will be greater than lcs if the common string
// ends at the termination of both strings
return (currLcs > lcs) ? currLcs : lcs;
}
public List<String> palindromicPermutations(String s) {
if (TextUtils.isEmpty(s)) return null;
HashMap<String, Integer> hm = new HashMap<>();
int numOdds = 0;
for (int i = 0; i < s.length; i++) {
if (hm.containsKey(s.charAt(i))
hm.put(s.charAt(i), hm.get(s.charAt(i) + 1));
else hm.put(s.charAt(i), 1);
}
StringBuilder sb = new StringBuilder();
String single = null;
// Permutable if all chars are even (1 odd is ok)
for (Entry e: hm.entrySet()) {
int value = e.value;
if (value % 2) {
numOdds++;
single = e.key;
}
if (numOdds > 1) return null;
// Build the half key set
for (int j = 0; j <= value/2; j++) sb.append(e.key);
}
return buildPermutations(sb.toString(), single);
}
private List<String> buildPermutations(String half, String single) {
List<String> perms = new ArrayList<String>();
permutations("", half, perms);
for (String s: perms) {
s = s + single + s.reverse();
}
return perms;
}
private void permutations(String prefix, String half, List<String> op) {
int n = half.length();
if (n == 0) op.add(prefix);
else {
for (int i = 0; i < n; i++)
permutation(prefix + str.charAt(i), str.substring(0, i) + str.substring(i+1, n), perms);
}
}
Sort the input values based on time. Walk down this array one by one, noting the number of logins and logouts.
Storage is O(n) and runtime is O(nlogn), n = number of login/out values
class InputValue {
String name;
double login;
double logout;
}
class Type implements Comparable {
boolean loggedin;
double time;
int compareTo(Type that) {
return this.time - that.time
}
}
class ReturnValue {
double time;
int numLoggedIn;
}
public List<ReturnValue> findLoggedIn(List<InputValue> list) {
List<Type> loggedIn = new ArrayList<Type>();
List<ReturnValue> retValue = new ArrayList<ReturnValue>();
int loggedInNow = 0
for (InputValue iv: list) {
loggedIn.add(iv.login, true);
loggedIn.add(iv.logout, false);
}
Collections.sort(loggedIn);
for(Type t: loggedIn) {
if (t.loggedin == true)
loggedInNow++;
else loggedInNow--;
retValue.add(t.time, loggedInNow);
}
return retValue;
}
public List<Integer> unique(List<Integer> arr) {
if (arr == null || arr.size == 0) return arr;
Set<Integer> hs = new HashSet<>();
for (int i = 0; i < arr.size; i++) {
if (!hs.contains(arr.get(i))) hs.put(arr.get(i))
}
return new ArrayList<Integer>(hs);
}
public List<Integer> unique(List<Integer> arr) {
if (arr == null || arr.size == 0) return arr;
List<Integer> ret = new ArrayList<>();
ret.add(arr.get(0));
Integer curr = ret.get(0);
for(Integer i : arr) {
if (i != null && i != curr) {
ret.add(i);
curr = i;
}
}
return ret;
}
An obvious solution is sorting the elements and compare yielding O(nlogn) complexity. I tried to do it in O(n), but it takes O(m) space where m = end time - start time of all cals. The algo is simple - add all units of intervals to a map with it's id. Then walk down this map and collect all entries that have more than 1 cal.
- dora March 25, 2018