由买买提看人间百态

boards

本页内容为未名空间相应帖子的节选和存档,一周内的贴子最多显示50字,超过一周显示500字 访问原贴
JobHunting版 - adobe coding Test
相关主题
那个skiplist的题谁来给谢谢这种牛逼的写法是实现Map接口的匿名内部类吗?
how to return two values in a C function?问一个min stack的
再发两道F电面题static initialization dependency c++ (转载)
几个多次被问到的c++问题请教[提供内推]Uber Maps Team is Hiring in Palo Alto
Analyst Information Technology (Lilly, IN)新鲜 interveiw questions
大家看看这个题目改怎么做。大家谈谈看???
[合集] 请教amd的面试怎么准备再问个C++题目
SQL find distinct values in large table (转载)用一个stack实现queue
相关话题的讨论汇总
话题: int话题: map话题: index话题: runs话题: rle
进入JobHunting版参与讨论
1 (共1页)
s***j
发帖数: 5
1
Let's write a new class called int_map which:
1 Is an associative map of int -> int
2 Has a size specified at construction, and all mappings from 0 to size-1
initialized to the same specified value
3 Supports get/set of individual mappings
Let's keep the interface simple:
class int_map
{
... member variables ...

public:
int_map(int num_values, int initial_val);

int get(int index) const;

void set(int index, int value);
};
Problem 1: Write this class using a std::vector.
Problem 2:
Let's suppose we expect the mapping to contain long spans of identical
values, and that run-length encoding the map will yield good storage gains:
class rle_int_map
{
struct run
{
int m_stop;
int m_value;
};

// The first run implicitly starts at 0; all subsequent runs start at
the previous run's m_stop
std::vector m_runs;

public:
rle_int_map(int num_values, int initial_val)
{
m_runs.push_back({ num_values, initial_val });
}

int get(int index) const
{
// It is illegal to pass in an invalid index, for the purposes of
this exercise we can
// just assert()
assert(0 <= index && index < m_runs.back().m_stop);

for (auto const& r : m_runs)
{
if (r.m_stop > index)
return r.m_value;
}
assert(false); // Shouldn't get here
}

void set(int index, int value)
{
???
}
};
Can you write a more efficient version of rle_int_map::get()?
Problem 3: Provide a correct implementation of rle_int_map::set().
求解第二第三问?谁能解释下m_runs struct 的作用
1 (共1页)
进入JobHunting版参与讨论
相关主题
用一个stack实现queueAnalyst Information Technology (Lilly, IN)
一道面试题大家看看这个题目改怎么做。
也来一道c++的题[合集] 请教amd的面试怎么准备
有面过knight的吗SQL find distinct values in large table (转载)
那个skiplist的题谁来给谢谢这种牛逼的写法是实现Map接口的匿名内部类吗?
how to return two values in a C function?问一个min stack的
再发两道F电面题static initialization dependency c++ (转载)
几个多次被问到的c++问题请教[提供内推]Uber Maps Team is Hiring in Palo Alto
相关话题的讨论汇总
话题: int话题: map话题: index话题: runs话题: rle