C++ interviews questions on algorithm like Fibonacci,brain teaser, probability

(Last Updated On: May 12, 2010)
Learn the Secret

Get  our 2 Free Books

Get these now which land directly to their inbox.
Invalid email address

Mutable
What is the (C++) keyword mutable used for? Give an example.

Algorithm:
C++ contains numerous algorithm functions that accept function objects as a parameter.

Referring to the statement above, which one of the following is another name for function objects?
Choice 1

Use Case
Choice 2

Operators
Choice 3

Actions
Choice 4

Iterators
Choice 5

Predicates
The answer is Iterators
I thought it was functors, but who cares for such stupid questions?

implement a function to_dollar(int a) that takes in an int, say ‘10200’, and prints $10,200.
this is the solution not only for the intergers but also for double values (using cents)

public class ConvertDolar {
public static void main(String[] args) {
double amount = 1234567.99222229292929d;
System.out.println(prinDollar(amount));
}

static String prinDollar(double number) {
int cents = (int) (number % 1 * 100); // saving the cents
int num = (int) number; // eliminating the cents
StringBuffer dollar = new StringBuffer();
int count = 0;
while (num > 0) {
if (count == 3) {
dollar.append(“,”);
count = 1;
} else {
count++;
}
dollar.append(num % 10);
num /= 10;
}
return “$” + dollar.reverse().toString() + “.” + (cents < 10 ? "0" + cents : cents); } } Result: $1,234,567.99 Reply to Comment intelliplay on March 26, 2010 |Edit | Edit And here is one using the STL: #include
#include
#include
#include

using namespace std;

void to_dollar(int a);

int main()
{
int userInput;

cout << "Please enter an integer-:> ” << endl; cin >> userInput;
to_dollar(userInput);

return (0);
}

void to_dollar(int a)
{
stringstream inString;
string strTemp;
long double intTemp;

inString << a; // convert integer to string for easier handling inString.str(inString.str()+"00"); // concatenate two zeos to denote currency fractional digits inString >> intTemp; // convert back to integer

locale loc(“english_USA”); // set the locale
cout.imbue(loc);

cout.setf(cout.flags() | ios::showbase); // turn on currency sign printing
const money_put& m_put = use_facet >(loc); // get the money_put facet
m_put.put(cout, false, cout, ‘ ‘, intTemp); // show me the money. Note to use fractionally adjusted value.
cout << endl; } Oh, I seem to have messed up the spacing. Hope you can still read the code. This is my first post so... Let me know your comments. With the STL, the solution is really simple. Just a matter of knowing which library objects/functions to call. int my_number_format(int num) { int idx; char buffer[64]; idx = sizeof(buffer)-1; buffer[idx--] = 0; // end zero int count = 0; while (num > 0) {
if (0 == idx)
return -1;
if (count > 2) {
buffer[idx–] = ‘,’;
if (0 == idx)
return -1;
count = 0;
}
count++;
buffer[idx–] = ‘0’+(num % 10);
num /= 10;
}

buffer[idx] = ‘$’; // currency sign
return printf(“%s\n”, &buffer[idx]);
}
Reply to Comment
dullboy on April 21, 2010 |Edit | Edit

We may code it using stack

void _dollar(int x)
{
char s[64];
stack stk;

*s = ‘\0′;

while(x/1000 > 0)
{
if(!stk.isFull())
stk.push(x%1000);

x = x/1000;
}
if(!stk.isFull())
stk.push(x);

while(!stk.isEmpty())
{
sprintf(s, “%s%d,”, s, stk.pop());
}

int i = 0;
while(s[i++]!=’\0’);

*(s+i-2) = ‘$’;

printf(s);
}

int main()
{
_dollar(12800900);
return 0;
}

Class Design:
Using char*,
design an CString implementation.
List the functions that are supported,
Implementation of “operator=”.
1

You simply count the number “l”s in the paragraph.

“iving numbers 2,3,5,7,11 ,
1.multiply each number by 2,
2.if the result is bigger than 25 , then go to next step, otherwise repeat the 1st step.
3. multipy the result by 3.
4. add XX
5. divide with XX.

question: which number will produce maximun output
2 will.
Steps 3,4,5 are useless, just check steps 1 and 2.
I believe the correct answer is 3 because 3*2*2*2 = 24 so *2 = 48 while 2*2*2*2*2 = 32…
yes, the correct answer is 3.
Given deck of cards + joker, what is the probability you see the joker before all four aces?
consider only 5 cards, 4aces and 1 joker

now there are 5 positions – – – – – and the joker can take any of the 4 positions except the last one, so the P = 4! / 5!

Suppose there is a rectangular map where you can only travel up or right to go from a start location in the bottom left corner to the top right corner, and each move is discrete. Write a program that prints all possible solutions to get from the start to finish.
Suppose you need 5 R (right moves) and 5 T (top moves) to reach the upper right corner. Then you can do a permutation of the string, “RRRRRTTTTT” to get all the possible paths.

give you 3L bottle and 5L bottle, to get 4L water.
1. Fill the 5L can.
2. Pour the 5L in 3L.
3. Empty 3L.
4. So, 2 litres remaining in 5L.
5. Pour 2 litres from 5L to 3L.
6. Fill 5L.
7. Pour 5L into 3L, so that only 1 litres goes from the 5L into 3L and 5L now has 4 litres.
by Anil:
Fill 3L and empty it by pouring all in 5L bucket.
Fill 3L again and pour water into 5L from 3L. 3L will be left with 1 litre of water.
Empty 5L and put the 1L into it. Again fill 3L and pour it into 5L.
Total water in 5L will be 4 litres.

“Given 5 prices of a share for 5 days i.e. from Monday-Friday share prices for a perticular share are $1, $4, $5, $2, $3. Find the max profit you could make in a given week. You are not allowd to do multiple trading in a day and its not mandatory to do trading on each day. Write a C code for this.”
“How would you reverse the digits of an integer? (say from 123456 to 654321)”
“string manipulation”

“Given a sequence of shape rotation steps, find the missing step that would transform the shape from initial to final phase.”
Write a function to convert First Name, Last Name to Last Name, First Name.

You can do it inplace my swapping the last and first char and then shifting the start index and rest string by one place each time.

If I arrange the numbers 1 to 100 in a random order and remove one number from this group – give me an algorithm to find the missing number?
Describe how you would rearrange a word and then a sentence in C!
Count # of times character ‘s’ appear in one paragraph
“Count the number of i’s in the paragraph.”
he wanted me to speak a lookup table
Suppose there is a rectangular map where you can only travel up or right to go from a start location in the bottom left corner to the top right corner, and each move is discrete. Write a program that prints all possible solutions to get from the start to finish.
Suppose you need 5 R (right moves) and 5 T (top moves) to reach the upper right corner. Then you can do a permutation of the string, “RRRRRTTTTT” to get all the possible paths.

give you 3L bottle and 5L bottle, to get 4L water.
1. Fill the 5L can.
2. Pour the 5L in 3L.
3. Empty 3L.
4. So, 2 litres remaining in 5L.
5. Pour 2 litres from 5L to 3L.
6. Fill 5L.
7. Pour 5L into 3L, so that only 1 litres goes from the 5L into 3L and 5L now has 4 litres.
by Anil:
Fill 3L and empty it by pouring all in 5L bucket.
Fill 3L again and pour water into 5L from 3L. 3L will be left with 1 litre of water.
Empty 5L and put the 1L into it. Again fill 3L and pour it into 5L.
Total water in 5L will be 4 litres.

“Given 5 prices of a share for 5 days i.e. from Monday-Friday share prices for a perticular share are $1, $4, $5, $2, $3. Find the max profit you could make in a given week. You are not allowd to do multiple trading in a day and its not mandatory to do trading on each day. Write a C code for this.”
“How would you reverse the digits of an integer? (say from 123456 to 654321)”
“string manipulation”

“Given a sequence of shape rotation steps, find the missing step that would transform the shape from initial to final phase.”
Write a function to convert First Name, Last Name to Last Name, First Name.

You can do it inplace my swapping the last and first char and then shifting the start index and rest string by one place each time.

If I arrange the numbers 1 to 100 in a random order and remove one number from this group – give me an algorithm to find the missing number?
Describe how you would rearrange a word and then a sentence in C!
Count # of times character ‘s’ appear in one paragraph
“Count the number of i’s in the paragraph.”
he wanted me to speak a lookup table
Given deck of cards + joker, what is the probability you see the joker before all four aces?
consider only 5 cards, 4aces and 1 joker

now there are 5 positions – – – – – and the joker can take any of the 4 positions except the last one, so the P = 4! / 5!

I think the question is asked differently. the probability of seeing the joker after all 4 aces is 1/5. So the probability of seeing the joker in any other place is 1 – (1/5) = 4/5 which should be the right answer
Split the horses into 5 groups and race each of the 5 groups (5 races). After that, you have the horse placements for each group. I laid it out like this:

A B C D E
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3
4 4 4 4 4
5 5 5 5 5

Five columns, one for each group of horses, lettered A-E. Each number represents a horse… say horse A1 is the one that came in first place from group A, C2 is the horse that placed 2nd in group C, and so on.

You can eliminate all 4’s and 5’s from the chart, since we know that there are at least 3 horses that are faster for each 4th and 5th place horse.

A B C D E
1 1 1 1 1
2 2 2 2 2
3 3 3 3 3

Now race all the 1’s (race #6). This will give you the fastest horse from the initial 25. But what about 2nd and 3rd place?

Let’s say A1 got 1st, B1 got 2nd, C1 got 3rd, D1 got 4th and E1 placed last in race #6. A1 is definitely the fastest horse, but B1 may or may not be. Horse A2 can still be faster than B1- we have never raced them together before.

Approach it this way: which horses can we eliminate? Find all horses that we know have at least 3 horses faster than them. We can eliminate D1 and E1, because we know that A1, B1, and C1 are all faster than them. We can also eliminate all other horses in columns D and E below them. We can’t eliminate C1, but we can eliminate C2 and C3. We also eliminate B3, since B2, B1, and A1 were all proven to be faster.

A B C D E
1* 1 1
2 2
3

The only horses left to race are A2, A3, B1, B2, and C1. (Race #7). The 2nd and 3rd place finishers are then 2nd and 3rd fastest from the original 25.

A Fibonacci spiral created by drawing arcs connecting the opposite corners of squares in the Fibonacci tiling; this one uses squares of sizes 1, 1, 2, 3, 5, 8, 13, 21, and 34; see Golden spiral
In mathematics, the Fibonacci numbers are the numbers in the following sequence:

By definition, the first two Fibonacci numbers are 0 and 1, and each remaining number is the sum of the previous two. Some sources omit the initial 0, instead beginning the sequence with two 1s.
In mathematical terms, the sequence Fn of Fibonacci numbers is defined by the recurrence relation

with seed values

: Describe how to implement a queue out of stacks. (no coding, just thought process)

Implementing queue using 2 stacks

You have three lightbulbs in one room and three switches in another room. You can play with the switches as much as you want to, but you can only visit the room withthe bulbs once. How can you determine which switch corresponds to which bulb?
Turn on two switches. Wait a while and turn off one of them. The bulbs will either be on, off, or off and still hot.
1. Turn on the 1st switch for sometime. Then turn it off. The bulb corresponding to this switch will be hot.
2. Turn on 2nd switch and then go to the room.
3. The bulb that will be on will correspond to the 2nd switch. The other 2 bulbs will be off. The one that will be hot among the 2 off bulbs will correspond to the first switch. And the other off bulb will correspond to the 3rd switch.
There are 20 floors in a building. I step into the elevator with 5 other people. What is the probability that I do not have to press my button? (ie someone else chooses the same floor as me)
Note the technicality that in a 20 floor building, people getting on the elevator have only 19 choices since they won’t get on the elevator to go to the current floor.

The number of combinations of floor choices for the 5 other people is

19^5

The number of these combinations that don’t include your choice is

18^5 (i.e. the number of combinations of the remaining 18 floors)

So the probability that someone will choose your floor is

1 – ( 18^5 / 19^5 ) ˜ .24 = 24%

STL:
What is the difference between a C++ array and an STL array type
one is a class and the other is just a memory block of a data type?

Specific questions on map functions (STL), on how to remove all elements that were <= 50 know STL , tell me what kind of containers are available , complexities of each ? how would you know if a map is corrupted? How about catching memory exception? if it's not sorted anymore. Why would map be sorted in the first place ? Its a key value association

NOTE I now post my TRADING ALERTS into my personal FACEBOOK ACCOUNT and TWITTER. Don't worry as I don't post stupid cat videos or what I eat!
This entry was posted in Quant Development and tagged , , , , , on by .

About caustic

Hi i there My name is Bryan Downing. I am part of a company called QuantLabs.Net This is specifically a company with a high profile blog about technology, trading, financial, investment, quant, etc. It posts things on how to do job interviews with large companies like Morgan Stanley, Bloomberg, Citibank, and IBM. It also posts different unique tips and tricks on Java, C++, or C programming. It posts about different techniques in learning about Matlab and building models or strategies. There is a lot here if you are into venturing into the financial world like quant or technical analysis. It also discusses the future generation of trading and programming Specialties: C++, Java, C#, Matlab, quant, models, strategies, technical analysis, linux, windows P.S. I have been known to be the worst typist. Do not be offended by it as I like to bang stuff out and put priorty of what I do over typing. Maybe one day I can get a full time copy editor to help out. Do note I prefer videos as they are much easier to produce so check out my many video at youtube.com/quantlabs