CareerCup

Find the number of ways you can have breakfast in 'n' days, given Bread-butter can be eaten every day, Pizza can be eaten every alternate day and Burger can be eaten every two days.

/*Find minimum size of text window which contain all keywords of a search query from document.
Order of keywords don't matter.


Input:
Document: "MS(1) x y Is MS(5) x y MS(8) x Is Awesome x y z Awesome"

doc index dictionary:

{
Keyword: Index Position for keyword in doc
"MS": [1,5,8],
"Is": [4,10]
"Awesome": [ 11, 15] (n)
}
Search Input 1 : "MS is" ( k)
Result: "Is MS Ms" --> [Ms: 5 ; "Is" : 4] --> 2
Search Input 2: "Ms is Awesome",
Result : "MS x is Awesome" --> [Ms:8, Is: 10, Awesome: 11] ---> 4

for -> n
n^k

[1 4 5 8 10 11 15]

*/

Design an IEvictionPolicy interface that allows users to perform put , get, delete functions based on user specified eviction policy.

Tried to use the strategy pattern here but the interviewer wasn't happy. He did not want me to have reference to the cache in the eviction policy's concrete implementation

Given input - xyzonexyztwothreeeabrminusseven as a string, return an integer as the sum of all numbers found in the string
Output - 1 + 23 + (-7) = 17

For a given Sum and N print all the combinations

For Example Sum = 16 and N=2

Then Answer :

16,0
15,1
14,2
13,3
12,4
11,5
10,6
9,7
8,8
7,9
6,10
5,11
4,12
3,13
2,14
1,15
0,16

private void recursivePrint(int sum, int n, int data[], int len, int originalSum) {

		if (n == 0) {

			int sum1 = 0;

			for (int j = 0; j < len; j++) {

				sum1 += data[j];
			}

			if (sum1 == originalSum)

			{
				for (int j = 0; j < len; j++) {

					System.out.print(data[j] + " ");
				}
				System.out.println();
			}

			return;
		}

		for (int i = 0; i <=sum; i++) {

			// System.out.println(" len: "+len+" sum: "+sum+" i: " + i+" n:"+n)
			data[len] = i;

			recursivePrint(sum - i, n - 1, data, len + 1, originalSum);
		}
	}

}

Need a better solution so that we can store previous results by using hashmaps

Was asked to implement a code profiler, which takes a piece of code and provides the run time of a particular function in the code .
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.

Implement Thread safe timer with start, stop and reset functionality.

There are two integer array arrayA and arrayB in the same size and two integer countA and countB. If arrayA[i] > arrayB[i], then we increase countA by 1, if arrayB[i]>arrayA[i], then we increase countB by 1. We will do nothing otherwise. Now you are given arrayA and arrayB, write a function to shuffle arrayA and so you can get countA > countB. Assume the input array are always valid, not empty and the input is guaranteed to have answer.

For example:

arrayA = [12, 24, 8, 32]
arrayB = [13, 25, 32, 11]

After shuffle:

arrayA = [24, 32, 8, 12]
arrayB = [13, 25, 32, 11]

Given two strings representing very large integer numbers, find the Product. Do not use BigInt.

using System;
					
public class Program
{
	public static void Main()
	{
		Console.WriteLine( GetProduct("18888888888888888888888888","19999999999999999999999999999999999999999999999999999999999"));
	}
	public static string GetProduct(string s1,string s2)
	{
		int digit1=0;
		int digit2=0;
		
		char[] str1=s1.ToCharArray();
		char[] str2=s2.ToCharArray();
		int carry;
		string[] result=new string[str1.Length];
		string finalproduct=string.Empty;
        int padding=0;
		
		for(int i=str1.Length-1;i>=0;i--)
		{
			digit1=str1[i]-'0';
			string resval=string.Empty;
			carry=0;
			int j;
			for(j=str2.Length-1;j>=0;j--)
			{
				digit2=str2[j]-'0';
				
				int product=digit1*digit2+carry;
				carry=product/10;
				resval=resval+(product%10);
				
			}
			if(carry>0)
			{
				resval=resval+carry;
			}
			for(int k=0;k<padding;k++)
			{
					resval="0"+resval;
			}
	        result[i]=resval;
			padding++;
		}
		
		int max=findMax(result);
		int count=0;
		int car=0;

		while(count<max)
		{
			 int sum=0;
		 
	 	  for(int x=0;x<result.Length;x++)
		  {
	
			if(count<result[x].Length)
			{
			
				sum+=result[x][count]-'0';
			}

		  }
			sum+=car;
			car=sum/10;
			int p=sum%10;
			finalproduct=p+finalproduct;
			count++;
		}
		
		finalproduct=car+finalproduct;
		
	   return finalproduct.TrimStart('0');		
		
	}
	
	public static int findMax(string[] s)
	{
		int max=0;
		for(int i=0;i<s.Length;i++)
		{
			int len=s[i].Length;
			max=Math.Max(max,len);
		}
		return max;
	}

}

The following code has a bug, find it and fix it

Release()
{
	m_refCount--;
	m.lock();
	if (m_refCount == 0)
	{
		free(this);
		return 0;
	}
	m.unlock()
	return m_refCount;
}

Write a function that receives a string an returns a list of all the substrings (of length >= 2) composed by consecutive characters. E.g input : "BCCDE" , output: ["BC","CD","CDE","DE"]

Given a linked list rotate it on the Kth element. For example, given 1->2->3->4->5 the list should be transformed into 4->5->1->2->3

Design a stock market system

Print elements of a matrix in spiral form.

Given 2 sorted linked lists, return a linked list that has all the elements and is sorted.

Given 3 strings "s" ssearch" and "sreplace", search string s for the substring ssearch and for every instance of ssearch you find, replace that part of the string with sreplace

Given an NxN Boolean matrix, find how many true regions there are in the matrixj

Create a basic minesweeper game that allows for board creation with custom height, width and number of mines. Create a <click> function that will take in a board location and return whether the user has won, lost, or the number of surrounding mines.

Given a string, print out all of the unique characters and the number of times it appeared in the string

What is the smallest number *n* by which the given number *x* must be divided to make it into a perfect square?

n = find_number( x )

Given a singly linked list of integers, write a function in java that returns true if the given list is palindrome, else returns false

Convert an unordered tree to a binary tree

merge two binary search trees

Sort a stack using only one other stack and no recursion.

Given a dictionary and an char array print all the valid words that are possible using char from the array.

Ex- char[] arr = {'e','o','b', 'a','m','g', 'l'}

Dict - {"go","bat","me","eat","goal", "boy", "run"}

Print - go, me, goal.

We can pre-compute as much we want but the query time must be optimal.

You are given a function getNum() that returns a random number in the range 1 to 10 million with repetitions. However, it may also return -1 when it no longer provides numbers. Write a function that calls getNum() continuously until it returns -1 (if a repetition, should not store it); as soon as u see -1, stop calling getnum() and print all the numbers seen so far in a sorted way. Condition: You have got very limited memory to work with.

You have a matrix that is sorted as such: For each value, every index to its right and below it must be larger than the current space's value. Likewise, all entries to its left and above it must be smaller than the current value. How would you go about searching this matrix for a specific number, given its sorted nature?

Just a disclaimer: I doubt you will ever get this interview question. My interviewer even started off by saying, "Hmm, well this isn't really fair, but..." So don't place too much stock in whether or not you can solve this.

Question: You have a group of pigs and buckets of food for said pigs. There are 1,000 buckets of food, and exactly 1 of them is poisoned. Your goal is to determine, by the end of 1 hour, which bucket is poisoned.

The poison takes 30 minutes to kill a pig, and you'd like to kill as few pigs as possible. The number of pigs you can test is limitless, and you can assign a number to each bucket and each pig so that you know exactly which pig ate from which bucket(s). You determine which buckets to feed to which pigs, but you have no timer and no way to guesstimate the time. What is the minimum number of pigs you need to use to solve the problem?

You are given an array of positive and negative integers. If a number n at an index is positive, then move forward n steps. Conversely, if it's negative, move backward n steps. Determine if there is a loop in this array.

For example, given the array [2, -1, 1, 2, 2], index 0 maps to index 2, 1 maps to 0, 2 maps to 3, and so on. There is a loop in this array because 0 maps to 2, 2 maps to 3, and 3 maps to 0 (use the modulo operator).

1. If I say quick sort takes O(e^n ) on the average, would I be wrong?

2. Do you think O( f ) is a good idea for real engineering?
3.Given a choice, what other 'order of' measure would you propose to use ?
4. Do you see a real problem with the modified *order of* ?
5. If you were to sort 10 elements, what sorting method would you have used?
6. If you were to sort 1 trillion unicode characters, what sorting method you would have used?