z**0
发帖数: 618 | 1 有没有不用双屏幕的，直接用pc remote来按数字键来选歌，然后画面上用小字体显示
播放列表?
另外礼光的歌曲管理软件界面全是问号(英文版xp，区域设中国，缺省non ascii code
page也是设成中文)，是不是非要用中文版系统才行?
谢谢! |
|
i**p
发帖数: 205 | 2 距信几乎和人一起到家. 把能想得起来的技术问题贴出来, 希望对大家有用.
1. 已知 bst 和两个数, count 在此范围内的节点. recursive and non-recursive
2. 打印任意树里所有path, for example:
1
/ \
2 3
output:
1
1,2
1,3
how about do it level by level
3. output bst height, height 的定义是从root 到leaf 的边数
4. 一只青蛙要跳到河对岸去,河被分割成若干cells, 每个cell可能有石头,可能没有.
青蛙最多跳3步. 写一个function告诉青蛙能不能跳到对岸.
5. match two strings (may be inexactly), 你能想出多少可能的方法, implement
one of them
6. 一个等边三角形里有5个点, 有没有可能任意两点的距离都大于二分之一边长,
prove it
7. 有一种奇怪的语言(therefore it's not ASCII), 已知char |
|
H*M
发帖数: 1268 | 3 1. if one number is missing, we can sum them up and compute the difference;
if more is missing, maybe we need hash table?
2.keep an array of bool for all ASCII chars
We loop from the beginning, if we see a new element, check if it already a
ppeared, if not mark the array; if yes, delete it.
I think the key is do it in O(n) time. We can not simply delete each char.
We need to keep two pointers, one for one element past the clean section,
one pointer to the current index.
wha
more |
|
N*D
发帖数: 3641 | 4 第一题BST怎么弄？array就完了，a-z的话就是O(26)space，算上A-Z就是O(52)，ascii
做相应扩展，Unicode就用Hash，BST是没法做，她存心刁难你呢，当然你给了她机会。
二三也是正常题目倒看不出刁难的地方来。
Bless。。。
第一个面试官是个中国人，女的。
开始想同她套套近乎，也不知道是不是套错了，反正感觉她不喜欢我。
编程题
given a character string, print the number of occurence of each charcater in
order. ie. if the string is "ceabcw", then you should print something like:
a 1 b 1 c2 e 1 w 1.
she asked the possible data strucutre to approach. I gave array, hashtable,
and BST. she asked me to use BST, and using no recursive. I tried a |
|
c*********e
发帖数: 252 | 5 关于Unicode就用Hash，这个如果要求按顺序打印如何处理呢？
ascii
in
like: |
|
v****s
发帖数: 1112 | 6 第一题如果字母都是ascii，用一个 counter[currentchar - 'a']++ 不就可以了么？
复杂度为O(N).为啥要bst？解释一下谢谢！
另外，怎么处理OF? 是不是
if( tmp >= MAX_INT ) { return；}
谢谢share 题目！
in
like:
,
guys |
|
s*****i
发帖数: 355 | 7 有重复的就计数器加一。用ascii bitmap的方法比较好 |
|
d****v
发帖数: 458 | 8 具体说一下什么是 ascii bitmap啊
用计数器这就涉及到上面说的true bias的时候第二个很长的可以不全遍历了吧 |
|
b****y
发帖数: 278 | 9 本人菜鸟， 请教一个C++ 问题，
对n个字符串，进行比较时，要求忽略大小写， 有没有什么快速的方法？ 用ASCII码转
换太慢了
多谢了 |
|
r********g
发帖数: 1351 | 10 不用ASCII怎么能认出来是同一个字母的大小写呢？
算法是另一个方面，我觉得hashtable最好了。 |
|
b****y
发帖数: 278 | 11 对， 我也想用hash table
不过，需要让“acd”,"Acd","ACD", 产生同样的key;
您是怎样用ASCII？ 假设一个个字母地把他们转化成 都小写是不是太费时了？ |
|
l*********r
发帖数: 26 | 12 来自主题: JobHunting版 - 面经+求助 amazon电话两轮，隔的时间比较长，把记得的题目贴一下
1.java gabage collector, how to work?
2.java, final, finally, finalize()的用法和区别
3. 怎样serialize一个binary tree, general tree(not binary)
4. N way merge sort
剩下主要是简历上面的东西，觉得amamzon的重点就是 scalability,总是问以前的
project如果upgrade scalability会怎么样。
要去onstie, 看到大家以前总是频繁的要求些hashtable, 请问是应该写哪种collision
solutions呢？changing, linear probing? 如果hash string,hash function 就用
ascii码的那个常用方法可以嘛？ 如果是数字，就取 %?
记得以前大家讨论过一个手机键盘输入的pop-up菜单的设计题，好像要写trie， 怎么
也找不到，完全不明白题目的意思，请大侠们指点一下。
回来贴面经:) |
|
j**l
发帖数: 2911 | 13 你的思路其实说到一种情况，就是已知取值的范围。这种情形也可以用数组（桶）来代
替Hash表的，每个Key直接作为下标去查找。比如对于ASCII字符，你用一个256大小的
数组就可以了。如果数值范围小，这种方法比Hash表还要快。但是这种方法可能会浪费
一些空间，而Hash表的好处就是只存储实际用到的元素。在PIE(Programming
Interview Exposed)一书中介绍Hash表的时候比较过了这两种方法。 |
|
j***i
发帖数: 1278 | 14 怎样让resume 粘贴的好看，
有没有好的排版工具，我用word贴过来 格式改的好麻烦 |
|
f****e
发帖数: 30 | 15 已经挂了。为下周google onsite求祝福
(1) 数组去duplicates
(2) 防火墙存了一组ip,进来一个ip，怎么查找在不在list里面。
给了hash solution,然后问，假设很多ip都是从amazon出来，他们前面两个byte的值一
样，这种情况怎么办。他期望的solution是trie,这里我有点不明白，因为你没有任何
先验知识这些ip是从一个地方不同机器出来的，难道观察trie每个节点下面有多少个
subtree,如果subtree数目==256，就把这些都剪了，然后加个mask?
(3) 一个大ascii文件，怎么样随机采样其中一行。然后问我怎么提高。
原来的算法只要scan文件一边，用一行的space,实在不觉得能改进。最后给了近似解，
用文件大小估计有多少个char,然后随即产生一个数，把文件指针指向相应的char,把那
一行剩下的都读出来。 |
|
m*******i
发帖数: 370 | 16 如果从command line输入一个text string，长度不超过n，比如n是32 bytes或者64
bytes
输入的格式是 account "usr1" "###usr1" "us*&ss"
double quote(")里面的是account name，这个name可以是任何printable AscII
character，除了double quto (")和 forward slash (/).
要求设计test case，除了输入一个正常的account name test一下能不能accept，比如
account "abc" 还有什么test case要设计啊？
多谢了！ |
|
Z*****Z
发帖数: 723 | 17 这样做可不可以？
假设ASCII字符，范围0-255。
假设做给字符集合c1，c2，...ck
用一个大小为256的int数组T记录当前所查找的子字符串包含给定字符的情况。
T[*] = -1;
T[ci] = 0;
用一个整数变量d记录未找到字符个数
d = k;
两个指针p，q
第1步，找到第一个符合条件的子字符串
第1.1步，找到第一个符合条件的子字符。用p从头扫描给定字串，如果不在给定字符集
合中，重复1.1。否则到1.2
第1.2步，假设p指向cj，那么T[cj]++，d--，q指向p+1
第1.3步，用q向后扫描寻找剩下的字符，每次找到一个cl，则：
if(T[cl] == 0){
d--;
}
T[cl]++
第1.4步，重复1.3直到到达所给字符串末尾（不存在那样的子串），或者d变成0（找到
第1个符合条件的子串）
记录当前子串长度L，
第2步，扫描剩下的字串，寻找更优解
第2.1步，用q继续向后扫描，每次发现cj，则T[cj]++，到2.2
第2.2步，
while(T[*p] != 1){
if(T[*p] > 1){
|
|
Z*****Z
发帖数: 723 | 18 这个算法有点小问题。
这是改进之后的算法实现。
请拍
public class ShortestSubString {
/**
*
* ASCII characters are assumed here
*
* @param str - input string
* @param charSet - a set of characters
* @return
*/
static public String findShortestSubString(String str, Set
> charS
et){
if(charSet == null || charSet.size() == 0 || str == null){
return null;
}
|
|
t********t
发帖数: 5415 | 19 1轮就够了吧？弄两个数组：indicate[128]=0, first[128]=0;然后走一遍字符串，对
每个字符查indicate：为0则改为1，first[字符]=位置；为1则改为-1；为-1直接skip
。这样一轮下来看indicate里第一个=1的字符(设为i)就行，然后first[i]是第一次出
现的位置。如果不需要位置可以把first省掉，数组index就是字符的ascii码。
学硬件的胡言乱语两句，有错还请指正 |
|
M********5
发帖数: 715 | 20 第一题最直接的想法是先sort两个array，然后再找intersect，这样复杂度好像是m*
logm+n*logn
第二题一种思路也是先sort，然后再找，如果不用hashtable的话
如果说里面包含的仅仅只是ascii码的话，可以定义一个array，以字符为下标，不过这
种做法其实根hashtable是一个思想 |
|
|
y*********e
发帖数: 518 | 22 视 string 为 bag of chars。把 s1 和 s2 分别转换成 bag of chars，然后找 s1 里
面最小的 substring，使得前者 bag 包含后者。O(n + m)，这里 n 和 m 分别是
s1 和 s2 的长度。
要注意一个 corner case：s1 不包含 s2 所有的 char。比如，s1 = "abc", s2 = "d"
/* C# code
*
* returns null if not found
* assumes ASCII
*/
public string FindSmallestSubStringContains(string s1, string s2) {
if (s2.Length == 0) return String.Empty;
if (s1.Length == 0) return null; // not found
char[] bag1 = new char[128];
char[] bag2 = new char[128];
forea |
|
j*****g
发帖数: 223 | 23 总结一下面试的准备活动,希望有帮助.
==================== AREAS/TOPICS to study/prep/review ====================
复习的东西还挺多的。比不过刚毕业的呀 :), 脑子不好使了，东西也差不多忘光了...
嘿嘿....
• Sorting
o Bubble/select/insertion/counting/qsort/heap/merge/bst
o Time/space complexity analysis
• Caching design
o Replacement policy (LRU, LFU, NRU, etc…)
o Efficiency/complexity/performance
o Distributed cache
o Hashing
• Multi-thread
o Locking/mutex/semaphore/critical sec... 阅读全帖 |
|
j*****g
发帖数: 223 | 24 总结一下面试的准备活动,希望有帮助.
==================== AREAS/TOPICS to study/prep/review ====================
复习的东西还挺多的。比不过刚毕业的呀 :), 脑子不好使了，东西也差不多忘光了...
嘿嘿....
• Sorting
o Bubble/select/insertion/counting/qsort/heap/merge/bst
o Time/space complexity analysis
• Caching design
o Replacement policy (LRU, LFU, NRU, etc…)
o Efficiency/complexity/performance
o Distributed cache
o Hashing
• Multi-thread
o Locking/mutex/semaphore/critical sec... 阅读全帖 |
|
n******n
发帖数: 49 | 25 @jerryju: sorry i can't type chinese in the lab
Thanks for your insightful suggestion. Actually for question 3, I suggested
hash at the very beginning saying that ascii only takes 8 bit at most. But
the interviewer seemed to look for other solutions, and told me "imagine you
can have random char from a char set of unknown size"... that's why i
switched to other solutions... |
|
s*******e
发帖数: 93 | 26 我也写了一个code. 有测试ihasleetcode的所有test case答案都一样。
如果没有想错的话应该是O(n)
因为begin和end两个值都最多扫过每一个字母一次
假设都是ascii字符
typedef struct range
{
int begin;
int end;
} Range;
Range shortestSubstring(const char* str, int strLen, const char* characters,
int charCount)
{
int* needToFind=new int[256];
int* hasFound=new int[256];
for(int i=0;i<256;i++)
{
needToFind[i]=0;
hasFound[i]=0;
}
for(int i=0;i
{
int index=(int)characters[i];
... 阅读全帖 |
|
f***g
发帖数: 214 | 27 看了上面的回复，受到启发。
也说一个想法：
Assumption: ASCII
对于每一个单词，利用bitset原理
用一个int就可以表示出其字母出现的模式。
假设用最低位表示z，最高的第7位表示a
预处理
1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
2.在每个数组中的保存符合当前模式的最长的单词。
找最大：
对于每一种模试，也就是每一个数组的index，翻转其index，比如模式是1010 (ac)，
则~1010=0101(bd)，这两个数组元素相乘（也就是长度想乘），保持最大值。然后每次
去掉一个1.(0100)在相乘比较。
这么做虽然数组很大，但对于每一个数组中的元素，需要相乘比较的次数不多，应该不
算慢吧 |
|
f***g
发帖数: 214 | 28 看了上面的回复，受到启发。
也说一个想法：
Assumption: ASCII
对于每一个单词，利用bitset原理
用一个int就可以表示出其字母出现的模式。
假设用最低位表示z，最高的第7位表示a
预处理
1.建hash，就是一个2^26的数组，每一个单词，预处理，算出相应的int值。
2.在每个数组中的保存符合当前模式的最长的单词。
找最大：
对于每一种模试，也就是每一个数组的index，翻转其index，比如模式是1010 (ac)，
则~1010=0101(bd)，这两个数组元素相乘（也就是长度想乘），保持最大值。然后每次
去掉一个1.(0100)在相乘比较。
这么做虽然数组很大，但对于每一个数组中的元素，需要相乘比较的次数不多，应该不
算慢吧 |
|
l********r
发帖数: 187 | 29 Hi,
I got an programming problem from Microsoft for screening purpose. Does
anyone has good idea about it? I am particularly puzzled by the second given
example. Thanks.
“bool F(string s, char ch1, char ch2, int n)”
The function determines whether or not there exists an occurrence of ch1 and
ch2 separated by a distance of no more than n in the given string s, where
s is ascii and user entered (your function needs to work on any input.) The
function must be efficient and **optimized** for both sp... 阅读全帖 |
|
l********r
发帖数: 187 | 30 Hi,
I got an programming problem from Microsoft for screening purpose. Does
anyone has good idea about it? I am particularly puzzled by the second given
example. Thanks.
“bool F(string s, char ch1, char ch2, int n)”
The function determines whether or not there exists an occurrence of ch1 and
ch2 separated by a distance of no more than n in the given string s, where
s is ascii and user entered (your function needs to work on any input.) The
function must be efficient and **optimized** for both sp... 阅读全帖 |
|
s*******f
发帖数: 1114 | 31 using System;
using System.Collections.Generic;
using System.Text;
namespace MSC
{
class Program
{
//“bool F(string s, char ch1, char
ch2, int n)”
//The function determines whether
or not there exists an occurrence of
//ch1 and ch2 separated by a
distance of no more than n in the given
//string s, where s is ascii and
user entered (your function needs
//to work on any input.) The
function must be efficient and
//**optimized** for both space... 阅读全帖 |
|
g********d
发帖数: 203 | 32 UTF-8是variable length的字符encoding，是backward compatible with ASCII。
这里有很好的解释：
http://en.wikipedia.org/wiki/UTF-8
我刚开始也并不知道UTF-8是什么东西，他给我解释了半天。
要求就是查这个文件里没有invalid character sequence。 |
|
s*****d
发帖数: 68 | 33 昨天早上面的，因为当地有分部，所以没有电面直接就on site了
典型的intern面试流程：一共两个人，每个45分钟左右
每个人都先就简历聊了5分钟左右，然后是技术问题
题目都很经典而且简单
第一个:
超经典的找中数问题，没让我编程。就直接告诉他用快排思想的那个算法
第二道是让实现tic-tac-toe，不光要设计，还要编程
我一直以来准备的都是对算法题编程，没想到会让编OO设计的题
所以这里表现得很不好……
第二个:
基本上就是围绕一道题展开：给一个字符串，找出其中出现频率最高的那个字符
最开始是限定于ASCII码，然后扩展到Unicode，再扩展到UTF-8
如果机器是4核的，该怎么利用4核来提高这个算法的性能
编程实现以上问题中的关键部分
自己觉得表现的比较鸡肋，食之无味弃之可惜
今天早上收到recruiter的邮件，让我再去on site面一次45分钟。
听说intern一般就是一轮45*2，看样子我对自己表现的评估还是很精确的……
不知道有没有人曾经经历过intern的第二轮重新鉴定的
能告诉我会和第一轮的难度、风格有很大差别吗？ |
|
y******5
发帖数: 43 | 34 Thank you for your post. I have two questions:
第一个:
超经典的找中数问题，没让我编程。就直接告诉他用快排思想的那个算法
第二道是让实现tic-tac-toe，不光要设计，还要编程
我一直以来准备的都是对算法题编程，没想到会让编OO设计的题
所以这里表现得很不好……
Implement the whole game or just whether there is a winner?
第二个:
基本上就是围绕一道题展开：给一个字符串，找出其中出现频率最高的那个字符
最开始是限定于ASCII码，然后扩展到Unicode，再扩展到UTF-8
如果机器是4核的，该怎么利用4核来提高这个算法的性能
编程实现以上问题中的关键部分
Implement or just describe how to do it in parallel? |
|
p*****a
发帖数: 147 | 35 This seems not necessary. a bit map of size 256bits would do the simple
check of duplicate or not. (assuming ascii codes here). |
|
f****4
发帖数: 1359 | 36 -127~127是ascii编码，char* 支持utf8
a[a[i]]==a[i]的确支持int a[10001]={10,100,10000};但必须有假设a足够大>=10001
（这个面试的人能同意么？特别是我给的这个情况）
我想强调的是，这个题目很多限制不确定，a[a[i]]==a[i]不一定能套上 |
|
b*****n
发帖数: 482 | 37
Cool, it's a clever move. It will solve the scenarios where the string
length is larger than 256 (assume the char set is ASCII). You will still
need to do some necessary work for the case of string length less than
256.
That was a solution without using extra memory. KMP is great when you
already have two strings, while in this case, what you've got are two
trees (need extra memory to convert them into strings) and the data might
not be characters. |
|
c******t
发帖数: 391 | 38 bless.
请问word怎么映射到ASCII码呢？有没有较好的办法为每个词生成signature? |
|
A*****i
发帖数: 3587 | 39 C直接用ASCII码就可以
n = 'c'-'a'
JAVA不懂 |
|
y**********u
发帖数: 6366 | 40 bitmap require extra memory space...
normally I guess string could be ascii ...
a |
|
y******n
发帖数: 47 | 41 如果数组元素只是ASCII字符的话, 只有255个可能的字符, 那么hashtable不就是o(1)
space的么?
这样就行了 int a [256]; |
|
p****n
发帖数: 294 | 42 string里只有 ascii码？ 有空格吗？完全不能用buffer还是得在O(1)范围内？ |
|
c****p
发帖数: 6474 | 43 我觉得他的意思是答案用了一个额外的表来记录字母出现的次数，这个不算没用extra
buffer。我个觉得可以用bitset来做，128个合法ASCII基本字符集，四个32-bit（或者
两个long）变量就够了。 |
|
c*****q
发帖数: 44 | 44 1st Interview
Introduction to master project
1. whether there is a cycle in linked list? time and space? how to make it
no cycle?
2. inline? adv vs. disadv? if all function are inline, will still treat as
inline? why?
Question and answer
2nd Interview
1. We have huge data flow, data come in at morning and at night we want to
get the repeated char with the min recurrences?
in place sort? data too huge, other method!
use hashtable. (in fact could just use 256 array if ascii). okay, time
complexit... 阅读全帖 |
|
c*****q
发帖数: 44 | 45 刚刚接到电话，收到offer
在此小女真心感谢板上的大牛们和前人们的讨论以及面经！
----------------------------------------------------
1st Interview
Introduction to master project
1. whether there is a cycle in linked list? time and space? how to make it
no cycle?
2. inline? adv vs. disadv? if all function are inline, will still treat as
inline? why?
Question and answer
2nd Interview
1. We have huge data flow, data come in at morning and at night we want to
get the repeated char with the min recurrences?
in place sort? data too huge,... 阅读全帖 |
|
w****x
发帖数: 2483 | 46
正负号的合法性： 比如-12 +123 123 合法，++123 --123 +-123非法
字符合法性: 12ad3就不对
溢出处理：1234567899999会溢出，负数的范围到-2^16, 正数的范围到2^16 -1， 所以
说正数溢出和负数溢出不能简单的先判断符号再判断后面的正数是否溢出
函数原型的设计 ：如果是int atoi(const char* str), 返回什么值代表异常？？ 返
回负一， 要是本来传的就是-1怎么办？？
标准的atoi实现大家可以看看更本没考虑这么多， 字符非法就非法，直接拿ascII值来
算。 溢出就溢出， 所有错误返回-1, 不管你传得是不是"-1"
我的意思是版上很多人说什么像这样简单的题15分钟内需要想都不想写出简洁无bug的
答案。 像这种考虑很多的题， 更本不可能在20分钟或15分钟内完成， 看起来简单，
实际上是吹毛求疵 |
|
q****x
发帖数: 7404 | 47 听说变态的Amazon要人念code，总结了一个。
这里面叹号和圆括号单词音节有点长，也有点绕口。我个人倾向用bang和round
bracket。但bang似乎不常见。
! exclamation mark, bang
" double quote
# pound, sharp
$ dollar
% percent
& ampersand, reference
' single quote
( left/opening parenthesis/round bracket
) right/closing
[ left/opening bracket/square bracket
] right/closing
{ left/opening brace/curly bracket
} right/closing
< less
> greater
* star
+ plus
, comma
- dash, minus
. dot
/ slash
\ back... 阅读全帖 |
|
|
|
|
