青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

A Za, A Za, Fighting...

堅(jiān)信:勤能補(bǔ)拙

Google面試題

來(lái)源:
http://coolshell.cn/articles/3345.html

Software Engineer
  • Why are manhole covers round? (陳皓:為什么下水井蓋是圓的?這是有N種答案的,上Wiki看看吧)
  • What is the difference between a mutex and a semaphore? Which one would you use to protect access to an increment operation?
  • A man pushed his car to a hotel and lost his fortune. What happened? (陳皓:腦筋急轉(zhuǎn)彎?他在玩大富翁游戲?!!)
  • Explain the significance of “dead beef”.(陳皓:要是你看到的是16進(jìn)制 DEAD BEEF,你會(huì)覺(jué)得這是什么?IPv6的地址?)
  • Write a C program which measures the the speed of a context switch on a UNIX/Linux system.
  • Given a function which produces a random integer in the range 1 to 5, write a function which produces a random integer in the range 1 to 7.(陳皓:上StackOverflow看看吧,經(jīng)典的問(wèn)題)
  • Describe the algorithm for a depth-first graph traversal.
  • Design a class library for writing card games. (陳皓:用一系列的類來(lái)設(shè)計(jì)一個(gè)撲克游戲,設(shè)計(jì)題)
  • You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?(陳皓:協(xié)議+數(shù)字加密,我試想了一個(gè),紙條上可以這樣寫(xiě),“Bob,請(qǐng)把我的手機(jī)號(hào)以MD5算法加密后的字符串,比對(duì)下面的字符串——XXXXXX,它們是一樣的嗎?”)
  • How are cookies passed in the HTTP protocol?
  • Design the SQL database tables for a car rental database.
  • Write a regular expression which matches a email address. (陳皓:上StackOverflow查相當(dāng)?shù)膯?wèn)題吧。)
  • Write a function f(a, b) which takes two character string arguments and returns a string containing only the characters found in both strings in the order of a. Write a version which is order N-squared and one which is order N.(陳皓:算法題,不難,不說(shuō)了。一個(gè)O(n^2)和一個(gè)O(n)的算法復(fù)雜度)
  • You are given a the source to a application which is crashing when run. After running it 10 times in a debugger, you find it never crashes in the same place. The application is single threaded, and uses only the C standard library. What programming errors could be causing this crash? How would you test each one? (陳皓:和隨機(jī)數(shù)有關(guān)系?或是時(shí)間?)
  • Explain how congestion control works in the TCP protocol.
  • In Java, what is the difference between final, finally, and finalize?
  • What is multithreaded programming? What is a deadlock?
  • Write a function (with helper functions if needed) called to Excel that takes an excel column value (A,B,C,D…AA,AB,AC,… AAA..) and returns a corresponding integer value (A=1,B=2,… AA=26..).
  • You have a stream of infinite queries (ie: real time Google search queries that people are entering). Describe how you would go about finding a good estimate of 1000 samples from this never ending set of data and then write code for it.
  • Tree search algorithms. Write BFS and DFS code, explain run time and space requirements. Modify the code to handle trees with weighted edges and loops with BFS and DFS, make the code print out path to goal state.
  • You are given a list of numbers. When you reach the end of the list you will come back to the beginning of the list (a circular list). Write the most efficient algorithm to find the minimum # in this list. Find any given # in the list. The numbers in the list are always increasing but you don’t know where the circular list begins, ie: 38, 40, 55, 89, 6, 13, 20, 23, 36. (陳皓:循環(huán)排序數(shù)組的二分查找問(wèn)題)
  • Describe the data structure that is used to manage memory. (stack)
  • What’s the difference between local and global variables?
  • If you have 1 million integers, how would you sort them efficiently? (modify a specific sorting algorithm to solve this)
  • In Java, what is the difference between static, final, and const. (if you don’t know Java they will ask something similar for C or C++).
  • Talk about your class projects or work projects (pick something easy)… then describe how you could make them more efficient (in terms of algorithms).
  • Suppose you have an NxN matrix of positive and negative integers. Write some code that finds the sub-matrix with the maximum sum of its elements.(陳皓:以前見(jiàn)過(guò)一維數(shù)組的這個(gè)問(wèn)題,現(xiàn)在是二維的。感覺(jué)應(yīng)該是把二維的第一行的最大和的區(qū)間算出來(lái),然后再在這個(gè)基礎(chǔ)之上進(jìn)行二維的分析。思路應(yīng)該是這個(gè),不過(guò)具體的算法還需要想一想)
  • Write some code to reverse a string.
  • Implement division (without using the divide operator, obviously).(陳皓:想一想手算除法的過(guò)程。)
  • Write some code to find all permutations of the letters in a particular string.
  • What method would you use to look up a word in a dictionary? (陳皓:使用排序,哈希,樹(shù)等算法和數(shù)據(jù)結(jié)構(gòu))
  • Imagine you have a closet full of shirts. It’s very hard to find a shirt. So what can you do to organize your shirts for easy retrieval?
  • You have eight balls all of the same size. 7 of them weigh the same, and one of them weighs slightly more. How can you fine the ball that is heavier by using a balance and only two weighings?
  • What is the C-language command for opening a connection with a foreign host over the internet?
  • Design and describe a system/application that will most efficiently produce a report of the top 1 million Google search requests. These are the particulars: 1) You are given 12 servers to work with. They are all dual-processor machines with 4Gb of RAM, 4x400GB hard drives and networked together.(Basically, nothing more than high-end PC’s) 2) The log data has already been cleaned for you. It consists of 100 Billion log lines, broken down into 12 320 GB files of 40-byte search terms per line. 3) You can use only custom written applications or available free open-source software.
  • There is an array A[N] of N numbers. You have to compose an array Output[N] such that Output[i] will be equal to multiplication of all the elements of A[N] except A[i]. For example Output[0] will be multiplication of A[1] to A[N-1] and Output[1] will be multiplication of A[0] and from A[2] to A[N-1]. Solve it without division operator and in O(n).(陳皓:注意其不能使用除法。算法思路是這樣的,把output[i]=a[i]左邊的乘積 x a[i]右邊的乘積,所以,我們可以分兩個(gè)循環(huán),第一次先把A[i]左邊的乘積放在Output[i]中,第二次把A[i]右邊的乘積算出來(lái)。我們先看第一次的循環(huán),使用迭代累積的方式,代碼如下:for(r=1; i=0; i<n-1; i++){ Output[i]=r; r*=a[i]; },看明白了吧。第二次的循環(huán)我就不說(shuō)了,方法一樣的。)
  • There is a linked list of numbers of length N. N is very large and you don’t know N. You have to write a function that will return k random numbers from the list. Numbers should be completely random. Hint: 1. Use random function rand() (returns a number between 0 and 1) and irand() (return either 0 or 1) 2. It should be done in O(n).(陳皓:本題其實(shí)不難。在遍歷鏈表的同時(shí)一邊生成隨機(jī)數(shù),一邊記錄最大的K個(gè)隨機(jī)數(shù)和其鏈接地址。)
  • Find or determine non existence of a number in a sorted list of N numbers where the numbers range over M, M>> N and N large enough to span multiple disks. Algorithm to beat O(log n) bonus points for constant time algorithm.(陳皓:使用bitmap,如果一個(gè)長(zhǎng)整形有64位,那么我們可以使用M/64個(gè)bitmap)
  • You are given a game of Tic Tac Toe. You have to write a function in which you pass the whole game and name of a player. The function will return whether the player has won the game or not. First you to decide which data structure you will use for the game. You need to tell the algorithm first and then need to write the code. Note: Some position may be blank in the game? So your data structure should consider this condition also.
  • You are given an array [a1 To an] and we have to construct another array [b1 To bn] where bi = a1*a2*…*an/ai. you are allowed to use only constant space and the time complexity is O(n). No divisions are allowed.(陳皓:前面說(shuō)過(guò)了)
  • How do you put a Binary Search Tree in an array in a efficient manner. Hint :: If the node is stored at the ith position and its children are at 2i and 2i+1(I mean level order wise)Its not the most efficient way.(陳皓:按順序遍歷樹(shù))
  • How do you find out the fifth maximum element in an Binary Search Tree in efficient manner. Note: You should not use use any extra space. i.e sorting Binary Search Tree and storing the results in an array and listing out the fifth element.
  • Given a Data Structure having first n integers and next n chars. A = i1 i2 i3 … iN c1 c2 c3 … cN.Write an in-place algorithm to rearrange the elements of the array ass A = i1 c1 i2 c2 … in cn(陳皓:這個(gè)算法其實(shí)就是從中間開(kāi)始交換元素,代碼:for(i=n-1; i>1; i++) {  for(j=i; j<2*n-i; j+=2) { swap(a[j], a[j+1]); } },不好意思寫(xiě)在同一行上了。)
  • Given two sequences of items, find the items whose absolute number increases or decreases the most when comparing one sequence with the other by reading the sequence only once.
  • Given That One of the strings is very very long , and the other one could be of various sizes. Windowing will result in O(N+M) solution but could it be better? May be NlogM or even better?
  • How many lines can be drawn in a 2D plane such that they are equidistant from 3 non-collinear points?
  • Let’s say you have to construct Google maps from scratch and guide a person standing on Gateway of India (Mumbai) to India Gate(Delhi). How do you do the same?
  • Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one?
  • Given a binary tree, programmatically you need to prove it is a binary search tree.
  • You are given a small sorted list of numbers, and a very very long sorted list of numbers – so long that it had to be put on a disk in different blocks. How would you find those short list numbers in the bigger one?
  • Suppose you have given N companies, and we want to eventually merge them into one big company. How many ways are theres to merge?
  • Given a file of 4 billion 32-bit integers, how to find one that appears at least twice? (陳皓:我能想到的是拆分成若干個(gè)小數(shù)組,排序,然后一點(diǎn)點(diǎn)歸并起來(lái))
  • Write a program for displaying the ten most frequent words in a file such that your program should be efficient in all complexity measures.(陳皓:你可能需要看看這篇文章Finding Frequent Items in Data Streams
  • Design a stack. We want to push, pop, and also, retrieve the minimum element in constant time.
  • Given a set of coin denominators, find the minimum number of coins to give a certain amount of change.(陳皓:你應(yīng)該查看一下這篇文章:Coin Change Problem
  • Given an array, i) find the longest continuous increasing subsequence. ii) find the longest increasing subsequence.(陳皓:這個(gè)題不難,O(n)算法是邊遍歷邊記錄當(dāng)前最大的連續(xù)的長(zhǎng)度。)
  • Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
  • Write a function to find the middle node of a single link list. (陳皓:我能想到的算法是——設(shè)置兩個(gè)指針p1和p2,每一次,p1走兩步,p2走一步,這樣,當(dāng)p1走到最后時(shí),p2就在中間)
  • Given two binary trees, write a compare function to check if they are equal or not. Being equal means that they have the same value and same structure.(陳皓:這個(gè)很簡(jiǎn)單,使用遞歸算法。)
  • Implement put/get methods of a fixed size cache with LRU replacement algorithm.
  • You are given with three sorted arrays ( in ascending order), you are required to find a triplet ( one element from each array) such that distance is minimum. Distance is defined like this : If a[i], b[j] and c[k] are three elements then distance=max(abs(a[i]-b[j]),abs(a[i]-c[k]),abs(b[j]-c[k]))” Please give a solution in O(n) time complexity(陳皓:三個(gè)指針,a, b, c分別指向三個(gè)數(shù)組頭,假設(shè):a[0]<b[0]<c[0],推進(jìn)a直到a[i]>b[0],計(jì)算 abs(a[i-1] – c[0]),把結(jié)果保存在min中。現(xiàn)在情況變成找 a[i], b[0],c[0],重復(fù)上述過(guò)程,如果有一個(gè)新的值比min要小,那就取代現(xiàn)有的min。)
  • How does C++ deal with constructors and deconstructors of a class and its child class?
  • Write a function that flips the bits inside a byte (either in C++ or Java). Write an algorithm that take a list of n words, and an integer m, and retrieves the mth most frequent word in that list.
  • What’s 2 to the power of 64?
  • Given that you have one string of length N and M small strings of length L. How do you efficiently find the occurrence of each small string in the larger one? (陳皓:我能想到的是——把那M個(gè)小字串排個(gè)序,然后遍歷大字串,并在那M個(gè)字串中以二分取中的方式查找。)
  • How do you find out the fifth maximum element in an Binary Search Tree in efficient manner.
  • Suppose we have N companies, and we want to eventually merge them into one big company. How many ways are there to merge?
  • There is linked list of millions of node and you do not know the length of it. Write a function which will return a random number from the list.
  • You need to check that your friend, Bob, has your correct phone number, but you cannot ask him directly. You must write a the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?
  • How long it would take to sort 1 trillion numbers? Come up with a good estimate.
  • Order the functions in order of their asymptotic performance: 1) 2^n 2) n^100 3) n! 4) n^n
  • There are some data represented by(x,y,z). Now we want to find the Kth least data. We say (x1, y1, z1) > (x2, y2, z2) when value(x1, y1, z1) > value(x2, y2, z2) where value(x,y,z) = (2^x)*(3^y)*(5^z). Now we can not get it by calculating value(x,y,z) or through other indirect calculations as lg(value(x,y,z)). How to solve it?
  • How many degrees are there in the angle between the hour and minute hands of a clock when the time is a quarter past three?
  • Given an array whose elements are sorted, return the index of a the first occurrence of a specific integer. Do this in sub-linear time. I.e. do not just go through each element searching for that element.
  • Given two linked lists, return the intersection of the two lists: i.e. return a list containing only the elements that occur in both of the input lists. (陳皓:把第一個(gè)鏈表存入hash表,然后遍歷第二個(gè)鏈表。不知道還沒(méi)有更好的方法。)
  • What’s the difference between a hashtable and a hashmap?
  • If a person dials a sequence of numbers on the telephone, what possible words/strings can be formed from the letters associated with those numbers?(陳皓:這個(gè)問(wèn)題和美國(guó)的電話有關(guān)系,大家可以試著想一下我們發(fā)短信的手機(jī),按數(shù)字鍵出字母,一個(gè)組合的數(shù)學(xué)問(wèn)題。)
  • How would you reverse the image on an n by n matrix where each pixel is represented by a bit?
  • Create a fast cached storage mechanism that, given a limitation on the amount of cache memory, will ensure that only the least recently used items are discarded when the cache memory is reached when inserting a new item. It supports 2 functions: String get(T t) and void put(String k, T t).
  • Create a cost model that allows Google to make purchasing decisions on to compare the cost of purchasing more RAM memory for their servers vs. buying more disk space.
  • Design an algorithm to play a game of Frogger and then code the solution. The object of the game is to direct a frog to avoid cars while crossing a busy road. You may represent a road lane via an array. Generalize the solution for an N-lane road.
  • What sort would you use if you had a large data set on disk and a small amount of ram to work with?
  • What sort would you use if you required tight max time bounds and wanted highly regular performance.
  • How would you store 1 million phone numbers?(陳皓:試想電話是有區(qū)段的,可以把區(qū)段統(tǒng)一保存,F(xiàn)lyweight設(shè)計(jì)模式)
  • Design a 2D dungeon crawling game. It must allow for various items in the maze – walls, objects, and computer-controlled characters. (The focus was on the class structures, and how to optimize the experience for the user as s/he travels through the dungeon.)
  • What is the size of the C structure below on a 32-bit system? On a 64-bit? (陳皓:注意編譯器的對(duì)齊)

struct foo {

char a;
char* b;
};

posted on 2011-07-14 10:13 simplyzhao 閱讀(571) 評(píng)論(0)  編輯 收藏 引用 所屬分類: M_面試題集錦

導(dǎo)航

<2011年7月>
262728293012
3456789
10111213141516
17181920212223
24252627282930
31123456

統(tǒng)計(jì)

常用鏈接

留言簿(1)

隨筆分類

隨筆檔案

搜索

最新評(píng)論

閱讀排行榜

評(píng)論排行榜

青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            快she精品国产999| 欧美激情一区二区| 国内精品写真在线观看| 欧美日韩中文字幕日韩欧美| 欧美精品九九99久久| 欧美激情久久久久久| 欧美精品18videos性欧美| 欧美日韩调教| 国产区精品视频| 在线欧美日韩精品| 一区二区三区视频在线播放| 亚洲综合社区| 久久综合久久88| 亚洲欧洲日产国产网站| 一区二区日韩| 小黄鸭视频精品导航| 久久全球大尺度高清视频| 欧美交受高潮1| 国产麻豆成人精品| 在线观看亚洲| 亚洲欧美另类在线观看| 久热精品视频在线| 亚洲电影成人| 亚洲一区二区三区乱码aⅴ| 香蕉久久夜色精品| 欧美激情1区| 亚洲欧美中文日韩在线| 免费一级欧美片在线播放| 国产精品久久二区| 亚洲激情午夜| 久久嫩草精品久久久精品| 99成人在线| 欧美成人精品在线观看| 国产伦精品一区二区三区高清 | 性欧美8khd高清极品| 欧美xxx成人| 国产亚洲a∨片在线观看| 99视频精品| 欧美成人中文字幕| 欧美一级专区| 国产精品v欧美精品∨日韩| 亚洲国产精品毛片| 久久亚洲综合| 欧美在线网站| 国产欧美综合一区二区三区| 在线一区二区三区四区| 亚洲大片av| 乱人伦精品视频在线观看| 国产欧美精品一区二区色综合 | 在线观看亚洲a| 欧美一级淫片播放口| 日韩午夜中文字幕| 欧美激情亚洲国产| 亚洲精品国产精品乱码不99按摩| 久久精品色图| 欧美一区久久| 国产一区二区精品久久91| 欧美一级久久久久久久大片| 制服诱惑一区二区| 国产精品久久久久久模特| 亚洲综合成人婷婷小说| 亚洲社区在线观看| 国产麻豆精品久久一二三| 亚洲欧美日本精品| 亚洲尤物在线| 国内精品美女在线观看| 久久久久久尹人网香蕉| 久久国产加勒比精品无码| 国产在线视频欧美| 美女网站久久| 欧美激情国产高清| 亚洲一区精品视频| 欧美一区二区三区视频在线观看| 国内精品视频666| 欧美bbbxxxxx| 欧美伦理视频网站| 香蕉成人久久| 欧美高清视频一区| 欧美国产日本韩| 亚洲综合国产| 欧美专区在线观看| 亚洲第一在线综合在线| 亚洲国产精品精华液网站| 欧美日韩亚洲一区二| 欧美一区午夜视频在线观看| 久久国产精品高清| 日韩一区二区免费高清| 亚洲直播在线一区| 在线观看中文字幕不卡| 亚洲国产一区二区三区在线播| 欧美日韩国产在线一区| 欧美在线播放一区| 免费在线播放第一区高清av| 亚洲手机在线| 欧美在线观看日本一区| 99精品国产高清一区二区 | 免费观看在线综合| 国产精品av久久久久久麻豆网| 久久国产欧美日韩精品| 欧美超级免费视 在线| 中日韩午夜理伦电影免费| 欧美在线视频在线播放完整版免费观看| 亚洲高清不卡一区| 亚洲欧美日韩国产一区二区三区| 激情欧美丁香| 一区二区三区导航| 亚洲精品小视频| 欧美专区在线播放| 亚洲欧美日本精品| 欧美11—12娇小xxxx| 欧美中文字幕视频在线观看| 欧美精品成人| 久久免费精品日本久久中文字幕| 欧美激情精品| 欧美成人午夜免费视在线看片| 国产精品日韩精品| 亚洲国产成人av| 国内揄拍国内精品久久| 亚洲综合欧美| 亚洲午夜羞羞片| 欧美国产欧美亚洲国产日韩mv天天看完整| 欧美在线观看天堂一区二区三区| 欧美美女bbbb| 亚洲国产99| 91久久极品少妇xxxxⅹ软件| 欧美在线关看| 欧美在线视频播放| 国产精品成人播放| 99精品99久久久久久宅男| 亚洲国产天堂久久综合网| 久久久欧美精品sm网站| 久久久久综合网| 国产伦精品一区二区三区免费 | 中文一区字幕| 亚洲一区免费看| 欧美日韩午夜在线| aa级大片欧美| 亚洲午夜久久久久久久久电影院| 欧美成人dvd在线视频| 欧美国产亚洲另类动漫| 欧美剧在线观看| 亚洲人成亚洲人成在线观看| 亚洲国产成人精品久久久国产成人一区| 久久久99爱| 亚洲电影免费观看高清| 亚洲精品免费一二三区| 欧美激情一二区| 日韩一级网站| 亚洲欧美日韩视频一区| 国产精品毛片在线看| 午夜精品国产| 欧美jjzz| 亚洲午夜在线| 国产色综合久久| 久久久91精品国产| 欧美激情一区二区三区四区| 亚洲精品免费一区二区三区| 欧美精品激情在线| 亚洲性感激情| 久久女同精品一区二区| 尤物在线精品| 欧美日韩免费网站| 亚洲免费视频成人| 老司机亚洲精品| 夜夜嗨av一区二区三区网站四季av| 欧美精品日韩一本| 校园春色国产精品| 91久久中文| 久久精品免费看| 亚洲精品免费一二三区| 国产精品一区二区在线观看网站 | 亚洲综合视频1区| 国产综合久久久久久| 欧美大片免费观看| 亚洲一区欧美激情| 欧美高清视频一二三区| 亚洲天堂成人在线观看| 国内一区二区三区在线视频| 欧美黄污视频| 亚洲欧美激情一区二区| 亚洲国产精品va在看黑人| 欧美一区二区视频在线| 亚洲高清网站| 国产亚洲欧美日韩日本| 欧美三级网址| 母乳一区在线观看| 亚洲欧美日韩国产中文| 91久久精品网| 老司机免费视频一区二区三区| 亚洲影院免费| 亚洲精品一区久久久久久| 国产专区欧美精品| 国产精品高清在线观看| 欧美国产综合视频| 久久久噜噜噜久噜久久| 亚洲欧美激情精品一区二区| 亚洲免费电影在线| 亚洲第一区在线观看| 免费不卡欧美自拍视频| 久久精品日韩|