面试题总结~~(google level)

题目一

Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example, 
Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!

这里计算面积不用一般几何书的方法,这里是两边往中间遍历,记录当前第二高点secHight,然后利用这个第二高点减去当前历经的柱子,剩下就装水容量了。

为什么是第二高点?因为两边比较,最高的点不用动,只移动第二高点。

第一个思路,按照上图的思想就能写出非常简洁的程序了,时间复杂度为O(n):

int trap(int A[], int n) {
		int secHight = 0;
		int left = 0;
		int right = n-1;
		int area = 0;
		while (left < right){
			if (A[left] < A[right]){
				secHight = max(A[left], secHight);
				area += secHight-A[left];//计算当前格的能装雨水的容量
				left++;
			} else {
				secHight = max(A[right], secHight);
				area += secHight-A[right];
				right--;
			}
		}
		return area;
	}

题目二

Given a number, can you remove k digits from the number so that the new 
formatted number is smallest possible.
input: n = 1432219, k = 3
output: 1219

public class Solution {
    public static void main(String[] args){
    	System.out.print(get_smallest("63534",2));
    }
    public static String get_smallest(String n, int k){
    	int len=n.length()-k;//最后的序列长
    	int index=0;
    	int temp=0;
    	String result="";//输出结果
    	for(int i=0;i<len;i++){
    		int min=9;
    		for(int j=index;j<=n.length()-len+i;j++){
    			if(Integer.parseInt(String.valueOf(n.charAt(j)))<min){
    				index=j+1;
    				min=Integer.parseInt(String.valueOf(n.charAt(j)));
    			}

    		}
    		result+=min+"";
    	}
    	return result;
    }
}

题目三

第一题:Median of Two Sorted Arrays

public class Solution {
     public static void main(String[] args){
        	int[] list1={1,5,8,8,9};
        	int[] list2={2,7,7};
        	System.out.print(get_median(list1,list2));
     }
     public static int get_median(int[] list1,int[] list2){
    	 int len1=list1.length;
    	 int len2=list2.length;
    	 if(len1==0 && len2==0) return 0;
    	 if(len1==0) return list2[len2/2];
    	 if(len2==0) return list1[len1/2];
    	 int median=(len1+len2)/2-2;
    	 int index_1=0;
    	 int index_2=0;
    	 int result=Integer.MIN_VALUE;
    	 while(index_1+index_2<=median && index_1<len1 && index_2<len2){
    		 if(list1[index_1]<=list2[index_2]){
    			 result=list2[index_2];
    			 index_1++;
    		 }
    		 else{
    			 result=list1[index_1];
    			 index_2++;
    		 }
    	 }
    	 if(index_1+index_2-1==median){
    		 return result;
    	 }
    	 else{
    		 if(index_1==len1){
    			return list2[median-len1];
    		 }
    		 else{
    			 return list1[median-len2];
    		 }
    	 }

     }
}

/********************************

* 本文来自博客  “李博Garvin“

* 转载请标明出处:http://blog.csdn.net/buptgshengod

******************************************/

时间: 2024-10-15 01:48:23

面试题总结~~(google level)的相关文章

一道面试题:140个google面试题

FROM:酷壳 来源:http://blog.seattleinterviewcoach.com/2009/02/140-google-interview-questions.html(墙) 某猎头收集了140多个Google的面试题,都张到他的Blog中了,主要是下面这些职位的,因为被墙,且无任何敏感信息,所以,我原文搬过来了. Product Marketing Manager Product Manager Software Engineer Software Engineer in Te

经典算法(11) 一道有趣的GOOGLE面试题 --【解法2】

上一篇<白话经典算法系列之十一道有趣的GOOGLE面试题>中对一道有趣的GOOGLE面试题进行了详细的讲 解,使用了类似于基数排序的做法在O(N)的时间复杂度和O(1)的空间复杂度完成了题目的要求,文章发表后 ,网友fengchaokobe在评论中给出了另一种解法,见下图. 文字版: int Repeat(int *a, int n) { for(int i = 0; i < n; i++) { if(a[i] > 0) //判断条件 { if(a[ a[i] ] < 0)

经典算法(10) 一道有趣的GOOGLE面试题

最近在微博上看到一道有趣的GOOGLE面试题,见下图: 文字版: 一个 大小为n的数组,里面的数都属于范围[0, n-1],有不确定的重复元素,找到至少一个重复元素,要求O(1)空 间和O(n)时间. 这个题目要求用O(n)的时间复杂度,这意味着只能遍历数组一次.同时还要寻找重复 元素,很容易想到建立哈希表来完成,遍历数组时将每个元素映射到哈希表中,如果哈希表中已经存在这个 元素则说明这就是个重复元素.因此直接使用C++ STL中的hash_set(参见<STL系列之六 set与hash_set

Google手机Android操作系统面试题

    Google 手机 Android操作系统面试题      1﹑Android 手机操作系统的四层架构?        架构框架以此从上到下:       1.Applications   (应用程序(应用层)):       Android 会同一系列核心应用程序包一起发布,该应用程序包包括 email 客户端,SMS 短消息程序,日历,地图,浏览器,联系人管理程序等.所有的应用程序都是使用 JAVA 语 言编写的.       2.Application FrameWork    (

Google承认:那些稀奇古怪的创意面试题对招聘无用

还记得一度疯传的Google创意面试题么? "校车里能放 多少个 高尔夫球?,世界上有多少个钢琴调音器?为啥井盖是圆的?"等等,这般面试题你可曾在面试中遇到过?对于此类瞬间杀死无数脑细胞的面试题,一直是众说纷纭,怒其坑爹的同时,也有人颇认同其测试效果. 现在面试者可以不必再如此纠结地"数高尔夫球or思考井盖圆不圆"的问题啦.Google方面已然表态,其一度用以测试求职者的这些颇费脑力的题目并非衡量雇员能力的良方. "我们发现问这些脑筋急转弯类的题目 其实一

Google面试题不科学 会让企业错过优秀人才

Google和微软的面试题是出了名的奇怪的,甚至 有点像脑筋急转弯的题目,比如"一辆校车可以装下 多少个高尔夫球?";"为什么井盖是圆的?",还有"如何移动富士山?".我想大家看到这样问题, 肯定哭笑不得,心想"井盖的形状跟这个职位有什么关系呢?我也不会去移动富士山啊,它在那挺好的,移动它不是浪费我的生命吗?" 这些问题都没有正确的答案,我觉得这种问题根本不是在考察面试者的智力,而是考察面试者用脚趾头思考的能力.旧金山州立大学

Google的疯狂面试题

中介交易 http://www.aliyun.com/zixun/aggregation/6858.html">SEO诊断 淘宝客 云主机 技术大厅 几星期前,一个朋友接受了Google公司的面试,他透露了面试中的一些问题.顺便,我把从其他几个曾经面试过的人那里听来的内容也整理在一起.最大的互联网公司Google的一份面试题集,看看你是否能够回答出来.其中很多问题都是开放式的,正确的解答有许多种,所以在这里就不提供答案了. 一辆学校班车里面能装多少个高尔夫球? 你被缩小到只有硬币厚度那么点

Google面试题解析:从1到n的整数中1出现的次数

题目:输入一个正整数n,求从1到n这n个整数的十进制表示1出现的次数. 例如: 例如输入12, 那么从1到12的整数中出现1的整数为:1,10, 11和12,1一共出现5次. 分析: 这题可以简单计算每个数中包含的1的个数,再遍历1-n个整数. 实现如下: #include<iostream> using namespace std; int count_num(int v) { int i = v; int num = 0; while(i > 0) { if(i%10 == 1) n

Google产品经理笔试题&#038;面试题

以下内容整理于网路,可能有些问题并不是来自Google,当时的话很值得思考.~ 1.一辆校车能装下多少个高尔夫球? 2.如果让你清洗西雅图市所有的窗户,你会对此索价多少? 3.在一个重男轻女的国家里,每家每户都想生男孩.若一户人家生了一个女孩,便会再生一个,直到生下的是男孩为止.请问这个国家的男女比例是多少? 4.全世界共有多少位钢琴调音师? 5.下水道井盖为什么是圆的? 6.为旧金山市设计一个紧急疏散方案. 7.时钟的指针一天内总共会重合多少次? 8.你有8个大小一样的球,其中7个重量相同,只