Interview Question
Software EngineersCountry: United States
Interview Type: Phone Interview
public int solution(int a[]) {
int start = 0, end = start + 1;
Set<Integer> dest = new HashSet<Integer>();
for (int i = 0; i < a.length; i++) {
if (a[start] == a[i] && i != 0) {
start++;
end = start + 1;
} else {
if (!dest.contains(a[i])) {
end = i;
}
}
dest.add(a[i]);
}
return end - start + 1;
}
{{
public int solution(int a[]) {
int start = 0, end = start + 1;
Set<Integer> dest = new HashSet<Integer>();
for (int i = 0; i < a.length; i++) {
if (a[start] == a[i] && i != 0) {
start++;
end = start + 1;
} else {
if (!dest.contains(a[i])) {
end = i;
}
}
dest.add(a[i]);
}
return end - start + 1;
}
}}
public int solution(int a[]) {
int start = 0, end = start + 1;
Set<Integer> dest = new HashSet<Integer>();
for (int i = 0; i < a.length; i++) {
if (a[start] == a[i] && i != 0) {
start++;
end = start + 1;
} else {
if (!dest.contains(a[i])) {
end = i;
}
}
dest.add(a[i]);
}
return end - start + 1;
}
public int solution(int a[]) {
int start = 0, end = start + 1;
Set<Integer> dest = new HashSet<Integer>();
for (int i = 0; i < a.length; i++) {
if (a[start] == a[i] && i != 0) {
start++;
end = start + 1;
} else {
if (!dest.contains(a[i])) {
end = i;
}
}
dest.add(a[i]);
}
return end - start + 1;
}
Just try to solver this tasks by memory :)
#pragma once
#include <map>
#include <vector>
#include <utility>
#include <limits>
namespace junk
{
namespace vacation_selector
{
class VacationSelector
{
public:
VacationSelector(const std::vector<std::pair<char, int>> &vacations)
: m_idx(0)
, m_size(0)
, m_value(INT_MAX){
process(vacations);
}
void process(const std::vector<std::pair<char, int>> &vacations)
{
// to identify unique set
std::map<char, int> flags;
for (const auto &v : vacations){
flags[v.first] = 0;
}
// use slow & fast runner
size_t slow = 0;
size_t fast = 0;
const size_t v_size = vacations.size();
do
{
bool is_full_set = true;
for (const auto &f : flags) {
if (f.second == 0){
is_full_set = false;
break;
}
}
if (is_full_set)
{
int curr = 0;
for (const auto &f : flags) {
curr += f.second;
}
if (m_value > curr)
{
m_idx = slow;
m_size = fast - slow;
m_value = curr;
}
flags[vacations[slow].first] -= vacations[slow].second;
slow++;
}
else
{
if (fast >= vacations.size()) {
return; // skip no full sets left
}
flags[vacations[fast].first] += vacations[fast].second;
fast++;
}
} while (true);
}
int min_idx() const { return m_idx; }
int size() const { return m_size; }
int value() const { return m_value; }
private:
int m_idx;
int m_size;
int m_value;
};
}
}
TEST(Array, MinCompleteSetInArray_VacationSelector_probe_a)
{
{
VacationSelector vacation(
{ {'A', 1}, {'A', 1 }, {'B', 2}, {'B', 2}, {'C', 4} }
);
EXPECT_EQ(vacation.min_idx(), 1);
EXPECT_EQ(vacation.value(), 9);
EXPECT_EQ(vacation.size(), 4);
}
{
VacationSelector vacation(
{ { 'A', 3 },{ 'A', 2 },{ 'A', 1 },{ 'A', 2 },{ 'A', 4 } }
);
EXPECT_EQ(vacation.min_idx(), 2);
EXPECT_EQ(vacation.value(), 1);
EXPECT_EQ(vacation.size(), 1);
}
{
VacationSelector vacation(
{ { 'A', 3 },{ 'B', 2 },{ 'C', 5 },{ 'A', 1 },{ 'B', 1 },{ 'B', 2 },{ 'C', 1 } }
);
EXPECT_EQ(vacation.min_idx(), 3);
EXPECT_EQ(vacation.value(), 5);
EXPECT_EQ(vacation.size(), 4);
}
}
class Solution(object):
@staticmethod
def solution(A):
start= end =i =0
b=set(sorted(A))
minDays=list()
while i < len(A) and end< len(b):
start= y= 0
c=b.copy()
B=A[i:]
end+=1
i+=1
while y <len(B) and len(c)>0:
try:
c.remove(B[y])
start=start+1
y+=1
except Exception, e:
start=start+1
y+=1
if len(c) ==0: minDays.append(start)
return minDays
- reganchan April 19, 2017