CareerCup

As ninhnnsoc pointed out, your solution has a worse complexity than O(n^2). Your time complexity is exponential. The code with the memoization technique which produces O(n^2) complexity is,

public int dpLps(int[] a, int i, int j, Integer[][] lps) {
		if (i > j)
			return 0;
		if (lps[i][j] == null) {
			if (i == j)
				lps[i][j] = 1;
			else {
				if (a[i] == a[j])
					lps[i][j] = 2 + dpLps(a, i + 1, j - 1, lps);
				else
					lps[i][j] = Math.max(dpLps(a, i + 1, j, lps),
							dpLps(a, i, j - 1, lps));
			}
		}
		return lps[i][j];
	}

you have to call the function as,

dpLps(a, 0, a.length - 1,new Integer[a.length][a.length])

One of the approaches would be to take the first, middle and last element and consider the median of the values as the pivot element

The problem in your approach is that.if I want to reach cat to dog it's not always a 3 step process.. What if this is the path followed

cat -> bat -> bot -> dot -> dog. So, it takes 4 steps but your answer will be 3.

The approach is to build a graph with vertices as words. An edge exists between two vertices if the two words differ by only one character. Once the graph is constructed, you need to a BFS to obtain the path/count the number of nodes between two words.

To construct the graph, we pass the dictionary as a Set<String>

public Map<String, List<String>> constructGraph(Set<String> set) {

	Map<String, List<String>> map = new HashMap<String, List<String>>();
	for (String str : set) {
		for (String match : set) {
			if (oneCharDiff(str, match)) {
				List<String> list = map.get(str);
				if (list == null) {
					list = new LinkedList<String>();
					map.put(str, list);
				}
				list.add(match);
			}
		}
	}
	return map;
}

In the above code, the function oneCharDiff returns true if there is exactly one character difference between two words.

The following code navigates to the path using the above function,

public static void path(String input, String output, Set<String> set) {

	Map<String, List<String>> map = constructGraph(set);
	Map<String, String> path = new HashMap<String, String>();
	Queue<Word> queue = new LinkedList<>();
	String parent = null;
	queue.add(new Word(input, parent));
	while (!queue.isEmpty()) {
		Word word = queue.remove();
		input = word.original;
		parent = word.parent;
		if (!path.containsKey(input)) {
			path.put(input, parent);
			if (input.equals(output)) {
				System.out.println(output);
				while (parent != null) {
					System.out.println(parent);
					parent = path.get(parent);
				}
				return;
			}
			List<String> list = map.get(input);
			if (list != null) {
				for (String child : list)
					queue.add(new Word(child, input));
			}
		}
	}
	System.out.println("No such path found");
}

Word is a simple class with 2 members - String original and String parent. This is used to print the order of the path followed.

Time complexity : O(n^2) when constructing the graph. Any suggestions to improve the solution are welcome. There is another way to handle this problem using the backtracking method but i'm sure the complexity would be exponential in that case.

Yes this approach works for sure. The solution provided by @Zortlord will also work. But this is easier to understand.

I have never mentioned it as instance of hour. I just said it's an instance of time. What if the times are given in seconds ? Will you maintain a array of total no of seconds in a day ? I feel this is not the right approach.

You have given a brute force approach. The complexity is O(n^2).
There is no use of sorting it based on start time. You can directly compare if the interval is overlapping with other interval and add the values.

I guess the interviewer won't ask for which library function you will use

Thanks for pointing out. I did not add the code for returning the lowest position of the element. I think the following piece of code will help in fixing it.

if (a[mid] == x) {
	while (mid > 0)
		if (a[mid - 1] == x)
			mid--;
	return mid;
}

It's very much similar to Bin search. One point to be noted is to check if the right side of the mid or left side of mid is sorted.
1. If the element is equal to a[mid] then return mid
2. If the right side of mid is sorted (meaning a[mid]<a[high],
a. If x > a[mid] and x< a[high] then x lies between mid and high
b. Else x lies between low and mid-1
3. If the left side of mid is sorted (meaning a[low] < a[mid]),
a. If x < a[mid] and x >a[low] then x lies between low and mid
b. Else x lies between mid and high

public int find(int[] a, int x) {
		int low = 0;
		int high = a.length - 1;
		int mid = 0;
		while (low <= high) {
			mid = (low + high) / 2;
			if (a[mid] == x)
				return mid;
			if (a[mid] <= a[high]) {
				if (x > a[mid] && x <= a[high])
					low = mid + 1;
				else
					high = mid - 1;
			} else {
				if (x < a[mid] && x >= a[low])
					high = mid - 1;
				else
					low = mid + 1;
			}
		}
		return -1;
	}

Space:O(n), Time :O(n)

rev = reverse_list(list);
while(true) {
	if (list == rev || list.next == rev) {
		list.data = list.data-rev.data;	
		break;
	}
	list.data = list.data-rev.data;	
	list = list.next;
	rev = rev.next;
}

One thing to add is while reversing, we shouldn't just swap the values. But must swap the nodes to get the stopping condition right..

How can we do it in less than O(n). What if all the n charecters are the same charecter (which is to be replaced).

Giving a complex solution is better than providing a solution from library...
may be you can tell the interviewer abt the lib function and then can give your solution

Everytime you have to do k comparisons with each of k element in your current array. So, it's definitely going to be O(n^2)

How abt this solution, Since he has not mentioned anything abt how much the memory can hold, we can take the first k elements from each file and put into a file.
Then we can use Quickselect algorithm to find the k smallest elements.
We can argue that this can be achieved in O(n) complexity...

I doubt if the complexity is O(100k)
From the first file, you will create a array of k size.
And, everytime you have to traverse all the elements in your array of k size for comparison with the first k elements of the file..
So, I guess the complexity is O(100*k^2).
Please correct me if I am wrong..

n is all the 100 million numbers = input size
k = heap size

You shouldn't create a min-heap. If you construct a min-heap, then you have the compare the new element with all the elements in the heap.

You should construct a max heap with first k elements. This will place the max element in the root. For each incoming element.
1) Check whether the element is less than the root.
2) If it's less than the root
3) Replace root with the incoming element
4) Heapify

This will produce a heap of k smallest elements at the end of traversing all the elements.
Complexity:O(nlogk)

public static String altCount(String str) {
		String output = "";
		str = str.toUpperCase();
		
		for(int i = 0;i<str.length();i++) {
			int count = 1;
			output += str.charAt(i);
			while (i< str.length()-1 && str.charAt(i+1) == str.charAt(i)) {
				i++;
				count++;
			}
			output +=count;
		}
		return output;
	}

public static String count(String str) {
		
		StringBuilder strB = new StringBuilder(str.toUpperCase());
		int count = 1;
		for(int i = 0;i<strB.length();i++) {
			if (i < strB.length()-1 && strB.charAt(i+1) == strB.charAt(i)) {
				strB.deleteCharAt(i);
				i--;
				count++;
			}
			else {
				strB.insert(i+1, count);
				count = 1;
				i++;
			}
		}
		return strB.toString();
	}

meetings will have start and end times... This is the classic greedy problem - Inteval scheduling problem

sort the n meeting according to their end times
Keep assigning the 1...n meetings to the first of the meeting room 1..m which is free

str1.hashCode() == str2.hashCode()

First ensure the length of two strings are same,
Then, compare each character by its ascii value one by one. This will take care of case automatically.

Are there any other conditions ?

There is no formatting.. How can you understand this thing ?

I guess it's for detecting cycles in a graph

I guess the qn should be moving right or down nor right or left ??

Same code with minor changes,

public static void printComb(String prefix,String str) {
	if (str.length() == 0) {
		System.out.println(prefix);
		return;
	}
	if (Character.isAlphabetic(str.charAt(0))) {
			printComb(prefix+str.substring(0,1).toLowerCase(),str.substring(1));
			printComb(prefix+str.substring(0,1).toUpperCase(),str.substring(1));
		}
		else
			printComb(prefix+str.substring(0,1),str.substring(1));
}

You can maintain a hashmap for storing the output. Instead of printing the prefix you can put it into the map and return it. This will avoid duplicates..

Sorting the input and removing duplicates will alter the length of the combination. So, I think this method should be simple..

Is this the right approach. I am keeping track of predecessor value using pre variable. Whenever I reach the given node, I return the tracked predecessor value.

public int inorderPredecessor(BST root, int x, int pre) {
        if (root != null) {
            pre = inorderPredecessor(root.left, x, pre);
            if (root.value == x) {
                System.out.println("Predecessor = " + pre);
                return pre;
            }
            pre = inorderPredecessor(root.right, x, root.value);
        }
        return pre;
    }

This is same as printing all the permutations of the string..

public void permutation(String prefix, String str) {
        int n = str.length();
        if (n == 0)
            System.out.println(prefix);
        else
            for(int i = 0;i < n;i++)
                permutation(prefix+str.charAt(i), str.substring(0, i)+str.substring(i+1, n));
        
    }

No, my solution asks to look for any character of string a in string b..

From your example: characters in string a = {a,b,c}
While traversing string b, it detects character c and then generate two possible combinations - cab, cba and check whether the combinations are present in string b which will be found. So, will return true..

We can maintain the characters of string a in a hashmap so that search will take just O(1) time for each of the characters of string b.

Will this one work...

Search for the occurrence of any character of string a in string b. Let this character be x.

If found, generate all anagrams of string a starting with x and check whether the same pattern is found in string b.

If found return true, else continue finding the next character

Nope, consider a right-skewed tree with node values - 5(root), 10, 15, 20.

Now Inorder predecessor(10) = 5. Your code will return null

Should we memoize based on the input string str ?
If yes, which is the best one to maintain a hashmap with str as key or maintain array with length of string ?

To budsiya: Can we use something like a priority queue which maintains the records by time so that we can get the records stored in the last 10 minutes easily.

Looks like the implementation of Observer design pattern

If you are going to sort the arrays, you can find the intersection of arrays via 2-way merge instead of going for binary search. It's much simpler than the binary search. It doesn't reduce the complexity by any means but it will be much simpler..

Do the same functionality as palindrome function does with below modifications:
a) you can convert the string to all lowercase
b) consider only ASCII characters within range 97-122 (a-z)

You can solve it in linear time. You need extra space.
Store the elements of array B in hashmap with values as keys.
traverse through array A. If the element is found in the hashmap include it in the output array.

The solution for this is called three way partition or the dutch national flag problem. This can be done using linear time and constant space.. Algorithm is available in wiki page:

ya sorry.. I will edit it

HashMap : Insert - O(1), search (by key) O(1)
Array : Insert - O(1), search O(n)
Linked List : Insert - O(n), search O(n)
Queue : Insert (by front pointer) - O(1), search O(n)

public Tree delete(Tree root, int x) {
        if (root == null) {
            return null;
        } else if (x < root.value) {
            root.left = delete(root.left, x);
        } else if (x > root.value) {
            root.right = delete(root.right, x);
        } else {
            if (root.left == null && root.right == null) {
                root = null;
            } else if (root.left == null) {

                return root.right;
            } else if (root.right == null) {
                return root.left;
            } else {
                Tree temp = find_min(root.right);
                root.value = temp.value;
                root.right = delete(root.right, temp.value);
            }
        }
        return root;
    }

Can you expand more.. I guess your technique might disturb the order..

Maintain two arrays - front [ ] and rear [ ]
front maintains the product before the current index
rear maintains the product after the current index
then the product of current index i = front[i]*rear[i]

int [] product (int [] input) {
	int [] front = new int[input.length];
	int [] rear = new int[input.length];
	int [] output = new int[input.length];
	front[0] = 1;
	rear[input.length-1] =1;
	for(int i = 1; i < input.length; i++)
		front[i] = front[i-1]*input[i-1];
	for(int i = input.length-2; i >=0; i--)
		rear[i] = rear[i+1]*input[i+1];
	for(int i = 0;i<input.length;i++)
		output[i] = front[i]*rear[i];
	return output;
}

I have a doubt.. We cannot heapify a tree unless it maintains the structural property right? Then how can we apply heapify

Can you provide a better solution ?

List merge(List head1, List head2) {
	List result = null;
	if (head1.data < head2.data) {
		result = head1;
		result.next = merge(head1.next,head2);
	}
	else {
		result = head2;
		result.next = merge(head1,head2.next);
	}
	return result;
}

public static int countPath(int m, int n) {
        int [] [] count = new int[m][n];
        for(int i=0;i<m;i++) {
            for(int j=0;j<n;j++) {
                if (i == 0 || j == 0)
                    count[i][j] = 1;
                else
                    count[i][j] = count[i-1][j]+count[i][j-1]+count[i-1][j-1];
            }
        }
        return count[m-1][n-1];
    }

Answer is stack. Push and Pop is O(1). For find_min, you can maintain a seperate stack which stores the min element so far and you can pop the element from this stack if the element is popped from the main stack..