## Software Engineer / Developer Interview Questions

- 1of 1 vote
Given a undirected graph with weights, return the sum of the weight of each path between two nodes (shortest path between two vertices). Assume there are no cycles.

Example:`Input: A | 1 B 2 / \ 3 C D Output: 18 since A to B has weight 1 A to C has weight 3 A to D has weight 4 B to C has weight 2 B to D has weight 3 C to D has weight 5`

Edit: Thanks, wangchenClark0512, forgot about C to D

Edit2: @Lukas, The question is just the sum of the shortest paths between two vertices. Also, all edges are positive.

Edit3: Assume the graph has no cycles, did not get to the follow-up, but follow-up probably is probably change your algorithm so that is works for cycles

- 4of 4 votes
You are given a graph with no cycles, each node representing different cities and there are stadiums for baseball games in all cities.

Each node contains a value representing the population of the city, and a list of neighbors. (feel free to extend data structure)

Every time there is a baseball game at a city, everyone from all the different cities will go to the city with the baseball game.

Return the maximum traffic between a city and its neighbours when there is a game at that city, for all cities. (Does not have to be sorted)

The total run-time after returning everything should be O(n).

Examples:`Input: 1 2 \ / 5 / \ 4 3 Output: 1 14 2 13 3 12 4 11 5 4 Input: 38 / 8 / 7 / 1 2 \ / \ 5 15 / \ 4 3 Output: 1 82 2 53 3 80 4 79 5 70 7 46 15 68 8 38 38 45`

- 1of 1 vote
Given a length n, return the number of strings of length n that can be made up of the letters 'a', 'b', and 'c', where there can only be a maximum of 1 'b's and can only have up to two consecutive 'c's

Example:

findStrings(3) returns 19

since the possible combinations are: aaa,aab,aac,aba,abc,aca,acb,baa,bac,bca,caa,cab,cac,cba,cbc,acc,bcc,cca,ccb

and the invalid combinations are:

abb,bab,bba,bbb,bbc,bcb,cbb,ccc

- 0of 0 votes
Suppose you have a matrix in the form of a 2 dimensional array. Write a method to read the rows of the matrix alternatively from right to left, left to right so on and return them as a 1 dimensional array.

for eg:

1 2 3

4 5 6

7 8 9

should return 1 2 3 6 5 4 7 8 9

- 3of 3 votes
# take an array and print non over lapping in order pairs. example:

`# [1,2,3,4] => input # output below is in order combination # (1234) # (1)(234) # (1)(23)(4) # (1)(2)(34) # (12)(34) # (12)(3)(4) # (123)(4) # (1)(2)(3)(4)`

- 0of 0 votes
You have given an array of integers. The appearance of integers vary (ie some integers appears twice or once or more than once) How would you determine which integers appeared odd number of times ?

a[] = { 1.1.1, 2,5,10000, 5,7,4,8}

as you can see 1 appeared 3 times, 2 appeared once etc

- 0of 0 votes
what is output for below code and what is purpose of using const type for pointer variable p?

#include<stdio.h>

#include<conio.h>

#include<string.h>

void main()

{

char a[10]="HELLO";

char *const p=a;

clrscr();

//puts(p);

printf("%s",p);

*p='n';

//puts(p);

printf("%s",p);

getch();

}

- 0of 0 votes
Int a=10;

Int b=a>15;

Print("%d",b);

a)15

b)10

c)0

d)1

- 0of 0 votes
Virtual memory can be handled by which of the following?

a)demand paging

b)demand segmentation

c)both a and b

- 0of 0 votes
Using which data structures the arthematic expressions can be calculated?

- 0of 0 votes
Find a sub string in a given string and replace it with another string?

- 0of 0 votes
Implement a solution nth_largest( array, n ) that takes in an array of arbitrary size and returns the nth largest element.

`Eg. array = [1, 8, 4, 5, 9, 7, 2, 10, 44, 55, 67] nth_largest( array, 2) = 55 nth_largest( array, 5) = 9`

- 0of 0 votes
Write a program to identify if a given binary tree is balanced or not.

- 0of 0 votes
Write a program to print all permutations of a given string.

- 0of 0 votes
If you have the chapter of a book and you're supposed to build an index such that given a word, you can tell which pages the word occurs on, what data structure can you use? Optimize for space utilization.

- 0of 0 votes
Write a Python program to print numbers from 1 to 100 except for multiples of 3 for which you should print "fuzz" instead, for multiples of 5 you should print 'buzz' instead and for multiples of both 3 and 5, you should print 'fuzzbuzz' instead.

- 0of 0 votes
Implement a function DoIt( o,a ) such that the following code:

`Object o = SomeClass() O.first = 'fizz' O.second = 'buzz' print DoIt( o, 'first) print DoIt(o, 'second')`

prints

fizz

buzz

- 0of 0 votes
Write a iterative Python function to print the factorial of a number n (ie, returns n!).

- 0of 0 votes
Write a recursive Python function to print the factorial of a number n (ie, returns n!).

- 0of 0 votes
Board Game:

1) Write a program that can take a board of N x N filled with alphabets and print/return all the words that can be constructed by connecting alphabets together. You're allowed to connect alphabets in any direction including diagonally, the only restriction is that you cannot cross over the same alphabet twice. So for eg:

A,B,C,D

E,K,L,A

C,A,M,N

D,I,N,G

So example words that can be made are: BEAD, CALM, CAN, DAMN, MAKE.

2) What's the run time for your algorithm? Does your algorithm scale for large sizes of the matrix? What optimizations can you make to improve the run time.

- 1of 1 vote
Given a non-directed, strongly connected graph where the node values are letters of the alphabet, write an algorithm that prints out all possible permutations of strings. What is this called?

For example:

V = A,B,C

Printout

ABC

ACB

BAC

BCA

CAB

CBA

BAC etc.

- 1of 1 vote
Given a sorted integer array, write a method that builds a balanced binary search tree. What is the runtime complexity?

Hint: Recursion.

Follow-up: Non-recursive solution

- 0of 0 votes
Given a list of tuples {x, y, x' } that describe histograms on the X/Y axis, such that X is the X coordinate, Y is the Y coordinate, and X' is the distance from X, write a function that draws the skyline of these tuples.

For example:

{3, 2, 4} , {4,5,3} will give the following points:

{3,0} - trivial

{3,2} - trivial

{4,5} -calculated

{7,0} -if list is done.

You cannot assume that the tuples are sorted. Provide runtime analysis.

- 0of 0 votes
Given a list of integers of size n, write a method to write all permutations the list; do this in O(1) space

Hint: No recursion.

- 1of 1 vote
Given a decimal number, write a function that returns its negabinary (i.e. negative 2-base) representation as a string.

`#!/usr/bin/env python3 assert solution(-15) == '110001' assert solution(2) == '110' assert solution(13) == '11101'`

- 0of 0 votes
I have an array with 60% sorted and 40% unsorted, which algorithm will give fastest accurate sorted output in C? And for Linked list which sorting algorithm suited?

- 0of 0 votes
How can I find factorial of positive integers using structures in C?

- 3of 3 votes
Assume there are 10000 stars in sky, how would you find which star is closest to the earth? in C

- 0of 0 votes
Create a program to compute nth Fibonacci number in O(1) space and faster than O(n) time.

(Target complexity is O(logn)).

- 0of 0 votes
i need to write code that union two nodes from graph G Vi ,Vj

then new node will generated Vm = ViUVj