nilukush
BAN USER- 1of 1 vote
AnswersYou are given an array / sequence of colors. In this sequence / array, find a couple (both colors adjacent to each other) which are same color. Now, remove that pair. Now, after this removal, if there are further couple of same color then remove that as well and so on.
For a given array / sequence of colors, find the maximum number of couples.
- nilukush in IndiaFor eg., consider following array of colors : R G B B G R Y 1. BB is one couple, so remove it : R G G R Y 2. GG is one such couple after removing BB, so remove it : R R Y 3. RR is one such couple, so remove it : Y So, the maximum number of couples is 3. Input : Y R G G R R G G R Y Output : 5 (maximum number of couples)
| Report Duplicate | Flag | PURGE
Groupon Senior Software Development Engineer Algorithm - 0of 0 votes
AnswersYou are given a matrix. Starting from [0, 0], you have to move over the matrix in clockwise-spiral direction, i.e., we start from [0, 0], move upto [0, 4], and then move to [3, 4], then move to [3, 0], then move to [1, 0], then to [1, 3] and so on.
Move in this way and print all the elements.
- nilukush in IndiaInput : 1 2 3 4 5 6 8 9 a b c d e f g h i j k l Output : 1 2 3 4 5 b g l k j i h c 6 8 9 a f e d
| Report Duplicate | Flag | PURGE
Groupon Senior Software Development Engineer Algorithm - 1of 1 vote
AnswersFlipkart handles millions of users looking to buy or sell products. It also provides a search bar to the user as an interface to search for items. At times when typing users may enter a query string which may be single word by mistake but the intention of the user was to type them separately. For eg.,
- nilukush in India
User may have entered flipkartmobile when in real, his / her intention was to search for flip kart mobile.
Considering above scenario, implement an algorithm to split up query string provided by user given a list of dictionary words, i.e, you will be given a list of dictionary words and the user-input query string and you have to give the split up of query string which satisfies the following requirements / properties :
1. In case of multiple split-ups, conclude on the one that is lexicographically smaller, i.e, has spaces more towards the left. For eg.,
Assume you are given the list of words : flip, kart, flipkart, mobile and user-input query string is flipkartmobile. Hence, possible split-ups are flip kart mobile and flipkart mobile. The answer / output in this case should be flip kart mobile with more spaces towards the left.
2. Number of characters in query string shall be < 500 characters. Reason being hackers may try to provide a very long input and hence, this may consume processing and result in unresponsive website ultimately.
3. Repetition of dictionary words in query string is possible. For eg.,
Assume you are given the list of words : lg, mobile and user-input query string is mobilelglg. The answer / output in this case should be mobile lg lg.
Now, format of Input and Output :
Input
4 // number of dictionary words given
flip // list of dictionary words the number equaling to input above
kart
flipkartmobile
flipkartmobile // user-input query string
Output
flip kart mobile| Report Duplicate | Flag | PURGE
Flipkart SDE-2 Algorithm - 3of 3 votes
AnswersConsider an array of integers wherein each element is +1 or -1 its preceding element. Given a number, find the first occurence of this number (index) in this array without using linear search.
- nilukush in India for World Wide Operations
For example, consider the array :
4 5 6 5 6 7 8 9 10 9 10 (each element in this array is +1 or -1 its preceding element)
Input : 10 (find first occurence of 10 without using linear search)
Output : 8| Report Duplicate | Flag | PURGE
Amazon SDE-2 Algorithm Arrays
There are multiple combinations by which a subset can be formed with sum equal to given sum. Hence, this problem is exponential.
Now, think of it this way : We start from first number (1 in given example), and combine it with remaining elements on right side of this number (3, 5, 2, 7), i.e, {1, 3}, {1, 5}, {1, 2}, {1, 7}. Now, we check if the sum of this set is equal to given sum. If yes, then add that set to solution set.
If not then just return an empty set. Do the above recursively, hence, in next iteration, we will have {1, 3, 5}, {1, 5, 2}, {1, 2, 7} - among these {1, 2, 7} is equal to given sum, hence this will be added to solution set. Again in next iteration, {1, 3, 5, 2} (> 10), {1, 5, 2, 7} (> 10) will be discarded as they are greater than given sum.
The above process is only for number 1. Then move onto next numbers 3, 5, 2 and 7 and repeat the above recursively.
#include <iostream>
#include <deque>
namespace
{
typedef std::deque<int> array;
typedef std::deque<int> set;
typedef std::deque<std::deque<int>> subsets;
}
class subsets_equal_sum
{
public :
std::deque<std::deque<int>> operator()(const std::deque<int>& a, const int& s)
{
if(a.empty()) return std::deque<std::deque<int>>();
return find_subsets_equal_sum(a, s, std::deque<int>(), 0);
}
std::deque<std::deque<int>> find_subsets_equal_sum(const std::deque<int> a, int s, std::deque<int> ps, size_t start)
{
if(s == 0)
{
subsets t;
t.push_back(ps);
return t;
}
if(s < 0) return std::deque<std::deque<int>>();
if(start == a.size()) return std::deque<std::deque<int>>();
subsets ss;
for(; start < a.size(); ++start)
{
set sp(ps.begin(), ps.end());
sp.push_back(a[start]);
subsets sst(find_subsets_equal_sum(a, s - a[start], sp, start + 1));
ss.insert(ss.end(), sst.begin(), sst.end());
}
return ss;
}
};
int main()
{
array a{1, 3, 5, 2, 7};
subsets_equal_sum ses;
std::cout << "\n[";
subsets ss(ses(a, 10));
for(size_t ssi(0); ssi < ss.size(); ++ssi)
{
std::cout << "{";
for(size_t si(0); si < ss[ssi].size(); ++si) std::cout << ss[ssi][si] << ((si == (ss[ssi].size() - 1)) ? "" : ", ");
std::cout << ((ssi == (ss.size() - 1)) ? "}" : "}, ");
}
std::cout << "]";
return 0;
}
How about the following approach? Let us assume the two sets of numbers are first and second.
* Let f point to start of first and s point to start of second;
1. if first[f] == second[s] { add first[f] to common list; increment f; increment s; }
2. if first[f] < second[s] increment f;
3. if first[f] > second[s] increment s;
* Repeat 1 - 3 until f < size of first && s < size of second
Pseudo code as :
set_common c;
for(size_t fi(0), si(0); (fi < first.size()) && (si < second.size());)
{
if(first[fi] == second[si]) { c.push_back(first[fi]); ++fi; ++si; }
else if(first[fi] < second[si]) ++fi;
else if(first[fi] > second[si]) ++si;
}
As mentioned by others, you can use modified binary search to search for elements. There are three cases :
* middle element == number whose start, end index has to be found
If number after middle element is also the search number, then search in right half
If number before middle element is also the search number, then search left half
* If middle element is less than search number, then search in right half
* If middle element is greater than search number, then search in left half.
Based on above algo, following is a recursive implementation of the same :
#include <iostream>
#include <deque>
#include <utility>
namespace
{
typedef std::deque<int> array;
typedef std::pair<int, int> startend;
}
class find_range
{
public :
std::pair<int, int> operator()(const std::deque<int>& a, const int& n)
{
// No elements to search
if(a.empty()) return std::make_pair(-1, -1);
int start(-1), end(-1);
size_t l(0), r(a.size() - 1);
find_range_r(a, l, r, n, start, end);
return std::make_pair(start, end);
}
private :
void find_range_r(const std::deque<int>& a, size_t l, size_t r, const int& n, int& s, int& e)
{
if(l > r) return;
if(r > (a.size() - 1)) return;
size_t m(l + (r - l) / 2); //std::cout << "\nl" << l << " m" << m << " r" << r << " s" << s << " e" << e << " a[m]" << a[m] << " n" << n;
if(a[m] == n)
{
if(m == 0) s = static_cast<int>(m);
else if((m - 1) >= 0)
{ if((a[m - 1] != n)) s = static_cast<int>(m); }
else s = static_cast<int>(m);
//std::cout << "\nsafter" << s;
if((m + 1) <= (a.size() - 1))
{ if((a[m + 1] != n)) e = static_cast<int>(m); }
else { e = static_cast<int>(m); }
//std::cout << "\neafter" << e;
if((s != -1) && (e != -1)) return;
if(((m - 1) >= 0) && (a[m - 1] == n)) find_range_r(a, l, m - 1, n, s, e);
if(((m + 1) <= (a.size() - 1)) && (a[m + 1] == n)) find_range_r(a, m + 1, r, n, s, e);
}
else if(a[m] < n) { find_range_r(a, m + 1, r, n, s, e); }
else if(a[m] > n) { find_range_r(a, l, m - 1, n, s, e); }
}
};
int main()
{
array a{0, 2, 3, 3, 3, 10, 10};
startend se(find_range()(a, 3));
std::cout << "\n(" << se.first << ", " << se.second << ")";
array a_2{0, 2, 3, 3, 3, 10, 10};
startend se_2(find_range()(a_2, 6));
std::cout << "\n(" << se_2.first << ", " << se_2.second << ")";
array a_3{0, 2, 3, 3, 3, 10, 10};
startend se_3(find_range()(a_3, 10));
std::cout << "\n(" << se_3.first << ", " << se_3.second << ")";
array a_4{0, 2, 3, 3, 3, 10, 10};
startend se_4(find_range()(a_4, 0));
std::cout << "\n(" << se_4.first << ", " << se_4.second << ")";
array a_5{0, 2, 3, 3, 3, 10, 10};
startend se_5(find_range()(a_5, 2));
std::cout << "\n(" << se_5.first << ", " << se_5.second << ")";
array a_6{0, 0, 2, 3, 3, 3, 10, 10};
startend se_6(find_range()(a_6, 0));
std::cout << "\n(" << se_6.first << ", " << se_6.second << ")";
array a_7{0, 2, 2, 2, 3, 3, 3, 10, 10};
startend se_7(find_range()(a_7, 2));
std::cout << "\n(" << se_7.first << ", " << se_7.second << ")";
array a_8{0, 2, 2, 2, 3, 3, 3, 10, 10, 10};
startend se_8(find_range()(a_8, 10));
std::cout << "\n(" << se_8.first << ", " << se_8.second << ")";
array a_9{0, 2, 2, 2, 3, 3, 3, 10, 10, 10};
startend se_9(find_range()(a_9, 12));
std::cout << "\n(" << se_9.first << ", " << se_9.second << ")";
array a_10{0, 2, 2, 2, 3, 3, 3, 10, 10, 10};
startend se_10(find_range()(a_10, -1));
std::cout << "\n(" << se_10.first << ", " << se_10.second << ")";
array a_11;
startend se_11(find_range()(a_11, 3));
std::cout << "\n(" << se_11.first << ", " << se_11.second << ")";
array a_12{1};
startend se_12(find_range()(a_12, 1));
std::cout << "\n(" << se_12.first << ", " << se_12.second << ")";
array a_13{1, 2};
startend se_13(find_range()(a_13, 1));
startend se_14(find_range()(a_13, 2));
std::cout << "\n(" << se_13.first << ", " << se_13.second << ")";
std::cout << "\n(" << se_14.first << ", " << se_14.second << ")";
return 0;
}
Assuming that all numbers in the dictionary are unique, let us first sort the dictionary - {1, 4, 5}.
In the dictionary {1, 4, 5} :
Is number 451 starting from 1 (in dictionary)? No - so the number starting from 1 are 2! = 2. ----> n1
Is the number 451 starting from 4(in dictionary)? Yes - Remove 4 from dictionary
Mark 4 in 451 as processed and now start from 5 and follow the below procedure :
In the dictionary {1, 5}:
(number is 51 as 4 has been marked processed)
Is the number 51 starting from 1(in dictionary)? No, so all numbers starting with 41 are 1! = 1 ---> n2
Is the number 51 starting from 5(in dictionary)? Yes, remove 5 from dictionary
Mark 5 as processed in 451 and follow the below procedure :
In the dictionary {1} :
(number is 1 in below as 5 has been marked as processed)
Is the number 1 starting from 1(in dictionary)? Yes, remove 1 from dictionary
Mark 1 as processed
In the dictionary {} :
Dictionary is empty now, so return 1 + n1 + n2 (see n1, n2 above) which is 1 + 2 + 1 = 4. So, rank of 451 is 4.
Assuming that all numbers in the dictionary are unique, let us first sort the dictionary - {1, 4, 5}.
In the dictionary {1, 4, 5} :
Is number 451 starting from 1 (in dictionary)? No - so the number starting from 1 are 2! = 2. ----> n1
Is the number 451 starting from 4(in dictionary)? Yes - Remove 4 from dictionary
Mark 4 in 451 as processed and now start from 5 and follow the below procedure :
In the dictionary {1, 5}:
(number is 51 as 4 has been marked processed)
Is the number 51 starting from 1(in dictionary)? No, so all numbers starting with 41 are 1! = 1 ---> n2
Is the number 51 starting from 5(in dictionary)? Yes, remove 5 from dictionary
Mark 5 as processed in 451 and follow the below procedure :
In the dictionary {1} :
(number is 1 in below as 5 has been marked as processed)
Is the number 1 starting from 1(in dictionary)? Yes, remove 1 from dictionary
Mark 1 as processed
In the dictionary {} :
Dictionary is empty now, so return 1 + n1 + n2 (see n1, n2 above)
It should be possible to use a FIFO mutex as well to solve this problem. It allows the mutex to be passed to next thread in queue.
Where to use :
Assume two threads T1 and T2 are trying to execute a critical section. Both don't have much to do outside this critical section and hold locks for a good amount of time. So, T1 may lock, execute and unlock and signal T2 for wakeup. But before T2 could wakeup and acquire lock, T1 reacquires lock and execute. In this way, T2 may have to wait a very long time before it actually gets the lock or may be not.
How it works / How to implement :
Have a mutex to lock on. Initialize Thread Specific Data (TSD) for each thread to a node containing thread id and semaphore. Also, have two variables - owned (TRUE or FALSE or -1), owner (owner thread id). In addition, keep a waiters queue and a pointer waiterLast pointing to last node in waiters queue.
lock operation :
node = get_thread_specific_data(node_key);
lock(mutex);
if(!owned)
{
owned = true;
owner = self;
return success;
}
node->next = nullptr;
if(waiters_queue == null) waiters_queue = node;
else waiters_last->next = node;
waiters_last = node;
unlock(mutex);
sem_wait(node->semaphore);
lock(mutex);
if(owned != -1) abort();
owned = true;
owner = self;
waiters_queue = waiters_queue->next;
unlock(mutex);
unlock operation :
lock(mutex);
owner = null;
if(waiters_queue == null)
{
owned = false;
return success;
}
owned = -1;
sem_post(waiters_queue->semaphore);
unlock(mutex);
template<typename T>
struct node_traits
{
typedef typename T type_value
typedef typename const T type_value_const;
typedef typename T& type_ref;
typedef typename const T& type_ref_const;
typedef typename T&& type_rref;
typedef typename const T&& type_rref_const;
typedef typename T* type_ptr;
typedef typename const T* type_ptr_const; // pointer to const
typedef typename const T* const type_const_ptr_const; // const pointer to const
typedef typename T* const type_const_ptr; // constant pointer to non-const
typedef std::shared_ptr<node> link;
};
template<typename T>
struct node
{
public :
typedef node_traits<T>::type_value type_value;
node(const T& x) : item(x) { l.reset(); r.reset(); }
private :
T item;
std::shared_ptr<node> l, r;
};
template<typename T>
class bst
{
public :
typedef node_traits<T>::link link;
friend void swap(link a, link b);
bst() { head.reset(); }
// ...
link mirror()
{
return mirrorR(head);
}
private :
// ...
link mirrorR(link h)
{
if(h == 0) return std::nullptr;
mirrorR(h->l);
mirrorR(h->r);
swap(h->l, h->r);
}
link head;
}
void swap(link a, link b)
{
link t(a);
a = b;
b = t;
}
I will approach the problem a little differently and conclude on the design of data structure required to support request as per question.
Let us assume that there is a server component which is going to serve the request. Assuming a client / server architecture, let us assume following plain old objects (poo) specification (Meaning - below will also have corresponding DB representations) :
class poo_user
{
long user_id; // maybe MD5 hash
// other details
}
class poo_ws_page
{
long ws_page_id; // maybe MD5 hash
}
class poo_website
{
long website_id; // maybe MD5 hash
sequence<poo_ws_page> list_ws_page; // may translate to ws_page_id in DB code
sequence<date> date_visited;
}
// data structure in code to support the request based on above specification
unordered_multimap<poo_user, poo_website> user_website;
Also, if followed the reverse logic, the starting node will point at end node of original linked list and the traverse will happen in backward direction, i.e, now starting pointer of reversed list and starting pointer of original list will be incremented and corresponding values increased.
- nilukush September 04, 2013Assuming 'a' is the array and 'n' is the size of 'a', we can get result in the following manner :
1. Start from index 0.
2. Check if for (index % 2 == 0), then a[index] > 0; if yes, then continue.
3. Check if for (index % 2 != 0), then a[index] < 0; if yes, then continue.
4. if for (index % 2 == 0) a[index] < 0; then add a[index] to QUEUE_NEG and continue in search of a +ve number (say, found_pos) and mark found index (found_index - position of found_pos) as EMPTY.
5. When found, do a[index] = found_pos.
6. If for (index % 2 != 0) a[index] > 0; then add a[index] to QUEUE_POS and continue in search of a -ve number (say, found_neg) and mark found index (found_index - position of found_neg) as EMPTY.
7. When found, do a[index] = found_neg.
8. If for (index % 2 == 0), a[index] = EMPTY, then do a[index] = QUEUE_POS.pop().
9. If for(index % 2 != 0), a[index] = EMPTY, then do a[index] = QUEUE_NEG.pop().
Advantage over the approach to having 2 QUEUEs from the start is that both QUEUE_POS and QUEUE_NEG may not store all the elements in average case, although in worst case it would be the same as the approach of having 2 QUEUEs from the start with positive and negative numbers separated out by scanning the array although with the approach described here, there would be no scanning and QUEUE will grow dynamically.
I implemented it using the following algorithm :
1. For each dictionary word, find the index of all occurences in query string (could be repetitions of dictionary words in query string as explained). Add this index and corresponding word in a map.
2. After this, there will be a map with indexes of all occuring dictionary words in query string.
3. Iterate through map (since map will have its keys sorted in C++) take each word and concatenate it. If the result of concatenation is not query string then, output "NULL".
At the same time, concatenate each word from map with space. In the event that result from above equals query string, then output this concatenation of words with spaces.
Following is the code snippet :
#include <iostream>
#include <deque>
#include <string>
#include <map>
namespace
{
static const size_t& MAX_QUERY_LENGTH(500);
}
int main() {
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
std::size_t dict_size;
std::deque<std::string> dict;
std::string query;
std::string output("NULL");
// read input
std::cin >> dict_size;
for(std::size_t i(0); i < dict_size; ++i)
{
std::string word;
std::cin >> word;
dict.push_back(word);
}
// limit query string to allowed MAX_QUERY_LENGTH
std::cin >> query;
if(query.size() > MAX_QUERY_LENGTH)
{
query.erase(MAX_QUERY_LENGTH);
}
std::map<std::size_t, std::string> index_word_map;
for(std::deque<std::string>::const_iterator dict_iter(dict.begin()), dict_end(dict.end()); dict_iter != dict_end; ++dict_iter)
{
std::string::size_type pos(0);
for(;(pos = query.find(*dict_iter, pos)) != std::string::npos;)
{
std::map<std::size_t, std::string>::iterator iwm_iter(index_word_map.find(pos));
if(iwm_iter == index_word_map.end())
{
index_word_map.insert(std::make_pair<std::string::size_type, std::string>(pos, *dict_iter));
}
else
{
std::string& word(iwm_iter->second);
if(word.size() > dict_iter->size())
{
word = *dict_iter;
}
}
pos += dict_iter->size();
}
}
std::string present, splitup;
for(std::map<std::size_t, std::string>::iterator iwm_iter(index_word_map.begin()),
iwm_end(index_word_map.end()); iwm_iter != iwm_end; ++iwm_iter)
{
present += "" + iwm_iter->second;
splitup += iwm_iter->second + " ";
}
if(present == query)
{
output = splitup;
}
std::cout << output;
return 0;
}
There is one more requirement / property that algorithm should satisy which I missed in above question :
4. If there is no match based on mentioned 3 properties / requirements, then output should be "NULL". For eg.,
Assume you are given the following list of words : mobile, flip, kart, flipkart and user-input query string is flipkartmobilenotpresent. In this case, the answer / output should be "NULL" as no split-up is possible based on given dictionary words.
Rep
RepGayle L McDowell, CEO at CareerCup
Gayle Laakmann McDowell is the founder / CEO of CareerCup, which provides programming interview prep for candidates interviewing with Microsoft, Google ...
Rep
Replucas.eustaquio, Software Engineer / Developer
Because I like challenges.
I am able to think of two solutions :
First one :
Second one :
Test cases :
- nilukush July 17, 2014