Victor
BAN USER- 7of 7 votes
AnswersGiven an array of integers.
- Victor in United States
Move all non-zero elements to the left of all zero elements.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 2of 2 votes
AnswersThere's a new language which uses the latin alphabet. However, you don't know the order among letters.
- Victor in United States
It could be:
a b c d ...
as it could also be:
b e z a m i ...
You receive a list of words lexicographically sorted by the rules of this new language. From this list, derive one valid particular ordering of letters in this language.| Report Duplicate | Flag | PURGE
Facebook Software Engineer Intern Algorithm - 1of 3 votes
AnswersImplement a vector-like data structure from scratch.
- Victor in Brazil
This question was to be done in C or C++.
Discussion topics:
1. Dealing with out of bounds accesses.
2. What happens when you need to increase the vector's size?
3. How many copies does the structure perform to insert n elements? That is, n calls to vector.push_back| Report Duplicate | Flag | PURGE
Google Software Engineer Intern Data Structures
This works, but the correct solution is using binary search to find indexes where each age begins.
Bear in mind your solution is O(n), whereas binary search is O(ylogn), where y is the number of distinct ages, ~130.
Roughly speaking:
O(n) = 6 x 10^9
O(ylogn) = 130 * log(6x10^9) = 4222
i, j, k are indexes. j is always i+1, k starts at i+2 and can increase.
Sort the input array in O(nlogn).
Given that A[i], A[j], A[k] start as A[i], A[i+1], A[i+2]:
First condition: A[i] < A[j] + A[k]. Always true since the array is sorted.
Second condition: A[j] < A[i] + A[k]. Again, always true since A[k] is alone greater than A[j.
Third condition: A[k] < A[i] + A[j]. This is where we need to iterate. We need to increment k until A[k] becomes greater or equal than A[i]+A[j]. This is where we stop the iteration and move on to the next step.
#include <vector>
#include <algorithm>
#include <iostream>
int trianglets(std::vector<int> input)
{
std::sort(input.begin(), input.end());
int num_trianglets = 0;
int i, j, k;
int N = input.size();
for (i = 0; i <= N-3; ++i) {
j = i+1;
num_trianglets += i;
for (k = j+1; k <= N-1; ++k) {
if (input[k] < input[i] + input[j]) {
++num_trianglets;
}
else {
break;
}
}
}
return num_trianglets;
}
Complexity: O(n^2) after sorting the array in O(nlogn).
We could maybe transform the inner loop into a binary search. Would it make it logn instead of n in practice? I'm not sure.
Sure.
Consider this example:
a b a e
b c d f
Suppose your first traversal gave the following path:
a b a e f d c b (which is the clockwise walk)
When you try another traversal, like going from the first a to the b just below:
a b
The natural next step would be going to the c (to the right of b), correct? This would give the following partial walk:
a b c
However, by this point you know that "abc..." will be worse than "abaefdcb" regardless of how to finish walking the grid, since c > a at the position 3. Therefore, you can cancel this walk.
This is the branch-and-bound technique.
Backtracking with branch-and-bound.
Perform every possible way of walking the grid, making sure you only execute valid steps. Store the best walk you've already come across.
At any given step, check if the current partial walk is leading to a better solution (by lexicographically comparing the partial string to the best string so far). If this partial walk is already worse than the best walk you found, no point in continuing, so cut this branch.
Thanks! Actually you can't have multiple edges from vertex A to B, otherwise you'd have a multigraph, not a graph.
When it's talked about graphs, very rarely it includes multigraphs. I believe the question would have made it explicit if multigraphs were allowed.
Problem is not very clear. Still, I came up with a solution.
Construct a graph where the vertices are the rooms, corridors, and fire exits; and the edges are the doors. Naturally these edges are directed in the same way as the corresponding doors.
For the floor design to be valid, any vertex of fire exit should be reachable from every vertex of room.
Reachability in planar graphs (which is the case here) can be computed in O(VlogV) using Thorup's Algorithm. An alternative could be regular DFS or BFS, but they are more expensive.
I would like to bring in a discussion about this problem.
I can think of two approaches:
1. for each year between 1900 and 2000, iterate through the list ahd check how many people were alive at that year. Return the max.
Complexity: O(ny), where n is the number of people and y is the number of years (1000).
This is better than sorting the list and keep a counter of how many people are alive. Why? Because O(ny) is very very likely to be less than O(nlogn), since n >> y.
2. A more clever solution is to use interval tree. However, it's not worth it in this case.
To build the interval tree, it would take O(nlogn): n insertions in the binary tree of intervals. Following the tree construction, we would need to perform y searches in the tree. Bear in mind however that search in interval tree for ALL conflicting intervals is not O(logn), but O(n) worst-case.
Complexity: O(nlogn) (interval tree construction) + O(ny) (searches)
This is a good example of how better data structures not always result in better solutions.
You achieved constant-time dequeue, but linear-time enqueue. While it works, it's not optimal.
There's a way to get constant-time enqueue and amortized constant-time dequeue using two stacks.
What if you kept one stack for enqueueing and the other for dequeueing?
Acyclic undirected graph:
V-1 edges. Spanning tree of the graph.
Acyclic directed graph:
Imagine the graph topologically sorted. It can only have edges going down (from top to bottom), otherwise it would have cycles.
The way to maximize the number of edges without creating cycles is to connect a given vertex to all other vertices that are below it (again, imagining the graph in a topological order). For instance, the vertex 0 is connected to 1, 2, 3, ..., V-1; vertex 1 to 2, 3, ..., V-1. So on and so forth.
Therefore, the total number of edges is: Sum (i=0 to V-1) i, which is equal to (V^2-V)/2.
This is a common kind of search in artificial intelligence. The time complexity is the same as DFS, O(b^h), where b is the branching factor (4 in this case = number of rules), and h is the height of the state space tree (edit distance between input and output).
In memory, it's also O(b^h). It can be problematic if we deal with large strings, however I believe it's worthy since we have the minimum number of steps by the first time we arrive at the output, as opposed to other kinds of search.
Furthermore, there is one question in the book about transforming one word into another by using only intermediary words that exist in the dictionary. The solution for that problem is very similar.
Launch a search over the state space using breadth-first search. Each state can branch to a maximum 4 more states, according to the rules defined.
You just need to be careful to store all states you already explored in order to avoid processing the same state more than once.
#include <iostream>
#include <string>
#include <deque>
#include <set>
// first: intermediate string; second: underscore position
typedef std::pair<std::string, int> StringPair;
// first: above; second: number of steps so far
typedef std::pair<StringPair, int> StatePair;
typedef std::deque<StatePair> Queue;
typedef std::set<std::string> StringSet;
int Swap(const std::string &input, const std::string &output)
{
Queue Q;
// Used to keep track of what states we have already explored
StringSet S;
// Position of the underscore
int us_pos = input.find('_');
StatePair p(StringPair(input, us_pos), 0);
Q.push_back(p);
unsigned strlength = input.length();
while (!Q.empty()) {
StatePair p = Q.front();
Q.pop_front();
const std::string state_string = p.first.first;
us_pos = p.first.second;
int len = p.second;
// Finished?
if (state_string == output)
return len;
// Have we already explored this state?
if (S.count(state_string)) continue;
S.insert(state_string);
std::string next_state_string;
// First branch
if (us_pos > 0) {
next_state_string = state_string;
next_state_string[us_pos] = next_state_string[us_pos-1];
next_state_string[us_pos-1] = '_';
p = StatePair(StringPair(next_state_string, us_pos-1), len+1);
Q.push_back(p);
}
// Second branch
if (us_pos < strlength-1) {
next_state_string = state_string;
next_state_string[us_pos] = next_state_string[us_pos+1];
next_state_string[us_pos+1] = '_';
p = StatePair(StringPair(next_state_string, us_pos+1), len+1);
Q.push_back(p);
}
// Third branch
if (us_pos > 1) {
next_state_string = state_string;
char c1 = next_state_string[us_pos-2];
char c2 = next_state_string[us_pos-1];
if (c1 != c2) {
next_state_string[us_pos] = c1;
next_state_string[us_pos-2] = '_';
p = StatePair(StringPair(next_state_string, us_pos-2), len+1);
Q.push_back(p);
}
}
// Fourth branch
if (us_pos < strlength-2) {
next_state_string = state_string;
char c1 = next_state_string[us_pos+2];
char c2 = next_state_string[us_pos+1];
if (c1 != c2) {
next_state_string[us_pos] = c1;
next_state_string[us_pos+2] = '_';
p = StatePair(StringPair(next_state_string, us_pos+2), len+1);
Q.push_back(p);
}
}
}
return -1;
}
Solution in C++. I read the string from right to left, but produce the new string from left to right, and reverse it in the end of the iteration.
using std::string;
string pattern(int input)
{
int current;
string output = "1";
for (current = 0; current < input; ++current) {
string new_output;
unsigned len = output.length();
int i = len-1;
int counter = 0;
int current_digit = 1;
int digit;
while (i >= 0) {
digit = output[i] - '0';
// Reset count
if (digit != current_digit) {
new_output.push_back(current_digit + '0');
string counter_str = std::to_string(counter);
std::reverse(counter_str.begin(), counter_str.end());
new_output.append(counter_str);
current_digit = digit;
counter = 1;
}
else {
++counter;
}
--i;
}
// Append last segment of the string
new_output.push_back(digit + '0');
string counter_str = std::to_string(counter);
std::reverse(counter_str.begin(), counter_str.end());
new_output.append(counter_str);
std::reverse(new_output.begin(), new_output.end());
std::cout << new_output << "\n";
output = new_output;
}
return output;
}
Sort both lists and traverse the two lists at the same time performing linear matching. This traversal uses one cursor on each list. They move forward until one of them reaches the end, which dictates the end of the algorithm.
In Python:
bolts = [...]
nuts = [...]
bolts.sort()
nuts.sort()
i = 0
j = 0
matches = 0
while i < n and j < n:
compare = check(bolts[i], nuts[i])
if compare == EQUAL:
# We found a match
matches = matches+1
i = i+1
j = j+1
elif compare == SMALLER:
# Proceed to the next bolt
i = i+1
else:
# Proceed to the next nut
j = j+1
Sorting is O(nlogn) with heap sort, while the traversal is O(n).
Edit: this solution is wrong. We aren't allowed to compare nuts with nuts and bolts with bolts.
This solution is similar to the 2-sum algorithm, used to see whether any two values of a sorted array sum to a specific number.
In this case, however, the lower bound is zero, while the upper bound is the square root of N. We set a cursor on the lower bound, and it only moves in +1 steps. Also, we set another cursor on the upper bound, and it only moves in -1 steps.
Whenever the sum of squares is greater than N, we need to decrease the sum. In order to do so, we move the upper cursor down (j = j-1). Whenever the sum is lower than N, we move the lower cursor up (i = i+1). Else, when we find a match, we move both.
import sys
import math
n = int(sys.argv[1])
root = math.sqrt(n)
floor = int(root)
i = 0
j = floor
while i <= j:
sqsum = i**2 + j**2
if sqsum == n:
print i, j
i = i + 1
j = j - 1
elif sqsum > n:
j = j - 1
else:
i = i + 1
This algorithm is O(n) loose, which is way better than the naive approach of two nested fors.
- Victor November 18, 2014Model it as a graph, where each coordinate in the grid has a respective node. You can disconsider the coordinates containing no mine (= 0).
Add edges between neighboring 1s in the grid. After this step, you'll have the grid represented as an disconnected graph. Then, just find the number of graph components by using any graph traversal algorithm, such as DFS.
You just need to use a binary search over the array looking for zeros. Whenever it finds one, just check whether the element to the right is also a zero.
Note however that you do not gain anything by using divide and conquer in this problem. It may incur additional cost even, since the DaC paradigm brings in more space complexity due to the call stack.
An implementation in C:
int count(const int *V, int s, int e, int n)
{
if (e < s) return 0;
int counter = 0;
int mid_idx = (s+e)/2;
if (V[mid_idx] == 0) {
if (mid_idx < n && V[mid_idx+1] == 0) {
++counter;
}
}
return counter + count(V, s, mid_idx-1, n) +
count(V, mid_idx+1, e, n);
}
int main(int argc, char *argv[])
{
int V[] = {3, 0, 0, 1, 0, 1, 3, 2, 0, 0, 0, 1, 2};
int n = sizeof(V)/sizeof(int);
printf("%d\n", count(V, 0, n-1, n-1));
return 0;
}
Build a Trie (suffix tree) of substrings that are present in the input string.
Whenever you come across a substring of length between K and L, insert this substring as a key in your trie. If it's already present, increment its counter which representes the number of occurrences.
You need to be careful about the distinct characters. Always check how many distincts chars you have used so far to form a substring, and abort a substring composition when this happens.
By the time you end inserting substrings in your Trie, you'll just need to traverse it looking for the highest occurrence counter.
N = length(input string)
for i = 0 to N-1:
for j = K to L:
substring = input.substr(i, j)
if (substring.distincts() > M)
break
Trie.insert(substr)
return Trie.get_highest_counter()
This code can be more optimized. Naturally you don't need to construct a whole another substring from scratch when you just need one char appended to it. But you get the idea.
Complexity: O(NL)
Repjennykyiler, Area Sales Manager at AMD
Jenny , an Assistant Secretary with a track record of employer satisfaction in performing various administrative tasks, and completing visual presentations ...
RepBimerLaura, Area Sales Manager at Bloomberg LP
I am a Job training specialist conducting training programs that will boost employees workplace performance in alliance with the company ...
RepJessicaHanda, Front-end Software Engineer at ABC TECH SUPPORT
Jessica , hard-working Packer with a strong determination to finish all assignments in a timely manner. I have joined a few ...
Repsarahchannah745, Android Engineer at ASAPInfosystemsPvtLtd
Hello, I am an information records clerk.We are responsible for maintaining their company records in a complete and orderly ...
Repgeachfadden9, cox customer service at Chicago Mercantile Exchange
Geach, my responsibilities include making travel and meeting arrangements, preparing reports and maintaining appropriate filing systems. I have excellent oral ...
Repddmohsi890, Associate at Abs india pvt. ltd.
Working as a Photographic processing machine operator at Cardinal Stores for almost 10 years . I have lots of experience in ...
Repsushiswla65, Area Sales Manager at ABC TECH SUPPORT
My name is SarahProctor . I am working as a Video editor at Konsili . I am exploring some magical tricks . vashikaran ...
Assuming that nodes in the BST hold counters for the number of elements in each of its subtrees. This is pretty much the approach zortlord presented but did not code.
In C:
- Victor December 04, 2014