CareerCup

Given a very large binary number which cannot be stored in a variable, determine the remainder of the decimal equivalent of the binary number when divided by 3. Then generalize to remainder of any number 'k'

Given a pre-order traversal, construct a binary search tree in O(n) time.

Given a large text file, find an efficient algorithm to find the least distance(measured in number of words) between any two given words.

You are given a text file. You have to return the list of starting index of the given word in text file. Design an efficient DS for that.

Example :-
Text file content : “geeks for geeks”
word : “geeks”
List : {0,10}

In a file, there are two columns, first column has some word (String) and 2nd column has some value (Double).
Example :-
ABC 23.4
ERF 34.89
WERT 122.9

Now user wants some arithmetic operations like
1) ABC + ERF = 23.4 + 34.89 = 58.29
2) ABC – WERT = 23.4 – 122.9 = -99.5

Design an efficient DS for these kind of operations.

Implement a queue using only one stack.

It’s a two player game. Both the players are equally intelligent to win the game. Give n no. of stones. A player can choose either 1 stone or k stones or l stone (1<k<l). Suppose player 'A' starts game then challenge was to identify the player who will win the game. Player who picks the last 1 stone or last k stone or last l stones win the game.

Design bus booking system:- Each row has x seat. If customer wants K seats if you have K consecutive seats available, reserve them. Otherwise give seats from any row.

There is a bridge and N no. people takes (a1,a2,—an) time to cross it and there are K torch and at any time x no of people can pass the bridge and it takes maximum of x people time to cross it. Minimum time required for N persons to cross the bridge.

There is a graph where each node represents a city and it contains specific no. of people. A tournament is going on and each match is playing in one city. All city’s people gather to watch match. Traffic department wants to manage how many people travel through city x if match is playing in city y for each x. City x and y can be any city.

Got Sp00ked by MS simple question..

Eight Ball problem, find Minimum steps to determine the heaviest one.

Anyone know the answer is 2 in case of 8 balls.. Question is code getHeavy when number of balls are not determined.

int getHeavy(List<Integer> balls){
// Your solution
}

Design a mall where there are 'm' entry gates and 'n' exit gates. There can be only 'x' number of people inside it. No more then 'x' people can be inside mall at any time.

How will you design a true collar?

Given an array of co ordinates (x,y). WAP to figure out if a square can be formed from any four points.

Given a 2d matrix and 4 points. WAP to figure out if they are row wise, column wise of diagonally wise consecutive.

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.