CareerCup

I found this really hard. It would be fairly straightforward if the words were not concatenated. I came up with some sort of complicated solution involving building a multimap of words of different lengths, so you read n letters, check for a word which matches all letters in the map of words of n length, but I assume there must be a simpler solution.

There's also a major problem if you get a false match. For example, if "hello" is scrambled as "ehllo", the first word you would probably try is "he". At some point you presumably decide "he" is incorrect, so then your next match might be "hell". That is incorrect as well though. There has to be some mechanism for backtracking the process and deciding that the previously tried word (or even words) must be incorrect.

#include <queue>
#include <iostream>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <stack>

struct Node
{
    std::string parentData;
	std::set<Node> adjacentNodes;
	std::string data;
	
	explicit Node(const std::string& dat) : data(dat) 
	{}
	bool operator< (const Node& rhs) const { return data < rhs.data; }
};

struct DictionaryGraph
{
	std::unordered_set<std::string> dictionary;
	std::unordered_map<std::string, Node> graph;
	
	explicit DictionaryGraph(const std::unordered_set<std::string>& dict)
	    : dictionary(dict)
	{
		for( const auto& word : dictionary )
		{
			Node node(word);
			std::set<Node> adjacent_nodes;
			
			for( auto change_char = 'A'; change_char <= 'Z'; ++change_char )
			{
			    if( change_char != word[0] )
				{
					std::string to_find(change_char + word.substr(1,2));
					const auto& found = dictionary.find(to_find);
					if( found != dictionary.end() )
					{
						adjacent_nodes.insert(Node(to_find));
					}
				}
				if( change_char != word[1] )
				{
					std::string to_find(word.substr(0, 1) + change_char + word.substr(2,1));
					if( dictionary.find(to_find) != dictionary.end() )
					{
						adjacent_nodes.insert(Node(to_find));
					}
				}
				if( change_char != word[2] )
				{
				    std::string to_find(word.substr(0, 2) + change_char);
					if( dictionary.find(to_find) != dictionary.end() )
					{
						adjacent_nodes.insert(Node(to_find));
					}
				}	
			}
			node.adjacentNodes = adjacent_nodes;
			graph.insert(std::make_pair(word, node));
		}
	}
};

void BreadthFirstSearch( const Node& root, const std::string& target, std::unordered_map<std::string, Node>& graph )
{
	std::cout << "start:" << root.data << " target:" << target << "\n";
	
	std::unordered_set<std::string> visited;
	std::queue<Node> node_queue;
	node_queue.push(root);
	visited.insert(root.data);
	
	while( !node_queue.empty() )
	{
		Node current_node = node_queue.front();
		node_queue.pop();
		if( current_node.data == target )
		{
			std::cout << "Found target:" << current_node.data << std::endl;
			
			std::stack<std::string> route;
			route.push(current_node.data);
		
			while( !current_node.parentData.empty() )
			{
				route.push(current_node.parentData);
				if( graph.find(current_node.parentData) != graph.end() )
				{
				    current_node = graph.find(current_node.parentData)->second;	
				}
				else
				{
					break;
				}
			}
			if( !route.empty() )
			{
			    std::cout << route.top();
				route.pop();
			}
			while( !route.empty() )
			{
				std::cout << "->" << route.top();
				route.pop();
			}
			break;
		}

		for( auto& node : current_node.adjacentNodes )
		{
			if( visited.find(node.data) == visited.end() )
			{
				Node& graph_node = graph.find(node.data)->second;
				graph_node.parentData = current_node.data;
				node_queue.push( graph_node );
				visited.insert(node.data);
			}
		}
	}
}

int main()
{
	std::unordered_set<std::string> dictionary { "CAT", "COT", "COG", "DOT", "DOG", "BAT", "BIN", "BOG", "GOT", "HIT", "BIT" };
	
	DictionaryGraph dictionary_graph(dictionary);
	
	std::string start_string = "COG";
	std::string end_string = "BIN";
	
	if( dictionary.find(start_string) == dictionary.end() ||
	    dictionary.find(end_string) == dictionary.end() )
	{
	    std::cout << "Bad input strings. Start:" << start_string << " End:" << end_string;
        return 1;		
	}
	
	Node start_node = dictionary_graph.graph.find(start_string)->second;
	BreadthFirstSearch( start_node, end_string, dictionary_graph.graph );
	return 0;
}

There's not enough information in the question to answer. How are the cards numbered? 1-50? 1-10? Do they contain picture cards? Are we talking about the chance that the number that land face up is divisible by seven, or the total value of the cards displayed? If 28 cards land face up, does it matter what the total value is? They're two very different questions to answer.

#include <array>
#include <iostream>

int main()
{
    std::array<int, 9> input { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	
	const int REVERSE_SIZE = 3;
	const int ORIGINAL_FRONT = 0;
	int front = ORIGINAL_FRONT;
	int back = ORIGINAL_FRONT + (REVERSE_SIZE - 1);
	
	while( back < input.size() )
	{
		int next_front = front + REVERSE_SIZE;
		while( front < back )
		{
		    std::swap( input[front++], input[back--] );	
		}
		front = next_front;
		back = front + (REVERSE_SIZE - 1);
	}
	for( const auto& num : input )
	{
	    std::cout << num << "\n" ;
	}
}

#include <vector>
#include <iostream>

int main()
{
    std::vector<int> input { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
	
	const int REVERSE_SIZE = 3;
	
	int front = 0;
	int swaps = 0;
	
	while( front < input.size() )
	{
	    int back = front + ((REVERSE_SIZE - (swaps * 2) - 1));
		if( back >= input.size() )
	    {
	        break;
		}
	    std::swap( input[front], input[back] );
		++swaps;
		++front;
		if( swaps == (REVERSE_SIZE / 2.0) )
		{
		    front += REVERSE_SIZE / 2.0;
			swaps = 0;
		}
		else if ( swaps == (REVERSE_SIZE / 2 ) ) // implicit truncation
		{
		    front += (REVERSE_SIZE / 2.0) + 0.5;
			swaps = 0;
		}
	}
	for( const auto& num : input )
	{
	    std::cout << "\n" << num;
	}
}

#include <vector>
#include <string>
#include <iostream>

int main()
{
    std::vector<char> row1 { 'a', 'b', 'c', 'd', 'e' };
    std::vector<char> row2 { 'f', 'g', 'h', 'i', 'j' };
    std::vector<char> row3 { 'k', 'l', 'm', 'n', 'o' };
    std::vector<char> row4 { 'p', 'q', 'r', 's', 't' };
    std::vector<char> row5 { 'u', 'v', 'w', 'x', 'y' };
    std::vector<char> row6 { 'z' };

    std::vector< std::vector<char> > screen;

    screen.push_back(row1);
    screen.push_back(row2);
    screen.push_back(row3);
    screen.push_back(row4);
    screen.push_back(row5);
    screen.push_back(row6);

    const int ROWS = 6;
    const int COLUMNS = 5;

    std::string searchString = "con";
    int searchIndex = 0;
    int column = 0;
    int row = 0;
    
    while( searchIndex < searchString.size() )
    {
        char currentChar = screen[row][column];
        char searchChar = searchString[searchIndex];   

        if ( currentChar == searchChar )
        {
            std::cout << "OK\n";
            ++searchIndex;
        }
        else if ( searchChar > (currentChar + (COLUMNS - column) - 1) )
        {
            std::cout << "DOWN\n";
            ++row;
        }
        else if ( searchChar < (currentChar - column) )
        {
            std::cout << "UP\n";
            --row;
        }
        else if ( searchChar < currentChar )
        {
            std::cout << "LEFT\n";
            --column;
        }
        else
        {
            std::cout << "RIGHT\n";
            ++column;
        }
        if( row > ROWS ||
            column > COLUMNS ||
            row == ROWS && column > 0 )
        {
            std::cout << "ERROR with row:" << row << " column:" << column << " currentChar:" << currentChar;
            break;
        }           
    }

}

Loop through rows, printing each row and storing each row in a vector, then loop through vector using a reverse iterator.

#include <iostream>
#include <vector>
#include <string>
#include <sstream>

void printPyramid( int size )
{
    int currNum = 0;
    std::vector<std::string> rows;
    int row = 0;
    
    for( ; row <= size; ++row )
    {
        std::ostringstream oss;
        for( int numbers = 0; numbers < row; ++numbers )
        {
            ++currNum;
            std::cout << "\t" << row << ":" << numbers << ":" << currNum << std::endl;
            oss << currNum;
            if( (numbers + 1) != row )
            {
                oss << "*";
            }
            else
            {
                std::cout << oss.str() << std::endl;
                rows.push_back(oss.str());
            }
        }
    }

    for( std::vector<std::string>::const_reverse_iterator rIter = rows.rbegin(); 
         rIter != rows.rend(); 
         ++rIter )
    {
        std::cout << *rIter << std::endl;
    }
}

int main()
{
    printPyramid(4);    
    return 0;
}

As Anonymous said below, this doesn't make sense to me. If the third person is lying, then the second person is telling the truth. The second person says that the first person is lying. So LTL is valid, there is no contradiction that I can see.

If the third person is telling the truth, then the second person is lying. The second person says that the first person is lying, so the first person must be telling the truth. So TLT also seems valid.

With the problem given I don't think there is a definite answer for the third person. If there is supposed to be a correct answer then we must be missing some information.

That takes two passes, so not as efficient as reversing each word as you come to it and then starting again when you get to a space (which is what chimpinchief does).

If you can get a single number equal to exactly the sum in the array and that should not be counted then yes, {15, 5, 3, 2} with sum 15 is a fail. However it would be easy to code around, e.g. add a "first_call" parameter to sumCountHelper; if total == 0 && first_call then return without incrementing count. If we get to the recursive call then call sumCountHelper with first_call = false.

I like the idea that you don't even need to store the longest string, you just need to store an index to that string. But:

1) char* str[] etc. needs to be const char* str[] to avoid warnings with my compiler. Anything between "" is implicitly a const char*.
2) I don't think you're using sizeof correctly. Dereferencing the pointer "str" will give you the first element in the array. So in other words sizeof(*str) is sizeof(char*). On my system the size of a pointer is 4 bytes. So in other words the code breaks if you add "Test test test test test test" to the end of the array, because that is the fifth element and we're only looping four times.
3) The code does work if you just use a constant for the size of the array which you can then use to loop through. Or a sensible C++ solution would be to use something like vector<string>, and then you don't have to worry about magic numbers.

You're traversing the array twice, which is unnecessary. If there can be only one longest string then just store the longest string you see as you traverse the array. If there can be more than one longest string then keep a container of all the strings which have the most characters seen, emptying it if you see a string with more characters.

Why do you need a HashMap? Why don't you just store one string and replace that string if you see a string with more characters as you traverse the array?

1. Add elements from array to ordered set, sorting by greater than.
2. Use an iterator to return value at position k.

1. If length of strings is different return false.
2. If first str1 character is not in str2, return false.
3. If character is in str2, iterate str2 from that position and check next character. Keep iterating both strings while characters match.
4. If next character in str1 != next character in str2, compare str1 character with index[0] in str2. If str2[0] matches then continue, iterating str2 from 0.
5. If a letter is duplicated it's possible to get a false starting point in str2, so if the first character is in str2 multiple times then save starting position and if we get a negative result then try again with the next occurrence of str1[0]. E.g. if str1 == "poppingPass" and str2 == "pingPasspop" then we would find the correct starting point on the second attempt. If str1 == "poppingPasspopped" and str2 == "poppedpoppingPass" then we would find the current starting point on the fourth attempt, so might not be great worst case complexity with many duplicated letters.

The question is not very clear. Assuming you have a specified number of exchanges and the data is stock_ticker and stock_price, then you could create multiple hash maps of <string, double>, one per exchange. i.e. If exch==LIFFE then add the stock data to liffe_exch_map. If you're supposed to be aggregating prices from different exchanges then you only actually need one hash map, as exchange is irrelevant. If you didn't know the number of exchanges in advance then you could create a hashmap where the key is exchange and the returned value is another hashmap of <string, double>. Look up the correct list of stocks and their values based on the exchange, then look up the value for that stock as before.

It's also worth pointing out that you don't have to use a string as the key, you could get a lot more flexibility if you defined a proper Stock object to use as the key, and then defined the Stock hash function as needed, and let your container handle how it stores the Stock objects. For example, if the hash includes the exchange and name, then stocks with the same name but different exchanges would be stored in separate buckets in the hashmap. You then lookup a Stock object in the hashmap using name and exchange, and if your hashing function is working properly it's constant time lookup. If you stop caring about exchange then you simply remove exchange from the hash function.

Very nice.

You should probably clarify with whoever is asking the question but in my experience "best" generally means time complexity and a hash table is frequently the best solution for fast lookup. This was basically the solution I was thinking of. In C++ it would be unordered_map country_states<string, vector<string> >, unordered_map state_cities<string, vector<string>.

It's worth pointing out that with the problem as described the second part of the hash map, i.e. the value as opposed to the key, doesn't actually have to be an array of strings, it could just be a comma or space separated string. That would simplify using the hash maps somewhat at the cost of losing some flexibility in handling the returned data. For example, if the client wished to list a country's states on separate lines they would have to tokenize the returned value themselves.

I like the idea, but if you index into an array of bools using a char, it's going to convert the char to an integer to get the index, isn't it? And that's an array bounds write if the array only has 26 elements, because 'a' != 0.

You could make ALPH_SIZE = 128 and I think it would work, with some unused array space, although the container used is so lightweight I can't imagine it matters. The best solution though presumably would be to subtract 'a' from the character c to get an integer to use as the correct array index.

You can also return early if s.length == 1, as there cannot be a missing character (there's no range).

Requires one pass through str1, so linear time.

1. Find first example from str2 in str1. (Any chars before this must make the string longer and can be ignored.)
2. Iterate through str1, adding characters to candidate_string. If character is in str2 and was not previously in candidate_string, increment match_counter. (This assumes there are no duplicate characters in str2.)
3. If we encounter a character in str3, truncate candidate_string, set match_counter to zero, move iterator to next occurrence of str2 character in str1, then start reading characters into candidate_string again.
4. If length of candidate_string is now >= any previously stored result_string, find the second occurrence of a str2 char in candidate_string (as that's the next possible shortest candidate_string start). Take the substring from that position to the end of candidate_string, decrement match_counter. Continue to iterate through str1 from current position, adding characters to candidate_string.
5. If match_counter == str2.length() then we have matched all candidate chars in a shorter length than the previous result_string. Copy candidate_string to result_string. Take the substring from second occurrence of str2 character in candidate_string to be the new candidate_string, as above.
6. If result_string.length() == str2.length() then this is the shortest possible sequence, so we can break. Otherwise, move the str1 iterator to the next occurrence of str2 in str1, decrement match_counter.
7. Finish when we break on shortest possible sequence or end of str1. Return result_string. Could be empty if there was no substring contained all chars from str2.

I actually quite like this solution, don't understand why it was down-voted. Assuming a Python dictionary is implemented as a hashmap, it's a very concise way of implementing the "hashmap with a count" idea.

Unfortunately that doesn't work, JustSteppedIn. Try it with the input 1, 2, 3, 5, 2, 2, 5, 3, 5, 3. The last element added to entries will be 5, not 1. That was why in my solution I kept track of "previously_seen" entries and potential "candidates" in separate unordered maps, adding entries to candidates but then deleting them if I saw them more than once. However matt.korwel pointed out that I didn't need to keep them in separate maps, I just needed to keep a count of how many times each one appeared and then iterate through to find the answer which only appears once at the end. Number of operations will increase linearly. In answer to the question 'Any other option without using "Contains"?', yes: use a container optimised for lookup, which is probably a hashmap. In C#, matt.korwel used a Dictionary, which checking the documentation appears to be implemented as a hashmap behind the scenes.

Could you explain how this code works please, as I don't understand it. What does "a[i]&;1" do? I don't recognise that syntax. Is it Java specific?

1) Use your preferred file i/o classes and libraries to read in the file. 2) Ignore "Name:"; find the token "favcolor=". 3) Read the string which follows it (worth clarifying how the file is formatted, i.e. is it white space separated). 4) If that string has not already been read, add it to your favourite map/ dictionary container of string, int, where the string is the key and int is the number of times you've seen that string in the file. 5) If it already exists in the container, find that key and increment its value. 6) Store the first string, int pair as "mostFavoriteColor". 7) If after incrementing a key it has a value which is greater than the value in mostFavoriteColor, set "mostFavoriteColor" = the more favored key, value. 8) When you've finished reading the file, print out mostFavoriteColor.

That will work, but it has an inner loop, so I think it's quadratic complexity, O(N^2). Also, unless the elements of the List are sorted as they are inserted, how is "Contains" implemented? According to the documentation I could find, "The List interface provides two methods to search for a specified object. From a performance standpoint, these methods should be used with caution. In many implementations they will perform costly linear searches." So for each element in the input you are potentially doing a linear search of the entries List to confirm it does not exist. If you think about the worst case, where you get input of the format 1,2,3,1,2,3,1,2,3,4, then you are doing a linear search for every single item in the input, and on top of that, you're comparing the first 1/3 of the input items to all later items in the input. For input of 10 items you'd be performing 3 * 3 comparisons; for input of 1,000,000 items you'd be performing 333,333 * 333,333 comparisons. Input size has gone up by 100,000 times, but worst case number of comparisons is 12,345,654,321 greater.

It's worth pointing out that there is a cost to having what are potentially two huge BitSets. The constructor must initialise the bits to 0 or this solution won't work. Assuming this is implemented as something like a memset of the values in an array to 0 then I would expect this to be lightning fast, as initialising memory to 0 is something computers do very well. The other issue is that you may have to compare 2147483647 bits when doing the xor, when you only actually set two of them. Again, comparing bits is something computers do very quickly, and compilers may be able to optimise, so I'm not sure this is a genuine issue. Running out of memory in a 64 bit world seems a more significant problem to me.

I'm not a Java person but I think this could work, as long as you had enough memory. If the data input is 1, 2147483647, 1, 1 then there's going to be a wee bit of unused memory, but if my calculations are correct then you're not going to run out on a modern system. It would almost certainly run out of memory if using large 64 bit integers though, so I'm not sure it's my preferred solution.

Interesting. Your final hash will be one third + 1 of the size of the input. My solution adds and then erases 1/3 of the input from my "candidates" hashmap, which is not ideal. So your solution does look more efficient than mine. My only other comment would be that I don't think hash.Single is helpful. Single must presumably iterate through the entire hashmap; hashmaps are not sorted by value, so how else can Single know that there is one and only one entry with value == 1? If you know that there can only be one value == 1 then rather than iterating through the entire hashmap you might as well stop iterating when you find the one example. Or you can iterate through the entire hashmap and report if there is more than value == 1, without having to handle the exception which Single would throw.

Does this actually work? If I read the code correctly it seems to compare the first character of string 1 with each character of string 2, then character 2 of string 1 with each character of string 2, etc. So I believe therefore that if comparing "xxx" with "xxy" it would get to a count of 6 and return false, which is not correct. It works with the examples in the original problem, but doesn't work with duplicates. It also makes a big assumption that the strings are three characters long; for example, with the strings "x" and "xy" I think it would count 1 (and therefore false); "xy" and "xz" would count 1 and return false; "wxyz" and "xyz" would count 3 and return false.

Nice. I haven't tested it but I like the idea, that the strings must match within 1 character. You could make the loop while(modificationCount < 2) though, as the result is never true if modificationCount > 1.

I believe this is linear time O(n), as lookup, insert, delete using hashmaps without collisions should be O(1). Works to find any unique values, it's not necessary that all multiple examples are in threes. It's assumed there is only one number which only appears once, but it's trivial to show multiple examples using a loop through "candidates" at the end.

int main()
{
    std::unordered_set<int> candidates;
    std::unordered_map<int,int> previously_seen;
    const int TEST_SIZE = 10;
    int test_data[TEST_SIZE] = { 2,3,5,1,2,2,5,3,5,3 };
    std::unordered_map<int, int>::iterator iter;

    for( int idx = 0; idx < TEST_SIZE; ++idx )
    {
        iter = previously_seen.find( test_data[idx] );
        if( iter != previously_seen.end() )
        {
            if( ++(iter->second) == 2 )
            {
                // if this is the second occurrence,
                // erase from candidates
                candidates.erase( iter->first );
            }
        }
        else
        {
            previously_seen.insert( std::make_pair(test_data[idx], 1) );
            candidates.insert( test_data[idx] );
        }
    }
    if( candidates.size() == 1 )
    {
        std::cout << "Answer is: " << *candidates.begin() << std::endl;
    }

    return 0;
}