Anon
BAN USER- 0of 0 votes
AnswerWas asked to implement a code profiler, which takes a piece of code and provides the run time of a particular function in the code .
- Anon in United States
If a function is internally calling other functions, we just want to see the time spent executing the original function, and not the overall time.| Report Duplicate | Flag | PURGE
Microsoft
This is a recursion question where you go from right to left building up and returning count.
static int count(int[]arr){
if(arr.length == 0) return 0;
return getCnt(arr, arr.length -1);
}
static int getCnt(int[]arr, int ind){
if(ind < 0) return 0;
if(ind == arr.length-1){
if(arr[ind] > 0){
return 1+getCnt(arr, ind-1);
}else{
return getCnt(arr, ind-1);
}
}
if(arr[ind] > 0 && arr[ind]*10 + arr[ind+1] <= 26)
return 1+getCnt(arr, ind-1);
return getCnt(arr, ind-1);
}
Approach:
Dynamic Programming solution:
we can paint the ith house with blue, red or green.
so we have the following equations:
cost[i,r] = min( cost[i-1,b], cost[i-1,g] ) + cost of painting i with r.
cost[i,g] = min( cost[i-1,b], cost[i-1,r] ) + cost of painting i with g.
cost[i,b] = min( cost[i-1,r], cost[i-1,g] ) + cost of painting i with b.
Final Min Cost = min (cost[n,b], cost[n,r], cost[n,g]);
I'm surprised, that this is a phone interview question.
1. Traverse the tree in Pre-Order form, push each node into a List.
2. For missing nodes, push null into the list.
public static List<Integer> getList(Tree root){
List<Integer> res = new ArrayList<>();
if(root == null) return res;
preOrder(root, res);
return res;
}
public static void preOrder(Tree root, List<Integer> res){
if(root == null){
res.add(null);
return;
}
res.add(root.data);
preOrder(root.left, res);
preOrder(root.right, res);
}
Then re-construct, the Tree back from the List.
public static Tree getTree(List<Integer> res){
Tree t = getTreeHelp(res);
return t;
}
private static Tree getTreeHelp(List<Integer> res){
if(res.size() == 0) return null;
Integer key = res.remove(0);
if(key == null) return null;
Tree root = new Tree(key);
root.left = getTreeHelp(res);
root.right = getTreeHelp(res);
return root;
}
static class Node{
int data;
Node next;
Node(int d){
data = d;
}
}
public static Node insert(Node n, int d){
if(n == null)
return new Node(d);
Node p = n;
if(p.data > d ){
while(p.data < p.next.data){
p = p.next;
}
Node l = p.next;
Node t = new Node(d);
p.next = t;
t.next = l;
p = p.next;
return p;
}else{
Node c = p;
while(p.data < p.next.data && p.data < d){
c = p;
p = p.next;
}
if(d < p.data){
Node t = new Node(d);
c.next = t;
t.next = p;
}else{
Node t = new Node(d);
Node l = p.next;
p.next = t;
t.next = l;
}
return n;
}
}
1. Use a hashmap to store the Character Count.
2. Then iterate through the char array again, and keep track of the last character used.
3. Remove the entries from hashmap when the count becomes 0.
public static int getJob(char[] arr, int k){
if(arr.length == 0){
return 0;
}
HashMap<Character, Integer> map = new HashMap<>();
for(int i=0; i<arr.length; i++){
if(map.containsKey(arr[i]))
map.put(arr[i], map.get(arr[i])+ 1);
else
map.put(arr[i], 1);
}
int res = 0;
char l = ' ';
int i = 0;
while(!map.isEmpty()){
if(i == arr.length){
i = 0;
}
if(arr[i] == ' '){
i++;
continue;
}
else if(arr[i] != l){
res +=1;
map.put(arr[i], map.get(arr[i])-1);
if(map.get(arr[i]) == 0){
map.remove(arr[i]);
}
l = arr[i];
arr[i] = ' ';
i++;
}
else if(map.size() == 1){
int val = map.get(arr[i]);
res += val * k + val;
map.remove(arr[i]);
i++;
}else
i++;
}
return res;
}
public static void main(String[] args){
char[] arr1 = {'A','A','A','B','B','B','C','C','C'};
char[] arr2 = {'A','A','A','B','C'};
System.out.println(getJob(arr1, 3));
System.out.println(getJob(arr2, 2));
}
This can be solved with Dynamic Programming.
Also remember if n - m == 1 i.e. if number of 0s is one less than that number of 1s the result is always 1.
public static int DP(int m, int n){
if(m == 0 && n == 0) return 1;
if(m == n-1) return 1;
int[][]T = new int[m+1][n+1];
for(int i = 0; i<T.length; i++){
T[i][0] = 1;
}
//T[0][1] = 1;
for(int i = 0; i < T.length; i++){
for(int j = 1; j< T[i].length; j++){
if(j == i+1){
T[i][j] = 1;
}
else if( j > i+1) break;
else if(j == i){
T[i][j] = T[i-1][j]+T[i-1][j-1];
}else{
T[i][j] = T[i][j-1]+T[i-1][j];
}
}
}
return T[m][n];
}
Time Complexity : O(M x N)
Space Complexity: O(M x N)
I explained that, I would have the compiler put in messages onto a file, whenever a particular function is executed and when returning from that function. The format will be like below:
<TimeStamp> <Action(Start/End)> <FunctionName>
Then I'll use a stack to push function names into the stack for every action "Start" and pop out of the stack for every action "End". Keeping track of the time, along the way.
Where-in I would keep checking if the function I want to analyse is at the head of the stack.
public static int getTime(String log, String fun){
if(log == null || log.length() == 0){
return -1;
}
Deque<String> stack = new LinkedList<>();
String[] arr = log.split("\n");
int currTime = 0;
int lastTime = 0;
for(String str: arr){
String[] st = str.split(" ");
int time = getTime(st[0]);
if(st[1].equals("start"))
{
if(st[2].equals(fun)){
lastTime = time;
}
if(!st[2].equals(fun)){
if(stack.peek().equals(fun)){
currTime += time - lastTime;
}
}
stack.push(st[2]);
}
else if(st[1].equals("end")){
String t = stack.pop();
if(t.equals(fun)){
currTime = currTime + time - lastTime;
// return currTime;
}
else{
if(stack.peek().equals(fun)){
lastTime = time;
}
}
}
}
return currTime;
}
public static int getTime(String str){
return Integer.parseInt(str);
}
public static void main(String[] args){
StringBuilder str = new StringBuilder();
str.append("10 start fun\n");
str.append("20 start f1\n");
str.append("22 end f1\n");
str.append("30 start f2\n");
str.append("31 start f3\n");
str.append("32 end f3\n");
str.append("33 end f2\n");
str.append("70 end fun\n");
System.out.println(getTime(str.toString(), "fun"));
}
The answer is the length of the largest sliding window possible, with 'K' zeros.
You also need to handle the case, where number of 1s outside the window should be greater or equal to 'K'.
public static int getMaxLen(int[] arr, int k){
int wL = 0, wR = 0;
int n = 0;
int maxLen = 0;
int maxWL = 0, maxWR = 0;
if(arr[wR] == 0) n =1;
while(wR < arr.length-1){
if(n <= k){
wR++;
if(arr[wR] == 0) n++;
}
if(n > k){
if(arr[wL] == 0) n--;
wL++;
}
if((wR - wL) > maxLen){
maxLen = wR - wL;
maxWL = wL;
maxWR = wR;
}
}
int oneC = 0;
for(int i = 0; i<maxWL; i++){
if(arr[i] == 1) oneC++;
}
for(int i = maxWR+1; i<arr.length; i++){
if(arr[i] == 1) oneC++;
}
if(oneC >= k)
return maxLen;
else{
return (maxLen - oneC);
}
}
public static void main(String[] args){
int[] arr= {0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0};
System.out.println(getMaxLen(arr, 3));
}
As the array is sorted :
1. Iterate through all the rows.
2. For each row, start from the last column, until you hit a 0 element.
3. Keep track of the 1 count for each row in a HashMap, and also keep track of the max 1 count seen so far.
4. Iterate through the HashMap and print all the rows (keys) with the value as the max count of 1.
public static List<List<Integer>> getAnswer(int[][] arr){
int maxCount = 0;
int colLength = arr[0].length -1;
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < arr.length; i++){
int j = arr[i].length-1;
while(arr[i][j] != 0){
j--;
}
int currL = colLength - j;
map.put(i, currL);
if(maxCount < currL ){
maxCount = currL;
}
}
List<List<Integer>> res = new ArrayList<>();
for(Map.Entry<Integer, Integer> e: map.entrySet()){
if(e.getValue() == maxCount){
List<Integer> t = new ArrayList<>();
t.add(e.getKey()+1);
t.add(maxCount);
res.add(t);
}
}
return res;
}
public static void main(String[] args){
int[][] arr = {{0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,1,1,1,1,1,1,1,1},
{0,0,0,0,0,0,1,1,1,1,1,1},
{0,0,0,0,0,0,0,0,0,1,1,1},
{0,0,0,0,0,0,0,1,1,1,1,1},
{0,0,0,0,1,1,1,1,1,1,1,1}};
System.out.println(getAnswer(arr));
}
It's just a K way partition problem, where you don't have to sort the array in reverse order, since the problem states, that the array is already sorted.
A greedy algorithm, works just fine.
public static List<List<Integer>> arraySplit(int[] arr, int k){
List<List<Integer>> res = new ArrayList<>();
int i = 0;
for(i=arr.length-1; i>=(arr.length - k); i--){
List<Integer> temp = new ArrayList<>();
temp.add(arr[i]);
res.add(temp);
}
//int c = 0;
while(i>=0){
int c = getListIndexWithMinSum(res);
res.get(c).add(arr[i]);
i--;
}
return res;
}
private static int getListIndexWithMinSum(List<List<Integer>> arr){
int minIndex = 0;
int minSum = Integer.MAX_VALUE;
int i = 0;
for(List<Integer> l:arr ){
int currSum = sum(l);
if(minSum > currSum){
minSum = currSum;
minIndex = i;
}
i++;
}
return minIndex;
}
private static int sum(List<Integer> arr){
int sum = 0;
for(int n: arr){
sum += n;
}
return sum;
}
public static void main(String[] args){
int[] arr = {1, 3, 6, 9, 10};
List<List<Integer>> res = arraySplit(arr, 2);
for(List<Integer> l: res){
System.out.println(l);
}
}
- Anon April 03, 2017public static List<List<Integer>> arraySplit(int[] arr, int k){
List<List<Integer>> res = new ArrayList<>();
int i = 0;
for(i=arr.length-1; i>=(arr.length - k); i--){
List<Integer> temp = new ArrayList<>();
temp.add(arr[i]);
res.add(temp);
}
//int c = 0;
while(i>=0){
int c = getListIndexWithMinSum(res);
res.get(c).add(arr[i]);
i--;
}
return res;
}
private static int getListIndexWithMinSum(List<List<Integer>> arr){
int minIndex = 0;
int minSum = Integer.MAX_VALUE;
int i = 0;
for(List<Integer> l:arr ){
int currSum = sum(l);
if(minSum > currSum){
minSum = currSum;
minIndex = i;
}
i++;
}
return minIndex;
}
private static int sum(List<Integer> arr){
int sum = 0;
for(int n: arr){
sum += n;
}
return sum;
}
public static void main(String[] args){
int[] arr = {1, 3, 6, 9, 10};
List<List<Integer>> res = arraySplit(arr, 2);
for(List<Integer> l: res){
System.out.println(l);
}
}
- Anon April 03, 2017public static int getPivot(int[] arr){
int l = 0, r = arr.length -1;
int piv = l+(r - l)/2;
int lSum = 0;
int rSum = 0;
for(int i= 0; i<piv;i++){
lSum += arr[i];
}
for(int j=piv; j<arr.length; j++){
rSum += arr[j];
}
while(piv > 0 && piv < r){
if(lSum == rSum){
return piv;
}
else if(lSum > rSum){
rSum+=arr[piv -1];
lSum-=arr[piv-1];
piv -= 1;
}
else{
rSum-=arr[piv+1];
lSum+=arr[piv+1];
piv += 1;
}
}
return -1;
}
- Anon March 22, 2017Seems like a very easy problem, for an in-person interview.
Unless I'm missing something.
public static int[] getCnt(){
Scanner in = new Scanner(System.in)
int[] res = new int[10];
for(in.hasNextInt()){
int t = in.nextInt();
if(t >= 0 && t <= 9){
res[t] += 1;
}
else{
throw new IllegalArgumentException("Please enter a number between 0-9");
}
}
return res;
}
- Anon March 21, 2017Use a hashset to keep track of unique nodes. While traversing the tree.
public static int getDisCnt(Tree root){
Set<String> uniq = new HashSet<>();
if(root == null){
return 0;
}
return getMaxHelper(root, uniq);
}
private static int getMaxHelper(Tree root, Set<String> uniq){
if(root == null){
return uniq.size();
}
int l = 0;
int r = 0;
if(uniq.add(root.data)){
l = getMaxHelper(root.left, uniq);
r = getMaxHelper(root.right, uniq);
uniq.remove(uniq.size()-1);
}
else{
l = getMaxHelper(root.left, uniq);
r = getMaxHelper(root.right, uniq);
}
return Math.max(l, r);
}
- Anon March 20, 2017
Dynamic Programming solution:
- Anon May 20, 2017