CareerCup

# There's a room with a TV and people are coming in and out to watch it. The TV is on only when there's at least a person in the room.
# For each person that comes in, we record the start and end time. We want to know for how long the TV has been on. In other words:
# Given a list of arrays of time intervals, write a function that calculates the total amount of time covered by the intervals.
# For example:

# input = [(1,4), (2,3)]
# > 3
# input = [(4,6), (1,2)]
# > 3
# input = {{1,4}, {6,8}, {2,4}, {7,9}, {10, 15}}
# > 11

I recently had a take home assignment for a optimization engineer position at FB. I got 24 hours to finish it however it was suggested to finish under 90 minutes. The problem was to calculate the dot product of sparse matrix (optimize for speed). I wrote following code but got dinged. Not sure what's wrong to not clear even first stage!

#include <iostream>
#include <string>
#include <map>
#include <sstream>
using namespace std;
class SparseVector{
private:
    map<int, double> m_map;
    int m_size;
public:
    SparseVector(int size){
        this->m_size = size;
        this->m_map =  *new map<int, double>();
    }
    void setValue(int i, double value){
        if( i < 0 || i > m_size)
            return;
        if(value == 0.0){
            map<int, double>::iterator it = m_map.find(i);
            if(it != m_map.end())
                m_map.erase(it);
        }
        else
            m_map[i] = value;
    }
    double getValue(int i){
        if( i < 0 || i > m_size)
            return 0.0;
        else {
            map<int, double>::iterator it = m_map.find(i);
            if(it != m_map.end())
                return it->second;
            else
                return 0.0;
        }
    }
    int getSize(){
        return m_size;
    }
    
    static double s_dotProduct(SparseVector a, SparseVector b){
        if (a.m_size != b.m_size)
            return 0.0;
        
        double sum = 0.0;
        if (a.m_map.size() <= b.m_map.size())
        {
            for (map<int, double>::iterator it = a.m_map.begin() ; it != a.m_map.end(); it++)
                if ((b.m_map.find(it->first)) != b.m_map.end())
                    sum += a.getValue(it->first) * b.getValue(it->first);
        }
        else
        {
            for (map<int, double>::iterator it = b.m_map.begin() ; it != b.m_map.end(); it++)
                if ((a.m_map.find(it->first)) != a.m_map.end())
                    sum += a.getValue(it->first) * b.getValue(it->first);
        }
        return sum;
    }
    template <typename T>
    static string s_ToString(T val)
    {
        stringstream stream;
        stream << val;
        return stream.str();
    }
    static string s_printSparseVector(SparseVector a)
    {
        string s = "";
        for (map<int, double>::iterator it =  a.m_map.begin(); it!= a.m_map.end(); it++)
            s += "(" +  s_ToString(it->first) + ", " + s_ToString(it->second) + ") ";
        return s;
    }
};

int main(int argc, char *argv[]){
     int lenA = 0, lenB = 0, setValA = 0, setValB = 0;
     cout << "Enter length for Sparse vector A : " << endl;
     cin>> lenA;
     cout << "Enter length for Sparse vector B : " << endl;
     cin>> lenB;
     
     SparseVector v1 = SparseVector(lenA);
     SparseVector v2 = SparseVector(lenB);
     double y; int x;
     
     cout << "Enter number of set values for Sparse vector A : " << endl;
     cin >> setValA;
     cout << "Enter the set Index, Value pair in separate lines" << endl;
     for(int i = 0; i < setValA; i++){
     cin >> x;
     cin >> y;
     v1.setValue(x, y);
     }
     
     cout << "Enter number of set values for Sparse vector B : " << endl;
     cin >> setValB;
     cout << "Enter the set Index, Value pair in separate lines" << endl;
     for(int j = 0; j < setValB; j++){
     cin >> x;
     cin >> y;
     v2.setValue(x, y);
     }
cout <<"Sparse Vector1 = " << SparseVector::s_printSparseVector(vectorA) << endl ;
     cout <<"Sparse Vector2 = " << SparseVector::s_printSparseVector(vectorB) << endl;
     cout <<"Dot product of two sparse vectors is  = " <<  SparseVector::s_dotProduct(vectorA, vectorB) << endl;
     return 0;
}

You are given a series of moves as a string, such as ">^V<^". You need to output a list with all the series of moves that represent a loop if they were made by a robot for example.

A loop is defined as a series of moves that lead to the same position, for example "><" or "^V".

In the case of "^>V<^" the output should be ["^>V<", "^>V<"], essentially the last move generates a new loop because it leads to a position that was visited before and that naturally can be followed up to the same position and describe a loop.

Giving a string and an string dictionary, find the longest string in dictionary which can formed by deleting some characters of the giving string.
eg:S = abpcplea, Dict = {ale, apple, monkey, plea}, the return "apple"

I was thinking of the following approach,

Build a Trie for all words in the Dict - O( n * k) where k is the longest string in the dict
For each character c, in S check if there is a word in Trie that starts with it and has the letters that appear in S after c. We can short circuit based on remaining characters and the length of longest string found so far.
This should take O( N * k) where N is length of S.

Find all comments in the Java (it could be Python or any other language of your choice) codes that’s parsed in as a string.
You may assume the codes given is valid.

Input is a single string, e.g.
String codes =
“/* file created by aonecode.com\\n” +
“ welcome to the tech blog*/ \\n” +
“//main method\\n” +
“public static void main(String[] args) { \\n“ +
“ System.out.println(“//welcome”); //output\\n” +
“}”


Output is a list of strings

List<String> ret =
[
“ file created by anecode.com\n welcome to the tech blog”,
“main method”,
“output”
]

Q: If you were given a series of equations e.g. [A = B, B = D, C = D, F = G, E = H, H = C]
and then another series [A != C, D != H, ..., F != A ]

Check whether the equations combined is valid.

For the example given, your program should return 'invalid', because the first series implies that A = C, which contradicts the statement A != C in the second series.

Given an input string "aabbccba", find the shortest substring from the alphabet "abc".

In the above example, there are these substrings "aabbc", "aabbcc", "ccba" and "cba". However the shortest substring that contains all the characters in the alphabet is "cba", so "cba" must be the output.

Output doesnt need to maintain the ordering as in the alphabet.

Other examples:
input = "abbcac", alphabet="abc" Output : shortest substring = "bca".

Given an array of integers, design an algorithm that moves all non-zero integers to the end of the array. Minimize the number of writes or swaps.

Write code to decode strings. For example, String str = "3[a2[bd]g4[ef]h]", the output should be "abdbdgefefefefhabdbdgefefefefhabdbdgefefefefh".

My solution is as follows.

public class StringDecoder {
	
	public static void main(String[] args){
		
		String s = "3[a2[bd]g4[ef]h]";
		
		System.out.println(decode(s));
		
	}
	
	public static String decode(String s){
		
		if(s == null || s.length()==0) return s;
		
		int indexOfFirstNumber = findIndexOfFirstNumber(s);
		int indexOfFirstBracket = findIndexOfFirstBracket(s);
		int indexOfClosingBracket = findIndexOfClosingBracket(s, indexOfFirstBracket);
		
		if(indexOfFirstNumber == -1) return s;
		
		String subStr1 = s.substring(0, indexOfFirstNumber);
		String subStr2 = decode(s.substring(indexOfFirstBracket+1, indexOfClosingBracket));
		String subStr3 = decode(s.substring(indexOfClosingBracket+1, s.length()));
		
		int duplicates = Integer.parseInt(s.substring(indexOfFirstNumber, indexOfFirstBracket));
		
		StringBuilder sb = new StringBuilder();
		sb.append(subStr1);
		
		while(duplicates>0){
			sb.append(subStr2);
			duplicates--;
		}
		
		sb.append(subStr3);
		
		return sb.toString();
	}
	

	public static int findIndexOfFirstNumber(String s){
		
		int index = -1;
		for(int i=0; i<s.length(); i++){
			
			char c = s.charAt(i);
			if(c>=47 && c<=58){
				index = i;
				break;
			}
			
		}
		
		return index;
	}
	
	public static int findIndexOfFirstBracket(String s){
		
		int index = -1;
		for(int i=0; i<s.length(); i++){
			
			char c = s.charAt(i);
			if(c=='['){
				
				index = i;
				break;
			}
			
		}
		
		return index;
	}
	
	public static int findIndexOfClosingBracket(String s, int indexOfBracket){
		int index = -1;
		
		int numberOfBracket = 1;
		
		for(int i=indexOfBracket+1; i<s.length(); i++){
			
			char c = s.charAt(i);
			if(c == '[') numberOfBracket++;
			
			if(c==']'){
				numberOfBracket--;
				if(numberOfBracket==0){
					index = i;
					break;
				}
			}
		}
		
		return index;
	}
}

Given a list of system packages, some packages cannot be installed until the other packages are installed. Provide a valid sequence to install all of the packages.

e.g.
a relies on b
b relies on c

then a valid sequence is [c, b, a]

Phone screen Q: String encoding and decoding: Design a method that converts a list of strings into a single string which can be later converted back to the list.

Q: Find the absolute paths to all directories with image files, given a file system that looks like this. The subdirectory is one indent over.

/usr
   /local
       profile.jpg
       /bin
           config.txt
           dest.png
       /rbin
    image.gif
/sys
   /re
   /tmp
       pic.jpg
       .....
……

You are given an array of integers(with all valid input) You have to write a function which will produce another array, where the value in each index of the array will be the product of all values in the given array accept that index.

Example
Array 1: 1 2 3 4 5
Array 2: 120 60 40 30 24.
Come up with a solution of O(n^2) can you improve it?

Random generate a NxN matrix with only four types of element: 1,2,3,4.
However, no column or row can have same type of element appears 3 times or above continuously (three same type of elements are connected)

ex:

valid:
1 2 1 1
3 1 4 2
1 2 4 2
3 1 2 3

invalid because the first column has element 1 appears three times and all 1s are connected to each other :

1 2 1 3
1 3 4 2
1 2 4 4
2 3 2 2

An interesting question asked in Google’s phone interview : suppose a row of parking lot with n spots, one of them is empty and n-1 spots are occupied with cars. Only one operation is allowed: move one car from its position to the empty spot. Given a initial order of cars and a final order, output steps needed to convert initial order to final oder with that operation.

Follow up: Minimize steps needed.

ex:

{1 2 3 -1 4 5}
move car 1 to empty spot(denoted as -1) will make it {-1,2,3,1,4,5}
push 1 to the output list because you move car 1 to the empty spot

suppose you have a initial order {1 2 3 -1 4 5} and a final order {5,1,-1,3,2,4}, you need to transfer {1 2 3 -1 4 5} to {5,1,-1,3,2,4}, push each car moved into a output list.

Given two big files merge the files on to a third file such that the lines interleave.

Given an array of random numbers, shuffle the numbers once again with the least possibility of it being same as previous configuration.

Given two linked lists find if they are making a shape of 'Y' or a shape of 'V'.

If you can hop 1, 2, or 3 steps at a time, calculate the total number of possible combinations for `n` steps.

Find longest consecutive path in a binary tree.
1. the path can be decreasing or increasing, i.e [1,2,3,4] and [4,3,2,1] are both valid
2. the path can be child-parent-child, not necessarily a parent-to-child path

similar to this question: http://www.geeksforgeeks.org/longest-consecutive-sequence-binary-tree/

Given a singly linked list: 1->2->3->4->5
Change it to 1->5->2->4->3 using O(1) space

Implement delete operation for N-ary tree. Your function should return a list of roots after deletion operation. Notice that your delete function only delete one node instead of a subtree. The delete function takes a list of nodes to be deleted.

private class TreeNode {
   int val;
   TreeNode[ ] child;
}

List<TreeNode> delete(TreeNode root, HashSet<TreeNode> set) { }

Given a list of manager and employee information represented in hashMap entries {AAA->BBB,CCC,EEE},{CCC->DDD}.
Print company structure tree with proper indentations. BBB, CCC and EEE directly reports to AAA, so they have one white space before "-", DDD reports to CCC, it has two whitespace before "-". The input is map<String,List<String>>

-AAA
 -BBB
 -CCC
  -DDD
 -EEE

A producer continuously produces a stream of characters. There are multiple consumer threads which read the chars and match to one of known strings and increment the counter for that pattern. Write the consumer function. Show how you will synchronize and maintain parallelism.

Ex: Producer: abcdegabccaabbaacv ......
Known strings[] = {"ab", "aa", "fff" ... }
patternMatchCount[] = {3, 2, 0 ... }

Given N stacks, each stack contains Si elements, find the maximum sum of the M numbers in the N stacks. To get the number of the stack, only supporting get the top number. For example, S=[1,200,1,2,3], if you want to get the number 200, you need choose 3,2,1 first.
EX:
S1=[1,1,100,3]
S2=[2000,2,3,1]
S3=[10,1,4]
the maximum sum of the 3 numbers in the above stacks is 3+100+3=107.
Any better solution for this problem?

Given two pre-order traversal arrays of two binary search tree respectively, find first pair of non-matching leaves.
Follow Up: If they are general binary trees instead of BSTs, could you solve it? give out your reason.

For the first question, I was thinking to construct two BSTs from pre-order traversal then do a leaf-level comparison. Any better solutions are welcome.

Given a binary tree and a target number, return whether or not there exist a path that can create target number. All inputs are integers. Target is not a string.

NOTE:: this is not path sums to target number
ex:
3
4 5
6 7 8 9

359 = return true
38 = return false
47 = return true
6 = return true

You are the main character in a game where you have to defeat a number of enemies in order. The player has a strength value and an initial amount of money. Each enemy also has a strength value, plus a price.

When facing each enemy you can either:
1) Fight him (if your strength is enough). You keep your money.
2) Bribe him (if you have the necessary money). You subtract the enemy's price from your money, and it joins you and adds its strength to yours.

Given a starting strength and amount of money, calculate the optimal strategy and the amount of money you end with (-1 if impossible).

This can be easily solved recursively in O(2^n) basically trying out each option at every enemy. But is there a polynomial solution, maybe involving DP?

Finding biggest plus sign "+" in a sparse matrix(matrix with elements 0 and 1)
For example, the biggest plus sign for following matrix is located at (2,2), with length 1 for each edge(Yes, each edge should have same length)
0 0 1 0 0 1 0
1 0 1 0 1 0 1
1 1 1 1 1 1 1
0 0 1 0 0 0 0
0 0 0 0 0 0 0

Hint: use DFS/BFS

Given a list of coin values, and quantity of each type of coin. Write a
program to return the set of all possible sums which can be made using those
coins.
ex. coins = [10, 50, 100, 500]
quantity = [5, 3, 2, 2]
sum could be 400 , 300 ,200 , 100