Google Interview Question for Software Engineer / Developers


Country: India
Interview Type: Phone Interview




Comment hidden because of low score. Click to expand.
1
of 1 vote

private static class Triple implements Comparable<Triple> {
        public final int source;
        public final int dest;
        public final Long timestamp;

        public static Triple of(int source, int dest, long timestamp) {
            return new Triple(source, dest, timestamp);
        }

        public Triple(int source, int dest, long timestamp) {
            this.source = source;
            this.dest = dest;
            this.timestamp = timestamp;
        }

        @Override
        public int compareTo(Triple o) {
            return this.timestamp.compareTo(o.timestamp);
        }
    }

//This solution has O(n*log n) complexity, to build the timeline. 		
 public static Collection<Integer> gossip(Collection<Triple> talks) {
        Map<Long, List<Pair<Integer, Integer>>> timeline = constructTimeline(talks);
        Set<Integer> theyKnow = new HashSet<>();
        theyKnow.add(1); //the first one to know.

        var it = timeline.entrySet().iterator();
        while (it.hasNext()) {
            Map.Entry<Long, List<Pair<Integer, Integer>>> next = it.next();
            System.out.printf("%s-%s%n", next.getKey(), next.getValue());

            for (Pair<Integer, Integer> pair : next.getValue()) {
                if (theyKnow.contains(pair.left)) {
                    theyKnow.add(pair.right);
                }
            }
        }
        return theyKnow;
    }

    private static Map<Long, List<Pair<Integer, Integer>>> constructTimeline(Collection<Triple> talks) {
        Map<Long, List<Pair<Integer, Integer>>> result = new HashMap<>();

        for (Triple triple : talks) {
            List<Pair<Integer, Integer>> listOfKnowers = result.getOrDefault(triple.timestamp, new LinkedList<>());
            listOfKnowers.add(Pair.of(triple.source, triple.dest));
            result.put(triple.timestamp, listOfKnowers);
        }

        return result;
    }

- juliccr July 11, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

Generate a graph of the form

Map<Integer, Pair<Integer, Integer>> graph = new HashMap<>();
// Each Pair<Integer, Integer> is the vertex and the time stamp of meeting

// Current node being processed.
Deque<Pair<Integer,Integer>> q= new ArrayDeque<>();

// Enque the root node and the time when it heard the story.
q.offer(new Pair<>(1, 0));

// Perform Level order/ BFS traversal starting at node 1. 
// And keep track of the time w.r.t to root node and the time stamp of iteraction between 
// node being processed and it's childern.

- aksa June 28, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

private List<Integer> whoKnows(int[][] meetings, Integer personId) {
        HashMap<Integer, LinkedList<Integer[]>> map = new HashMap<>();
        int[] actualPerson = meetings[0];
        for(int[] meeting: meetings) {
            map.put(meeting[0], map.getOrDefault(meeting[0], new LinkedList<>()));
            map.get(meeting[0]).add(new Integer[]{meeting[1],meeting[2]});
        }


        Queue<Integer[]> queue = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();

        queue.offer(new Integer[]{meetings[0][0],meetings[0][2]});
        visited.add(meetings[0][0]); //adding the actual person

        while(!queue.isEmpty()) {
            Integer[] meeting = queue.poll();
            LinkedList<Integer[]> children = map.getOrDefault(meeting[0], new LinkedList<>());
            for(Integer[] child: children) {
                Integer id = child[0];
                Integer time = child[1];
                if(time >= meeting[1] ) {
                    queue.offer(child);
                    visited.add(id);
                }
            }
        }

        return new ArrayList<>(visited);
    }

- Shahrukh June 29, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findlist(input):
	dictn={}
  for pair in input:
  	dictn[pair[0]]=dictn.get(pair[0], [])+[(pair[2],pair[1])]
  queue=[(0, 1)]
  ans=[1]
  while queue:
  	tmstmp, person = queue.pop(0)
    if dictn.get(person) is not None:
    	for neighbour in dictn[person]:
    		if neighbour[0]>=tmstmp:
      		queue.append((neighbour[0], neighbour[1]))
        	ans.append(neighbour[1])
	return ans

- Anonymous July 03, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findlist(input):
	dictn={}
  for pair in input:
  	dictn[pair[0]]=dictn.get(pair[0], [])+[(pair[2],pair[1])]
  queue=[(0, 1)]
  ans=[1]
  while queue:
  	tmstmp, person = queue.pop(0)
    if dictn.get(person) is not None:
    	for neighbour in dictn[person]:
    		if neighbour[0]>=tmstmp:
      		queue.append((neighbour[0], neighbour[1]))
        	ans.append(neighbour[1])
	return ans

- Anonymous July 03, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

def findlist(input):
	dictn={}
  for pair in input:
  	dictn[pair[0]]=dictn.get(pair[0], [])+[(pair[2],pair[1])]
  queue=[(0, 1)]
  ans=[1]
  while queue:
  	tmstmp, person = queue.pop(0)
    if dictn.get(person) is not None:
    	for neighbour in dictn[person]:
    		if neighbour[0]>=tmstmp:
      		queue.append((neighbour[0], neighbour[1]))
        	ans.append(neighbour[1])
	return ans

- priyakoshta21 July 03, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import os

def userInput():
    items = []
    noofelements = int(input('Enter range : '))
    for rangeIndex in range(0, noofelements):
        lst=[]
        for rowIndex in range(0, 3):
            print("***********Intiating information share list***********")
            person1 = int(input("Enter First Person Id in this list >"))
            person2 = int(input("Enter Second Person Id in this list >"))
            timestamp = int(input("Enter the timestamp when the information was shared >"))
            print("***********IInformation is saved lets continue for next item iteration in the list **********")
            screen_clear()
            lst.append(person1)
            lst.append(person2)
            lst.append(timestamp)
            items.append(tuple(lst))
            break
    return items

def screen_clear():
   # for mac and linux(here, os.name is 'posix')
   if os.name == 'posix':
      os.system('clear')
   else:
      # for windows platfrom
      os.system('cls')
   

def personsSharingSameInformation(input):
    dictn=[]
    dictInd = 0
    
    for index, tuple in enumerate(input):
        tindex = 0

        #first persons to know from the list
        if (index ==0 ):            
            dictn.append(tuple[tindex])
            dictn.append(tuple[tindex + 1])
            continue

        if (tuple[tindex] in dictn):
            dictn.append(tuple[tindex])
            dictn.append(tuple[tindex + 1])
    final_list = list(dict.fromkeys(dictn).keys())

    return final_list


if __name__ == '__main__':
    items = userInput()
    sortedByTimestamp = sorted(items, key=lambda tup: tup[2])
    print("Information we are going to process >> ", sortedByTimestamp)
    final_list = personsSharingSameInformation(sortedByTimestamp)
    print(final_list)

- dassandeep173 July 05, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node:
def __init__(self, val):
self.val = val
self.nodes = list()

def bfs(m , i, val, res):
node = m[i]
if i not in res:
res.add(i)
for n in node.nodes:
if n[0] >= val:
bfs(m, n[1].val, n[0], res)


if __name__ == '__main__':
m = {}
l = [ (2, 3, 100), (4, 5, 100), (1, 2, 100)]
for i in l:
if i[0] in m:
node = m[i[0]]
else:
node = Node(i[0])
m[i[0]] = node
if i[1] in m:
n = m[i[1]]
else:
n = Node(i[1])
m[i[1]] = n
node.nodes.append(tuple([i[2], n]))
res = set()
bfs(m, 1, 0, res)
print(res)

- Parth Menon July 18, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

class Node:
    def __init__(self, val):
        self.val = val
        self.nodes = list()

def bfs(m , i, val, res):
    node = m[i]
    if i not in res:
        res.add(i)
    for n in node.nodes:
        if n[0] >= val:
            bfs(m, n[1].val, n[0], res)


if __name__ == '__main__':
    m = {}
    l = [ (2, 3, 100), (4, 5, 100), (1, 2, 100)]
    for i in l:
        if i[0] in m:
            node = m[i[0]]
        else:
            node = Node(i[0])
            m[i[0]] = node
        if i[1] in m:
            n = m[i[1]]
        else:
            n = Node(i[1])
            m[i[1]] = n
        node.nodes.append(tuple([i[2], n]))
    res = set()
    bfs(m, 1, 0, res)
    print(res)

- Parth July 18, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

simple steps to solve
1. sort the list by timestamps.
2. keep one hashmap of people who knows the story. initially put 1 person as true in the map.
3. go through the list.
a. check if the person_id_1 is in hashmap
b. if person_id_1 is in hashmap then put person_id_2 also in hashmap.
4. count all the persons in the hashmap.
5. return the list

complexity is O(nlogn) + O(n) + O(n) -> O(nlogn)

- vikas maan August 04, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

import heapq

def story_teller_seqeunce(meeting_list):
meetings = []

for meeting in meeting_list:
heapq.heappush(meetings, (meeting[2], 
 [meeting[0], meeting[1]])

	
	final_meeting_sequence = []
	while meetings:
		current_meeting = heapq.heappop(q)
		if current_meeting[0] in final_meeting_sequence:
			current_meeting.append(meeting(1))

	return final_meeting_sequence

- Manish Sharma September 05, 2021 | Flag Reply
Comment hidden because of low score. Click to expand.
0
of 0 vote

space complexity = O(nlogn)
time complexity = O(n)

Can I make a tree out of it?
import heapq

def story_teller_seqeunce(meeting_list):
meetings = []

for meeting in meeting_list:
heapq.heappush(meetings, (meeting[2], 
 [meeting[0], meeting[1]])

	
	final_meeting_sequence = []
	while meetings:
		current_meeting = heapq.heappop(q)
		if current_meeting[0] in final_meeting_sequence:
			current_meeting.append(meeting(1))

	return final_meeting_sequence

- manish.sharma0201cs September 05, 2021 | Flag Reply


Add a Comment
Name:

Writing Code? Surround your code with {{{ and }}} to preserve whitespace.

Books

is a comprehensive book on getting a job at a top tech company, while focuses on dev interviews and does this for PMs.

Learn More

Videos

CareerCup's interview videos give you a real-life look at technical interviews. In these unscripted videos, watch how other candidates handle tough questions and how the interviewer thinks about their performance.

Learn More

Resume Review

Most engineers make critical mistakes on their resumes -- we can fix your resume with our custom resume review service. And, we use fellow engineers as our resume reviewers, so you can be sure that we "get" what you're saying.

Learn More

Mock Interviews

Our Mock Interviews will be conducted "in character" just like a real interview, and can focus on whatever topics you want. All our interviewers have worked for Microsoft, Google or Amazon, you know you'll get a true-to-life experience.

Learn More